1
\$\begingroup\$

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).

OctreeExample

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.

\$\endgroup\$
2
  • \$\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\$ Commented Oct 25, 2016 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\$ Commented Oct 25, 2016 at 22:59

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.