AI Local Avoidance 3.0.0

Hey,

So almost 8 years ago I started creating my very first RTS Game on Unity. It was really a blast and I managed to recreate very close experience of Warcraft 3 on Mobile

.

For agent avoidance I used Unity built-in navmesh agents. However I quickly noticed that it does not perform that well in most critical RTS cases (etc. circling targets, getting around standing agents). I decided maybe I should try to roll out my solution, it should not be that hard, is it? Boy... I was wrong... Not long I realized outside RVO solution, many successful companies tend to not share their navigation tech (Maybe things did change now). I remember spending many hours dissecting one of the GDC videos where blizzard employee was show-offing their local avoidance, but leaving all details unexplained . Finally, I came up with cool solution...

Fast forward to now, sadly project did not reached the daylight for various reasons. Yet I noticed there is a lot of value in my custom local avoidance solution. So I decided to create a package out of it using even more powerful algorithm with DOTS.

For version 2.0.0
I released complete minimum API so it could be fit into any design with ease, regardless it is OOD or DOD. Here is small example with one obstacle and drawing it in gizmos:

Code (CSharp):

1.  
2. void OnDrawGizmos()
3. {
4.     using (var sonar = new SonarAvoidance(transform.position, quaternion.identity, InnerRadius, OuterRadius, math.length(Velocity), Allocator.Temp))
5.     {
6.         sonar.InsertObstacle(new float3(-1, 0, 0), math.radians(180));
7.         if (Obstacle)
8.         {
9.             sonar.InsertObstacle(Obstacle.transform.position, ObstacleVelocity, ObstacleRadius);
10.             sonar.DrawObstacle(Obstacle.transform.position, ObstacleVelocity, ObstacleRadius);
11.         }
12.         sonar.DrawSonar();
13.         sonar.DrawClosestDirection();
14.     }
15. }
16.  

This solution end up exhibiting many cool behaviors like:

• Manages navigation out of concave obstacles
• Circles target
• Avoids head to head moving
• Accurately respects radius
• Predicts collisions and avoids based on that
• Avoids only when necessary

Some of them can be seen in:

To honor the Starcraft2 I even recreated Zerg demo:

In Bigger crowd:

Finally, decided to bring back new solution to my Old game and see how it works :

Package AssetStore
Support Discord
Demo Zerg

Now for version 3.0.0
I plan to create some MonoBehaviour implementation so there would be possibility to use package without coding. I am currently fixated on idea having MonoBehaviour as wrapper and behind the hood running ECS in hybrid mode. This would allow code to work with other MonoBehaviour components and also having all advantages of ECS. Also as bonus this enables easy way using ECS only for those who would want. I am curious to hear other opinion about this approach, as this would require having ECS in your project.

To give better idea here is the scene with 10 agents. Each agent GameObject has its copy of Entity as seen in Entity Debugger. Their settings gets in sync.



Here is image with Entity selected.


That is kind a it, thanks for taking interest.

 

Oooh, ECS-only would be awesome. Looking forward to 3.0.0))

 

Recreating now test scenes with new systems. Will keep them as benchmark across the development. There is still some overlaps, but that will be improved.

 

Design coming together really nice.

Here is example where monobehavior agents gets converted to entity and still syncs transform.


Solution is very modular and you can replace any behavior easily. Like gif shows firstly it has no avoidance and goes through the obstacle. In other plays to different avoid algorithms are used.


The same design will allow for adding/removing with ease other components like unity navmesh, flocking, agent shapes, 2d/3d, different movement algorithms or even implementing other package navigations like A*.

 

Awesome, I think performance is key.

 

i like it !!!
is there a roadmap?

 

For now there is not much of the roadmap.
Version 3 is set to include:
- Hybrid/ECS agent implementation
- Version 2 avoidance component
- ORCA component
- Jobified Unity NavMesh component
- Few shapes for obstacles (Capsule for 3D, Circle for 2D and probably some polygon for non moving)
- Flocking (Not sure about this one yet)
The whole focus will be to have very modular and high performance solution for agents.

 

K seems like ECS unity navmesh works now :O! It uses UnityEngine.Experimental.AI.

Also auto repath works in case obstacles added that carves navmesh.


So far really happy about how it goes. Fully multi-threaded and still work with unity builtin navmesh, that is crazy.
Will do stress test on this later.

 

Looks awesome! I'm searching for some good dots based pathfinding and local avoidance system right now. Your is looking very promising. Does version 3.0 still under development?

 

I am back at developing it. Was a bit sidetracked by my other asset store packages.

Here is overview of current progress:
1. Implement Agent, Agent Capsule Shape components. Which allows simple agent movement (Done Before)

2. Implement Agent Collider, Agent Separation components. Which allows distance enforcing between agents (Done Before)

3. Implement Agent Avoid component. Which enables local avoidance using this package (Done Before)

4. Implement Agent Navigation component. Which allows agent to use Unity NavMesh (Done)

5. Upgrade from ECS 0.5 to ECS 1.0 (Done)
6. Implement Agent Circle Shape for proper 2D support (Not Started)
7. Sync GameObject properties to Entity (In Progress)
8. Change most of the systems from SystemBase class to ISystem interface. This will reduce main thread overhead even more (Not Started)
9. Huge zerg demo, with ground small zergs and flying zergs (Not Started)
10. Cache NavMesh requested paths. As example if huge groups requests path, in theory they all can reuse same path (Not Started)

This solution will be designed to work with both Entity and GameObject. In Entity case you will use usual ECS workflow of baking. Where with GameObject, there will be internal ECS world syncing with GameObjects.

 

As I haven't started huge zerg demo. For now got performance numbers with 60 agents GameObjects.
There is still place for optimization, but so far not bad. Overhead on main thread is 0.12ms, avoid job 0.06ms, collider jobs 0.2ms, 0.155ms navmesh update.
So far biggest performance offender is collider jobs as they are not scheduled parallel and requires 4 iterations.

 

This is really cool I've been looking for something like this for ages in DOTS. I tried making my own, but like you say its really bloody hard.

 

Managed to make collider job also parallel. Now made initial stress test demo (Going to look better in the future ).


It is still not many agents roughly ~2k. However impressive part is still GameObjects that are driven by internal ECS world.


Green blocks bursted navigations jobs, as you can see most cost comes from Game Object Skinned mesh, rendering and others.

This demo does not uses SonarAvoidance jobs, only NavMesh and Collision jobs.

 

Would it be possible to prevent agents from pushing each other?

 

Awesome work, this looks really efficient!

 

Yes, plan to provide mask probably

 

I have a dumb basic question that probably is answered somewhere, but does this work without the navmesh I have my own flow field navigation system I want to use this with.

 

