Search Unity

Pathfinding & ECS

Discussion in 'Data Oriented Technology Stack' started by ImmortalDax, Jul 29, 2018.

  1. ImmortalDax

    ImmortalDax

    Joined:
    Jul 29, 2018
    Posts:
    5
    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.
     
  2. X301

    X301

    Joined:
    Jan 24, 2013
    Posts:
    97
    Last edited: Jul 30, 2018
    ImmortalDax likes this.
  3. X301

    X301

    Joined:
    Jan 24, 2013
    Posts:
    97
    You could also use Hybrid ECS and use unitys pathfinding system. Here is a link to brackeys tutoral on YouTube.
     
    Tony_Max and ImmortalDax like this.
  4. eizenhorn

    eizenhorn

    Joined:
    Oct 17, 2016
    Posts:
    1,366
    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
     
    Last edited: Jul 31, 2018
    ImmortalDax likes this.
  5. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    1,558
    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)

    upload_2018-7-31_18-44-20.png
     
    Last edited: Jul 31, 2018
  6. X301

    X301

    Joined:
    Jan 24, 2013
    Posts:
    97
    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?
     
    ImmortalDax likes this.
  7. edoarn

    edoarn

    Joined:
    Feb 8, 2014
    Posts:
    10
    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!
     
  8. starikcetin

    starikcetin

    Joined:
    Dec 7, 2017
    Posts:
    225
    Glad to see I am not the only one to use MS Paint for algorithm planning :)
     
  9. jdtec

    jdtec

    Joined:
    Oct 25, 2017
    Posts:
    74
    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.
     
  10. edoarn

    edoarn

    Joined:
    Feb 8, 2014
    Posts:
    10
    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!
     
  11. jdtec

    jdtec

    Joined:
    Oct 25, 2017
    Posts:
    74
    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.
     
  12. eterlan

    eterlan

    Joined:
    Sep 29, 2018
    Posts:
    54
    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.
    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?:p
     
  13. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    1,558
    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.
     
  14. eterlan

    eterlan

    Joined:
    Sep 29, 2018
    Posts:
    54
    Thanks for your help, sorry it's my bad, I shouldn't use it to run parallel. So it works fine!