I have an octree that I'm planning to use for 3D pathfinding. My plan was to break down the world such that all the leaf nodes of the tree would be of equal dimensions that would create a nice grid and then adapt A* by adding an extra dimension and just run searches on the grid. The image below shows a sample of my leaf nodes to demonstrate what I'm talking about (ignore the spheres, they are for something else).


What I'm not sure about is how do I perform A* on a tree structure. My thought was to convert the tree structure to a 3D array, which would make it really easy to perform A* on, but I'm not sure how I would go about this. I can recursively work my way down the tree and tell which nodes are the leaf nodes, but I don't know how I could necessarily work my way down in an ordered fashion such that I could index nodes into an array properly. How would I go about this? Is it even the right approach; or it there a better approach to performing A* on the tree?

Note: I am aware the space might not actually be open enough to justify full 3D pathfinding, but this is intended to be a demonstration/test of the concept, so I wanted to keep things relatively simple.

  • \$\begingroup\$ 1. If all your leaf nodes are the same size, why use an Octree at all? One of the main advantages of an Octree is you can stop subdividing a node at some threshold, focusing the structure's subdivisions in high-detail areas, while sparser areas take up less data and fewer iterations to process. 2. Morton order converts between 3D coordinates and octreee traversal order readily. \$\endgroup\$ – DMGregory Oct 25 '16 at 22:02
  • \$\begingroup\$ Well subdivision this fine only happens in areas where enemies will actually spawn (i.e. where the enemy would actually need navigation). The octree subdivides as little as possible on any of the space outside these areas. I initially had it subdivide on level geometry only, but it didn't seem like I got enough granularity for navigation in tighter areas (like under the bridge). But you're right, I should probably use the structure more efficiently. \$\endgroup\$ – user1265215 Oct 25 '16 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.