Yes, if you would check the gifs above carefully (https://forum.unity.com/threads/local-avoidance-3-0-0.1299813/#post-8498078), you will notice that each of them are with different components combination, first one does not even have navmesh. Idea is that you would combine components to have desired behaviour and everything will be modular.

 

That's awesome, thanks.

 

Looks excellent, good work!

 

So Cool！It's amazing to me！

 

Very cool! How long until you are able to do this without game-objects?

 

Could you elaborate the questions not sure I fully understood. Are you asking, when full ECS solution will be available?

 

You wrote: "However impressive part is still GameObjects that are driven by internal ECS world". So I figured that you might try with pure entities instead (without game objects) sometime and I was just curious as to when that might be.

 

hello when is the new version coming

 

Yea this is something on my plan want to finish samples first. Performance should not differ that much, as only slow part with game object solution is syncing transform, as rendering depend on it also triggers main thread wait.

For progress you can check my discord channel https://discord.gg/uZJGzN253D. I plan to release until December.

 

Finally, found some time to compare same scene performance ECS and Hybrid.

Scene setup is very simple there is total of 3k agents. They use two behaviours navmesh and collision.


For Hybrid, it uses Game Objects that are synced with Entity copy.
For ECS, I wrote my simple custom rendering system (Did not wanted to use ECS graphics package, as it requires SRP). Of course, it is not efficient, but good enough for test.

Code (CSharp):

1. public partial class DrawStaticMeshRendererSystem : SystemBase
2. {
3.     protected override void OnUpdate()
4.     {
5.         Entities.ForEach((in StaticMeshRenderer mesh, in StaticMaterialRenderer material, in LocalToWorld localToWorld) =>
6.         {
7.             Graphics.DrawMesh(mesh.Value, localToWorld.Value, material.Value, 0);
8.         }).WithoutBurst().Run();
9.     }
10. }

Cool part that both solutions uses same scene, where ECS one have that scene as subscene. In theory, you can use both solutions at the same time. :O

Performance, end up being almost the same as the key difference between Hybrid and ECS was syncing transforms. Which is fairly cheap in production build (For 3k agents it as taking somewhat ~0.5ms)

 

I almost done, I plan to release next week!

Some videos:

 

second not milisecond ? because 0.5s is not cheap for me

 

Yea it is ms, 0.5s would be super slow .

 

Released https://assetstore.unity.com/packages/tools/ai/agents-navigation-239233! For those who have local avoidance, there is paid upgrade.

 

what is the ideal setup for using agents navigation?

should we import it into a 3D URP 2022.2 BETA project, or import com.unity.jobs before hand? hybrid renderer?

full ECS DOTS work flow within 2022.2? do you have any docs or tutorials for setup available?

thanks again

 

Hey, yes for ESC workflow. You going to need com.unity.entities.graphics (a.k.a hybrid renderer) and as hybrid requires SRP, either URP or HDRP.
For now, my samples are more focused with hybrid workflow. As hybrid renderer is not very stable and don't want to add hybrid renderer as dependency into package (For now UPM does not support samples with dependencies).

 

As I haven't posted for a while here is recap:

## [3.0.4] - 2022-12-23
- Fixed NavMeshAgent correctly handle partial paths (Paths where destination can not be reached)
- Fixed few more cases where NavMesh update would result in "Any jobs using NavMeshQuery must be completed before we mutate the NavMesh."
- Fixed NavMeshAgent in some cases reusing path from other agent
- Changed Zerg scene camera to be centered around controllable units

## [3.0.3] - 2022-12-17
- Added to EntityBehaviour OnEnable and OnDisable
- Added error message box to AgentNavMeshAuthoring, if game objects also has NavMeshObstacle
- Added SetDestination method to AgentAuthoring
- Changed that if agent is not near any NavMesh it will throw error instead moved to the center of the world
- Fixed few cases where NavMesh update would result in "Any jobs using NavMeshQuery must be completed before we mutate the NavMesh."

## [3.0.2] - 2022-12-15
- Fixed NavMesh at the end of destination throwing error `System.IndexOutOfRangeException: Index {0} is out of range of '{1}' Length`.
- Fixed transform sync from game object to entity not override transform in most calls.

## [3.0.1] - 2022-12-08
- Added correct documentation
- Added com.unity.modules.ui dependency as samples uses ui
- Removed second navmesh surface from zerg samples

For the roadmap:
- avoidance account navmesh
- collab with other global navigation solutions (etc. if you dont want to use unity navmesh)
- fixed type support

 

Hello, thanks again for supporting your asset, it means a lot

also, what is the best way to stop a navmesh agent within specified range (both 2D and 3D axis) of a target?

I have this code modified for a simple test on your "Circle Target Reciprocal" test scene under Scenarios folder:

Code (CSharp):

1.         public Transform Target;
2.         public float Radius;
3.  
4.     public AgentAuthoring agent = null;
5.  
6.         private void Start()
7.         {
8.             agent = transform.GetComponent<AgentAuthoring>();
9.         }
10.  
11. private void Update()
12.         {
13.            
14.             var body = agent.EntityBody;
15.            
16.             //if ((Vector3)body.Destination == Target.position)
17.             if (this.gameObject.transform.position == Target.position)
18.             {
19.                
20.                 Debug.Log("Reached destination!");
21.                 body.Stop();
22.                
23.                 agent.EntityBody = body;
24.                
25.             }
26.             else
27.             {
28.                
29.                 body.Destination = Target.position;
30.                 body.IsStopped = false;
31.                
32.                 agent.EntityBody = body;
33.                
34.             }
35.            
36.         }
37.     }

i am trying not to make use of triggers unless I have to, also, not sure if I'm doing this most efficiently so I thought I would ask you how to best go about it, thanks again!

as I understand it, I should try and compare the distance of the two points using basic math, and if its less than a certain distance, I should manually call stop? However I am trying to see what ways you would approach it before I use line/distance and compare which might be more expensive... not sure.

 

Thanks!

You should try to get in EntitySteering and modify StoppingDistance property.

 

Could this be used as a drop in replacement for unitys NavMeshAgent in GameObjects? As in could I just remove NavMeshAgent component and use this one instead and then replace all NavMeshAgent references in my code with this?

 

