Pathfinding & ECS

I'm having a bit of trouble with how to handle pathfinding! I'm trying to make a game with minions that do tasks like build and fight. I'm having trouble trying to figure out a way to do the pathfinding. How do a create a path for them to follow, and feed it to them, so they follow the path.

 

Look at a* pathfinding algorithm. I'm actually going to make a ECS example once native arrays become available in I componentData.

Here is my monobehaviour version.
https://github.com/nickkorta/CSharp...mmit/273db501916321da860696c299700c364350a33b

 

You could also use Hybrid ECS and use unitys pathfinding system. Here is a link to brackeys tutoral on YouTube.

 

This aproach don’t give big performance boost, and didnt work on many cases, for example 30-100k units. For unity pathfinding and ECS you must write your own system based on jobs, NavMeshQuery (supported in IJob), caching paths and other.

You can look this for example: https://forum.unity.com/threads/100-000-entities-traversing-navmesh.534526

 

I wrote an a* pathfinding system with jobs/ecs already.
I only finished it yesterday and it's a bit of a mess atm but you can get some ideas from it.
Uses a very fast MinHeap for performance.
Designed for grid based pathfinding at the moment, though there's no real reason the concept is restricted to that. I already though about how to add portals I just haven't to around to it yet.

This is the main job that finds the path

Code (CSharp):

1.  
2.         [BurstCompile]
3.         private struct FindPathJob : IJob
4.         {
5.             public PathRequest Request;
6.             public int DimX;
7.             public int DimY;
8.             public int2 Offset;
9.             public int IterationLimit;
10.  
11.             [ReadOnly] public NativeArray<Neighbour> Neighbours;
12.             [ReadOnly] public NativeArray<Cell> Grid;
13.  
14.             public NativeList<int2> Waypoints;
15.             public NativeArray<float> CostSoFar;
16.             public NativeArray<int2> CameFrom;
17.             public NativeMinHeap OpenSet;
18.  
19.             public void Execute()
20.             {
21.                 Waypoints.Clear();
22.  
23.                 var start = Request.From.xz.FloorToInt() - Offset;
24.                 var end = Request.To.xz.FloorToInt() - Offset;
25.  
26.                 FindPath(start, end);
27.             }
28.  
29.             private void FindPath(int2 start, int2 end)
30.             {
31.                 if (start.Equals(end))
32.                     return;
33.  
34.                 var head = new MinHeapNode(start, H(start, end));
35.                 OpenSet.Push(head);
36.  
37.                 while (IterationLimit > 0 && OpenSet.HasNext())
38.                 {
39.                     var currentIndex = OpenSet.Pop();
40.                     var current = OpenSet[currentIndex];
41.  
42.                     if (current.Position.Equals(end))
43.                     {
44.                         ReconstructPath(start, end);
45.                         return;
46.                     }
47.  
48.                     var initialCost = CostSoFar[GetIndex(current.Position)];
49.  
50.                     for (var i = 0; i < Neighbours.Length; i++)
51.                     {
52.                         var neigbour = Neighbours[i];
53.                         var position = current.Position + neigbour.Offset;
54.  
55.                         if (position.x < 0 || position.x >= DimX || position.y < 0 || position.y >= DimY)
56.                             continue;
57.  
58.                         var index = GetIndex(position);
59.  
60.                         var cellCost = GetCellCost(currentIndex, index, true);
61.          
62.                         if (float.IsInfinity(cellCost))
63.                             continue;
64.  
65.                         var newCost = initialCost + neigbour.Cost * cellCost;
66.                         var oldCost = CostSoFar[index];
67.  
68.                         if (!(oldCost <= 0) && !(newCost < oldCost))
69.                             continue;
70.  
71.                         CostSoFar[index] = newCost;
72.                         CameFrom[index] = current.Position;
73.  
74.                         var expectedCost = newCost + H(position, end);
75.                         OpenSet.Push(new MinHeapNode(position, expectedCost));
76.                     }
77.  
78.                     IterationLimit--;
79.                 }
80.  
81.                 // If the openset still has a next, means we ran out of iterations (and not path is unobtainable)
82.                 // So just return the best we've found so far, will finish it later
83.                 if (OpenSet.HasNext())
84.                 {
85.                     var currentIndex = OpenSet.Pop();
86.                     var current = OpenSet[currentIndex];
87.                     ReconstructPath(start, current.Position);
88.                 }
89.             }
90.  
91.             private float GetCellCost(int fromIndex, int toIndex, bool areNeighbours)
92.             {
93.                 var cell = Grid[toIndex];
94.                 if (cell.Blocked)
95.                     return float.PositiveInfinity;
96.  
97.                 // TODO HEIGHT ADJUSTMENTS ETC
98.  
99.                 return 1;
100.             }
101.  
102.             private static float H(int2 p0, int2 p1)
103.             {
104.                 var dx = p0.x - p1.x;
105.                 var dy = p0.y - p1.y;
106.                 var sqr = dx * dx + dy * dy;
107.                 return math.sqrt(sqr);
108.             }
109.  
110.             private void ReconstructPath(int2 start, int2 end)
111.             {
112.                 Waypoints.Add(end + Offset);
113.  
114.                 var current = end;
115.                 do
116.                 {
117.                     var previous = CameFrom[GetIndex(current)];
118.                     current = previous;
119.                     Waypoints.Add(current + Offset);
120.                 } while (!current.Equals(start));
121.  
122.                 Waypoints.Reverse();
123.             }
124.  
125.             private int GetIndex(int2 i)
126.             {
127.                 return i.y * DimX + i.x;
128.             }
129.         }

