hi devs,
I’m trying to recreate the unreal engine navigation system in order to understand it and adapt it to my needs.
can you help me understand how the recast navigation system works?
and which pathfinding algorithm UE is using?
thank y’all in advance <3
There is multiple aspects of how it works in deeper level. However in simple terms
- Navmesh bounds volume, voxelize, grid divide surfaces according to its settings in project, finds walkable, traversable surfaces according to settings.
- Triangulate and organise/optimise navmesh, triangulate, sometimes divide if its open world navmesh into loadable objects.
- When it is used depending on the node provided generally simply runs A* finds points, calculates path towards objects and controller can follow path move.
- There are other aspects of how and what controller is used and how it behaves. Such as detour, avoidance. They have their own aspects you can find it over here
- Pathfinding is always 2d along X and Y, there is no built in 3D grid pathfinding in engine
- Pathfinding can have some contexts like avoiding costly paths etc. Areas can be marked with data like, mud etc. so slow fast paths in some terms can be calculated.
- You can find code blocks here and some other places ofc DetourNavMeshQuery.cpp / dtNavMeshQuery::findPath -
findStraightPath
All the engineering at its core still find traversable path from A to B with A*. Think there is other alghorithms also like Djikstra and BFS available in engine somewhere however not sure they are used for pathfinding maybe on top calculations for avoidance and so on used.
If you are extending searching think DetourNavMeshQuery.cpp would be a good starting point for changes.
1 Like