Dotsnav

DotsNav is a fully dynamic and robust planar navmesh Unity package, supporting agents of any size. DotsNav is built on DOTS and ECS, but can easily be used through monobehaviours. DotsNav is freely available on GitHub, as well a guide to getting started using monobehaviours or ECS. To see DotsNav in action check out the video or download the demo.

Dotsnav

DotsNav is a fully dynamic and robust planar navmesh Unity package, supporting agents of any size. DotsNav is built on DOTS and ECS, but can easily be used through monobehaviours. DotsNav is freely available on GitHub, as well a guide to getting started using monobehaviours or ECS. To see DotsNav in action check out the video or download the demo.

Advantages

Add and remove many obstacles each frame

Supports agents of any size

Use through ECS or gameobjects and monobehaviours

Insertion and removal operations guaranteed to succeed

Closed polygons guaranteed to remain closed

Navmesh size has no impact on performance

Fully Burst compatible

Parallel path finding

Triangulation exposed for additional algorithms

Ray and disc cast algorithms included

Advantages

Add and remove many obstacles each frame

Supports agents of any size

Use through ECS or gameobjects and monobehaviours

Insertion and removal operations guaranteed to succeed

Closed polygons guaranteed to remain closed

Navmesh size has no impact on performance

Fully Burst compatible

Parallel path finding

Triangulation exposed for additional algorithms

Ray and disc cast algorithms included

Technical information

DotsNav uses a Local Clearance Triangulation which reduces path finding using an arbitrary agent radius to a single floating point comparison per expanded edge. It uses a quadedge to represent the triangulation, and a bucketed quadtree for point location.

DotsNav’s insertion and removal algorithms are guaranteed to succeed and guarantee closed polygons remain closed, no matter how many intersecting obstacles are inserted or removed. In short, intersections use an existing point chosen to converge on the destination in the rare case no valid point can be created due to the density of the navmesh. When points chosen in this way are not connected directly, A* is used to determine which edges need to be constrained.

Due to the nature of the algorithms involved exact geometric predicates are required for a robust implementation. DotsNav relies on adaptive predicates, only when regular floating point calculations do not provide sufficient precision is the costly exact calculation performed. The predicates are available separately.

DotsNav provides locally optimal search. First, a channel of connected triangles with enough clearance is found using A*. The optimal path given this channel is then found using the funnel algorithm. While channels found are often optimal they are not guaranteed to be. An algorithm to find the optimal channel exists, but can easily take 100 times longer to execute and is not currently implemented. As there are valid use cases for globally optimal search, if only to benchmark cost functions, it is included on the roadmap.

Technical information

DotsNav uses a Local Clearance Triangulation which reduces path finding using an arbitrary agent radius to a single floating point comparison per expanded edge. It uses a quadedge to represent the triangulation, and a bucketed quadtree for point location.

DotsNav’s insertion and removal algorithms are guaranteed to succeed and guarantee closed polygons remain closed, no matter how many intersecting obstacles are inserted or removed. In short, intersections use an existing point chosen to converge on the destination in the rare case no valid point can be created due to the density of the navmesh. When points chosen in this way are not connected directly, A* is used to determine which edges need to be constrained.

Due to the nature of the algorithms involved exact geometric predicates are required for a robust implementation. DotsNav relies on adaptive predicates, only when regular floating point calculations do not provide sufficient precision is the costly exact calculation performed. The predicates are available separately.

DotsNav provides locally optimal search. First, a channel of connected triangles with enough clearance is found using A*. The optimal path given this channel is then found using the funnel algorithm. While channels found are often optimal they are not guaranteed to be. An algorithm to find the optimal channel exists, but can easily take 100 times longer to execute and is not currently implemented. As there are valid use cases for globally optimal search, if only to benchmark cost functions, it is included on the roadmap.