Simple reset between jobs as we're sharing the same Array because of memory limitations

Code (CSharp):

1.         /// <summary>
2.         ///     Job that resets our CostSoFar array and Heap, the CameFrom array does not need resetting
3.         /// </summary>
4.         [BurstCompile]
5.         private unsafe struct ResetJob : IJob
6.         {
7.             [WriteOnly] public NativeArray<float> CostSoFar;
8.             [WriteOnly] public NativeMinHeap OpenSet;
9.  
10.             public void Execute()
11.             {
12.                 var buffer = CostSoFar.GetUnsafePtr();
13.                 UnsafeUtility.MemClear(buffer, (long) CostSoFar.Length * UnsafeUtility.SizeOf<float>());
14.  
15.                 OpenSet.Clear();
16.             }
17.         }

The NativeMinHeap

Code (CSharp):

1. using System;
2. using Unity.Collections;
3. using Unity.Collections.LowLevel.Unsafe;
4. using Unity.Mathematics;
5.  
6. namespace BovineLabs.Systems.World.Pathfinding
7. {
8.     [NativeContainerSupportsDeallocateOnJobCompletion]
9.     [NativeContainerSupportsMinMaxWriteRestriction]
10.     [NativeContainer]
11.     public unsafe struct NativeMinHeap : IDisposable
12.     {
13.         [NativeDisableUnsafePtrRestriction] private void* m_Buffer;
14.         private int m_capacity;
15. #if ENABLE_UNITY_COLLECTIONS_CHECKS
16.         private AtomicSafetyHandle m_Safety;
17.         [NativeSetClassTypeToNullOnSchedule] private DisposeSentinel m_DisposeSentinel;
18. #endif
19.         private Allocator m_AllocatorLabel;
20.  
21.         private int m_head;
22.         private int m_length;
23.         private int m_MinIndex;
24.         private int m_MaxIndex;
25.  
26.         public NativeMinHeap(int capacity, Allocator allocator/*, NativeArrayOptions options = NativeArrayOptions.ClearMemory*/)
27.         {
28.             Allocate(capacity, allocator, out this);
29.             /*if ((options & NativeArrayOptions.ClearMemory) != NativeArrayOptions.ClearMemory)
30.                 return;
31.             UnsafeUtility.MemClear(m_Buffer, (long) m_capacity * UnsafeUtility.SizeOf<MinHeapNode>());*/
32.         }
33.  
34.         private static void Allocate(int capacity, Allocator allocator, out NativeMinHeap nativeMinHeap)
35.         {
36.             var size = (long) UnsafeUtility.SizeOf<MinHeapNode>() * capacity;
37.             if (allocator <= Allocator.None)
38.                 throw new ArgumentException("Allocator must be Temp, TempJob or Persistent", nameof (allocator));
39.             if (capacity < 0)
40.                 throw new ArgumentOutOfRangeException(nameof (capacity), "Length must be >= 0");
41.             if (size > int.MaxValue)
42.                 throw new ArgumentOutOfRangeException(nameof (capacity),
43.                     $"Length * sizeof(T) cannot exceed {(object) int.MaxValue} bytes");
44.  
45.             nativeMinHeap.m_Buffer = UnsafeUtility.Malloc(size, UnsafeUtility.AlignOf<MinHeapNode>(), allocator);
46.             nativeMinHeap.m_capacity = capacity;
47.             nativeMinHeap.m_AllocatorLabel = allocator;
48.             nativeMinHeap.m_MinIndex = 0;
49.             nativeMinHeap.m_MaxIndex = capacity - 1;
50.             nativeMinHeap.m_head = -1;
51.             nativeMinHeap.m_length = 0;
52.  
53. #if ENABLE_UNITY_COLLECTIONS_CHECKS
54. #if UNITY_2018_3_OR_NEWER
55.             DisposeSentinel.Create(out nativeMinHeap.m_Safety, out nativeMinHeap.m_DisposeSentinel, 1, label);
56. #else
57.             DisposeSentinel.Create(out nativeMinHeap.m_Safety, out nativeMinHeap.m_DisposeSentinel, 1);
58. #endif
59. #endif
60.  
61.  
62.         }
63.  
64.         public bool HasNext()
65.         {
66. #if ENABLE_UNITY_COLLECTIONS_CHECKS
67.             AtomicSafetyHandle.CheckReadAndThrow(m_Safety);
68. #endif
69.             return m_head >= 0;
70.         }
71.  
72.         public void Push(MinHeapNode node)
73.         {
74. #if ENABLE_UNITY_COLLECTIONS_CHECKS
75.             if (m_length == m_capacity)
76.                 throw new IndexOutOfRangeException($"Capacity Reached");
77.             AtomicSafetyHandle.CheckReadAndThrow(m_Safety);
78. #endif
79.  
80.             UnsafeUtility.WriteArrayElement(m_Buffer, m_length, node);
81.             m_length += 1;
82.  
83.             if (m_head < 0)
84.             {
85.                 m_head = m_length - 1;
86.             }
87.             else if (node.ExpectedCost < this[m_head].ExpectedCost)
88.             {
89.                 node.Next = m_head;
90.                 m_head = m_length - 1;
91.             }
92.             else
93.             {
94.                 var currentPtr = m_head;
95.                 var current = this[currentPtr];
96.  
97.                 while (current.Next >= 0 && this[current.Next].ExpectedCost <= node.ExpectedCost)
98.                 {
99.                     currentPtr = current.Next;
100.                     current = this[current.Next];
101.                 }
102.  
103.                 node.Next = current.Next;
104.                 current.Next = m_length - 1;
105.             }
106.         }
107.  
108.         public int Pop()
109.         {
110. #if ENABLE_UNITY_COLLECTIONS_CHECKS
111.             AtomicSafetyHandle.CheckWriteAndThrow(m_Safety);
112. #endif
113.             var result = m_head;
114.             m_head = this[m_head].Next;
115.             return result;
116.         }
117.  
118.         public MinHeapNode this[int index]
119.         {
120.             get
121.             {
122. #if ENABLE_UNITY_COLLECTIONS_CHECKS
123.                 if (index < m_MinIndex || index > m_MaxIndex)
124.                     FailOutOfRangeError(index);
125.                 AtomicSafetyHandle.CheckReadAndThrow(m_Safety);
126. #endif
127.    
128.                 return UnsafeUtility.ReadArrayElement<MinHeapNode>(m_Buffer, index);
129.             }
130.         }
131.  
132.         public void Clear()
133.         {
134.             m_head = -1;
135.             m_length = 0;
136.         }
137.  
138.         public void Dispose()
139.         {
140.             if (!UnsafeUtility.IsValidAllocator(m_AllocatorLabel))
141.                 throw new InvalidOperationException("The NativeArray can not be Disposed because it was not allocated with a valid allocator.");
142. #if ENABLE_UNITY_COLLECTIONS_CHECKS
143.             DisposeSentinel.Dispose(m_Safety, ref m_DisposeSentinel);
144. #endif
145.             UnsafeUtility.Free(m_Buffer, m_AllocatorLabel);
146.             m_Buffer = null;
147.             m_capacity = 0;
148.         }
149.  
150. #if ENABLE_UNITY_COLLECTIONS_CHECKS
151.         private void FailOutOfRangeError(int index)
152.         {
153.             if (index < m_capacity && (this.m_MinIndex != 0 || this.m_MaxIndex != m_capacity - 1))
154.                 throw new IndexOutOfRangeException(
155.                     $"Index {(object) index} is out of restricted IJobParallelFor range [{(object) this.m_MinIndex}...{(object) this.m_MaxIndex}] in ReadWriteBuffer.\nReadWriteBuffers are restricted to only read & write the element at the job index. You can use double buffering strategies to avoid race conditions due to reading & writing in parallel to the same elements from a job.");
156.             throw new IndexOutOfRangeException(
157.                 $"Index {(object) index} is out of range of '{(object) m_capacity}' Length.");
158.         }
159. #endif
160.     }
161.  
162.     public struct MinHeapNode
163.     {
164.         public MinHeapNode(int2 position, float expectedCost)
165.         {
166.             Position = position;
167.             ExpectedCost = expectedCost;
168.             Next = -1;
169.         }
170.  
171.         public int2 Position { get; } // TODO to position
172.         public float ExpectedCost { get; }
173.         public int Next { get; set; }
174.     }
175. }

