100,000 entities traversing navmesh

Unity Engine
,
41

This is very nice!
Unfortunately, when I tried to adapt it to the latest entities package (mainly MatrixTransform → LocalToWorld), I am now running into an endless loop, freezing Unity.

Has anyone successfully adapted this code for the latest entities package, by any chance?

42

Yeah I have a similar version running fine in my project.

What line in particular is your issue?

I’ve cleaned it up and modified it a bit.

1 Like
43

Thanks tertle for the quick answer. I’ve restarted Unity, and now it’s running on 2019.1.0a12, with entities 0.0.12-preview.21 (also with slight modifications). Apologies for posting without performing that basic debug step :sweat_smile:

44

I moved AgentStatus in another component (splitting Agent and NavData) and removed Position and Rotation from AgentComponent. Here it is :

NavAgentSystem.cs

#region

using System.Collections.Concurrent;
using UnityEngine;
using Unity.Burst;
using Unity.Collections;
using Unity.Entities;
using Unity.Jobs;
using Unity.Mathematics;
using Unity.Transforms;
using NavJob.Components;

#endregion

namespace NavJob.Systems
{
    class SetDestinationBarrier : BarrierSystem { }
    class PathSuccessBarrier : BarrierSystem { }
    class PathErrorBarrier : BarrierSystem { }

    [DisableAutoCreation]
    public class NavAgentSystem : JobComponentSystem
    {
        private struct AgentData
        {
            public int index;
            public Entity entity;
            public Agent agent;
            public NavData navData;
            public Position position;
        }

        private NativeQueue<AgentData> needsWaypoint;
        private ConcurrentDictionary<int, Vector3[]> waypoints = new ConcurrentDictionary<int, Vector3[]> ();
        private NativeHashMap<int, AgentData> pathFindingData;

        [BurstCompile]
        private struct DetectNextWaypointJob : IJobParallelFor
        {
            public int navMeshQuerySystemVersion;
            public InjectData data;
            public NativeQueue<AgentData>.Concurrent needsWaypoint;

            public void Execute (int index)
            {
                Agent agent = data.Agents[index];
                NavData navData = data.NavDatas[index];
                if (navData.remainingDistance - navData.stoppingDistance > 0 || agent.status != AgentStatus.Moving)
                {
                    return;
                }
                if (navData.nextWaypointIndex != navData.totalWaypoints)
                {
                    needsWaypoint.Enqueue (new AgentData { navData = data.NavDatas[index], position = data.Positions[index], entity = data.Entities[index], index = index });
                }
                else if (navMeshQuerySystemVersion != navData.queryVersion || navData.nextWaypointIndex == navData.totalWaypoints)
                {
                    navData.totalWaypoints = 0;
                    navData.currentWaypoint = 0;
                    agent.status = AgentStatus.Idle;
                    data.Agents[index] = agent;
                    data.NavDatas[index] = navData;
                }
            }
        }

        private struct SetNextWaypointJob : IJob
        {
            public InjectData data;
            public NativeQueue<AgentData> needsWaypoint;
            public void Execute ()
            {
                while (needsWaypoint.TryDequeue (out AgentData item))
                {
                    Entity entity = data.Entities[item.index];
                    if (instance.waypoints.TryGetValue (entity.Index, out Vector3[] currentWaypoints))
                    {
                        NavData agent = data.NavDatas[item.index];
                        agent.currentWaypoint = currentWaypoints[agent.nextWaypointIndex];
                        agent.remainingDistance = Vector3.Distance (data.Positions[item.index].Value, agent.currentWaypoint);
                        agent.nextWaypointIndex++;
                        data.NavDatas[item.index] = agent;
                    }
                }
            }
        }

        [BurstCompile]
        private struct MovementJob : IJobParallelFor
        {
            private readonly float dt;
            private readonly float3 up;
            private readonly float3 one;

            private InjectData data;

            public MovementJob (InjectData data, float dt)
            {
                this.dt = dt;
                this.data = data;
                up = Vector3.up;
                one = Vector3.one;
            }

