Search Unity

A* 2D Grid Pure ECS JOB/Burst Pathfinding

Discussion in 'Data Oriented Technology Stack' started by Omniaffix-Dave, Aug 8, 2019.

  1. Omniaffix-Dave

    Omniaffix-Dave

    Joined:
    Jan 11, 2019
    Posts:
    4
    **EDIT Here is an update on progress. I am moving it to the top for visibility

    Optimization and cleanup may still be needed, please feel free to contribute.



    Any input, feedback, problems or recommendations is always appreciated.

    This was created strongly using examples from @tertle pathfinding that he shared to the forums, converted to IJobChunk. Thank you again, for your help.

    https://github.com/Omniaffix-Dave/Unity-2D-Pathfinding-Grid-ECS-Job

    Initializer for testing
    Code (CSharp):
    1.  
    2. namespace Pathfinding
    3. {
    4.     public class InitializePathfinding : MonoBehaviour
    5.     {
    6.         //Options
    7.         public int2 size;
    8.         public bool showGrid;
    9.         public bool showPaths;
    10.         public bool canMoveDiag;
    11.         public Color pathColor;
    12.  
    13.         //Manual Path
    14.         [HideInInspector] public Vector2Int start;
    15.         [HideInInspector] public Vector2Int end;
    16.         [HideInInspector] public bool searchManualPath;
    17.  
    18.  
    19.         //Random Path
    20.         [HideInInspector] public int numOfRandomPaths;
    21.         [HideInInspector] public bool searchRandomPaths;
    22.  
    23.         //Manual blocked
    24.         List<int2> blockedNodes = new List<int2>();
    25.         [HideInInspector] public Vector2Int blockedNode;
    26.         [HideInInspector] public bool addManualBlockedNode;
    27.  
    28.         //Random blocked
    29.         [HideInInspector] public int numbOfRandomBlockedNodes = 1;
    30.         [HideInInspector] public bool addRandomBlockedNode;
    31.  
    32.         int previousSize; // Prevent GUI Errors
    33.  
    34.         private void Awake()
    35.         {
    36.             World.Active.GetExistingSystem<PathfindingSystem>().canMoveDiag = canMoveDiag;
    37.             CreateGrid();
    38.         }
    39.  
    40.         private void Update()
    41.         {
    42.             if(size.x * size.y != previousSize)
    43.             {
    44.                 CreateGrid();
    45.             }
    46.  
    47.             if(addManualBlockedNode)
    48.             {
    49.                 blockedNodes.Add(new int2(blockedNode.x, blockedNode.y));
    50.                 addManualBlockedNode = false;
    51.                 CreateGrid();
    52.             }
    53.  
    54.             if(searchManualPath)
    55.             {
    56.                 CreateSearcher(new int2(start.x, start.y), new int2(end.x, end.y));
    57.                 searchManualPath = false;
    58.             }
    59.  
    60.             if (addRandomBlockedNode)
    61.             {
    62.                 addRandomBlockedNode = false;
    63.                 CreateBlockedNodes();
    64.             }
    65.  
    66.             if(searchRandomPaths)
    67.             {
    68.                 searchRandomPaths = false;
    69.  
    70.                 for (int i = 0; i < numOfRandomPaths; i++)
    71.                 {
    72.                     CreateSearcher(new int2(Random.Range(0, size.x), Random.Range(0, size.y)), new int2(Random.Range(0, size.x), Random.Range(0, size.y)));
    73.                 }
    74.             }
    75.         }
    76.  
    77.         public void CreateBlockedNodes()
    78.         {
    79.             EntityManager entityManager = World.Active.EntityManager;
    80.             var cells = RequiredExtensions.cells;
    81.  
    82.             for (int i = 0; i < numbOfRandomBlockedNodes; i++)
    83.             {
    84.                 int randomCell = Random.Range(0, size.x * size.y);
    85.  
    86.                 cells[randomCell] = new Cell { blocked = Convert.ToByte(true), Height = 0 };
    87.             }
    88.         }
    89.  
    90.         public void CreateSearcher(int2 s, int2 e)
    91.         {
    92.             EntityManager entityManager = World.Active.EntityManager;
    93.             var pathSearcher = entityManager.CreateEntity(typeof(PathRequest), typeof(Translation), typeof(NavigationCapabilities));
    94.             var trans = entityManager.GetComponentData<Translation>(pathSearcher);
    95.             trans.Value = new float3(s.x, s.y, 0);
    96.             entityManager.SetComponentData<Translation>(pathSearcher, trans);
    97.      
    98.             entityManager.AddBuffer<Waypoint>(pathSearcher);
    99.             PathRequest pathRequest = new PathRequest
    100.             {
    101.                 Entity = pathSearcher,
    102.                 start = s,
    103.                 end = e,
    104.                 Destination = NodeToWorldPosition(e),
    105.                 NavigateToBestIfIncomplete = true,
    106.                 NavigateToNearestIfBlocked = true
    107.             };
    108.  
    109.             entityManager.SetComponentData(pathSearcher, pathRequest);
    110.         }
    111.  
    112.         private void OnDisable()
    113.         {
    114.             RequiredExtensions.cells.Dispose();
    115.         }
    116.  
    117.         public void CreateGrid()
    118.         {
    119.             if(RequiredExtensions.cells.IsCreated)
    120.                 RequiredExtensions.cells.Dispose();
    121.             RequiredExtensions.cells = new Unity.Collections.NativeArray<Cell>(size.x * size.y, Unity.Collections.Allocator.Persistent);
    122.  
    123.             previousSize = size.x * size.y;
    124.  
    125.             for (int y = 0; y < size.y; y++)
    126.             {
    127.                 for (int x = 0; x < size.x; x++)
    128.                 {
    129.                     Cell cell = new Cell
    130.                     {
    131.                         blocked = Convert.ToByte(blockedNodes.Contains(new int2(x, y)))
    132.                     };
    133.                     RequiredExtensions.cells[GetIndex(new int2(x, y))] = cell;
    134.                 }
    135.             }
    136.             World.Active.GetExistingSystem<PathfindingSystem>().worldSize = size;
    137.         }
    138.  
    139.         void OnDrawGizmos()
    140.         {
    141.             if (!showGrid && !showPaths) return;
    142.  
    143.             if (Application.isPlaying)
    144.             {
    145.                 if (showGrid && size.x * size.y == previousSize)
    146.                 {
    147.                     var cells = RequiredExtensions.cells;
    148.  
    149.                     for (int x = 0; x < size.x; x++)
    150.                     {
    151.                         for (int y = 0; y < size.y; y++)
    152.                         {
    153.                             Gizmos.color = cells[GetIndex(new int2(x, y))].Blocked ? Color.grey : Color.white;
    154.                             Gizmos.DrawCube(NodeToWorldPosition(new int2(x, y)), new Vector3(.90f, .90f));
    155.                         }
    156.                     }
    157.                 }
    158.  
    159.                 if (showPaths)
    160.                 {
    161.                     EntityManager entityManager = World.Active.EntityManager;
    162.                     var query = entityManager.CreateEntityQuery(ComponentType.ReadOnly<Waypoint>());
    163.                     if (query.CalculateEntityCount() > 0)
    164.                     {
    165.                         var actualGroup = query.ToEntityArray(Unity.Collections.Allocator.TempJob);
    166.  
    167.                         foreach (Entity entity in actualGroup)
    168.                         {
    169.                             var buffer = entityManager.GetBuffer<Waypoint>(entity);
    170.  
    171.                             if (buffer.Length > 0)
    172.                             {
    173.                                 Gizmos.color = pathColor;
    174.  
    175.                                 for (int i = 0; i < buffer.Length - 1; i++)
    176.                                 {
    177.                                     Gizmos.DrawLine(buffer[i].waypoints - .5f, buffer[i + 1].waypoints - .5f);
    178.                                 }
    179.                             }
    180.                         }
    181.                         actualGroup.Dispose();
    182.                     }
    183.                 }        
    184.             }                
    185.         }
    186.  
    187.         public float3 NodeToWorldPosition(int2 i) => new float3(i.x, i.y, 0);
    188.  
    189.         int GetIndex(int2 i)
    190.         {
    191.             if (size.y >= size.x)
    192.                 return (i.x * size.y) + i.y;
    193.             else
    194.                 return (i.y * size.x) + i.x;
    195.         }
    196.     }
    197. }
    198.  
    Pathfinding Job
    Code (CSharp):
    1.  
    2. namespace Pathfinding
    3. {
    4.     public class PathfindingSystem : JobComponentSystem
    5.     {
    6.         NativeArray<Neighbour> neighbours;
    7.         EntityQuery pathRequests;
    8.  
    9.         const int IterationLimit = 1000;
    10.         public int2 worldSize;
    11.  
    12.         public bool canMoveDiag;
    13.  
    14.         protected override void OnCreate()
    15.         {
    16.             pathRequests = GetEntityQuery(typeof(Waypoint), ComponentType.ReadOnly<PathRequest>(), ComponentType.ReadOnly<Translation>(), ComponentType.ReadOnly<NavigationCapabilities>());
    17.             pathRequests.SetFilterChanged(typeof(PathRequest));
    18.  
    19.             if (canMoveDiag)
    20.             {
    21.                 neighbours = new NativeArray<Neighbour>(8, Allocator.Persistent)
    22.                 {
    23.                     [0] = new Neighbour(-1, -1), // Bottom left
    24.                     [1] = new Neighbour(0, -1), // Bottom
    25.                     [2] = new Neighbour(1, -1), // Bottom Right
    26.                     [3] = new Neighbour(-1, 0), // Left
    27.                     [4] = new Neighbour(1, 0), // Right
    28.                     [5] = new Neighbour(-1, 1), // Top Left
    29.                     [6] = new Neighbour(0, 1), // Top
    30.                     [7] = new Neighbour(1, 1), // Top Right
    31.                 };
    32.             }
    33.             else
    34.             {
    35.                 neighbours = new NativeArray<Neighbour>(4, Allocator.Persistent)
    36.                 {
    37.                     [0] = new Neighbour(0, -1), // Bottom
    38.                     [1] = new Neighbour(-1, 0), // Left
    39.                     [2] = new Neighbour(1, 0), // Right
    40.                     [3] = new Neighbour(0, 1), // Top
    41.                 };
    42.             }
    43.         }
    44.  
    45.         protected override void OnDestroy()
    46.         {
    47.             neighbours.Dispose();
    48.         }
    49.  
    50.         protected override JobHandle OnUpdate(JobHandle inputDeps)
    51.         {
    52.             int numberOfRequests = pathRequests.CalculateChunkCount();
    53.             if (numberOfRequests == 0) return inputDeps;
    54.  
    55.             //Schedule the findPath to build <Waypoints> Job
    56.             FindPathJobChunk findPathJob = new FindPathJobChunk()
    57.             {
    58.                 WaypointChunkBuffer = GetArchetypeChunkBufferType<Waypoint>(false),
    59.                 PathRequestsChunkComponent = GetArchetypeChunkComponentType<PathRequest>(true),
    60.                 CellArray = RequiredExtensions.cells,
    61.                 TranslationsChunkComponent = GetArchetypeChunkComponentType<Translation>(true),
    62.                 NavigationCapabilitiesChunkComponent = GetArchetypeChunkComponentType<NavigationCapabilities>(true),
    63.                 Neighbors = neighbours,
    64.                 DimY = worldSize.y,
    65.                 DimX = worldSize.x,
    66.                 Iterations = IterationLimit,
    67.                 NeighborCount = neighbours.Length
    68.             };
    69.             JobHandle jobHandle = findPathJob.Schedule(pathRequests, inputDeps);
    70.  
    71.             return jobHandle;
    72.         }
    73.  
    74.         [BurstCompile]
    75.         struct FindPathJobChunk : IJobChunk
    76.         {
    77.             [ReadOnly] public int DimX;
    78.             [ReadOnly] public int DimY;
    79.             [ReadOnly] public int Iterations;
    80.             [ReadOnly] public int NeighborCount;
    81.             [ReadOnly] public NativeArray<Cell> CellArray;
    82.             [WriteOnly] public ArchetypeChunkBufferType<Waypoint> WaypointChunkBuffer;
    83.             [ReadOnly] public ArchetypeChunkComponentType<PathRequest> PathRequestsChunkComponent;
    84.             [ReadOnly] public NativeArray<Neighbour> Neighbors;
    85.             [ReadOnly] public ArchetypeChunkComponentType<Translation> TranslationsChunkComponent;
    86.             [ReadOnly] public ArchetypeChunkComponentType<NavigationCapabilities> NavigationCapabilitiesChunkComponent;
    87.  
    88.             public void Execute(ArchetypeChunk chunk, int chunkIndex, int firstEntityIndex)
    89.             {
    90.                 int size = DimX * DimY;
    91.                 BufferAccessor<Waypoint> Waypoints = chunk.GetBufferAccessor(WaypointChunkBuffer);
    92.                 NativeArray<PathRequest> PathRequests = chunk.GetNativeArray(PathRequestsChunkComponent);
    93.                 NativeArray<Translation> Translations = chunk.GetNativeArray(TranslationsChunkComponent);
    94.                 NativeArray<NavigationCapabilities> NavigationCapabilities = chunk.GetNativeArray(NavigationCapabilitiesChunkComponent);
    95.                 NativeArray<float> CostSoFar = new NativeArray<float>(size * chunk.Count, Allocator.Temp);
    96.                 NativeArray<int2> CameFrom = new NativeArray<int2>(size * chunk.Count, Allocator.Temp);
    97.                 NativeMinHeap OpenSet = new NativeMinHeap((Iterations + 1) * Neighbors.Length * chunk.Count, Allocator.Temp);
    98.  
    99.                 for (int i = chunkIndex; i < chunk.Count; i++)
    100.                 {
    101.                     NativeSlice<float> costSoFar = CostSoFar.Slice(i * size, size);
    102.                     NativeSlice<int2> cameFrom = CameFrom.Slice(i * size, size);
    103.  
    104.                     int openSetSize = (Iterations + 1) * NeighborCount;
    105.                     NativeMinHeap openSet = OpenSet.Slice(i * openSetSize, openSetSize);
    106.                     PathRequest request = PathRequests[i];
    107.  
    108.                     Translation currentPosition = Translations[i];
    109.                     NavigationCapabilities capability = NavigationCapabilities[i];
    110.  
    111.                     // cache these as they're used a lot
    112.                     int2 start = currentPosition.Value.xy.FloorToInt();
    113.                     int2 goal = request.end;
    114.  
    115.                     DynamicBuffer<float3> waypoints = Waypoints[i].Reinterpret<float3>();
    116.                     waypoints.Clear();
    117.  
    118.                     // Special case when the start is the same point as the goal
    119.                     if (start.Equals(goal))
    120.                     {
    121.                         // We just set the destination as the goal, but need to get the correct height
    122.                         int gridIndex = this.GetIndex(goal);
    123.                         Cell cell = CellArray[gridIndex];
    124.                         float3 point = new float3(request.Destination.x, request.Destination.y, cell.Height);
    125.                         waypoints.Add(point);
    126.                         continue;
    127.                     }
    128.  
    129.                     var stash = new InstanceStash
    130.                     {
    131.                         Grid = CellArray,
    132.                         CameFrom = cameFrom,
    133.                         CostSoFar = costSoFar,
    134.                         OpenSet = openSet,
    135.                         Request = request,
    136.                         Capability = capability,
    137.                         CurrentPosition = currentPosition,
    138.                         Start = start,
    139.                         Goal = goal,
    140.                         Waypoints = waypoints,
    141.                     };
    142.  
    143.                     if (this.ProcessPath(ref stash))
    144.                         this.ReconstructPath(stash);
    145.                 }
    146.                 CostSoFar.Dispose();
    147.                 CameFrom.Dispose();
    148.                 OpenSet.Dispose();
    149.             }
    150.  
    151.             static float H(float2 p0, float2 p1)
    152.             {
    153.                 float dx = p0.x - p1.x;
    154.                 float dy = p0.y - p1.y;
    155.                 float sqr = (dx * dx) + (dy * dy);
    156.                 return math.sqrt(sqr);
    157.             }
    158.  
    159.             bool ProcessPath(ref InstanceStash stash)
    160.             {
    161.                 // Push the start to NativeMinHeap openSet
    162.                 float hh = H(stash.Start, stash.Goal);
    163.                 MinHeapNode head = new MinHeapNode(stash.Start, hh, hh);
    164.                 stash.OpenSet.Push(head);
    165.  
    166.                 int iterations = this.Iterations;
    167.  
    168.                 MinHeapNode closest = head;
    169.  
    170.                 // While we still have potential nodes to explore
    171.                 while (stash.OpenSet.HasNext())
    172.                 {
    173.                     MinHeapNode current = stash.OpenSet.Pop();
    174.  
    175.                     if (current.DistanceToGoal < closest.DistanceToGoal)
    176.                         closest = current;
    177.                     // Found our goal
    178.                     if (current.Position.Equals(stash.Goal))
    179.                         return true;
    180.  
    181.                     // Path might still be obtainable but we've run out of allowed iterations
    182.                     if (iterations == 0)
    183.                     {
    184.                         if (stash.Request.NavigateToBestIfIncomplete)
    185.                         {
    186.                             // Return the best result we've found so far
    187.                             // Need to update goal so we can reconstruct the shorter path
    188.                             stash.Goal = closest.Position;
    189.                             return true;
    190.                         }
    191.                         return false;
    192.                     }
    193.                     iterations--;
    194.  
    195.                     var initialCost = stash.CostSoFar[this.GetIndex(current.Position)];
    196.                     var fromIndex = this.GetIndex(current.Position);
    197.  
    198.                     // Loop our potential cells - generally neighbours but could include portals
    199.                     for (var i = 0; i < this.Neighbors.Length; i++)
    200.                     {
    201.                         var neighbour = this.Neighbors[i];
    202.                         var position = current.Position + neighbour.Offset;
    203.  
    204.                         // Make sure the node isn't outside our grid
    205.                         if (position.x < 0 || position.x >= this.DimX || position.y < 0 || position.y >= this.DimY)
    206.                             continue;
    207.  
    208.                         var index = this.GetIndex(position);
    209.  
    210.                         // Get the cost of going to this cell
    211.                         var cellCost = this.GetCellCost(stash.Grid, stash.Capability, fromIndex, index, neighbour, true);
    212.  
    213.                         // Infinity means the cell is un-walkable, skip it
    214.                         if (float.IsInfinity(cellCost))
    215.                             continue;
    216.  
    217.                         var newCost = initialCost + (neighbour.Distance * cellCost);
    218.                         var oldCost = stash.CostSoFar[index];
    219.  
    220.                         // If we've explored this cell before and it was a better path, ignore this route
    221.                         if (!(oldCost <= 0) && !(newCost < oldCost))
    222.                             continue;
    223.  
    224.                         // Update the costing and best path
    225.                         stash.CostSoFar[index] = newCost;
    226.                         stash.CameFrom[index] = current.Position;
    227.  
    228.                         // Push the node onto our heap
    229.                         var h = H(position, stash.Goal);
    230.                         var expectedCost = newCost + h;
    231.                         stash.OpenSet.Push(new MinHeapNode(position, expectedCost, h));
    232.                     }
    233.                 }
    234.  
    235.                 if (stash.Request.NavigateToNearestIfBlocked)
    236.                 {
    237.                     stash.Goal = closest.Position;
    238.                     return true;
    239.                 }
    240.  
    241.                 // All routes have been explored without finding a route to destination
    242.                 return false;
    243.             }
    244.  
    245.             void ReconstructPath(InstanceStash stash)
    246.             {
    247.                 var current = stash.CameFrom[this.GetIndex(stash.Goal)];
    248.  
    249.                 var from = this.GetPosition(stash.Grid, current);
    250.  
    251.                 stash.Waypoints.Add(from);
    252.  
    253.                 var next = this.GetPosition(stash.Grid, current);
    254.  
    255.                 while (!current.Equals(stash.Start))
    256.                 {
    257.                     current = stash.CameFrom[this.GetIndex(current)];
    258.                     var tmp = next;
    259.                     next = this.GetPosition(stash.Grid, current);
    260.  
    261.                     if (!this.IsWalkable(stash.Grid, from.xy, next.xy))
    262.                     {
    263.                         // skip
    264.                         stash.Waypoints.Add(tmp);
    265.                         from = tmp;
    266.                     }
    267.                 }
    268.  
    269.                 stash.Waypoints.Reverse();
    270.  
    271.                 stash.Request.fufilled = true;
    272.             }
    273.  
    274.             bool IsWalkable(NativeArray<Cell> buffer, float2 from, float2 to)
    275.             {
    276.                 const float step = 0.25f;
    277.  
    278.                 var vector = to - from;
    279.                 var length = math.length(vector);
    280.                 var unit = vector / length;
    281.                 var iterations = length / step;
    282.                 var currentCell = buffer[this.GetIndex(from.FloorToInt())];
    283.  
    284.                 for (var i = 0; i < iterations; i++)
    285.                 {
    286.                     var point = (i * step * unit) + from;
    287.  
    288.                     var index = this.GetIndex(point.FloorToInt());
    289.                     var cell = buffer[index];
    290.                     if (cell.Blocked)
    291.                         return false;
    292.  
    293.                     if (cell.Height != currentCell.Height)
    294.                         return false;
    295.                 }
    296.                 return true;
    297.             }
    298.  
    299.             float GetCellCost(NativeArray<Cell> grid, NavigationCapabilities capabilities, int fromIndex, int toIndex, Neighbour neighbour, bool areNeighbours)
    300.             {
    301.                 var target = grid[toIndex];
    302.                 if (target.Blocked)
    303.                     return float.PositiveInfinity;
    304.  
    305.                 // If we're not neighbours, then we're a portal and can just go straight there
    306.                 if (!areNeighbours)
    307.                     return 1;
    308.  
    309.                 var from = grid[fromIndex];
    310.  
    311.                 var heightDiff = target.Height - from.Height;
    312.                 var absDiff = math.abs(heightDiff);
    313.  
    314.                 // TODO Should precompute this
    315.                 var dropHeight = 0;
    316.                 var climbHeight = 0;
    317.  
    318.                 if (heightDiff > 0)
    319.                     climbHeight = absDiff;
    320.                 else
    321.                     dropHeight = absDiff;
    322.  
    323.                 var slope = math.degrees(math.atan(absDiff / neighbour.Distance));
    324.  
    325.                 // TODO End precompute
    326.                 if ((capabilities.MaxClimbHeight < climbHeight || capabilities.MaxDropHeight < dropHeight) &&
    327.                     capabilities.MaxSlopeAngle < slope)
    328.                     return float.PositiveInfinity;
    329.  
    330.                 return 1;
    331.             }
    332.  
    333.             float3 GetPosition(NativeArray<Cell> grid, int2 point)
    334.             {
    335.                 var index = this.GetIndex(point);
    336.                 var cell = grid[index];
    337.                 var fPoint = point + new float2(0.5f, 0.5f);
    338.                 return new float3(fPoint.x, fPoint.y, cell.Height);
    339.             }
    340.  
    341.             int GetIndex(int2 i)
    342.             {
    343.                 if (DimY >= DimX)
    344.                     return (i.x * DimY) + i.y;
    345.                 else
    346.                     return (i.y * DimX) + i.x;
    347.             }
    348.  
    349.             struct InstanceStash
    350.             {
    351.                 public Translation CurrentPosition;
    352.                 public PathRequest Request;
    353.                 public NavigationCapabilities Capability;
    354.                 public DynamicBuffer<float3> Waypoints;
    355.  
    356.                 public int2 Start;
    357.                 public int2 Goal;
    358.  
    359.                 public NativeArray<Cell> Grid;
    360.  
    361.                 public NativeSlice<float> CostSoFar;
    362.                 public NativeSlice<int2> CameFrom;
    363.                 public NativeMinHeap OpenSet;
    364.             }
    365.         }
    366.     }
    367. }
    368.  

    --- Old Original question starts here ---
    Greetings all, I have recently started researching and moving my project to ECS for performance and organization reasons, and have really had an enjoyable time. The performance boost is just insane, and it feels like an entirely different level of complexity in programming.

    I normally shy away from asking forum questions and help in general, as I think most resources are out there on subjects and the answers can be found with enough searching... but in this particular scenario I have struggled to find what I think I need.

    I have searched through numerous sites and forum posts to try to find a close enough example to reference for use in my own project, but have fallen short as I feel like people are taking the easy way out, or maybe I am just over-complicating things. I am still newer to complex programming, so its very possible that the later is the case.

    A few months ago when I started I originally wanted a simple solution to pathfinding because I knew it was more advanced than I was ready for, so I started with using arongranberg's A* pathfinding project. This allowed me to simply set a grid size, flip a few Boolean's, and rotate 90 degrees and I could toss a few scripts on Game Objects and I had resolved the problem for the time being. Later on I researched and built my own system, but never put it in place because I knew performance wouldn't be as good, and I wanted to make the leap to ECS anyway.

    I am now trying to create a solution in Pure ECS for 2d grid based A* pathfinding, and I have a few questions about what I have found so far. First I was wondering what the current best standard likely is for this scenario if there is one. I have seen many people posts with people taking their already in place NavMesh systems or other Pathfinding and converting portions of it to ECS, while still keeping the core content on the Game Objects in the Scene. The large majority of posts on any subject has been 3D, but not a lot on 2D, which I assume is because its much easier dealing with 2D grid, so less questions. In my case overall I am aiming for an almost zero Game Object approach. From the start I choose 2D thinking its the easy way out and the best way to start learning, but I feel cheated on the amount of compatibly unity provides, or the difficulty to make 2D compatible.

    I have considered the following and would like to know the best option...

    1. Create a system where each node is Essentially an Entity holding the ComponentData that I may normally have in a node struct.
    2. Create a single Entity buffer and attempt to keep all nodes in that entity.
    3. Use a NativeHashMap to search through entities (Obstacles or Blocked paths) that actually exist in quadrants and just avoid them by offsetting transforms (Doesn't seem like its going to go well)
    4. Use NavMeshPlus to use the built in systems converted to work for 2D, have a hybrid ECS approach, and have to keep all entities in sync with game objects (My least favorite and likely easiest?)

    I have looked at the three following forum posts along with others, and they have helped me gather some concepts of what I am supposed to do, but I am also a little hesitant to dive into them because I see the "Unsafe" word getting tossed around a lot, and I am a little worried about production with this.
    https://forum.unity.com/threads/100-000-entities-traversing-navmesh.534526/ (3D using Navmesh)
    https://forum.unity.com/threads/pathfinding-ecs.542882/
    https://forum.unity.com/threads/ecs...edback-on-how-to-improve.591523/#post-3961198 (Using Entites as Nodes, also using much more than needed)
    Along with many comments in other posts by @tertle, @jdtec, @Antypodish, @zulfajuniadi
    These guys have been a really great help and its amazing to see the support they provide publicly for others.
    I have also seen a few external sites, but I am not sure the policy on posting those, so I will hold off on that.
    -Dave
     
    Last edited: Aug 14, 2019
    SiriusRU, jdtec and Opeth001 like this.
  2. xVergilx

    xVergilx

    Joined:
    Dec 22, 2014
    Posts:
    1,875
    If you're using A* Pathfinding Project Pro, you should look into beta version.
    It has an RVO pathfinding system that is burst compatible (Look into LightweightRVO example and SimulatorBurst).

    Meaning that with some extra integration flavor, you can link entities to the RVO system.
    This will allow you to scale up to at least 5k entities pathfinding (or much more with ECS / Burst) on a proper nav mesh (recast mesh).

    Or you can wait for it. I think it will be available sooner or later as a feature.
     
  3. jdtec

    jdtec

    Joined:
    Oct 25, 2017
    Posts:
    77
    I went with
    I'm not sure about using entities as nodes. I've gone with dynamic buffers that I cast to NativeArrays and store indices for neighbours and open/close lists.

    However I wouldn't necessarily suggest my approach is the best for everyone. I'm using a hybrid pathfinding method including:
    • A* on the map grid as an offline process to create my own HPA* (hierarchical pathfinding A*) navmesh
    • A* within an individual HPA* sector of the map grid (for local sector searches for temporary HPA nodes)
    • Flow field tiles through each HPA* sector

    Further reading on HPA* https://harablog.files.wordpress.com/2009/06/beyondastar.pdf

    I've written all the systems for this because I'm interested in learning, having more control of the code and want to be a bit independent of Unity for key sim/gameplay systems that I may want to port to another engine in the future.

    It's quite hard to give a definitive answer because it really depends on what the project is. It can be good to decide what high level goals are important about whatever you are developing and narrow down the solutions from there. Questions such as: Why not pick one of the hand made solutions? Does it have to be pure ECS? Do you care about learning or do you want to make something as quick as possible? etc
     
    Omniaffix-Dave likes this.
  4. Omniaffix-Dave

    Omniaffix-Dave

    Joined:
    Jan 11, 2019
    Posts:
    4
    Thank you for that link @jdtec as I said I am very new to the pathfinding world, and honestly newer to development overall. The one thing that seemed to strike me as odd while I was researching how the different current pathfinding algorithms worked currently was how horribly optimized it feels even the most common pathfinding systems are. I understand there are always memory constraints, but it seemed odd to me that A* has to search neighbors heading the complete wrong direction, just to ensure that things are done in the right order by the algorithm we are iterating through. I started immediately trying to come up with other solutions because I hatted the idea of settling with the most commonly used because everyone else is doing it and the resources are out there.

    In the end I decided I need to crawl before I can walk, so I want to start rather basic using A* without optimization and try to work it into a pure ECS system, then go from there. In the future I really want to think on other concepts myself, I don't see why there can't be a way to ask the Obstacle we run into along our path what it's size is, and have it tell us the best direction to go based on a given point, instead of asking 50 neighboring nodes are you any better off than what I currently have to get around this thing.

    I understand not being able to answer fully without reference to the project, at the moment it is an RTS style TD, with hopes to branch out to something bigger. I don't think it has to be pure ECS, but as you mentioned for me its currently about solving this current task, while hopefully learning more so the next task is a little easier.

    From what I have gathered so far from the Unity Discord chat I have been in, it sounds like I was on the wrong path overall. I have had two different recommendations that I now am a little more understanding about.

    1. Use a persistent 1D NativeArray that I will create when the level is building. This will contain all of my Node structs. When an Entity needs a path we give it a ComponentData "RequestPath" or something, and have a IJobForEach setup to iterate through these, request a path from a method say "FindPath". This removes the RequestPath component, and adds a HasPath component that another system uses to navigate. When a change is made to the map (shouldn't happen often?) I remove all HasPath from all Entities, and the cycle runs again.
    2. Same NativeArray (nodes) holding the Node structs. A second NativeArray (entitiesRequestingPath) that will take Entity ID's that need a path. A job that will iterate through this array and provide the entity with the path it needs, then remove it from the entitiesRequestingPath. *This is to reduce garbage from adding and removing components.
    I still have work to do on researching before I choose a solution, but does it sound like this is the correct pseudo path?
     
  5. jdtec

    jdtec

    Joined:
    Oct 25, 2017
    Posts:
    77
    If a unit had to move towards a direct goal through a series of small-medium sized rock objects no bigger than say 3-5x the unit size then you could probably come up with a basic routine to path around them locally probably in a sub-optimal way. However, as soon as you have more complex maps with maze like structures where you might need to double back on yourself to avoid getting stuck in a local dead-end a complete pathfinding solution, such as A*, becomes required. A local obstacle in a complex maze can’t tell you which way to go if the path ahead to the final goal hasn’t been completely discovered.

    Bear in mind you can alter A*. See https://takinginitiative.wordpress.com/2011/05/02/optimizing-the-a-algorithm/ where an overestimated heuristic is used to find a direct path goal faster, although as he points out it might not return the optimal path in certain situations.

    Standard A* (no overestimating heuristic) always provides the optimal pathing solution. To achieve that it may search lots of neighbours.

    If you were pathing across a ClashRoyale style map with a river and 2 bridges (although some might not even consider this pathfinding) you could probably make do with simply having bridge/tower as direct movement destinations and then some local avoidance (such as boids) to handle interaction with other units.

    Your pseudo code description sounds ok. I found the devil was in the details with regard to implementing the algorithm with DOTs.

    Your idea of starting small and implementing basic A* first was a good idea. Pathfinding and group movement in RTS games can be quite difficult so starting basic and getting small modular bits working step by step with visual debugging should help.
     
    Omniaffix-Dave likes this.
  6. Omniaffix-Dave

    Omniaffix-Dave

    Joined:
    Jan 11, 2019
    Posts:
    4
    Fixed all bugs that I encountered.

    Still could be optimized better, but at this point I am able to use it for my own project.

    Please feel free to contribute.
     
    foxnne likes this.