Setting it up

Code (CSharp):

1.         protected override JobHandle OnUpdate(JobHandle inputDeps)
2.         {
3.             var jobHandles = new NativeArray<JobHandle>(_jobCollections.Length, Allocator.TempJob);
4.             for (var index = 0; index < _jobCollections.Length; index++)
5.                 jobHandles[index] = inputDeps;
6.  
7.             for (var r = 0; r < _data.Length; r++)
8.             {
9.                 var index = r % jobHandles.Length;
10.                 var data = _jobCollections[index];
11.  
12.                 var findPathJob = new FindPathJob
13.                 {
14.                     Request = _data.Request[r],
15.                     Waypoints = _data.Waypoints[r].Value,
16.                     Grid = _grid,
17.                     DimX = _size.x,
18.                     DimY = _size.y,
19.                     Offset = -_size / 2,
20.                     IterationLimit = Iterations,
21.                     Neighbours = _neighbours,
22.                     CostSoFar = data.CostSoFar,
23.                     CameFrom = data.CameFrom,
24.                     OpenSet = data.OpenSet
25.                 };
26.  
27.                 var findPathJobHandle = findPathJob.Schedule(jobHandles[index]);
28.      
29.                 var resetJob = new ResetJob
30.                 {
31.                     CostSoFar = data.CostSoFar,
32.                     OpenSet = data.OpenSet
33.                 };
34.      
35.                 jobHandles[index] = resetJob.Schedule(findPathJobHandle);
36.             }
37.  
38.             var jobHandle = JobHandle.CombineDependencies(jobHandles);
39.             jobHandles.Dispose();
40.             return jobHandle;
41.         }

I can't afford to allocate temp arrays for every path finder (my grid is currently huge 4096x4096 so it'd be gigabytes/memory) so instead I allocate 4-8 and manually schedule and reuse them between jobs. Ends up looking like this (if there were 4 workers and 6 path requests came in)

 

Instead of me using a array of grid node strucks couldi just have let's say 1000 entities with a grid node component attached for a 100x100 grid? Would this be efficient?

 

Sorry for reviving this old thread, but I didn't find anything similar and didn't want to open a new thread just for a simple question.
I'm having a hard time bringing an old (and simple) pathfinding system of mine to DOTS, your code really helped in terms of general organization.
I was just wondering how to organize the "central shared data" of the grid map: in my old work I basically had a singleton object containing a 2D matrix that could be shared for the path calculations, here I see you are passing a similar grid to the job with the ReadOnly annotation and it's reasonable, but where do you keep it stored and updated? Do I make a singleton entity with a "grid" component, or just keep it in a ad-hoc system as a sort of buffer? I don't really know how to deal with this shared information in ECS.
Thanks in advance!

 

Glad to see I am not the only one to use MS Paint for algorithm planning

 

I create an entity with a dynamic buffer of TerrainElement : IBufferElements on them. This is effectively my 2d terrain grid. I query for this in several systems, particularly pathfinding ones. TerrainElement is the category of the terrain and then I have a separate HeightElement for terrain height at a coordinate.

It's worked quite nicely for me so far. Lots of other systems need this information so in my case it didn't make sense to cache it as internal system data.

 

Cool approach, so instead of having one grid cell with all the info inside you effectively make multiple "maps" by using different buffers, am I right? It's even more decoupled, I like it

That was exactly my issue: if I cache the grid/map inside the system it becomes a mess of references to the single system.
Thanks for the advices!

 

Yep that's right. This works well for my situation as I don't always need all the data that is associated with a cell.

 

Hi tertle! Your generous sharing greatly help me figure out how to make A* with DOD. Thanks a lot! I can get it work with Hybrid ECS. But when I try to get it work with Job system, the editor said NativeMinHeap has no atomicSafeHandle embedded. Which is confusing, because your implementation already has atomicSafeHandle.

Spoiler

InvalidOperationException: PathFindingJob.Data.OpenSet uses the [NativeContainer] but has no AtomicSafetyHandle embedded, this is an internal error in the container type.

Can you give me some insight about that?

 

I haven't looked at this in months and it was based on a much older version of ecs, but i suspect all you'd need to do is remove the attributes from the heap and it'd work.

[NativeContainerSupportsDeallocateOnJobCompletion]
[NativeContainerSupportsMinMaxWriteRestriction]
[NativeContainer]

At some point they probably added more strict requirements for containers since I wrote this.

 

Thanks for your help, sorry it's my bad, I shouldn't use it to run parallel. So it works fine!

 

Sorry for necro-ing this thread, but I am currently trying to wrap my head around ECS and I am trying to implement path finding with my own set of path nodes grid. The approach presented here in this thread is to handle the path node grid data as Component Data. My question is, if it would be better or worse, to store the path nodes grid in Shared Component Data, instead of Component Data assigned to an entity. Maybe my question is entirely invalid, since I thing that I don't fully understand ECS, yet.

 

How can we finish the search later?