Efficient datastructure to store a galaxy map

Question

I'm working on a project for an intro level Ai class, and the project I've closen is to create a simulated universe in which Ai actors play against each other economically and militarily. I have the actual Ai fundamentals planned out, but I've hit a bit of a snag in trying to properly store the randomly generated game world.

The solar system objects are generated and populated randomly and the aim I'm going for is to place them in a 3d world, with x,y,z positions relative to a galactic center.

Each system should be reachable from any other system, limited only by the jump range of a given ship. Which I assume would mean that id need a 3d bounding algorithm to determine what other systems are in range.

For storing them, would a weighted edge graph be best, although the number of edges would be huge as in theory each system is reachable from any other. Or would an octree be better. And if so how would I calculate a list of reachable systems from the current system with an octree.

Answer 1

This is naturally modelled as a graph structure, as you knew when you posed the question. So let's look at how we can take a graph and make it more efficient.

Let's look at topological methods. Making N^2 checks at runtime is ridiculous as you suggest, so we rule that out. Now there are two ways we can proceed - order nodes in such a way that we are likely to find locals quickly (e.g. hilbert curves which still aren't going to be effective), or pre-cache everything as the complete graph in N nodes; if N^2 is large, memory use may be prohibitive. So we may as well forego topological / classic graph style storage altogether.

Okay, so let's look at geometric methods. This is where I can see why wondra suggested octrees, however I don't think it is necessary to go that far. All you need is a single-level/depth 3D grid with reasonably cell granularity. Pre-process: If there's at least one star system anywhere in a cell, mark it occupied... assume e.g. that cells are 1 AU wide/deep/high. Now snap a sphere of the appropriate radius to this grid, roughly centring around player's position, and iterate cells within that [xyz] cubic range (that neatly surrounds your sphere) to see where you have candidates for travel.

This works well because in reality, physics tend to cause systems to cluster, so you often have systems grouped within the same cell/bucket so that you could rapidly run through only what is local. Again to return to the octree suggestion, I would only suggest implementing this if you really have a very matter-heavy galaxy. Octrees / quadtrees introduce cost due to multi-level traversal that can easily make them slower than "flat" approaches, though that is always mitigated as size grows geometrically. If you like octrees? Then by all means.

Conceptually I'd say this is simplest though and allows you to get on with other things. I guess the granularity of the grid is something you're going to have to play with - depends on your dispersion.

EDIT k-means clustering is one way you could classify various star-clusters from your starting collection of star systems; you could then create routes between them - this would allow a more traditional graph structure but with the "buckets" necessary to do fast local searches.