Request: Pathfinding 3D

[ViniciusFXavier]

Possibility of creating a 3D Pathfinding, the idea is to be able to create agents(NPC) with the ability to move in 3D space. For example a bird/helicopters flying between buildings, spacecraft between asteroids.

2D pathfinding is usually done using a navigation mesh or even a 2D grid map.

So far I've seen many examples of Pathfinding 3D using a 3D grid strategy.

Presentation: Pathfinding in 3D Space - CHIA-MAN HUNG & RUOQI HE https://ascane.github.io/assets/portfolio/pathfinding3d-slides-en.pdf

Sample images from internet:

[ViniciusFXavier]

Studying a little more I ended up finding this video from GDC that talks about Getting off the NavMesh: Navigating in Fully 3D Environments: URL: https://www.gdcvault.com/play/1022016/Getting-off-the-NavMesh-Navigating

[Mugen87]

I find it strange that the video talks about spares voxel octrees. SVO is a rendering technique and always includes some sort of raycasting or tracing. Pathfinding in 3D is totally unrelated to rendering.

The first presentation outlines the steps for an algorithm:

• Generate an Octree from the environment. The Octree might become sparse since depending on the scenario most parts of the data space will be empty and thus not subdivided.
• Generate a graph by processing the corner points/edges of certain cells of the Octree.
• Query the graph with (lazy) Theta*.

Yuka already provides a graph class but no Octree and Theta* implementation. Since Theta* is just an enhancement of A* (which is implemented by the engine), the real challenge is the development of an Octree class and the logic that brings all components together in order to implement the above algorithm.

[Mugen87]

It's not yet clear to me how to handle game entities with different size.

The above algorithm basically only works when the game entity is a point and thus infinitely small. However, game entities usually have a spatial extension.

In context of navigation meshes, the maximum bounding radius of a game entity is honored when the nav mesh is generated by a tool. A similar approach needs to be used for 3D pathfinding when computing the Octree. Otherwise a too big game entity will intersect obstacles. Consider this image from the first post:

If the agent is bigger, it can't use the blue path through the cube, sphere and cone. It probably has to go outside.

[ViniciusFXavier]

@Mugen87 First thank you very much for responding.

This unreal engine plugin is one of the most used because it is very complete and free. https://github.com/VSZue/DonAINavigation About the size of object starts on 23:00

This image is from this repo for unreal engine plugin -> https://github.com/darbycostello/Nav3D

---

I was trying to take a look and even testing these plugins in the unreal engine and they work very well.

In the first case it is the best of all because it works even in the form of infinite worlds, it uses the same octree for all entities so it can avoid collisions between them, it regenerates the octree in a time that is controllable and can be in all frames or at longer intervals, thus being able to map objects that move and re-calculate paths.