I’m having some difficulty coming up with the appropriate data structure to use for a game.
I’m aiming for a galaxy view with tens of thousands of visitable star systems.
Hierarchically, each star system can contain one or more of the following:
- Planets (and their moons)
- Asteroid Belts
- Megastructures (and their moons/sub-structures)
All of the above can have “points of interest” (POI) eg a station in low orbit, a surface resource node, a docking bay.
I don’t particularly care about physical location within a system beyond knowing its order in the hierarchy (I’ll be showing a list of locations, rather than trying to render them in 3D space). So I can treat all objects within a system as located at the star for the pursposes of calculation.
I do, however, need a way to specify routes from any Planet/AsteroidBelt/Moon/Megastructure/POI to any other. I also need to be able to search for other locations meeting certain criteria (both to offer as destinations in the UI and to handle rendering).
Each type of location will have some unique properties (Asteroid belts have resource distributions, for example whereas planets ave atmospheres) but they also have lots of common properties (inventory, owner, comms network node id, etc).
Obviously, with the numbers I’m considering I need to take a sparse/lazy generated approach. Currently the galaxy is built entirely in the GPU and stars are only presented to the CPU when the user first clicks on them.
That lends itself nicely to a hierarchical data structure with a load-on-first-access approach. Click on a star and it’s added to the list, so the name is saved. Scan/visit it and I’ll generate the system contents.
Unfortunately, I also need to be able to search across all generated locations efficiently (given an ID, find the star system coordinates, find planets with an atmosphere like X, find any location with X in its inventory) in a potentially huge search space.
That doesn’t align with recursively walking up/down trees.
I considered using a heirarchy and manually maintaining a number of separate indices to speed up searching. It’s doable but a pain and error-prone. It also feels like one of those solutions where I’m going to keep finding one more type of query I need to support and before long I’m trying to implement a minimal database.
Speaking of which I also need to persist this data at some point. Currently I’m serializing to a densely packed binary blob.
So… I took a step back and wondered whether I should actually use a database. I can see the benefits of using something like SQLite which I could bundle with the game and would handle persistence, indices, and the rest.
After spending a couple of days implementing the basics, I can see this is going to be quite a long and involved process.
None of the friendly tooling works well in Unity, so I can’t take advantage of entity framework w/ code first, nor nice Linq-To-Sqlite predicate handling. Even worse, most of the libraries to work with EF are tightly coupled to windows. EF Core seems like an option but I haven’t been able to get it working in Unity (I need to do some assembly version mapping but as Unity overwrites the project file regularly and doesn’t seem to support this itself, I think it’s a losing battle).
So I’ve headed down the route of implementing a data layer that generates SQL as needed.
I can do that, but it opens up a huge can of worms in terms of manually maintaining the DB schema. I’m going to have to start tracking a DB version and bundling migration scripts with any update/patch. It’s a whole new maintenance burden.
So… What am I missing? What’s the elegant way to store a sparse hierarchy of data whilst still supporting flexible search across disparate object types that just happen to have a lot of common properties?