            public void Execute (int index)
            {
                if (index >= data.NavDatas.Length)
                {
                    return;
                }

                Agent agent = data.Agents[index];
               
                if (agent.status != AgentStatus.Moving)
                {
                    return;
                }

                NavData navData = data.NavDatas[index];

                if (navData.remainingDistance > 0)
                {
                    Position position = data.Positions[index];
                    Rotation rotation = data.Rotations[index];

                    navData.currentMoveSpeed = Mathf.Lerp (navData.currentMoveSpeed, navData.moveSpeed, dt * navData.acceleration);
                    // todo: deceleration
                    if (navData.nextPosition.x != Mathf.Infinity)
                    {
                        position.Value = navData.nextPosition;
                    }
                    Vector3 heading = navData.currentWaypoint - position.Value;
                    navData.remainingDistance = heading.magnitude;
                    if (navData.remainingDistance > 0.001f)
                    {
                        Vector3 targetRotation = Quaternion.LookRotation (heading, up).eulerAngles;
                        targetRotation.x = targetRotation.z = 0;
                        if (navData.remainingDistance < 1)
                        {
                            rotation.Value = Quaternion.Euler (targetRotation);
                        }
                        else
                        {
                            rotation.Value = Quaternion.Slerp (rotation.Value, Quaternion.Euler (targetRotation), dt * navData.rotationSpeed);
                        }
                    }

                    navData.nextPosition = position.Value + math.forward(rotation.Value) * navData.currentMoveSpeed * dt;
                    data.NavDatas[index] = navData;
                    data.Positions[index] = position;
                    data.Rotations[index] = rotation;
                }
                else if (navData.nextWaypointIndex == navData.totalWaypoints)
                {
                    navData.nextPosition = new float3 { x = Mathf.Infinity, y = Mathf.Infinity, z = Mathf.Infinity };
                    agent.status = AgentStatus.Idle ;
                    data.Agents[index] = agent;
                    data.NavDatas[index] = navData;
                }
            }
        }

        private struct InjectData
        {
            public readonly int Length;
            [ReadOnly] public EntityArray Entities;
            public ComponentDataArray<Agent> Agents;
            public ComponentDataArray<NavData> NavDatas;
            public ComponentDataArray<Position> Positions;
            public ComponentDataArray<Rotation> Rotations;
        }

        [Inject] private InjectData data;
        [Inject] private NavMeshQuerySystem querySystem;
        [Inject] SetDestinationBarrier setDestinationBarrier;
        [Inject] PathSuccessBarrier pathSuccessBarrier;
        [Inject] PathErrorBarrier pathErrorBarrier;

        protected override JobHandle OnUpdate (JobHandle inputDeps)
        {
            inputDeps = new DetectNextWaypointJob { data = data, needsWaypoint = needsWaypoint.ToConcurrent(), navMeshQuerySystemVersion = querySystem.Version }.Schedule (data.Length, 64, inputDeps);
            inputDeps = new SetNextWaypointJob { data = data, needsWaypoint = needsWaypoint }.Schedule (inputDeps);
            inputDeps = new MovementJob (data, Time.deltaTime).Schedule (data.Length, 64, inputDeps);
            return inputDeps;
        }

        /// <summary>
        /// Used to set an agent destination and start the pathfinding process
        /// </summary>
        /// <param name="entity"></param>
        /// <param name="navData"></param>
        /// <param name="destination"></param>
        public void SetDestination (Entity entity, Agent agent, NavData navData, Position position, Vector3 destination, int areas = -1)
        {
            if (pathFindingData.TryAdd (entity.Index, new AgentData { index = entity.Index, entity = entity, agent = agent, navData = navData, position = position }))
            {
                agent.status = AgentStatus.PathQueued;
                navData.destination = destination;
                navData.queryVersion = querySystem.Version;
                setDestinationBarrier.CreateCommandBuffer().SetComponent(entity, agent);
                setDestinationBarrier.CreateCommandBuffer().SetComponent(entity, navData);
                querySystem.RequestPath (entity.Index, position.Value, navData.destination, areas);
            }
        }

        /// <summary>
        /// Static counterpart of SetDestination
        /// </summary>
        /// <param name="entity"></param>
        /// <param name="navData"></param>
        /// <param name="destination"></param>
        public static void SetDestinationStatic (Entity entity, Agent agent, NavData navData, Position position, Vector3 destination, int areas = -1)
        {
            instance.SetDestination (entity, agent, navData, position, destination, areas);
        }

        protected static NavAgentSystem instance;

        protected override void OnCreateManager ()
        {
            instance = this;
            querySystem.RegisterPathResolvedCallback (OnPathSuccess);
            querySystem.RegisterPathFailedCallback (OnPathError);
            needsWaypoint = new NativeQueue<AgentData> (Allocator.Persistent);
            pathFindingData = new NativeHashMap<int, AgentData> (0, Allocator.Persistent);
        }

        protected override void OnDestroyManager ()
        {
            needsWaypoint.Dispose ();
            pathFindingData.Dispose ();
        }

        private void SetWaypoint (Entity entity, Agent agent, NavData navData, Position position, Vector3[] newWaypoints)
        {
            waypoints[entity.Index] = newWaypoints;
            agent.status = AgentStatus.Moving;
            navData.nextWaypointIndex = 1;
            navData.totalWaypoints = newWaypoints.Length;
            navData.currentWaypoint = newWaypoints[0];
            navData.remainingDistance = Vector3.Distance (position.Value, navData.currentWaypoint);
            pathSuccessBarrier.CreateCommandBuffer().SetComponent(entity, agent);
            pathSuccessBarrier.CreateCommandBuffer().SetComponent(entity, navData);
        }

        private void OnPathSuccess (int index, Vector3[] waypoints)
        {
            if (pathFindingData.TryGetValue (index, out AgentData entry))
            {
                SetWaypoint (entry.entity, entry.agent, entry.navData, entry.position, waypoints);
                pathFindingData.Remove (index);
            }
        }

        private void OnPathError (int index, PathfindingFailedReason reason)
        {
            if (pathFindingData.TryGetValue (index, out AgentData entry))
            {
                entry.agent.status = AgentStatus.Idle;
                pathErrorBarrier.CreateCommandBuffer().SetComponent(entry.entity, entry.agent);
                pathFindingData.Remove (index);
            }
        }
    }
}

NavDataComponent.cs

using UnityEngine;
using Unity.Entities;
using Unity.Mathematics;

namespace NavJob.Components
{
    [System.Serializable]
    public struct NavData : IComponentData
    {
        public float stoppingDistance;
        public float moveSpeed;
        public float acceleration;
        public float rotationSpeed;
        public int areaMask;
        public float3 destination { get; set; }
        public float currentMoveSpeed { get; set; }
        public int queryVersion { get; set; }
        public float3 nextPosition { get; set; }
        public float remainingDistance { get; set; }
        public float3 currentWaypoint { get; set; }
        public int nextWaypointIndex { get; set; }
        public int totalWaypoints { get; set; }

        public NavData (
            float stoppingDistance = 1f,
            float moveSpeed = 4f,
            float acceleration = 1f,
            float rotationSpeed = 10f,
            int areaMask = -1
        )
        {
            this.stoppingDistance = stoppingDistance;
            this.moveSpeed = moveSpeed;
            this.acceleration = acceleration;
            this.rotationSpeed = rotationSpeed;
            this.areaMask = areaMask;
            destination = Vector3.zero;
            currentMoveSpeed = 0;
            queryVersion = 0;
            nextPosition = new float3 (Mathf.Infinity, Mathf.Infinity, Mathf.Infinity);
            remainingDistance = 0;
            currentWaypoint = Vector3.zero;
            nextWaypointIndex = 0;
            totalWaypoints = 0;
        }
    }

    public class NavDataComponent : ComponentDataWrapper<NavData> { }
}

AgentComponent.cs

using Unity.Entities;

    public enum AgentStatus
    {       
Idle = 0,
PathQueued = 1,
Moving = 2,
Paused = 4
    }

    [System.Serializable]
    public struct Agent : IComponentData
    {
        public AgentStatus status { get; set; }
    }

    public class AgentComponent : ComponentDataWrapper<Agent> { }

I did the same for local avoidance and totally removed the rest. Let me know if there’s a problem, but it should work.

1 Like
45

speed up ? faster ?

46

Sorry, I didn’t compare, I just needed to make it work with current packages.

4 Likes
47

awesome work!

1 Like
48

