How does one make a Escape Velocity type linked node map?

April 10, 2013 1:42 PM

So there was an old Mac space trading game named Escape Velocity. On its map, each star system was connected to 1 to 8 other star systems. Each of those systems could be connected to another 1 to 8 star systems, on and on to the edge of the map. What is that type of thing generically called (node map, node web, I'm just guessing)? More inside.

I want to generate those types of maps randomly in a game I'm writing. It's easy to make a (X by Y) matrix of X number of systems with 1 to Y connections from system Z to systems Z1, Z2, Z3...ZY. But when you draw it visually, I don't know how you make it so connected systems are close to each other on the map. Each system should be as close as possible to the systems it is connected to. If you just start drawing links, you end up with a tangled mess of lines after the first few link levels (if that's the correct term).

My solution, which I think is kind of funny, was to model them as spheres in the Unity physics engine, and have them attract the spheres they are linked to while repulsing spheres they are not linked to, all locked into a single plane to keep the map flat. Sometime I set up an "explosion" in the middle to get them moving around faster. This sort of works, but is there a "mathier" way to make these maps?

I'm asking this here instead of the Unity forums because it isn't a Unity specific question, and this place has a lot of math folks. I can follow you as far as DiffEq, but if you start talking tensor fields and such I'll need a translation.

Thanks!

posted by BeeDo to Computers & Internet (8 answers total)

Best answer: The data structure of these sorts of maps is an "undirected graph". Mathematica has a page documenting how to use its own graph-plotting tools and algorithms, which might be a good place to start.
posted by tylerkaraszewski at 1:51 PM on April 10, 2013

Probably the first thing you want to read about is Graph Theory. This is the study of linked structures like you describe.

I am willing to bet that whatever you're coding in has libraries for doing graph work. As a bonus, said libraries should also help you with pathfinding.
posted by Just this guy, y'know at 1:51 PM on April 10, 2013

A graph. They're composed to edges (the connections) and vertices (a node, if you will). If edges are one-way, then it's a directed graph.
posted by k5.user at 1:52 PM on April 10, 2013

Best answer: Your Unity-based solution is a force-directed graph layout algorithm. As Just this guy said, there are plenty of libraries out there that will help you generate and plot graphs.
posted by qxntpqbbbqxl at 1:59 PM on April 10, 2013

Response by poster: Awesome. Thanks!
posted by BeeDo at 2:04 PM on April 10, 2013

On further thought, another way to do this would be to generate random coordinates for nodes, and use a Delaunay triangulation to decide the edges. This has the advantage of giving you a planar graph (can be drawn in 2D without overlapping edges).
posted by qxntpqbbbqxl at 2:16 PM on April 10, 2013 [2 favorites]

The next step is to assign a cost to each link.
posted by Bruce H. at 5:58 PM on April 10, 2013

This is totally not answering the question, and the mods may smite me, but if you're designing a game anywhere remotely similar to EV, for the love of god memail me and I will buy it with real money.

Also, I once had extensive correspondence with one of the EV developers and can try and coax his email out of the (internet) paleolithic if you need.
posted by digitalprimate at 10:17 AM on April 11, 2013