Pathfinding with A* and octree

Development Programming & Scripting C++
1

Hello,
I am currently working on implementing a simple pathfinding algorithm for my 3D Space game. My thoughts were on using an octree representation and than use something like a* or lazy theta.

I have implemented the TOctree2 - which was already a struggle because the lack of examples and documentation. For A* I would need to identify neighboors and calculate gCost/hCost for the different nodes in Octree.

My question is anybody knows some good examples or good papers for that to dig into?

Best

2

Maybe let me specify the problem a little bit.

In it is easy to find elements. I am not interested defacto in the elements in the tree but the nodes and leafs of the octree.

And in addition, I am only interested to only see nodes which are empty because they are representing empty space for the space?

Is that somehow possible or do I have to go the other way around and create an Octree with “empty-elements” and whenever something is getting placed in the bounds of the octree remove the empty-element? I guess that would work but does not sound very optimized

3

If there’s no element, a cell should have no bounds.
I would check bounds to initialize the cost of each cell.

Maybe you want to take a look at talks from Havok over at GDC Vault to collect ideas.

4

thanks for the hint with Havok - will take a look!

If there’s no element, a cell should have no bounds.

One question for clarification, what is cell exactly in this context? Nodes in the octree obviously needs bounds even if they do not have an element. Sorry I am quite new to Octrees.

5

And doing some more research - I guess the important part is to identify not the nodes but leaves. As far as I understood in terms of Octrees, a leaf always represents an empty space.

By any chance does somebody knows how to get the leaves from TOctree2? It has to exists, because if you execute DumpStats() it will tell you how many leaves it has they just not expose it.

6

I would probably make my own type instead:

Octrees in Unreal Engine 4

7

I was actually following this one while creating it. He uses also TOctree (DEPRECATED) but it works similar to TOctree2.
In this example there is still the same problem.

I guess maybe implementing a very, simple Octree by myself is maybe faster than researching how this UE works :smiley: