Dotsnav

Short text Short text Short text Short text Short text Short text Short text Short text Short text Short text Short text Short text Short text Short text Short text Short text Short text Short text Short text Short text

Advantages

Fully Burst compatible, runs entirely on background threads and fully utilizes Unity’s memory leak detection and thread safety systems. Includes ray and disc cast algorithms.

Resources spent on pending requests can be regulated deterministically.

Fully exposes the underlying triangulation, all included algorithms use public APIs only.

Built to be modified at runtime, fast enough to add and remove many obstacles each frame.

Built to be used with DOTS and ECS, but can be used in a GameObject context without prior knowledge.

Easy to use. Insert obstacles by supplying a list of vertices. Remove obstacles by supply corresponding ids. Invalidated paths are tracked or recalculated automatically.

Supports paths of any width, simply supply the agent radius when creating a path query.

Operations are local, they take the same amount of time no matter the size of the navmesh.

Highly robust by relying on exact geometric primitives, and insertion and removal operations guaranteed to succeed.

Closed polygons are guaranteed to remain closed, no matter how many intersecting obstacles are inserted or removed.

Technical information

DotsNav uses a Local Clearance Triangulation, a triangulation embedding local clearance information, reducing path searches with arbitrary width to a single floating point comparison per traversed edge. The Local Clearance Triangulation is an extension of a fully dynamic Constrained Delaunay Triangulation using a quadedge as datastructure and a bucketed quadtree for point location.

Due to the nature of the algorithms involved exact geometric predicates are required for a robust implementation. DotsNav relies on adaptive predicates described by Jonathan Shewchuk and ported to C# by Govert van Drimmelen. Only when regular floating point calculations do not provide sufficient precision is the costly exact calculation performed.

Insertion and removal algorithms are guaranteed to succeed. The ideas underlying these algorithms are described in detail by Marcello Kallmann. In short however intersections can be guaranteed to succeed by using an existing point when no valid point can be created due to the density of the navmesh. 

As points chosen in this way are not guaranteed to be connected A* is used to ensure this. DotsNav provides locally optimal search. When searching for a path, first a channel of connected triangles with enough clearance is found. The optimal path given this channel is then found using the funnel algorithm. While channels found are usually optimal they are not guaranteed to be. An algorithm to find the optimal channel exists, but can easily take up to 100 times longer and is not currently implemented. As there are valid use cases for globally optimal search, despite it’s costliness, it is included on the roadmap.

DotsNav is currently in beta. It passes very stringent stress tests, examples can be seen in the demo and in video on this page. DotsNav has not yet been used outside of developing the examples in the demo. Initial tests on Android have indicated no issues, but DotsNav has yet to be tested on consoles or Apple products. Please report any issue you may encounter.

Technical information

DotsNav uses a Local Clearance Triangulation, a triangulation embedding local clearance information, reducing path searches with arbitrary width to a single floating point comparison per traversed edge. The Local Clearance Triangulation is an extension of a fully dynamic Constrained Delaunay Triangulation using a quadedge as datastructure and a bucketed quadtree for point location.

Due to the nature of the algorithms involved exact geometric predicates are required for a robust implementation. DotsNav relies on adaptive predicates described by Jonathan Shewchuk and ported to C# by Govert van Drimmelen. Only when regular floating point calculations do not provide sufficient precision is the costly exact calculation performed.

Insertion and removal algorithms are guaranteed to succeed. The ideas underlying these algorithms are described in detail by Marcello Kallmann. In short however intersections can be guaranteed to succeed by using an existing point when no valid point can be created due to the density of the navmesh. As points chosen in this way are not guaranteed to be connected A* is used to ensure this.

DotsNav provides locally optimal search. When searching for a path, first a channel of connected triangles with enough clearance is found. The optimal path given this channel is then found using the funnel algorithm. While channels found are usually optimal they are not guaranteed to be. An algorithm to find the optimal channel exists, but can easily take up to 100 times longer and is not currently implemented. As there are valid use cases for globally optimal search, despite it’s costliness, it is included on the roadmap.

DotsNav is currently in beta. It passes very stringent stress tests, examples can be seen in the demo and in video on this page. DotsNav has not yet been used outside of developing the examples in the demo. Initial tests on Android have indicated no issues, but DotsNav has yet to be tested on consoles or Apple products. Please report any issue you may encounter.

Bibliography

Dynamic and Robust Local Clearance Triangulations: Kallmann 2014

Shortest Paths with Arbitrary Clearance fromNavigation Meshes: Kallmann 2010

Fully Dynamic Constrained Delaunay Triangulations: Kallmann et al. 2003  

Adaptive Precision Floating-Point Arithmetic and Fast Robust Predicates for Computational Geometry: Shewchuk 1996

Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams: Guibas and Stolfi 1985