Map Detangling

[TechSY730]

If you had been following my posts about the save game stuff, you may have notice I have figured out how planet placement and connectivity are stored. That is really all that is needed to make a map layout editor.

There is no way I am up to the task of writing a map editor, but I do want to raise an interesting question.

I know that in the general case, map detangling is an NP-hard problem. (Determining whether a map can be detangled, aka, its planar, thankfully is not NP-hard). However, is there a good algorithm (probabilistic, approximate, and/or randomized is fine) to make a map "less tangled"?

Also, is there a way to easily recognize special case maps? (Spokes, tree, snake, and a few other map types are not only guanteed to be planar, but also have properties that make detangling them trivial) In those cases, a specialized algorithm can be used to reflect their nice underlying structure.

[Hearteater]

I'd start here and here.  You might also consider determining if the map is a k-apex graph and if so, remove the apex nodes and detangle the remaining nodes and finally restore the apex nodes with minimal edge crossings to create the least tangled map.  You'll probably also want to identify sub-graphs and detangle them separately.  I'm afraid my graph theory is a little rusty so I can't give you the algorithms directly.

[x4000]

Interestingly, I wrote three different graph untangling algorithms in an attempt to render the AVWW maps in a different fashion.  Essentially to make the cross connections all show better, etc.  Several of those algorithms are darn easy to code, and while they are computationally intensive you're only talking a few seconds of time to detangle something like an AVWW map.

My favorite of the algorithms essentially simulates the nodes as being nodes, and the connections as being springs with the force on those springs being simulated.  After a number of iterations the nodes stop moving on their springs, and everything is at a good distance from everything else, and thus very much detangled.  Some of the things like that aren't perfect at untangling every last bit of the map, but it gets like 98% of it.

Here's the bad news: it also makes it MASSIVE.  In order for all the lines to be drawn in a way where there are very few overlaps, what you wind up with is something that has spread out to an immense degree.  In other words, for an AVWW map that normally took up maybe 1200x500 pixels with a thousand nodes (at the time), using these detangling algorithms led to something that took up closer to 10k pixels in both dimensions, with huge amounts of open space in the center except for the really long cross-connections across from one side to the other.  AI War has fewer nodes and lots more cross connections, so I don't know if that would be better or worse suited to this sort of thing.  But I highly doubt it would fit on one screen in most cases, even so.

[NickAragua]

Yeah, it might be NP hard, but since you're talking about 120 systems at most and the de-tangler only needs to run once per map, I don't think it matters. Hearteater's got the basics of it right.

You could always go with the ol' dartboard method (bounded by heuristics of course).

[Ranakastrasz]

@x4000

Cant you just scale them down? Or would it squish certain parts of them so much that it would be impossible to decern one star from anouther?

[x4000]

@x4000

Cant you just scale them down? Or would it squish certain parts of them so much that it would be impossible to decern one star from anouther?

Scale their positions down?  Or the actual elements themselves?  The elements in question are already as small as they can be while still being visually understandable.  If you're referring to scaling the positions so that stuff isn't so far apart, then what you wind up doing is re-tangling the de-tangled nodes: the reason that they are so far apart is that that's the only way that they don't wind up overlapping each others' lines in unclear ways.  Look at a large database diagram to see what I mean: http://thedailywtf.com/Articles/Enterprise-Dependency-Big-Ball-of-Yarn.aspx

Obviously not all are like that, but on a smaller scale that's what winds up happening when there are lots of arbitrary cross-connections between nodes.  As in AI War maps, or the side-links in the AVWW buildings of yore.

[Ranakastrasz]

Ah, I see. I meant the positions, but if you have significant distance differences between nodes, then yea, scaling wont really help.