Unity Navigation & Pathfiding:
Unity’s navigation system provides agents the ability to intelligently move around the game world using navigation meshes. Dynamic obstacles can alter the navigation of agents at runtime, while off-mesh links can be used to implement custom behavior associated unique actions performed under specific criteria.
Creating a navigation mesh can happen prior to initialization or at runtime. The creation method can be customized through by attaching a NavMesh modifier component to objects. This modifier can alter how the object it is attached to will affect the NavMesh creation process. There are three area types available through the component which include “Walkable”, “Not Walkable” and “Jump” type. Selecting each of them modifies the properties associated with the generation of a navigation surface. Volume modifiers can also be used at runtime to alter the type of area of a navigation surface where their associated game objects are located based on their properties.
NavMesh Obstacle components can be attached to game objects and influence the pathfinding of agents at runtime in two ways. The first is by interfacing with the obstacle avoidance properties of their associated NavMesh Agent components and configuring them to steer away when in certain proximity of the obstacle. The second is by carving the generated layout of the navigation surface, dynamically updating the pathfinding of every active agent as the obstacle positions change.
The pathfinding algorithm works by adapting the A* search algorithm to traverse a graph of nodes that represent each polygon tile of the walkable areas of a navigation surface generated by the NavMesh system for the associated terrain. Unity is using reciprocal velocity obstacles (RVO) to predict and prevent collisions for the AI.
Performance & Challenges:
The performance factors are associated with the size and inner complexity of vertices that are used for the navigation surface generation process and the number of dynamic obstacles that are present and change the layout data at runtime. If a large surface is composed of many nodes the speed of traversing through the graph will increase by O(n), n being the number of nodes, the more movement that is detected by obstacles the higher the performance cost will be to compute local navigation at runtime and process the global pathfinding for the NavMesh surface by carving it for each available agent. Performance will also decrease with the number of active agents based on the complexity of their pathfinding. Carving the layout of a navigation surface at runtime is a very costly process and will incur heavy performance impacts if unaccounted for in large scenes with lots of complex geometry.
The AI in this type of system will struggle when navigation surfaces are being regenerated often at runtime and with changes to geometry which the agents cannot account for and compute their global pathfinding efficiently. The AI can face problems with local navigation when presented with multiple objects dynamically surrounding and obstructing any available path of the agent to its target. Other issues include overlapping positions of off-mesh links which prevent agents from accurately interacting with them at runtime. When multiple agents attempting to reach a target simultaneously with the same distance of travel required for each of them to reach it, they can get stuck walking towards each other when they get close enough to the target, unable to accurately reach it.
Credits:
- Featured Image: https://medium.com/@bryanmanuele/friday-fun-facts-002-dijkstra-path-finding-and-grid-tessellation-f52c75858da5
References:
- Unity NavMesh System: https://learn.unity.com/tutorial/unity-navmesh#5c7f8528edbc2a002053b498
- A* Search Algorithm: https://en.wikipedia.org/wiki/A*_search_algorithm
- Navigation Mesh: https://en.wikipedia.org/wiki/Navigation_mesh
- A* Pathfinding in Unity: https://blog.nobel-joergensen.com/2011/02/26/a-path-finding-algorithm-in-unity/
- Pathfinding: https://happycoding.io/tutorials/libgdx/pathfinding
- Unity Navigation: https://docs.unity3d.com/Manual/Navigation.html
- Navigation Basics: https://learn.unity.com/tutorial/navigation-basics#5c7f8528edbc2a002053b49a
Games and AI - Kristiyan Stoyanov 