This could work with entities path, as I could write bakers that would convert NavMeshAgent to entities components like I am doing with all Agent*. However, for now I am a bit hesitant as obviously they would work differently, which could create a bit of confusion. But I think it is really nice idea, which I will think about it.
For hybrid solution, it would not be that trivial as it would need some mechanic to indicate should it use my navigation or unity's. Which in most cases would need some additional component, at the same time defeating the whole purpose of it.

 

Documentation https://lukaschod.github.io/agents-navigation-docs/manual/index.html

 

Unity already use RVO.
If they simply open that part in their source code, it can be easily implemented, but they don't do that.

 

Currently, I am going to use this set with the 2022 version.
My project is 2d.
However, using this set requires Entities, but installing Entities causes conflicts with Unity 2D Animation.

The collision error message is related to Native HashMap.
Is there a solution?

 

As you already asked this in discord, I will still answer as somebody might have similar question. This happens, because entities package require collection package 2.0 and 2d animations uses collections 1.0. You will have to wait till 2d animations package will release new version that will use collection 2.0 (I heard rumor's it might happen by the end of the January, but it would be good to track the roadmap to see it)

 

## [3.1.0] - 2023-1-31
- Added new feature to local avoidance `Walls` that accounts for navmesh.
- Added new property to AgentNavMeshAuthoring UseWalls.
- Added new option to SonarAvoidance angle.
- Changed standing agents now puch each other.
- Fixed local avoidance gizmos drawing.
- Fixed then desination either above or below agent would result in error.
- Fixed path failure case then it is out of nodes and path is in progress.

Agents going through chock point. You should notice that with feature agents don't end up moonwalking the wall.
Without Walls
With Walls


Obstacle navmesh walls in front of moving group. You should notice that with feature on, agent doesn't get pushed into wall and moonwalking
Without walls

With Walls

 

I played around with idea having `NavMeshSurface 2D` component. Basically would be almost the same as NavMeshSurface just tailored for 2D.

I made really small prototype of that idea by copying original NavMeshSurface and adding two features:
- Up axis as Z
- Sprites use for baking with their sorting layer


I am curious if anyone would be interested to have this feature in this package? If yes, what features would you want it to support and what 2d renderers are you using in your game?

 

I imported the package and I'm seeing these errors:



I think think 1.0.0-pre.44 changed NativeMultiHashMap to NativeParallelMultiHashMap. I think the errors about "Spatial" are also related to the hashmap renaming because it contains a hashmap as well.

 

Thanks, yea for now use pre.15. I will try to release in upcoming days new version that will support pre.44.

 

K seems like Unity renamed HashMap again (It seems like they keep renaming it every release)...
So for quick fix you can rename NativeMultiHashMap to NativeParallelMultiHashMap.

 

That is what I did. There was about 10 warnings about unused/uninitialized variables after, but the errors went away.

Spoiler: warnings

Build started...
------ Build started: Project: ProjectDawn.LocalAvoidance, Configuration: Debug Any CPU ------
------ Build started: Project: ProjectDawn.ReciprocalAvoidance, Configuration: Debug Any CPU ------
------ Build started: Project: ProjectDawn.Navigation, Configuration: Debug Any CPU ------
Temp/GeneratedCode/ProjectDawn.Navigation(13,73): warning CS0649: Field 'NavMeshPathSystem.NavMeshPathJob.__Unity_Entities_EntityTypeHandle' is never assigned to, and will always have its default value
------ Build started: Project: ProjectDawn.Navigation.Hybrid, Configuration: Debug Any CPU ------
------ Build started: Project: ProjectDawn.Navigation.Editor, Configuration: Debug Any CPU ------
Temp/GeneratedCode/ProjectDawn.Navigation.Editor(14,73): warning CS0649: Field 'NavMeshNodesGizmosSystem.Job.__Unity_Entities_EntityTypeHandle' is never assigned to, and will always have its default value
C:\Code\TestProject\Packages\com.projectdawn.navigation\ProjectDawn.Navigation.Editor\AgentColliderGizmoSystem.cs(62,27): warning CS0649: Field 'AgentColliderGizmosSystem.DrawSpatialEntities.Position' is never assigned to, and will always have its default value
Temp/GeneratedCode/ProjectDawn.Navigation.Editor(16,73): warning CS0649: Field 'AgentColliderGizmosSystem.Job.__Unity_Entities_EntityTypeHandle' is never assigned to, and will always have its default value
Temp/GeneratedCode/ProjectDawn.Navigation.Editor(19,73): warning CS0649: Field 'AgentAvoidGizmosSystem.AgentAvoidJob.__Unity_Entities_EntityTypeHandle' is never assigned to, and will always have its default value
------ Build started: Project: ProjectDawn.Navigation.Samples.Zerg, Configuration: Debug Any CPU ------
Temp/GeneratedCode/ProjectDawn.Navigation.Samples.Zerg(13,73): warning CS0649: Field 'UnitBrainSystem.UnitBrainAttackJob.__Unity_Entities_EntityTypeHandle' is never assigned to, and will always have its default value
Temp/GeneratedCode/ProjectDawn.Navigation.Samples.Zerg(13,73): warning CS0649: Field 'UnitBrainSystem.UnitBrainIdleJob.__Unity_Entities_EntityTypeHandle' is never assigned to, and will always have its default value
Temp/GeneratedCode/ProjectDawn.Navigation.Samples.Zerg(13,73): warning CS0649: Field 'UnitBrainSystem.UnitBrainFacingJob.__Unity_Entities_EntityTypeHandle' is never assigned to, and will always have its default value
Temp/GeneratedCode/ProjectDawn.Navigation.Samples.Zerg(13,73): warning CS0649: Field 'UnitBrainSystem.UnitBrainSmartStopJob.__Unity_Entities_EntityTypeHandle' is never assigned to, and will always have its default value
------ Build started: Project: ProjectDawn.Navigation.Samples.Scenarios, Configuration: Debug Any CPU ------
------ Build started: Project: ProjectDawn.Navigation.Hybrid.Editor, Configuration: Debug Any CPU ------
------ Build started: Project: ProjectDawn.Navigation.Sample.Mass, Configuration: Debug Any CPU ------
------ Build started: Project: Assembly-CSharp, Configuration: Debug Any CPU ------
------ Build started: Project: Assembly-CSharp-Editor, Configuration: Debug Any CPU ------
========== Build: 11 succeeded or up-to-date, 0 failed, 0 skipped ==========

Couple of comments after first install....

In a URP project, most of the materials in the demo were pink. I had to convert them from the standard renderer to URP Simple-Lit.

I was surprised to run the Mass benchmark demo and see game-objects in the hierarchy. Even with only 390 agents it drops to less than 20 FPS (Colliders disabled). I have been using A* Pathfinding Project's RVO with ECS and it can run several thousand entities in its simulation before FPS drops under 30 - even in the editor. I think under the hood the A*PFP RVO simulation only runs at about 10fps because the player won't notice if it runs any faster. I hope the reason the Project Dawn simulation is so slow is because of the game objects, and I hope that running it with entities will be much faster. Is there a sample project for the entities version?

EDIT: I don't know why, but disabling burst and re-enabling it fixed it! With colliders disabled, I started getting about 3100 objects before the FPS dropped under 30 FPS.

 

Hey

Yes, samples are using builtin render pipeline, so it is expected that using URP will have magenta. I did not wanted to add dependency on URP for samples.

It is a bit odd, do you have burst enabled just in case? It should easily handle 1k even in hybrid.
As this is getting a bit to support zone, could you post this in my discord Discord. I want to keep discord for support related questions as it is easier to handle and have forum for overall news, suggestions (I hope it sounds acceptable).

This is interesting idea about variable rate update, I was thinking about it before. This is really nice thing to post into my Discord as feature-request. Only concern about this making it deterministic, as everything is running in fixed step, maybe just do frame skips for avoidance.

 

Sure, that's no problem. I'm already a member there.

You were right. I checked and burst was enabled, but just for the heck of it I disabled and then enabled it and a window popped up saying burst was compiling and then it got MUCH faster (3100 agents before dropping under 30fps). I put an edit in my post above in case anyone is reading they'll know right away that it was a burst issue. Thanks for your help and sorry I didn't check that earlier.

OK, I'll post it there. It wasn't really a feature request so much as it was an observation about how A*PFP worked and I was curios if your package did something similar. In theory running the simulation less often could triple performance if it ran around 10fps instead of 30, and it would give up to a 6x improvement for projects that are shooting for 60fps!