3D grid or 3D point graph?

Hi! First of all, congratulations for the plugin, it is awesome!
My project is a turn based space strategy game, where spaceships can move using the three axis (x, y, z).
The map is almost empty, except for some planets and several enemy units. Which graph should I use for best results and easiest implementation? A modified grid graph, a point graph or even a navmesh graph?

Thanks in advance!

Hi

3D graphs unfortunately usually take up a huge amount of resources even for small maps since there are so many cells.
However if you want to go with this, the easiest way is to use a point graph and arrange a bunch of objects in a 3D grid. Also make sure that the maximum connection distance is just slightly larger than the distance between two objects in the grid.

You can also create a custom graph (see the documentation for a tutorial), but initially it will likely be a lot faster to start with a point graph.

Thank you very much Aron. I will follow your suggestion starting with a point graph, as it will be much faster and I still need to learn a lot about the framework.
Thanks a lot!

Sorry for necro post…
3D pathfinding is going to be critical to the game I’m making. I used your Pro pathfinding tool on an android game and was very impressed. The pathfinding was so efficient it was basically free.
I’ve implemented a super simple 3D pathfinder but performance is already an issue - n^3 branching factor is a bitch. I’d like to extend/add 3D pathfinding to your already amazing product.

Can you give me a few more pointers on where to start looking to implement this? I’ve written several A* algorithms over the years and am a professional programmer. I know this is going to be hard. I’d like to share the results with you once it’s done.

Hi

I’m glad it worked out nicely for you in your other game.
Ok, if you really want to do this, you will probably want to implement your own graph type (for best performance).
Take a look at http://arongranberg.com/astar/docs/writing-graph-generators.php
A point graph also works, but for larger graphs, the overhead of having a huge number of game objects will add up.

As well as the methods implemented in that tutorial, you will also want to override the GetNearest method (and possibly GetNearestForce) so that it does not have to search the whole graph for the closest node to the start and end points of a path.

You will want to use the heuristic optimization (assuming the graph is static): http://arongranberg.com/astar/docs/heuristic-opt.php
to bring down the number of nodes that the A* algorithm needs to visit to a minimum.

I hope this will help you get started.

And can you give link to example X-Y-Z PathAI.cs ?

1 Like