Please don’t misunderstand my question: Obviously there are tons of good pathfinding solutions which can cope with a three-dimensional world(The most popular probably being Aron Granberg’s A* implementation).
However, I am looking for a solution which is able to path-finding in a full three dimensional space, like for example space itself(and able to e.g. avoid asteroids in its path).
Is there any asset available that provides such features out-of-the-box, or would I have to implement this myself? If the latter, how should I go about it? Grids aren’t really an option since they would blow up memory, and I haven’t implemented any non-grid based path-finding algorithms myself so far.
Thank you for your time.
I’m not aware of any pre-made assets that do exactly what you want, but you could at least avoid writing your own pathfinding algorithm by using PointGraph in Aron Granberg’s A* implementation.
You provide a list of node positions and the algorithm automatically creates edges between nodes that are close together. It allows nodes to be at any position rather than bound to the ground as long all axes of the “limits” parameter are set to 0 (infinity).
Granted, I’ve only played with that library’s navmesh and grid based approaches myself so there could be a catch.
You’re still stuck with having to generate the points yourself, but you could get a very simple first pass at that quickly. Generate a bunch of nodes in 3D space at some standard distance from each other. Exclude points that are overlapping with obstacles.
This is like a 3D grid, which as you said it might have memory issues. You could try using a k-d tree or Octree to prune out points in open spaces while keeping a larger density of points in more intricate areas with obstacles.
Would love to hear how other space themed games do this, but that’s where I would start.
Have you found the solution?