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**.

**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**.

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

**∴ **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 **∴**

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.

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.