I’m just starting out with this great project and I’m looking to apply this to my 3D space title. I’m familiar with A* and have implemented my own versions in 2D games. In this title, while most of space is ‘empty’, there will still be lots of ‘terrain’ to navigate around (systems, nebulas, etc.). I’d like to hear some thoughts from others experienced with this project on how best to approach ‘graphing’ such a large 3D environment.
Working with 3D space (something like a 3D cell-grid) is not especially hard. But it is veeery memory intensive. I have done it once before, the maximum resolution I could reasonably get was 707070, which is roughly equivalent, in memory to a 580580 normal grid graph.
If you ramp it up to something like 150150150 you get the equivalent of a 18401840 grid graph, and that would probably use something on the order of 300-400 mb of memory without special casing for optimizations.
The only practical way is to build some kind of point graph, which would work like normal point graphs.
In theory, the best way would be a 3D navmesh graph, something consisting of tetrahedrons. But I haven’t really seen anyone do that in practice, and I am not even sure how to generate it in the first place.
I agree the point graph seems like the most straight forward approach to this kind of environment. However, I’d also like to explore the notion of a ‘3D cell-grid’. As your grid graph is 2D, I assume you are talking about your Layered Gridgraph? Can you expand a bit on how you would structure a ‘3D cell-grid’?