@zulfajuniadi just wondering, did you ever finish rvo2 on your project?

1 Like
49

Hi,
Has anyone been able to get this to complie, i see @Djayp did some work to get it working for “current packages” do we know the version of Unity and DOTS that this project works in?
I have seen a post on the git by PodeCaradox 10 days ago who linked a new NavAgentSystem.cs but still 41 complie errors remain

50

Hello ! It was Entities 0.0.12-preview.21 or just after… I think there’s a lot of changes since but I didn’t update it. You’d better go with PodeCaradox’s code.

51

How are the paths computed in the OP video? I see that the ‘Awaiting Path’ field is bigger than 0 only when spawning new entities, meaning that existing paths never get refreshed once computed? If so, then the performance is not all that great.

Since it looks like it’s using cached paths, does that mean it doesn’t support runtime manipulation of the nav graph (adding/removing obstacles)?

52

https://github.com/zulfajuniadi/unity-ecs-navmesh/blob/master/Assets/Demo/Scripts/Behaviours/
In the sample you can add new buildings using the BuildingCacheSystem. The DetectIdleAgentSystem will enqueue idle agents and assign them a destination from the “Commercial” buildings in the BuildingCacheSystem (see Building.cs and DemoSystems.cs).

https://github.com/zulfajuniadi/unity-ecs-navmesh/tree/master/Assets/NavJob/Systems
The NavAgentSystem will then request a path to the NavMeshQuerySystem. If the path is cached the NavMeshQuerySystem invokes the success callbacks, else it enqueues a PathQueryData. OnUpdate, it uses NavMeshQuery on 256 jobs slots (see NavAgentSystem.cs and NavMeshQuerySystem.cs).

Existing paths don’t get refreshed but I don’t understand why performances wouldn’t be great with cached paths. You can use PurgeCache() if you need to empty it. It’s using NavMeshModifier component to add/remove obstacles, so it already involves baking a NavMesh at runtime (see https://github.com/zulfajuniadi/unity-ecs-navmesh/blob/master/Assets/Demo/Scripts/Behaviours/TownBuilder.cs).

GetComponent<BuildNavMesh> ().Build ((AsyncOperation operation) =>
{
    NavMeshQuerySystem.PurgeCacheStatic ();
    Debug.Log ("Town built. Cache purged.");
});
1 Like
53

Hey Guys,

i’m PodeCaradox from Github, i changed the Systems to work with the new Entites Package but i don’t saw the avoidance system updated. If i use the old one i changed a little bit it does weird things, maybe you will update the Github?

I saw in the old one you don’t use the avoidance variable:

public void ExecuteNext(int firstIndex, int index)
            {
                var agent = agents[entities[index]];
                var avoidance = avoidances[entities[index]];
                var move = Vector3.left;
                if (index % 2 == 1)
                {
                    move = Vector3.right;
                }
                float3 drift = agent.rotation * (Vector3.forward + move) * agent.currentMoveSpeed * dt;
                if (agent.nextWaypointIndex != agent.totalWaypoints)
                {
                    var offsetWaypoint = agent.currentWaypoint + drift;
                    var waypointInfo = navMeshQuery.MapLocation(offsetWaypoint, Vector3.one * 3f, 0, agent.areaMask);
                    if (navMeshQuery.IsValid(waypointInfo))
                    {
                        agent.currentWaypoint = waypointInfo.position;
                    }
                }
                agent.currentMoveSpeed = Mathf.Max(agent.currentMoveSpeed / 2f, 0.5f);
                var positionInfo = navMeshQuery.MapLocation(agent.position + drift, Vector3.one * 3f, 0, agent.areaMask);
                if (navMeshQuery.IsValid(positionInfo))
                {
                    agent.nextPosition = positionInfo.position;
                }
                else
                {
                    agent.nextPosition = agent.position;
                }
                agents[entities[index]] = agent;
            }
        }

A Update would be pretty nice, and thanks for the git it helped me alot. :slight_smile:

Also maybe for the Raycasts, the new Physics System would be nice :slight_smile:

3 Likes
54

an interesting thread… just wanted to say I’m following along.

55

Anybody here managed to update this project to the Entities 0.4.0 version?

1 Like