RFC: map optimization

[jonseq]

I converted some LoY maps (see http://seq.sourceforge.net/forums/showthread.php?s=&threadid=3126) and noticed that performance is very bad for those zones, except when I turn map lines off. This is with a windows X server on a slow laptop, but still ... (I already turned off ssh X forwarding and instead directly set DISPLAY, which helps a little)

It looks like the converted map files (generated using the in-game cartography tool, no doubt) contain an excessive number of line segments - in fact, displaying some of them, with labels, in-game, depletes EQ's internal UI resources when zoomed out all the way. Specifically, my torgiran and gunthak maps are half a meg each, and seem to consist entirely of 2-point line segments (as opposed to probably more efficient polylines)

I'm sure I could come up with an algorithm to minimize the map by joining line segments (or find one on citeseer). This is probably something that should be done offline outside of SEQ.

Would there be any speedup from merging adjacent line segments into polylines?

Are there any in-game modifications that could speed map drawing? I don't know much about X, but could you do something to save the map into a display list and animate spawns without having to resend the entire map frame? Player movement could use a larger display list with a X-server-side scaling and clipping - but is such a capability available?

It also might be nice to add a "layers" tag/filter since height based filtering is hackish and doesn't work well for many maps. The three layers allowed by the in-game tool seem sufficient and it would be nice to not lose information translating between the in-game and seq map formats.

[Ratt]

Yes, you would see a great speed up. The map drawing functions could use a lot of optimizing, but I don't see that happening in the near future, unless someone gets a wild hair up their butt.

If you joined all the mini-lines into one big line, it would speed up your redraws dramatically.

All the maps could probably use a bit of optimization in that aspect.

[Fatal]

I already have the software that does this for the in game maps. Im sure it wouldnt be difficult to change it to the seq format.

Let me move the program to my server and I'll have it available for download in the mornin.


It does exactly what ratt said, it optimizes the mini lines into a single line where possible. It works in batch mode so you can do all your maps at once, etc.

[Fatal]

Posted the file. get it at http://maps.eq-toolbox.com/MappieSetup.exe .

[jonseq]

Fatal - any chance you could make the source available? It would be nice to add both load/save as eq/seq format.

By 'merging line segments' I didn't mean just connecting polylines (although that's the obvious first step), but rather repeatedly combining two adjacent nearly colinear line segments into a single line segment (which point can be removed with the minimum error?).

Polylines is the obvious first step and might be enough, of course.

[Fatal]

Sure will. let me get it from the author.

Alos, this does what you want. IF you run optimize repeatedly on the same map, eventually, it will straighten out curves.

Anyway, let me get the source and you can take a look at it and maybe you have a better method :)

[jonseq]

cool - I was going to comment that it doesn't properly read the whole
http://maps.eq-toolbox.com/files/Nadox_1.txt
(which is the largest file there)
but I see you're not the author =)

[Fatal]

The nadox map is full of errors.
When i run it through the optimizer it strips it clean. So that one is um.. un optimized until i can track down whats bad in it.

The basic formula for the optimization is:
Distance Difference = Distance secant - distance 1 - distance 2. If Distance difference is less then .0002, join line

[ksmith]

I'm currently working on a program to optimize the maps converted from the in-game cartography to showeq that combines multiple M-lines that share a common point.

Here's some file sizes:


-rw-r--r-- 1 ksmith ksmith 166310 Apr 21 16:36 Gunthak.map
-rw-r--r-- 1 ksmith ksmith 424313 Apr 21 10:15 gunthak_2.txt

Gunthak.map is the result of gunthak_2.txt after being optimized first by Mappie, then converted to showeq format and having the M-lines combined.

Edit: spelling

[jonseq]

Did some poking around and finally settled on 'polyline simplification' as a google search term and got this explanation/code for the Douglas-Peucker algorithm (which uses the criteria I was thinking of but proceeds in the reverse direction, starting with 1 edge and restoring points, rather than searching for points to remove):

http://geometryalgorithms.com/Archive/algorithm_0205/algorithm_0205.htm

It looks like the primary application of these algorithms is in simplifying coastline polylines.

I don't care so much about the detail at the edge of a map (look at PoDisease for instance) as preserving the topological features (like a narrow tunnel between two huge areas).

I'm not sure what 'distance secant' means (I assume you're referring to the trig function sec, not the geometrical secant as a line intersecting a circle at 2 points?

[jonseq]

It seems that the polyline rep alone saves a lot of space, and probably time, so except for idiot mappers who keep adding vertices every 2 feet, I'm not going to worry too much about this for now =)

[ahminus]

"I'm sure I could come up with an algorithm to minimize the map by joining line segments (or find one on citeseer). This is probably something that should be done offline outside of SEQ. "

SINS did this.

I had thought that made it back into SEQ.

If not, someone can suck it in.

It was fairly trivial code.

But, the other solution of fixing up the maps themselves is probably better.