# Efficient datastructure to store a galaxy map

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.

• Why would you store graph if it is 1.) complete graph with 2.) well-known edge weight(and easily computable!)? All the information is implicit given by already existing attribute(position). – wondra Oct 30 '15 at 19:43
• So what are you suggesting, that every time I check all available jump targets in range I iterate through the entire collection of all systems to determine what's in range? – Systemsfailed Oct 30 '15 at 19:50
• An octree is overkill for this, IMO. – Engineer Oct 30 '15 at 19:56
• It is only fairly quick O(N) test (two multiplications, one addition) or just one condition if you precomputed it in 2D array... see the Arcane Engineers answer - the talk about this started there. Problem with 2D array might be the memory 4*N bytes. – wondra Oct 30 '15 at 19:56
• See edit, my original answer was far from complete. – Engineer Oct 30 '15 at 20:10

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.

• Why would you store complete grahp? It is an array of objects - nothing more. What is the point of storing accessibility if it is always true and alway sgiven by (pos2-pos1).Length ? And pre-caching is nothing more than 2d array of distances(adjacency matrix). – wondra Oct 30 '15 at 19:46
• I think OP was questioning the cost of the N^2 complete table of neighbor hop distances. If neighborhood can be efficiently discovered on-demand for a given jump range, some searchable spatial structure (like an octree?) could trade time for space here... – david van brink Oct 30 '15 at 19:48
• @wondra Why not keep it conceptually simple for the OP? – Engineer Oct 30 '15 at 19:50
• @davidvanbrink Fair enough, I probably didn't read the question too well. – Engineer Oct 30 '15 at 19:50
• If the O(N) test for regions in range was the problem, than any spatial partitioning is the correct answer. Probably the suggested octree is the best because it is one of the simplest. – wondra Oct 30 '15 at 19:54