graph optimization

Is there a well-known method to simplify a nav graph? From what I've seen most people have a nav mesh (made of triangles), not a graph (made of edges). But assume you have a graph - is there a well-known method to remove the edges that wouldn't significantly shorten the paths found on the graph? I wonder if this is a well-known problem (I don't know what to search for on google - "graph simplification" turns up a bunch of weird topology papers).

I wrote up a little solution for it that I think works pretty well. Here's my sweet-ass visualization: http://i.imgur.com/XMOaM.png
It's a graph made of random edges in 3d. Black lines were rejected from the original graph, white lines were kept in the simplified graph.

The method is to keep candidate edges from the original graph only when they're shorter than some fraction of the shortest existing path between those vertices. Like building a minimum spanning tree, visit the candidates in length order.

The tricky part is you need to know those shortest path lengths (for all pairs of verts in the graph as they're added). To do that, you can propagate shortest-path updates each time you add an edge (a newly shortened path AB adds new potential shortened paths from A to each of B's neighbors and from B to each of A's neighbors too).

All paths in the shrunk graph are guaranteed to be within an arbitrary threshold of optimal. (if the threshold is small, you get a minimum spanning tree, which is neat!). In the picture, it's a <2x optimal path length guarantee.

Performance is weird, something like O(#verts * #edges)? The shortest-path-update ordering (stack vs. queue for the to-visit list) has a huge impact on performance and I'm not really sure why :o It handles graphs up to about 500-1000 edges instantly, but barfs on bigger inputs. The aspect that could be improved is the shortest path propogation - depending on the edge add order, a lot of the path shrinking is wasted effort.

I think a further improvement would be start with the minimum spanning tree (which is decently fast), compute the all-pairs shortest paths, then start adding the remaining candidate edges. This skips the majority of the shortest-path updating, since the graph is mostly connected.

Let me know if you want me to post the code somewhere, it's pretty simple.

spacechem!

Spacechem is my game of the year so far (either that or terraria!): Introductory video.

It’s in the weird little genre of engineering games, where you design a machine that performs some task, like “fantastic contraption”, “the incredible machine”, or “armadillo run”. They’re never really that popular, but they’re like catnip to me - puzzle games where you invent a solution instead of discovering it.

Here's an interview with the developer that I really liked.

Although it’s called spacechem, it’s only fictionally about chemistry (you’re physically manipulating atoms to perform chemical reactions... in space!). It’s really a programming game – you design a machine on a 2D grid of component machine parts, and the parts have different interaction rules. It’s kind of like visual scripting, kind of like designing a circuit. You watch the machine run, then tweak your design until your machine can perform some task.

The game does a great job of building up complexity gradually – at the beginning of the game you’re given simple components and tasks, and by the end of the game you’re doing things that would have been completely impossible for you in the beginning. It’s the good kind of mind-bending – you feel yourself getting better at the game, and you see your designs getting more efficient and elegant.

The game has a demo if it seems like your kind of thing!