Open source planar navmesh built on DOTS

Hi there, hope you dont mind me stealing a second of your time to point your attention to DotsNav, a fully dynamic and robust planar navmesh built on DOTS. It is fast enough to add and remove many obstacles each frame, and supports agents of any size. Please check out the video or demo to see DotsNav in action or get the package at github

 

This looks really cool, thanks for posting. I'll definitely check this out.

I notice determinism is on the road-map. Other than floating point maths, is there anything else making the path-finding non-deterministic at the moment?

 

Thanks The determinism on the roadmap refers to the path finding budget, performing the same amount of calculations regardless of the time it takes

Currently all pending paths queries are performed, so the same amount of calculations are performed by default.

I'm not aware of fundamental issues beyond floating point stuff, I have not kept up with Unity's efforts in that regard

 

Very cool! Nice to see such a polished dots project and open source no less.

 

Love it. I'm on monobehaviour at the moment and doing a spot of VR. Is this a suitable solution even so (in that it doesn't produce garbage) ? I expect this to be too good to be true really.

 

I have not specifically looked at gc pressure yet, but there should be little and what is there should be easy enough to get rid of.

On the native side I have taken care to recycle allocations in most places.

The paths found are dumped in recycled .net List when using monobehaviours, so once they have grown a few times you should be good.

 

@hippocoder btw, are we talking about desktop vr? The geometric primitives rely on specific behaviour of floating point operations and have not been tested by me beyond (a more strenuous version of) the stress test in the demo and video. I have made an android build which appeared to run fine on my phone

 

Android VR, Quest and Consoles (PSVR)

 

Wel, I'm curious to hear how you get on

 

Thanks for sharing, I will play around

What was your inspiration for this?

 

@Bas-Smit First of all, this is really cool project.

My question is, how difficult would be, to adapt this, to maps with different elevations, ramps and overpasses (i.e. bridges, stairs)?

Secondary question is, did you stress test, to see how many paths you can generate efficently per frame?

 

+1 on a bit of 3D but I didn't want to ask since this being open source makes me feel guilty as hell (even though recast is 2.5D, if it can be called that).

 

It should be easy to support additional navmeshes, while Im not entirely sure about the current DOTS integration, each navmesh is an entity and you can create more by adding a NavmeshComponent, this then triggers all allocations through ISystemState. Deallocations are handled in the same way.

The easiest way to connect these navmeshes would be to teleport agents from one to the other, using some kind of animation of walking up the stairs etc. Another way would be to connect an edge from one navmesh to an edge from another and allow the path finding to traverse these edges. I have not goven much thought yet to the best way of doing this.

No, path planning performance has not been a focus up to this point. As a first improvement I'll add a pathfinding budget, but this can only terminate after a completed query.

 

The main drawback to the lct is it does not allow for tesselation, agents have a radius and as such can not pass over vertices in the same way a point agent can. This makes it hard to account for slope and terrain etc. in the path planning cost function

 

Yeah, that sounds like pretty valid solution.

No worry. My question was just out of curiosity.

 

I see you are using float2 for path finding.
Which naturally calculating path on a plane.
Since you consider radius, would flaot3 with adding height consideration into calculatios, solve the 3D problem?
For example having obstacles with different heights (height parameter) and having lets say birds, with low and high flying paths.

Mind I am not asking about features. I just wonder, if it is feasible with your repo at given state.

 

The real solution would be something hierarchical, but I have only seen solutions for static navmeshes
https://www.cs.upc.edu/~npelechano/Pelechano_HNAstar_prePrint.pdf

 

Different traversability requires a separate navmesh. You could end up with vertices that do not have an edge connected you could not traverse, and as you have a radius you can not pass over this vertex

There are no fundamental issues with multiple navmeshes though

 

Really just a pandemic project that spiralled out of control I read the first 2 papers mentioned near the bottom of the readme on github. For a while I considered making it an asset on the store, but given the breadth of the project this felt more appropriate

 

To quickly follow up on myself here, every lct (local clearance triangulation) is also a cdt (constrained delaunay triangulation). It is therefore straightforward to add support for point agents and tesselation. Given a custom cost function it should then be possible to take in to account slope, movement cost and traversability per agent category, and game specific strategic path planning.

 

Do you have any overall thoughts on DOTS and how much it might've got in the way of you making this? I ask because you've achieved quite a bit already but there must be a catch!

 

I'm not quite sure what you mean by catch, dotsnav is in an early stage of development and not well tested especially on platforms other than my pc I also expect scheduling and ECS integration in general could be improved, I did not dig very deep there. Someone mentioned sub scenes and honestly I did not even consider those.

I have my doubts about a few design decisions in DOTS, namely the inability to nest Native* structures and the inability to insert entities during a frame.

The first one is easily remedied, as you can see I simply created collections that do allow nesting, at the cost of losing memory leak detection.

The second one is less relevant to dotsnav, but I really dont see why entities added during a frame can not be iterated on without being layed out sequentially in memory first. I would prefer paying the associated cost almost always.

 

I suspect, it is due to memory layout changes. I may be wrong however..
At given frame, you know layout, so it is highly optimal accessed data in linear manner.
If you would try inject entities in mid frame, you will end up potentially with memory fragmentation.
I am not sure, how for example ForEach jobs would handle that in such case.

 

the idea would be to maintain a collection seperately from the chunks, iterate on those, insert in chunk at usual time. There are probably a lot of things I'm glossing over though

 

I haven't looked more into your code. But maybe could utilize more ECBs?
Or prearranged spare entities. Like a pooling?

 

I briefly considered subscene/conversion for some of my NavGraph stuff previously and then realised that it's all unusable in standalone so none of it would work in a map editor or similar.

 

Hi @Bas-Smit, thank you for sharing, it looks great!
I watched your video and there you use DotsNavAgent.Direction in the hybrid model to change the position of the game object. I tried using it in pure DOTS and when I tried to get the value of AgentDirectionComponent I found that this struct is private, and I don't have access to it from my system. I also haven't found any other interface to get this. Please tell me how can I get this?

 

Hi @as_nau, AgentDirectionComponent being private is an oversight, I will make it public in the next release, until then please maintain a local copy or fork the repo. Thanks for letting me know

 

If anyone knows how I get the update arrow to appear for a github package please let me know

https://forum.unity.com/threads/github-package-not-showing-update-arrow-for-new-version.1065230/

 

Thank you for your response. I also faced another issue. If I use your package, with already installed DOTS Physics package (com.unity.physics), I get this error:

GUID [b0127e7e38d54ef4394014ff4ccab268] for asset 'Packages/com.unity.physics/Unity.Physics.Hybrid/Assets/DebugDisplay/Resources/LineShaderProc.shader.meta' conflicts with:

  'Packages/com.bassmit.dotsnav/Internal/Drawing/LineShaderProc.shader.meta'

We can't assign a new GUID because the asset is in an immutable folder. The asset will be ignored.

and DotsNavRenderer stops working, paths and obstacles are not rendered.

If I install your package first, then the physics package, the paths are rendered sometimes. If first the physical package, then yours -the paths are not rendered at all.

 

Out of the box the package manager can not show or install updates for packages installed through a GitHub url like the dotsnav readme suggested. I now added dotsnav to openupm (thanks @Favo-Yang) if you install dotsnav through the unitypackage installer (top right), and install UpmGitExtensions (thanks @mob-sakai) you will be notified of and allowed to install updates to dotsnav and other custom packages. The readme has been updated with instructions.

A few fixes have been pushed, Agent components have been made public and the meta conflict should be resolved

@as_nau oops, missed your msg, I trust you figured it out? I ripped the drawing from the physics package

 

I just tried a new release: v0.1.4. The error message disappeared, but for some reason the navigation paths still don't render in scene window if I using your package with the unity physics package.

 

Hmm, I'll have to look in to it further then, thanks for letting me know

 

Thank you. I also noticed one more thing.
It looks like the boundaries of the obstacles are not always displayed correctly in the editor if the obstacle is non uniform scaled and rotated along the Y axis. But in play mode the vertices take the correct position.

 

@as_nau 0.1.5 is released containing the following fixes

- fix obstacle gizmo drawing
- fix drawing when the physics package is installed
- prevent crash when drawing too many lines
- warn when drawing max lines
- remove Assets folder from Samples to avoid confusion

 

@Bas-Smit, thank you for update! Now paths are drawn without problems with the installed physics package.
The shape of the obstacles is now correct even if the object is scaled and rotated. But the gizmo is shifted from the object when the object is rotated along the Y axis:

 

fixed in 0.1.6

also removes [CanEditMultipleObjects] from obstacle editor

 

@Bas-Smit, Is it possible to create a dynamic obstacle component that follows the parent entity?
If I add a DotsNavObstacle.cs script to a dynamic object, then in game, after conversion, when the entity is moved, the obstacle and gizmo remains in the same place. I have read the docs section on dynamic obstacles, but I have no success to implement them. Can you please explain how to make dynamic obstacles?

 

Dynamic means they can be removed, you would have to remove and reinsert each frame

Removing dynamic obstacles is possible as they are associated with their own entity. This also allows you to identify them, for instance when doing a ray cast and applying damage to a building

 

@as_nau while dotsnav is fast enough to do this for a bunch of entities, most likely you want to use local avoidance for something like this. Here is a demo of what I've been working on, I just need to find some time to integrate it Use wasd mouse and shift

https://drive.google.com/uc?export=download&id=1SXRZcM7tLgTwVisA9SmoZB3dGeNpBZ6M

It's a google drive link, the download takes a long time to kick in. The algorithm is rvo, it is a straight port of https://github.com/snape/RVO2-CS

 

This looks great!

Does this mean that both agents must be able to move freely to avoid a collision? If I have one agent that can move freely (some character) and one obstacle that can only move along a certain trajectory (some gate or train or a big rolling stone), then the obstacle cannot take half of the responsibility to avoid a collision.

I wrote a small authoring script and a system in order to respawn new obstacle entity if the parent was moved:

Spoiler

Code (CSharp):

1. using DotsNav.Data;
2. using DotsNav.Systems;
3. using Unity.Entities;
4. using Unity.Mathematics;
5. using Unity.Transforms;
6. using UnityEngine;
7.  
8. public struct DynamicObstacleData : IComponentData {
9.     public Entity obstacle;
10.     public float posTolerance;
11.     public float rotTolerance;
12. }
13.  
14. [DisallowMultipleComponent]
15. public class DynamicNavObstacleAuthoring : MonoBehaviour, IConvertGameObjectToEntity
16. {
17.     [SerializeField] bool Close = true;
18.     public bool Closed => Close && Vertices.Length > 2;
19.  
20.     [SerializeField] private Vector2[] Vertices = new Vector2[] {new Vector2(-0.5f, 0.5f), new Vector2(0.5f, 0.5f), new Vector2(0.5f, -0.5f), new Vector2(-0.5f, -0.5f),};
21.  
22.     [SerializeField] private float positionUpdateTolerance = 0.1f;
23.     [SerializeField] private float rotationUpdateTolerance = 0.001f;
24.  
25.     public void Convert(Entity entity, EntityManager dstManager, GameObjectConversionSystem conversionSystem)
26.     {
27.         var obstacleEntity = conversionSystem.CreateAdditionalEntity(this);
28.    
29.         if (dstManager.HasComponent<LocalToWorld>(entity)) {
30.             dstManager.AddComponentData(obstacleEntity, dstManager.GetComponentData<LocalToWorld>(entity));
31.         }
32.  
33.         if (dstManager.HasComponent<CompositeScale>(entity)) {
34.             dstManager.AddComponentData(obstacleEntity, dstManager.GetComponentData<CompositeScale>(entity));
35.         }
36.  
37.         if (dstManager.HasComponent<Translation>(entity)) {
38.             dstManager.AddComponentData(obstacleEntity, dstManager.GetComponentData<Translation>(entity));
39.         }
40.  
41.         if (dstManager.HasComponent<Rotation>(entity)) {
42.             dstManager.AddComponentData(obstacleEntity, dstManager.GetComponentData<Rotation>(entity));
43.         }
44.  
45.         dstManager.AddComponentData(obstacleEntity, new ObstacleComponent());
46.         var buffer = dstManager.AddBuffer<VertexElement>(obstacleEntity);
47.  
48.         for (int i = 0; i < this.Vertices.Length; i++)
49.             buffer.Add((float2)this.Vertices[i]);
50.  
51.         if (this.Closed)
52.             buffer.Add((float2)this.Vertices[0]);
53.  
54.         dstManager.AddComponentData(entity, new DynamicObstacleData {obstacle = obstacleEntity, posTolerance = positionUpdateTolerance, rotTolerance = rotationUpdateTolerance});
55.     }
56. }
57.  
58. [UpdateInGroup(typeof(LateSimulationSystemGroup))]
59. public class DynamicObstacleUpdateSystem : SystemBase
60. {
61.     private EndSimulationEntityCommandBufferSystem endSimulationEntityCommandBufferSystem;
62.     private BeginInitializationEntityCommandBufferSystem beginInitializationEntityCommandBufferSystem;
63.  
64.     private EntityArchetype compositeScaleObstacleArchetype;
65.  
66.     protected override void OnCreate() {
67.         base.OnCreate();
68.         endSimulationEntityCommandBufferSystem = World.GetOrCreateSystem<EndSimulationEntityCommandBufferSystem>();
69.         beginInitializationEntityCommandBufferSystem = World.GetOrCreateSystem<BeginInitializationEntityCommandBufferSystem>();
70.  
71.         compositeScaleObstacleArchetype = EntityManager.CreateArchetype(new ComponentType[] {
72.             ComponentType.ReadOnly<LocalToWorld>(),
73.             ComponentType.ReadOnly<CompositeScale>(),
74.             ComponentType.ReadOnly<Translation>(),
75.             ComponentType.ReadOnly<Rotation>(),
76.             ComponentType.ReadOnly<ObstacleComponent>(),
77.             ComponentType.ReadOnly<VertexElement>()
78.         });
79.     }
80.  
81.     protected override void OnUpdate() {
82.         var endSimEcb = endSimulationEntityCommandBufferSystem.CreateCommandBuffer().AsParallelWriter();
83.         var beginInitEcb = beginInitializationEntityCommandBufferSystem.CreateCommandBuffer().AsParallelWriter();
84.  
85.         var allLocalToWorld = GetComponentDataFromEntity<LocalToWorld>(true);
86.         var allVertexBuffers = GetBufferFromEntity<VertexElement>(true);
87.  
88.         var obsArchetype = compositeScaleObstacleArchetype;
89.  
90.         Entities.
91.         WithReadOnly(allLocalToWorld).
92.         WithReadOnly(allVertexBuffers).
93.         ForEach((Entity entity, int entityInQueryIndex, in DynamicObstacleData dynamicObstacle, in LocalToWorld localToWorld, in CompositeScale compositeScale, in Translation translation, in Rotation rotation) => {
94.             if (!allLocalToWorld.HasComponent(dynamicObstacle.obstacle) || !allVertexBuffers.HasComponent(dynamicObstacle.obstacle)) {
95.                 endSimEcb.RemoveComponent<DynamicObstacleData>(entityInQueryIndex, entity);
96.                 return;
97.             }
98.  
99.             var pos = new float2(translation.Value.x, translation.Value.z);
100.             var obstaclePos = new float2 (allLocalToWorld[dynamicObstacle.obstacle].Position.x, allLocalToWorld[dynamicObstacle.obstacle].Position.z);
101.  
102.             var rot = allLocalToWorld[entity].Rotation;
103.             var obstacleRot = allLocalToWorld[dynamicObstacle.obstacle].Rotation;
104.  
105.             if (math.distance(pos, obstaclePos) < dynamicObstacle.posTolerance && RotationsEqual(rot, obstacleRot, dynamicObstacle.rotTolerance)) { return; }
106.        
107.             endSimEcb.DestroyEntity(entityInQueryIndex, dynamicObstacle.obstacle);
108.  
109.             var newObs = beginInitEcb.CreateEntity(entityInQueryIndex, obsArchetype);
110.             beginInitEcb.SetComponent<DynamicObstacleData>(entityInQueryIndex, entity, new DynamicObstacleData{obstacle = newObs, posTolerance = dynamicObstacle.posTolerance, rotTolerance = dynamicObstacle.rotTolerance});
111.             beginInitEcb.SetComponent(entityInQueryIndex, newObs, localToWorld);
112.             beginInitEcb.SetComponent(entityInQueryIndex, newObs, compositeScale);
113.             beginInitEcb.SetComponent(entityInQueryIndex, newObs, translation);
114.             beginInitEcb.SetComponent(entityInQueryIndex, newObs, rotation);
115.             var buffer = beginInitEcb.SetBuffer<VertexElement>(entityInQueryIndex, newObs);
116.             buffer.AddRange(allVertexBuffers[dynamicObstacle.obstacle].AsNativeArray());
117.  
118.         }).ScheduleParallel();
119.  
120.         endSimulationEntityCommandBufferSystem.AddJobHandleForProducer(Dependency);
121.         beginInitializationEntityCommandBufferSystem.AddJobHandleForProducer(Dependency);
122.     }
123.  
124.  
125.     public static bool RotationsEqual(quaternion quatA, quaternion quatB, float acceptableTolerance) {
126.         return 1f - math.abs(math.dot(quatA, quatB)) < acceptableTolerance;
127.     }
128. }
129.  

It works, but it seems a bit overkill, to respawn the whole entity with all transforms components, when I need to refresh only obstacle component stuff and Navmesh. I tried to remove "ObstacleComponent" on BeginInitializationECB and add it back on EndDotsNavECB in order to make UpdateNavmeshSystem system think that this is a new entity and re-register it on next tick, but had no success). Maybe a job WithAll< NeedUpdateObstacleTag, ObstacleComponent, ObstacleSystemStateComponent >() makes sense, which will remove the obstacle from the Navmesh and add it back according to the current LocalToWorld? And we could just add the NeedUpdateObstacleTag to those entities whose position needs to be updated.

 

I have seen videos in the past of larger agents with fixed velocities, but I have not looked further than that. Similar issues occur with steering behaviours limiting your freedom of movement (rvo can produce any direction each step), it seems making the steering brake under certain conditions would solve most reasonably well. Line segment obstacles are fully supported.

For moving obstacles, see Update, Navmesh.cs 197. From memory I dont see any issues with first calling
RemoveConstraint then Insert using the same entity

 

Love the local avoiding covid virus

 

Hi there, local avoidance (RVO) is now available for your perusal



First though, the structure of the github repository has changed. The master branch now contains a 2020 LTS project. The upm branch contains the latest version of the package. Development takes place in the dev branch. The installation instructions have been updated.

There are a lot of breaking changes in the dev branch, the samples have been updated to provide some working examples.

To see local avoidance in action check out the dev branch and see RVO Circle Test scene. Note that agents can get stuck on obstacles as there is no path finding in this scene, agents simply move to their targets. To use the dev version of the package in a different project use Add package from disk.

Known issues:
- currently only closed, counter clockwise wound polygons are supported
- bulk insertion of obstales is not yet implemented (ObstacleBlobComponent and VertexElement + VertexAmountElement archetypes)
- job scheduling can be improved
- not deterministic on subsequents runs
- comments/summaries have not been updated

Let me know if you find any issues or have any feedback

 

Does it support automatically generating navmesh based on the geometry of the scene? Or I would need to manually feed it what is an obstacle and what is a moveable surface? I understand that it is inheritly 2D, but my scene is nothing that couldn't be solved by many connected 2D navmeshes

 

It does not. You can however have obstacles as part of prefabs so they get inserted wherever you place a prefab.

It is my intention to support this, but for now you are limited to one navmesh centered around the origin. The dynamic and obstacle tree systems implement a pattern I intend to replicate in the update navmesh system which allows for many navmeshes

You could consider embedding many such smaller navmeshes in one very large DotsNav navmesh, but probably easier to rewrite update navmesh system or wait for me to do it

 

@Guedez while allowing for multiple navmeshes is relatively straightforward, a lot more would be required. There needs to be a mechanism for connecting navmeshes that does not violate the lct, a way of setting up these navmeshes and connections conveniently, the path finding must be able to traverse these connections, and the local avoidance needs to "bleed through" to neighbouring navmeshes. It will be some time before I get around to this. A more feasible approach in the short term would be to only teleport from one navmesh to another masked by some game specific visuals (walking up stairs etc)

 

The most preferable features for using this in my project would be:

• A system to generate said navmeshes using the scene meshes
• Elevation data so npcs are not forced to walk on a plane and need not to rely on raycasts to ensure they are not walking through the ground or floating
• Enable multiple navmeshes.

Anything else I probably can cook up myself without relying on understanding someone's else code and doing hackey things that would need to be done again each update. I think I can figure out some ways of doing the first requirement, but they would certainly be very inneficient. Like setting up a 'AABB and fill the thing with boxes, if the box hits something, read the triangles form what hit it and if they have upward normals, then it's walkable' or some other terrible brute force thing. Worst comes to worst, I can still make them manually in blender and read the triangles to generate the navmesh, just need to make 'pathfind meshes'. The navmesh connections would need to be set up manually and would preferably be lines rather than points.
Pathfinding from one connected navesh all the way to the last one in a single command is not really required, it can be done in steps by an outside path controller, on demand even.

As for how I would use the navmeshes, I would use a two part pathfinding, first it would pathfind in a huge 'pathables' graph, then individually in each navmesh, since it needs to know about closed doors to begin with, it can't simply rely on the navmesh, especially if it can contextually know which doors it can open and which it cannot.
If an NPC needs to go from his house to a store, it would:

1. Do an A* in the navmesh graph (probably using some fancy navmesh-link heuristics)
2. Foreach tile in the graph:
   1. Do the pathfinding on a per-navmesh basis with the 'navmesh connection' that leads to his next navmesh as the target
   2. Walk his path
   3. On reaching the navmesh connection, walk into the next navmesh in the list, then repeat 1, unless it's the goal

If anything, I would need 'right side/left side' road navmeshes, inshop navmesh, inhouse navmesh, and a whole lot of other navmeshes full of metadata that specifies how and how often they need to be used, their weights (NPCS prefer roads rather than walking on top of railings, through brushes or on the grass (no desire path allowed), etc). I might actually relax those limitations depending on the NPC, to give them more character, so kids would walk through grass but old ladies won't, etc.

 

Multiple navmeshes are now available in the dev branch. They can be positioned and so on. Agents need to be assigned to a plane and are projected on to it, their positions are now 3d. The sample scenes have been updated.

The local avoidance demo scene is also ready, here's a 20 second video

 

If not for my deadline being way too short I would toss out my default Unity navmesh "solution" and start messing with this right now.