SVO Navigation in UE4

[anonymous_user_4f973aae]

Hello,

For a game I am developing I was looking into 3D Navigation for pawns. After some research I decided to try it by myself - in theory it does not look too difficult to have a basic version. My game will not have very complex navigation requirements, the environment is basically rather large voxels, and the navigation area is not really big.

Originally I thought using the data structure from UE4 to build the navigation mesh. Anyhow, after working with it for a couple of days now I am actually wondering if this is the best approach.

Basically what I am trying to achieve is an SVO with some simple greedy A* algorithm. With I have no a couple of problems:

1. How to identify leaf nodes with an TOctree2
Based on documentation and looking at engine code, it does not look like the expose a way to find leaf nodes easily. You can iterate through nodes with a predicate (problem is a leaf is not a node I think) or you can iterate through elements (a leaf node would not have elements since it is representing empty space)
I am pretty sure there is maybe a way but I havent found it yet. If anybody has an idea would be nice.

2. Neighbors finding (obviously important for A)*
SVO contains neighbor connectivity information and not only parent-child information. Not sure if this is easily done in TOctree2

Basiclly I am starting to think instead of going with UE’s TOctree2, it is more feasible to work on an own SVO implementation. Similar to this project for example:

And yes I could just use this one or any other implementation. Figuring out how to do it is the main fun part for me, this why I try not to use any plugins. Yes, I am re-inventing the wheel but I enjoy it.

Anybody has some experience on that? Is this possible with Octree2 or do you need an own SVO for that?

Best

[anonymous_user_4f973aae]

Also found this one:

3D Navigation Plugin

Another plugin! After watching Daniel Brewer’s GDC talk on SVO navigation, I thought I’d give it a go…so what we have here is basically a straight UnrealEngine implementation of what is described in this talk : https://www.gdcvault.com/play/102201…esh-Navigating Code is here ( Contributions are extremely welcome and will be credited) : Demo : [UESVON - Sparse Voxel Octree Navigation for UnrealEngine] Documentation: [Capture.PNG.jpg] [Capture1.jpg]

It looks everyone trying to do something similar is going with their own SVO type.

[anonymous_user_4f973aae]

For the ones interested - I ended up to do kind of a combination. I use Octree to generate the tree with blocking elements. Then I traverse through the tree to identify places were no nodes exists. The unique static traits of an octree makes that rather easy. Then I store these identified empty spaces in a new data structure which also contains its neighbor relations. Suprisingly runs quite performant - I guess for my use-case this is good enough.