Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

ECS Grid2D Pathfinding Example and feedback on how to improve

Discussion in 'Entity Component System' started by Filtiarn_, Dec 2, 2018.

  1. Filtiarn_

    Filtiarn_

    Joined:
    Jan 24, 2013
    Posts:
    173
    Edit: Right now there is a error pathfinding if are grid dimensions is not equal to max grid dimensions. Will Fix

    Edit 2 : Edit 1 has been fixed.

    I have been working on 2D pathfinding in ECS for turn based games such as 2D Fire emblem and Advanced Wars. Some feedback would be nice. Not sure how to jobify it since I use Grid2DExpansion as a class as a link list to keep track of expanding to grid nodes so I can recreate path.

    Here is a link to the Github Repo https://github.com/nickkorta/Unity_ECSGrid2D-Pathfinding

    -Bootstrap takes care of creating grid and updating path
    Code (CSharp):
    1. public class Bootstrap : MonoBehaviour
    2. {
    3.     public TextAsset gridDataTextAsset;
    4.     public float3 gridWorldPosition;
    5.     public int2 pathStartIndex;
    6.     public int2 pathEndIndex;
    7.     public byte isEightConnections;
    8.     public bool requestPath = true;
    9.  
    10.     private bool isTestGridLoaded;
    11.     private string pathId;
    12.  
    13.     void Start()
    14.     {
    15.         var entityManager = Unity.Entities.World.Active.GetOrCreateManager<EntityManager>();
    16.  
    17.         //Create Grid
    18.         var grid2DEntity = entityManager.CreateEntity(typeof(Grid2D));
    19.         entityManager.SetComponentData<Grid2D>(grid2DEntity, new Grid2D() { dimensions = new int2(10, 10), maxDimensions = new int2(10, 10) });
    20.     }
    21.  
    22.     public void Update()
    23.     {
    24.         if (!Grid2DUtilites.IsGrid2DInitalized())
    25.             return;
    26.  
    27.         //Modify Grid to test
    28.         if (!isTestGridLoaded)
    29.         {
    30.             isTestGridLoaded = true;
    31.             Grid2DUtilites.CreateGrid(gridDataTextAsset.text);
    32.         }
    33.  
    34.         //Clamp
    35.         pathStartIndex = math.clamp(pathStartIndex, new int2(0, 0), Grid2DUtilites.Grid2D.dimensions);
    36.         pathEndIndex = math.clamp(pathEndIndex, new int2(0, 0), Grid2DUtilites.Grid2D.dimensions);
    37.  
    38.         //Request Path
    39.         if (requestPath)
    40.         {
    41.             requestPath = false;
    42.             Grid2DUtilites.RequestPath(pathStartIndex, pathEndIndex, OnCompletePath, isEightConnections);
    43.         }
    44.  
    45.         //Set Grid Position
    46.         Grid2DUtilites.SetGrid2DWorldPosition(gridWorldPosition);
    47.     }
    48.  
    49.     void OnDrawGizmos()
    50.     {
    51.         Grid2DUtilites.OnDrawGizmosGrid();
    52.         Grid2DUtilites.OnDrawGizmosPath(pathId);
    53.     }
    54.  
    55.     private void OnCompletePath(string pathId)
    56.     {
    57.         this.pathId = pathId;
    58.     }
    59. }
    60.  
    -Grid can be generated from a text file
    Code (CSharp):
    1. 10,10
    2. 0,0,0,1,0,0,0,0,0,0
    3. 0,1,0,0,0,0,0,0,0,0
    4. 0,1,0,0,0,0,0,0,0,0
    5. 0,1,0,0,0,0,0,0,0,0
    6. 0,1,0,0,0,0,0,0,0,0
    7. 0,1,0,0,0,0,0,0,0,0
    8. 0,1,0,0,0,0,0,0,0,0
    9. 0,1,1,1,1,1,1,1,1,0
    10. 0,1,0,0,0,0,0,0,0,0
    11. 0,1,0,0,0,0,1,1,1,1
    -Grid2DUtilties is useful for getting Grid, Nodes and helper functions
    Code (CSharp):
    1. public class Grid2DUtilites : MonoBehaviour
    2. {
    3.     public static List<Grid2DPath> grid2DPathsToFind = new List<Grid2DPath>();
    4.     public static Dictionary<string, Grid2DPath> grid2DPathsFoundDictanary = new Dictionary<string, Grid2DPath>();
    5.  
    6.     //Groups------------------------------------------------------------------------------------------------------------
    7.     public struct Grid2DGroup
    8.     {
    9.         readonly public int Length;
    10.         public EntityArray Entity;
    11.         public ComponentDataArray<Grid2D> Grid2D;
    12.     }
    13.  
    14.     public struct GridNode2DGroup
    15.     {
    16.         readonly public int Length;
    17.         public ComponentDataArray<Grid2DNode> Grid2DNode;
    18.     }
    19.  
    20.     //Properties----------------------------------------------------------------------------------------------------------
    21.     public static Grid2D Grid2D
    22.     {
    23.         get { return Unity.Entities.World.Active.GetOrCreateManager<EntityManager>().GetComponentData<Grid2D>(Grid2DEntity); }
    24.         set { Unity.Entities.World.Active.GetOrCreateManager<EntityManager>().SetComponentData<Grid2D>(Grid2DEntity, value); }
    25.     }
    26.  
    27.     public static EntityArchetype Grid2DNodeArchetype
    28.     {
    29.         get { return Unity.Entities.World.Active.GetOrCreateManager<EntityManager>().CreateArchetype(typeof(Grid2DNode)); }
    30.     }
    31.  
    32.     public static Entity Grid2DEntity { get; set; }
    33.  
    34.     public static Entity[] Grid2DNodeEntities { get; set; }
    35.  
    36.     //Functions----------------------------------------------------------------------------------------------------------
    37.     public static bool IsGrid2DInitalized()
    38.     {
    39.         return Unity.Entities.World.Active.GetOrCreateManager<EntityManager>().Exists(Grid2DEntity);
    40.     }
    41.  
    42.     public static void SetGrid2DWorldPosition(float3 worldPosition)
    43.     {
    44.         if (Grid2D.worldPosition.x == worldPosition.x && Grid2D.worldPosition.y == worldPosition.y)
    45.             return;
    46.  
    47.         Grid2D grid2D = Grid2D;
    48.         grid2D.worldPosition = worldPosition;
    49.         grid2D.isDirty = 1;
    50.         Grid2D = grid2D;
    51.     }
    52.  
    53.     public static Entity GetGrid2DNodeEntity(int2 i)
    54.     {
    55.         return Grid2DNodeEntities[To1D(i)];
    56.     }
    57.  
    58.     public static void SetGrid2DNodeEntity(Entity entity, int2 i)
    59.     {
    60.         Grid2DNodeEntities[To1D(i)] = entity;
    61.     }
    62.  
    63.     public static Grid2DNode GetGrid2DNode(int2 i)
    64.     {
    65.         if (IsGrid2DNodeInBounds(i))
    66.             return Unity.Entities.World.Active.GetOrCreateManager<EntityManager>().GetComponentData<Grid2DNode>(Grid2DNodeEntities[To1D(i)]);
    67.         return new Grid2DNode() { i = new int2(-1, -1) };
    68.     }
    69.  
    70.     public static Grid2DNode GetGrid2DNode(int i)
    71.     {
    72.         if (IsGrid2DNodeInBounds(i))
    73.             return Unity.Entities.World.Active.GetOrCreateManager<EntityManager>().GetComponentData<Grid2DNode>(Grid2DNodeEntities[i]);
    74.         return new Grid2DNode() { i = new int2(-1, -1) };
    75.     }
    76.  
    77.     public static void SetGrid2DNode(Grid2DNode grid2DNode, int2 i)
    78.     {
    79.         Unity.Entities.World.Active.GetOrCreateManager<EntityManager>().SetComponentData(Grid2DNodeEntities[To1D(i)], grid2DNode);
    80.         Grid2D = new Grid2D() { worldPosition = Grid2D.worldPosition, dimensions = Grid2D.dimensions, maxDimensions = Grid2D.maxDimensions, isDirty = 1 };
    81.     }
    82.  
    83.     public static bool IsGrid2DNodeInBounds(int2 i)
    84.     {
    85.         return i.x >= 0 && i.x < Grid2D.dimensions.x && i.y >= 0 && i.y < Grid2D.dimensions.y;
    86.     }
    87.  
    88.     public static bool IsGrid2DNodeInBounds(int i)
    89.     {
    90.         return i != -1;
    91.     }
    92.  
    93.     public static unsafe void SetGrid2DNodeNeigbours(int2 i)
    94.     {
    95.         var n = GetGrid2DNode(i);
    96.  
    97.         //
    98.         n.neigbours[0] = IsGrid2DNodeInBounds(i + new int2(1, 0)) ? To1D(i + new int2(1, 0)) : -1;
    99.         n.neigbours[1] = IsGrid2DNodeInBounds(i + new int2(-1, 0)) ? To1D(i + new int2(-1, 0)) : -1;
    100.         n.neigbours[2] = IsGrid2DNodeInBounds(i + new int2(0, 1)) ? To1D(i + new int2(0, 1)) : -1;
    101.         n.neigbours[3] = IsGrid2DNodeInBounds(i + new int2(0, -1)) ? To1D(i + new int2(0, -1)) : -1;
    102.  
    103.         //Di
    104.         n.neigbours[4] = IsGrid2DNodeInBounds(i + new int2(1, 1)) ? To1D(i + new int2(1, 1)) : -1;
    105.         n.neigbours[5] = IsGrid2DNodeInBounds(i + new int2(1, -1)) ? To1D(i + new int2(1, -1)) : -1;
    106.         n.neigbours[6] = IsGrid2DNodeInBounds(i + new int2(-1, 1)) ? To1D(i + new int2(-1, 1)) : -1;
    107.         n.neigbours[7] = IsGrid2DNodeInBounds(i + new int2(-1, -1)) ? To1D(i + new int2(-1, -1)) : -1;
    108.  
    109.         SetGrid2DNode(n, i);
    110.     }
    111.  
    112.     public static void CreateGrid(string data)
    113.     {
    114.         int x = 0;
    115.         int y = 0;
    116.  
    117.         using (StringReader reader = new StringReader(data))
    118.         {
    119.             string line;
    120.             int lineNum = 0;
    121.             while ((line = reader.ReadLine()) != null)
    122.             {
    123.                 if (lineNum == 0)
    124.                 {
    125.                     var grid2D = Grid2D;
    126.                     grid2D.dimensions = new int2(int.Parse(line.Split(',')[0]), int.Parse(line.Split(',')[1]));
    127.                     grid2D.dimensions.x = Mathf.Clamp(grid2D.dimensions.x, 1, grid2D.maxDimensions.x);
    128.                     grid2D.dimensions.y = Mathf.Clamp(grid2D.dimensions.y, 1, grid2D.maxDimensions.y);
    129.                     Grid2D = grid2D;
    130.                     y = grid2D.dimensions.y - 1;
    131.                 }
    132.                 else
    133.                 {
    134.                     foreach (var i in line.Split(','))
    135.                     {
    136.                         Grid2DNode n = GetGrid2DNode(new int2(x, y));
    137.                         n.isSolid = i == "0" ? (byte)0 : (byte)1;
    138.                         SetGrid2DNode(n, new int2(x, y));
    139.                         x++;
    140.                     }
    141.                     x = 0;
    142.                     y--;
    143.                 }
    144.                 lineNum++;
    145.             }
    146.         }
    147.     }
    148.  
    149.     public static void RequestPath(int2 startGridPosition, int2 endGridPosition, OnGrid2DPathComplete onGrid2DPathComplete, byte isEightConnections)
    150.     {
    151.         grid2DPathsToFind.Add(new Grid2DPath() { startGridPosition = startGridPosition, endGridPosition = endGridPosition, onGrid2DPathComplete = onGrid2DPathComplete, isEightConnections = isEightConnections });
    152.     }
    153.  
    154.     public static int To1D(int2 i)
    155.     {
    156.         return (int)(i.x + (i.y * Grid2D.maxDimensions.y));
    157.     }
    158.  
    159.     public static void OnDrawGizmosGrid()
    160.     {
    161.         for (int x = 0; x < Grid2D.dimensions.x; x++)
    162.             for (int y = 0; y < Grid2D.dimensions.y; y++)
    163.             {
    164.                 Grid2DNode n = GetGrid2DNode(new int2(x, y));
    165.                 Gizmos.color = n.isSolid == 1 ? Color.red : Color.blue;
    166.                 Gizmos.DrawCube(n.localPosition + Grid2D.worldPosition, new Vector3(0.1f, 0.1f));
    167.             }
    168.     }
    169.  
    170.     public static void OnDrawGizmosPath(string pathID)
    171.     {
    172.         if (pathID == string.Empty || !grid2DPathsFoundDictanary.ContainsKey(pathID))
    173.             return;
    174.  
    175.         Grid2DPath p = grid2DPathsFoundDictanary[pathID];
    176.         Gizmos.color = Color.green;
    177.         for (int i = 1; i < p.worldPoints.Count; i++)
    178.             Gizmos.DrawLine(p.worldPoints[i], p.worldPoints[i - 1]);
    179.     }
    180. }
     

    Attached Files:

    Last edited: Dec 3, 2018
  2. Filtiarn_

    Filtiarn_

    Joined:
    Jan 24, 2013
    Posts:
    173
    Components
    Code (CSharp):
    1. using Unity.Mathematics;
    2. using Unity.Entities;
    3.  
    4. [System.Serializable]
    5. public struct Grid2D: IComponentData
    6. {
    7.     public float3 worldPosition;
    8.     public int2 dimensions;
    9.     public int2 maxDimensions;
    10.     public byte isDirty;
    11. }
    12.  
    13. [UnityEngine.DisallowMultipleComponent]
    14. public class Grid2DComponent : ComponentDataWrapper<Grid2D> { }
    15.  
    16.  
    17. [System.Serializable]
    18. public unsafe struct Grid2DNode : IComponentData
    19. {
    20.     public int2 i;
    21.     public float3 localPosition;
    22.     public byte isSolid;
    23.     public fixed int neigbours[8];
    24. }
    25.  
    26. [UnityEngine.DisallowMultipleComponent]
    27. public class Grid2DNodeComponent : ComponentDataWrapper<Grid2DNode> { }
    Grid Initialize System
    Code (CSharp):
    1. public class Grid2DInitalizeSystem : ComponentSystem
    2. {
    3.     [Inject] private Grid2DUtilites.Grid2DGroup grid2DGroup;
    4.  
    5.     protected override void OnUpdate()
    6.     {
    7.         var entityManager = Unity.Entities.World.Active.GetOrCreateManager<EntityManager>();
    8.  
    9.         //Break out if already Initalized
    10.         if (Grid2DUtilites.IsGrid2DInitalized())
    11.             return;
    12.  
    13.         //Read
    14.         var grid2D = grid2DGroup.Grid2D[0];
    15.  
    16.         //Translate
    17.         {
    18.             Grid2DUtilites.Grid2DNodeEntities = new Entity[((int)(grid2D.maxDimensions.x * grid2D.maxDimensions.y))];
    19.             Grid2DUtilites.Grid2DEntity = grid2DGroup.Entity[0];
    20.             grid2D = grid2DGroup.Grid2D[0];
    21.             grid2D.isDirty = 1;
    22.  
    23.             for (int x = 0; x < grid2D.maxDimensions.x; x++)
    24.                 for (int y = 0; y < grid2D.maxDimensions.y; y++)
    25.                 {
    26.                     var grid2DNodeEntity = entityManager.CreateEntity(Grid2DUtilites.Grid2DNodeArchetype);
    27.                     entityManager.SetComponentData(grid2DNodeEntity, new Grid2DNode { i = new int2(x, y), localPosition = new float3(x * 1, y * 1, 0), isSolid = 0 });
    28.                     Grid2DUtilites.SetGrid2DNodeEntity(grid2DNodeEntity, new int2(x, y));
    29.                     Grid2DUtilites.SetGrid2DNodeNeigbours(new int2(x, y));
    30.                 }
    31.         }
    32.  
    33.         //Write
    34.         Grid2DUtilites.Grid2D = grid2D;
    35.  
    36.         //Disable
    37.         Enabled = false;
    38.     }
    39. }
    40.  
    41.  
    Grid Pathfinding System
    Code (CSharp):
    1. public class Grid2DPathfindingSystem : ComponentSystem
    2. {
    3.  
    4.     //GridPath
    5.     private Grid2DPath grid2DPath;
    6.     private Grid2DNode startGrid2DNode;
    7.     private Grid2DNode endGrid2DNode;
    8.     private string grid2dPathId;
    9.  
    10.     //Pathfinding
    11.     private Grid2DExpansion current;
    12.     private List<Grid2DExpansion> open;
    13.     private bool[] closed;
    14.  
    15.     protected unsafe override void OnUpdate()
    16.     {
    17.         if (Grid2DUtilites.grid2DPathsToFind.Count == 0)
    18.             return;
    19.  
    20.         //Get Path To Find | Start | End | Create ID
    21.         grid2DPath = Grid2DUtilites.grid2DPathsToFind[0];
    22.         Grid2DUtilites.grid2DPathsToFind.RemoveAt(0);
    23.         grid2DPath.worldPoints = new List<float3>();
    24.         startGrid2DNode = Grid2DUtilites.GetGrid2DNode(grid2DPath.startGridPosition);
    25.         endGrid2DNode = Grid2DUtilites.GetGrid2DNode(grid2DPath.endGridPosition);
    26.         grid2dPathId = startGrid2DNode.i.ToString() + endGrid2DNode.i.ToString();
    27.  
    28.         //Make Closed List | Set Current to start | Add Current(Start) To open
    29.         closed = new bool[Grid2DUtilites.Grid2D.dimensions.x * Grid2DUtilites.Grid2D.dimensions.y];
    30.         current = new Grid2DExpansion(startGrid2DNode, null, 0);
    31.         open = new List<Grid2DExpansion>();
    32.         open.Add(current);
    33.  
    34.         //Find Path
    35.         for (; ; )
    36.         {
    37.             //Return path if at end or open count is 0
    38.             if (current.grid2DNode.i.x == endGrid2DNode.i.x && current.grid2DNode.i.y == endGrid2DNode.i.y || open.Count == 0)
    39.             {
    40.                 ReturnRetracedPath();
    41.                 return;
    42.             }
    43.  
    44.             //Set current to null | Set current to best element in open | Remove it from open list
    45.             current = null;
    46.             foreach (var i in open)
    47.                 if (current == null || i.cost < current.cost)
    48.                     current = i;
    49.  
    50.  
    51.             //Remove Current form open
    52.             open.Remove(current);
    53.  
    54.             //closed[Grid2DUtilites.To1D(current.grid2DNode.i)] = true; //Moved This to Expansion which improves speed since were expanding less, but at the same time gives same results
    55.  
    56.             //Expand
    57.             int ea = grid2DPath.isEightConnections == 0 ? 4 : 8;
    58.             for (int i = 0; i < ea; i++)
    59.                 Expand(current.grid2DNode.neigbours[i],Grid2DUtilites.GetGrid2DNode(current.grid2DNode.neigbours[i]));
    60.         }
    61.     }
    62.  
    63.     private unsafe void Expand(int i, Grid2DNode neigbourGridNode2D)
    64.     {
    65.         //Dont Expand if out of obunds | in closed list | Is Solid
    66.         if ( !Grid2DUtilites.IsGrid2DNodeInBounds(i) || closed[i] || neigbourGridNode2D.isSolid == 1)
    67.             return;
    68.  
    69.         //Add To Closed list
    70.         closed[i] = true;
    71.  
    72.         //Add To Open
    73.         open.Add(new Grid2DExpansion(neigbourGridNode2D, current, 0));
    74.     }
    75.  
    76.     private void ReturnRetracedPath()
    77.     {
    78.         //Create Path by going throug link list
    79.         while (current != null)
    80.         {
    81.             grid2DPath.worldPoints.Add(Grid2DUtilites.Grid2D.worldPosition + current.grid2DNode.localPosition);
    82.             current = current.previous;
    83.         }
    84.  
    85.         //Reverse Path so first worldPoint is start of path
    86.         grid2DPath.worldPoints.Reverse();
    87.  
    88.         //Add Path found path Dictanary
    89.         if (Grid2DUtilites.grid2DPathsFoundDictanary.ContainsKey(grid2dPathId))
    90.             Grid2DUtilites.grid2DPathsFoundDictanary.Remove(grid2dPathId);
    91.         Grid2DUtilites.grid2DPathsFoundDictanary.Add(grid2dPathId, grid2DPath);
    92.  
    93.         //Invoke On Complete
    94.         grid2DPath.onGrid2DPathComplete.Invoke(grid2dPathId);
    95.         return;
    96.     }
    97. }
    Delegate for returning path | Grid2D Path | Grid2D Expansion
    Code (CSharp):
    1. public delegate void OnGrid2DPathComplete(string pathID);
    2.  
    3. public class Grid2DPath
    4. {
    5.     public List<float3> worldPoints;
    6.     public int2 startGridPosition;
    7.     public int2 endGridPosition;
    8.     public OnGrid2DPathComplete onGrid2DPathComplete;
    9.     public byte isEightConnections;
    10. }
    11.  
    12. public class Grid2DExpansion
    13. {
    14.     public Grid2DNode grid2DNode;
    15.     public Grid2DExpansion previous;
    16.     public float cost;
    17.  
    18.     public Grid2DExpansion(Grid2DNode grid2DNode, Grid2DExpansion previous, float cost)
    19.     {
    20.         this.grid2DNode = grid2DNode;
    21.         this.previous = previous;
    22.         this.cost = cost;
    23.     }
    24. }
     
  3. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    3,753
    I wrote a grid based pathfinding solution using burst compiled jobs a while ago.
    It was pretty fast, I was using 4096x4096 grids as well (which is ridiculously large)

    I have since moved to using navmeshqueries so I don't actually need this anymore, but you're welcome to have a look to give you an idea how to use jobs.

    This is just the system, if you want everything that goes with it (custom native containers, components etc) let me know and I'll see if I can bundle it up (as I said don't use it anymore so need to pull it from repo).

    Main thing you probably care about is the FindPathJob.

    It supports climb, drop and slopes (i.e. the grid doesn't have to be flat) as well as cells that have different costs and optionally navigating to nearest if cell is blocked etc.

    Code (CSharp):
    1. // <copyright file="PathfindingSystem.cs" company="Timothy Raines">
    2. //     Copyright (c) Timothy Raines. All rights reserved.
    3. // </copyright>
    4.  
    5. namespace BovineLabs.Systems.Pathfinding
    6. {
    7.     using System;
    8.     using BovineLabs.Common.Jobs;
    9.     using BovineLabs.Common.Native;
    10.     using BovineLabs.Common.Utility;
    11.     using BovineLabs.Systems.World;
    12.     using JetBrains.Annotations;
    13.     using Unity.Burst;
    14.     using Unity.Collections;
    15.     using Unity.Collections.LowLevel.Unsafe;
    16.     using Unity.Entities;
    17.     using Unity.Jobs;
    18.     using Unity.Mathematics;
    19.     using Unity.Transforms;
    20.  
    21.     /// <summary>
    22.     /// The pathfinding system.
    23.     /// </summary>
    24.     public class PathfindingSystem : JobComponentSystem
    25.     {
    26.         private const int WorkerCount = 8;
    27.         private const float DiagonalCost = 1.41421f; // sqrt(2)
    28.  
    29.         private const int IterationLimit = 1000;
    30.         private const int NeighbourCount = 8;
    31.  
    32.         private readonly int2 worldSize;
    33.  
    34.         private NativeArray<Neighbour> neighbours;
    35.  
    36.         private BarrierSystem barrier;
    37.         private ComponentGroup gridQuery;
    38.         private NativeQueue<PathRequest> requestsQueue;
    39.         private NativeList<PathRequest> requestsList;
    40.  
    41.         private NativeArray<float> costSoFar;
    42.         private NativeArray<int2> cameFrom;
    43.         private NativeMinHeap openSet;
    44.  
    45.         /// <summary>
    46.         /// Initializes a new instance of the <see cref="PathfindingSystem"/> class.
    47.         /// </summary>
    48.         /// <param name="settings">Shared settings between pathfinding systems.</param>
    49.         public PathfindingSystem(Settings settings)
    50.         {
    51.             // heightmap is 2d
    52.             this.worldSize = settings.WorldSize.xz;
    53.  
    54.         }
    55.  
    56.         /// <inheritdoc />
    57.         protected override void OnCreateManager()
    58.         {
    59.             this.barrier = this.GetBarrier<PathfindingBarrier>();
    60.  
    61.             var size = this.worldSize.x * this.worldSize.y;
    62.  
    63.             this.costSoFar = new NativeArray<float>(size * WorkerCount, Allocator.Persistent);
    64.             this.cameFrom = new NativeArray<int2>(size * WorkerCount, Allocator.Persistent);
    65.             this.openSet = new NativeMinHeap((IterationLimit + 1) * NeighbourCount * WorkerCount, Allocator.Persistent);
    66.  
    67.             this.neighbours = new NativeArray<Neighbour>(8, Allocator.Persistent)
    68.             {
    69.                 [0] = new Neighbour(-1, -1), // Bottom left
    70.                 [1] = new Neighbour(0, -1), // Bottom
    71.                 [2] = new Neighbour(1, -1), // Bottom Right
    72.                 [3] = new Neighbour(-1, 0), // Left
    73.                 [4] = new Neighbour(1, 0), // Right
    74.                 [5] = new Neighbour(-1, 1), // Top Left
    75.                 [6] = new Neighbour(0, 1), // Top
    76.                 [7] = new Neighbour(1, 1), // Top Right
    77.             };
    78.  
    79.             this.requestsQueue = new NativeQueue<PathRequest>(Allocator.Persistent);
    80.             this.requestsList = new NativeList<PathRequest>(Allocator.Persistent);
    81.  
    82.             this.gridQuery = this.GetComponentGroup(new EntityArchetypeQuery
    83.             {
    84.                 Any = Array.Empty<ComponentType>(),
    85.                 None = Array.Empty<ComponentType>(),
    86.                 All = new[] { ComponentType.ReadOnly<Cell>() },
    87.             });
    88.         }
    89.  
    90.         /// <inheritdoc />
    91.         protected override void OnDestroyManager()
    92.         {
    93.             this.costSoFar.Dispose();
    94.             this.cameFrom.Dispose();
    95.             this.openSet.Dispose();
    96.  
    97.             this.neighbours.Dispose();
    98.  
    99.             this.requestsQueue.Dispose();
    100.             this.requestsList.Dispose();
    101.         }
    102.  
    103.         /// <inheritdoc />
    104.         protected override JobHandle OnUpdate(JobHandle handle)
    105.         {
    106.             if (this.gridQuery.CalculateLength() == 0)
    107.             {
    108.                 return handle;
    109.             }
    110.  
    111.             this.requestsQueue.Clear();
    112.  
    113.             var gridChunks = this.gridQuery.CreateArchetypeChunkArray(Allocator.TempJob);
    114.             var cellTypeRO = this.GetArchetypeChunkBufferType<Cell>(true);
    115.  
    116.             var groupRequestsJob = new GroupRequestsJob
    117.             {
    118.                 Requests = this.requestsQueue.ToConcurrent(),
    119.                 EntityCommandBuffer = this.barrier.CreateCommandBuffer().ToConcurrent(),
    120.             };
    121.  
    122.             var groupRequestsHandle = groupRequestsJob.Schedule(this, handle);
    123.  
    124.             var copyQueueToListJob = new CopyQueueToListJob
    125.             {
    126.                 RequestsQueue = this.requestsQueue,
    127.                 RequestsList = this.requestsList,
    128.             };
    129.  
    130.             var copyQueueToListHandle = copyQueueToListJob.Schedule(groupRequestsHandle);
    131.  
    132.             var findPathJob = new FindPathJob
    133.             {
    134.                 Neighbours = this.neighbours,
    135.                 GridChunks = gridChunks,
    136.                 CellTypeRO = cellTypeRO,
    137.                 Requests = this.requestsList,
    138.                 NavigationCapabilities = this.GetComponentDataFromEntity<NavigationCapabilities>(true),
    139.                 Positions = this.GetComponentDataFromEntity<Position>(true),
    140.                 Waypoints = this.GetBufferFromEntity<Waypoint>(),
    141.                 CostSoFar = this.costSoFar,
    142.                 CameFrom = this.cameFrom,
    143.                 OpenSet = this.openSet,
    144.                 DimX = this.worldSize.x,
    145.                 DimY = this.worldSize.y,
    146.                 Iterations = IterationLimit,
    147.             };
    148.  
    149.             var findPathHandle = findPathJob.Schedule(WorkerCount, 4, copyQueueToListHandle);
    150.  
    151.             return new DeallocateJob<NativeArray<ArchetypeChunk>>(gridChunks).Schedule(findPathHandle);
    152.         }
    153.  
    154.         [BurstCompile]
    155.         private struct GroupRequestsJob : IJobProcessComponentDataWithEntity<PathRequest>
    156.         {
    157.             [WriteOnly]
    158.             public NativeQueue<PathRequest>.Concurrent Requests;
    159.  
    160.             public EntityCommandBuffer.Concurrent EntityCommandBuffer;
    161.  
    162.             /// <inheritdoc />
    163.             public void Execute(Entity entity, int index, ref PathRequest data)
    164.             {
    165.                 this.Requests.Enqueue(data);
    166.                 this.EntityCommandBuffer.DestroyEntity(index, entity);
    167.             }
    168.         }
    169.  
    170.         [BurstCompile]
    171.         private struct CopyQueueToListJob : IJob
    172.         {
    173.             public NativeQueue<PathRequest> RequestsQueue;
    174.  
    175.             [WriteOnly]
    176.             public NativeList<PathRequest> RequestsList;
    177.  
    178.             /// <inheritdoc />
    179.             public void Execute()
    180.             {
    181.                 this.RequestsList.Clear();
    182.  
    183.                 while (this.RequestsQueue.TryDequeue(out var request))
    184.                 {
    185.                     this.RequestsList.Add(request);
    186.                 }
    187.             }
    188.         }
    189.  
    190.         [BurstCompile]
    191.         private unsafe struct FindPathJob : IJobParallelFor
    192.         {
    193.             [ReadOnly]
    194.             public NativeArray<Neighbour> Neighbours;
    195.  
    196.             [ReadOnly]
    197.             public NativeArray<ArchetypeChunk> GridChunks;
    198.  
    199.             [ReadOnly]
    200.             public ArchetypeChunkBufferType<Cell> CellTypeRO;
    201.  
    202.             [ReadOnly]
    203.             public NativeList<PathRequest> Requests;
    204.  
    205.             [ReadOnly]
    206.             public ComponentDataFromEntity<NavigationCapabilities> NavigationCapabilities;
    207.  
    208.             [ReadOnly]
    209.             public ComponentDataFromEntity<Position> Positions;
    210.  
    211.             [NativeDisableParallelForRestriction]
    212.             public BufferFromEntity<Waypoint> Waypoints;
    213.  
    214.             [NativeDisableParallelForRestriction]
    215.             public NativeArray<float> CostSoFar;
    216.  
    217.             [NativeDisableParallelForRestriction]
    218.             public NativeArray<int2> CameFrom;
    219.  
    220.             [NativeDisableParallelForRestriction]
    221.             public NativeMinHeap OpenSet;
    222.  
    223.             public int DimX;
    224.             public int DimY;
    225.             public int Iterations;
    226.  
    227.             public void Execute(int index)
    228.             {
    229.                 var accessor = this.GridChunks[0].GetBufferAccessor(this.CellTypeRO);
    230.                 var grid = accessor[0].Reinterpret<Cell>();
    231.  
    232.                 var size = this.DimX * this.DimY;
    233.  
    234.                 var costSoFar = this.CostSoFar.Slice(index * size, size);
    235.                 var cameFrom = this.CameFrom.Slice(index * size, size);
    236.  
    237.                 var openSetSize = (this.Iterations + 1) * NeighbourCount;
    238.                 var openSet = this.OpenSet.Slice(index * openSetSize, openSetSize);
    239.  
    240.                 var requestIndex = index;
    241.  
    242.                 while (this.Requests.Length > requestIndex * NeighbourCount)
    243.                 {
    244.                     var request = this.Requests[requestIndex];
    245.                     requestIndex += WorkerCount;
    246.  
    247.                     // Clear our shared data
    248.                     var buffer = costSoFar.GetUnsafePtr();
    249.                     UnsafeUtility.MemClear(buffer, (long)costSoFar.Length * UnsafeUtility.SizeOf<float>());
    250.                     openSet.Clear();
    251.  
    252.                     var entity = request.Entity;
    253.  
    254.                     var currentPosition = this.Positions[request.Entity];
    255.                     var capability = this.NavigationCapabilities[entity];
    256.  
    257.                     // cache these as they're used a lot
    258.                     var start = currentPosition.Value.xz.FloorToInt();
    259.                     var goal = request.Destination.FloorToInt();
    260.  
    261.                     DynamicBuffer<float3> waypoints = this.Waypoints[entity].Reinterpret<float3>();
    262.                     waypoints.Clear();
    263.  
    264.                     // Special case when the start is the same point as the goal
    265.                     if (start.Equals(goal))
    266.                     {
    267.                         // We just set the destination as the goal, but need to get the correct height
    268.                         var gridIndex = this.GetIndex(goal);
    269.                         var cell = grid[gridIndex];
    270.                         var point = new float3(request.Destination.x, cell.Height, request.Destination.y);
    271.                         waypoints.Add(point);
    272.                         continue;
    273.                     }
    274.  
    275.                     var stash = new InstanceStash
    276.                     {
    277.                         Grid = grid,
    278.                         CameFrom = cameFrom,
    279.                         CostSoFar = costSoFar,
    280.                         OpenSet = openSet,
    281.                         Request = request,
    282.                         Capability = capability,
    283.                         CurrentPosition = currentPosition,
    284.                         Start = start,
    285.                         Goal = goal,
    286.                         Waypoints = waypoints,
    287.                     };
    288.  
    289.                     if (this.ProcessPath(ref stash))
    290.                     {
    291.                         this.ReconstructPath(stash);
    292.                     }
    293.                 }
    294.             }
    295.  
    296.             private static float H(float2 p0, float2 p1)
    297.             {
    298.                 var dx = p0.x - p1.x;
    299.                 var dy = p0.y - p1.y;
    300.                 var sqr = (dx * dx) + (dy * dy);
    301.                 return math.sqrt(sqr);
    302.             }
    303.  
    304.             private bool ProcessPath(ref InstanceStash stash)
    305.             {
    306.                 // Push the start to NativeMinHeap openSet
    307.  
    308.                 var hh = H(stash.Start, stash.Goal);
    309.                 var head = new MinHeapNode(stash.Start, hh, hh);
    310.                 stash.OpenSet.Push(head);
    311.  
    312.                 var iterations = this.Iterations;
    313.  
    314.                 var closest = head;
    315.  
    316.                 // While we still have potential nodes to explore
    317.                 while (stash.OpenSet.HasNext())
    318.                 {
    319.                     var current = stash.OpenSet.Pop();
    320.  
    321.                     if (current.DistanceToGoal < closest.DistanceToGoal)
    322.                     {
    323.                         closest = current;
    324.                     }
    325.  
    326.                     // Found our goal
    327.                     if (current.Position.Equals(stash.Goal))
    328.                     {
    329.                         return true;
    330.                     }
    331.  
    332.                     // Path might still be obtainable but we've run out of allowed iterations
    333.                     if (iterations == 0)
    334.                     {
    335.                         if (stash.Request.NavigateToBestIfIncomplete)
    336.                         {
    337.                             // Return the best result we've found so far
    338.                             // Need to update goal so we can reconstruct the shorter path
    339.                             stash.Goal = closest.Position;
    340.                             return true;
    341.                         }
    342.  
    343.                         return false;
    344.                     }
    345.  
    346.                     iterations--;
    347.  
    348.                     var initialCost = stash.CostSoFar[this.GetIndex(current.Position)];
    349.  
    350.                     var fromIndex = this.GetIndex(current.Position);
    351.  
    352.                     // Loop our potential cells - generally neighbours but could include portals
    353.                     for (var i = 0; i < this.Neighbours.Length; i++)
    354.                     {
    355.                         var neighbour = this.Neighbours[i];
    356.                         var position = current.Position + neighbour.Offset;
    357.  
    358.                         // Make sure the node isn't outside our grid
    359.                         if (position.x < 0 || position.x >= this.DimX || position.y < 0 || position.y >= this.DimY)
    360.                         {
    361.                             continue;
    362.                         }
    363.  
    364.                         var index = this.GetIndex(position);
    365.  
    366.                         // Get the cost of going to this cell
    367.                         var cellCost = this.GetCellCost(stash.Grid, stash.Capability, fromIndex, index, neighbour, true);
    368.  
    369.                         // Infinity means the cell is un-walkable, skip it
    370.                         if (float.IsInfinity(cellCost))
    371.                         {
    372.                             continue;
    373.                         }
    374.  
    375.                         var newCost = initialCost + (neighbour.Distance * cellCost);
    376.                         var oldCost = stash.CostSoFar[index];
    377.  
    378.                         // If we've explored this cell before and it was a better path, ignore this route
    379.                         if (!(oldCost <= 0) && !(newCost < oldCost))
    380.                         {
    381.                             continue;
    382.                         }
    383.  
    384.                         // Update the costing and best path
    385.                         stash.CostSoFar[index] = newCost;
    386.                         stash.CameFrom[index] = current.Position;
    387.  
    388.                         // Push the node onto our heap
    389.                         var h = H(position, stash.Goal);
    390.                         var expectedCost = newCost + h;
    391.                         stash.OpenSet.Push(new MinHeapNode(position, expectedCost, h));
    392.                     }
    393.                 }
    394.  
    395.                 if (stash.Request.NavigateToNearestIfBlocked)
    396.                 {
    397.                     stash.Goal = closest.Position;
    398.                     return true;
    399.                 }
    400.  
    401.                 // All routes have been explored without finding a route to destination
    402.                 return false;
    403.             }
    404.  
    405.             private void ReconstructPath(InstanceStash stash)
    406.             {
    407.                 var current = stash.CameFrom[this.GetIndex(stash.Goal)];
    408.                 var from = this.GetPosition(stash.Grid, current);
    409.  
    410.                 stash.Waypoints.Add(from);
    411.  
    412.                 var next = this.GetPosition(stash.Grid, current);
    413.  
    414.                 while (!current.Equals(stash.Start))
    415.                 {
    416.                     current = stash.CameFrom[this.GetIndex(current)];
    417.                     var tmp = next;
    418.                     next = this.GetPosition(stash.Grid, current);
    419.  
    420.                     if (!this.IsWalkable(stash.Grid, from.xz, next.xz))
    421.                     {
    422.                         // skip
    423.                         stash.Waypoints.Add(tmp);
    424.                         from = tmp;
    425.                     }
    426.                 }
    427.  
    428.                 stash.Waypoints.Reverse();
    429.             }
    430.  
    431.             private bool IsWalkable(DynamicBuffer<Cell> buffer, float2 from, float2 to)
    432.             {
    433.                 const float step = 0.25f;
    434.  
    435.                 var vector = to - from;
    436.                 var length = math.length(vector);
    437.                 var unit = vector / length;
    438.                 var iterations = length / step;
    439.  
    440.                 var currentCell = buffer[this.GetIndex(from.FloorToInt())];
    441.  
    442.                 for (var i = 0; i < iterations; i++)
    443.                 {
    444.                     var point = (i * step * unit) + from;
    445.  
    446.                     var index = this.GetIndex(point.FloorToInt());
    447.                     var cell = buffer[index];
    448.                     if (cell.Blocked)
    449.                     {
    450.                         return false;
    451.                     }
    452.  
    453.                     if (cell.Height != currentCell.Height)
    454.                     {
    455.                         return false;
    456.                     }
    457.                 }
    458.  
    459.                 return true;
    460.             }
    461.  
    462.             private float GetCellCost(DynamicBuffer<Cell> grid, NavigationCapabilities capabilities, int fromIndex, int toIndex, Neighbour neighbour, bool areNeighbours)
    463.             {
    464.                 var target = grid[toIndex];
    465.                 if (target.Blocked)
    466.                 {
    467.                     return float.PositiveInfinity;
    468.                 }
    469.  
    470.                 // If we're not neighbours, then we're a portal and can just go straight there
    471.                 if (!areNeighbours)
    472.                 {
    473.                     return 1;
    474.                 }
    475.  
    476.                 var from = grid[fromIndex];
    477.  
    478.                 var heightDiff = target.Height - from.Height;
    479.                 var absDiff = math.abs(heightDiff);
    480.  
    481.                 // TODO Should precompute this
    482.                 var dropHeight = 0;
    483.                 var climbHeight = 0;
    484.  
    485.                 if (heightDiff > 0)
    486.                 {
    487.                     climbHeight = absDiff;
    488.                 }
    489.                 else
    490.                 {
    491.                     dropHeight = absDiff;
    492.                 }
    493.  
    494.                 var slope = math.degrees(math.atan(absDiff / neighbour.Distance));
    495.  
    496.                 // TODO End precompute
    497.                 if ((capabilities.MaxClimbHeight < climbHeight || capabilities.MaxDropHeight < dropHeight) &&
    498.                     capabilities.MaxSlopeAngle < slope)
    499.                 {
    500.                     return float.PositiveInfinity;
    501.                 }
    502.  
    503.                 return 1;
    504.             }
    505.  
    506.             private float3 GetPosition(DynamicBuffer<Cell> grid, int2 point)
    507.             {
    508.                 var index = this.GetIndex(point);
    509.                 var cell = grid[index];
    510.                 var fPoint = point + new float2(0.5f, 0.5f);
    511.                 return new float3(fPoint.x, cell.Height, fPoint.y);
    512.             }
    513.  
    514.             private int GetIndex(int2 i)
    515.             {
    516.                 return (i.y * this.DimX) + i.x;
    517.             }
    518.  
    519.             private struct InstanceStash
    520.             {
    521.                 public Position CurrentPosition;
    522.                 public PathRequest Request;
    523.                 public NavigationCapabilities Capability;
    524.                 public DynamicBuffer<float3> Waypoints;
    525.  
    526.                 public int2 Start;
    527.                 public int2 Goal;
    528.  
    529.                 public DynamicBuffer<Cell> Grid;
    530.  
    531.                 public NativeSlice<float> CostSoFar;
    532.                 public NativeSlice<int2> CameFrom;
    533.                 public NativeMinHeap OpenSet;
    534.             }
    535.         }
    536.  
    537.         /// <summary>
    538.         /// Simple precomputed neighbour data.
    539.         /// </summary>
    540.         private struct Neighbour
    541.         {
    542.             public readonly float Distance;
    543.             public readonly int2 Offset;
    544.  
    545.             public Neighbour(int x, int y)
    546.             {
    547.                 if (x < -1 || x > 1)
    548.                 {
    549.                     throw new ArgumentOutOfRangeException(
    550.                         nameof(x),
    551.                         $"Parameter {nameof(x)} cannot have a magnitude larger than one");
    552.                 }
    553.  
    554.                 if (y < -1 || y > 1)
    555.                 {
    556.                     throw new ArgumentOutOfRangeException(
    557.                         nameof(y),
    558.                         $"Parameter {nameof(y)} cannot have a magnitude larger than one");
    559.                 }
    560.  
    561.                 if (x == 0 && y == 0)
    562.                 {
    563.                     throw new ArgumentException(
    564.                         nameof(y),
    565.                         $"Paramters {nameof(x)} and {nameof(y)} cannot both be zero");
    566.                 }
    567.  
    568.                 this.Offset = new int2(x, y);
    569.  
    570.                 // Penalize diagonal movement
    571.                 this.Distance = x != 0 && y != 0 ? DiagonalCost : 1;
    572.             }
    573.         }
    574.  
    575.         [UsedImplicitly(ImplicitUseKindFlags.Assign)]
    576.         private class PathfindingBarrier : BarrierSystem
    577.         {
    578.         }
    579.     }
    580. }
     
    Filtiarn_ likes this.
  4. Filtiarn_

    Filtiarn_

    Joined:
    Jan 24, 2013
    Posts:
    173
    Let me first start off by saying thanks for all your help tertle . I learned a lot. My main objective of getting rid of class refrences in for pathfinding has been completed. No longer using Grid2DExpansion in pathfinding which was a class. Still need to move logic into a Job System but I find it easy to do things step by step than all at once and I ran out of time for today. I also fixed the error I wrote in edit on my first post which was grid was not acting correctly if dimensions was not same as max dimensions. Also I have written a A* system in Unity that uses multiple floors(like Xcom 2), has slopes, Walls between nodes and ladders. It's on my GitHub. This time I just chose to do a 2D grid to learn ECS, and Jobs.

    Code (CSharp):
    1. public class Grid2DPathfindingSystem : ComponentSystem
    2. {
    3.     private Grid2DPathRequest grid2DPathRequest;
    4.     private NativeList<int2> openSet;
    5.     private NativeArray<float> cost;
    6.     private NativeArray<int2> cameFrom;
    7.     private int2 current;
    8.  
    9.     protected override void OnCreateManager()
    10.     {
    11.         int gridSize = Grid2DUtilites.MaxGrid2DSize;
    12.         openSet = new NativeList<int2>(gridSize, Allocator.Persistent);
    13.         cost = new NativeArray<float>(gridSize, Allocator.Persistent);
    14.         cameFrom = new NativeArray<int2>(gridSize, Allocator.Persistent);
    15.     }
    16.  
    17.     protected override void OnDestroyManager()
    18.     {
    19.         this.openSet.Dispose();
    20.         this.cost.Dispose();
    21.         this.cameFrom.Dispose();
    22.     }
    23.  
    24.     protected unsafe override void OnUpdate()
    25.     {
    26.         //Dont find paths if there is no requests
    27.         if (Grid2DUtilites.grid2DPathRequests.Count == 0)
    28.             return;
    29.  
    30.         //Get Grid2D Path Request | Remove from requests
    31.         grid2DPathRequest = Grid2DUtilites.grid2DPathRequests[0];
    32.         Grid2DUtilites.grid2DPathRequests.RemoveAt(0);
    33.  
    34.         //Clear open and closed set
    35.         openSet.Clear();
    36.  
    37.         //Recrete Cost so far because we can clear Native Array
    38.         cost.Dispose();
    39.         cost = new NativeArray<float>(Grid2DUtilites.MaxGrid2DSize, Allocator.Persistent);
    40.  
    41.         //Set Current to start | Add current to open set
    42.         current = grid2DPathRequest.start;
    43.         openSet.Add(current);
    44.  
    45.         //Find Path
    46.         for (; ; )
    47.         {
    48.             //Were at the End | Or open Set Count is 0
    49.             if (current.Equals(grid2DPathRequest.end) || openSet.Length == 0)
    50.             {
    51.                 RetracePath();
    52.                 return;
    53.             }
    54.  
    55.             //Set Current | Remove From Open
    56.             current = openSet[0];
    57.             openSet.RemoveAtSwapBack(0);
    58.  
    59.             //Expand
    60.             foreach (var i in Grid2DUtilites.GetGrid2DNodeNeigbours(current))
    61.                 Expand(i);
    62.         }
    63.     }
    64.  
    65.     private unsafe void Expand(int2 i)
    66.     {
    67.         //Get Index
    68.         int index = Grid2DUtilites.To1D(i);
    69.  
    70.         //Check for Bounds | In Closed List | Is Solid
    71.         if (!Grid2DUtilites.IsGrid2DNodeInBounds(i) || cost[index] != 0 || Grid2DUtilites.GetGrid2DNode(i).isSolid == 1)
    72.             return;
    73.  
    74.         //Update Costing and best path
    75.         cost[index] = 1;
    76.         cameFrom[index] = current;
    77.  
    78.         //Add To Open
    79.         openSet.Add(i);
    80.     }
    81.  
    82.     private void RetracePath()
    83.     {
    84.         //New Waypoints
    85.         Grid2DPath grid2DPath = new Grid2DPath() { worldPoints = new List<float3>() };
    86.  
    87.         //Retrace Path
    88.         while (!current.Equals(grid2DPathRequest.start))
    89.         {
    90.             int index = Grid2DUtilites.To1D(current);
    91.             grid2DPath.worldPoints.Add(Grid2DUtilites.GetGrid2DNode(index).localPosition + Grid2DUtilites.Grid2D.worldPosition);
    92.             current = cameFrom[index];
    93.         }
    94.  
    95.         //Reverse path
    96.         grid2DPath.worldPoints.Reverse();
    97.  
    98.         //Add to paths found
    99.         Grid2DUtilites.AddGridPathFound(grid2DPathRequest.id, grid2DPath);
    100.     }
    101. }

    I do hate 2 questions
    -----------------------------------------------------------------------------------------------------------------------------------------------------------


    - Since I'm using NativeList for my openSet there is no "Remove" function but rather a remove "RemoveAtSwapBack" function. While the path is being found it is all weird unlike before(Image in attachments). I see you'r using a "NativeMinHeap". I'm guessing that is one of your custom Native Collections. Is there anyway to get around the RemoveAtSwapBack with whats already in Unity. I would not mind using the NativeMinHeap(Probably boost performance) but I rather not use any extensions to keep code base more clean.


    -I'm not understanding on how you reset your cost array. I have create a new array every time I want to find a path but this won't fly when moving this to a JobComponentSystem.
    Code (CSharp):
    1.  //Recrete Cost so far because we can clear Native Array
    2. cost.Dispose();
    3. cost = new NativeArray<float>(Grid2DUtilites.MaxGrid2DSize, Allocator.Persistent);

    Again thanks for all your help. Looking at your code I learned a lot about ECS and data approach.
     

    Attached Files:

    Last edited: Dec 3, 2018
  5. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    3,753
    It's annoying especially since DynamicBuffer actually has a RemoveAt(t) and RemoveRange(t, range) methods and they work pretty much the same.
    You could write your own RemoveAt(t) extension but you'd have to use some unsafe code

    Coincidentally I actually took a break from coding to read the forums and replied to this just after I had finished up writing an Insert extension method for the NativeList<T> which is quite similar.

    This is my NativeMinHeap container. Works just like other native containers, need to allocate, dispose etc.

    Code (CSharp):
    1. // <copyright file="NativeMinHeap.cs" company="Timothy Raines">
    2. //     Copyright (c) Timothy Raines. All rights reserved.
    3. // </copyright>
    4.  
    5. namespace BovineLabs.Systems.Pathfinding
    6. {
    7.     using System;
    8.  
    9.     using Unity.Collections;
    10.     using Unity.Collections.LowLevel.Unsafe;
    11.     using Unity.Mathematics;
    12.  
    13.     /// <summary>
    14.     ///     A native min heap implementation optimized for pathfinding.
    15.     /// </summary>
    16.     [NativeContainerSupportsDeallocateOnJobCompletion]
    17.     [NativeContainer]
    18.     public unsafe struct NativeMinHeap : IDisposable
    19.     {
    20.         private readonly Allocator allocator;
    21.  
    22.         [NativeDisableUnsafePtrRestriction]
    23.         private void* buffer;
    24.  
    25.         private int capacity;
    26.  
    27. #if ENABLE_UNITY_COLLECTIONS_CHECKS
    28.         private AtomicSafetyHandle m_Safety;
    29.  
    30.         [NativeSetClassTypeToNullOnSchedule]
    31.         private DisposeSentinel m_DisposeSentinel;
    32. #endif
    33.  
    34.         private int head;
    35.  
    36.         private int length;
    37.  
    38.         /// <summary>
    39.         /// Initializes a new instance of the <see cref="NativeMinHeap"/> struct.
    40.         /// </summary>
    41.         /// <param name="capacity"> The capacity of the min heap. </param>
    42.         /// <param name="allocator"> The allocator. </param>
    43.         /// <exception cref="ArgumentOutOfRangeException"> Thrown if allocator not set, capacity is negative or the size > maximum integer value. </exception>
    44.         public NativeMinHeap(int capacity, Allocator allocator)
    45.         {
    46.             var size = (long)UnsafeUtility.SizeOf<MinHeapNode>() * capacity;
    47.             if (allocator <= Allocator.None)
    48.             {
    49.                 throw new ArgumentException("Allocator must be Temp, TempJob or Persistent", nameof(allocator));
    50.             }
    51.  
    52.             if (capacity < 0)
    53.             {
    54.                 throw new ArgumentOutOfRangeException(nameof(capacity), "Length must be >= 0");
    55.             }
    56.  
    57.             if (size > int.MaxValue)
    58.             {
    59.                 throw new ArgumentOutOfRangeException(
    60.                     nameof(capacity),
    61.                     $"Length * sizeof(T) cannot exceed {int.MaxValue} bytes");
    62.             }
    63.  
    64.             this.buffer = UnsafeUtility.Malloc(size, UnsafeUtility.AlignOf<MinHeapNode>(), allocator);
    65.             this.capacity = capacity;
    66.             this.allocator = allocator;
    67.             this.head = -1;
    68.             this.length = 0;
    69.  
    70. #if ENABLE_UNITY_COLLECTIONS_CHECKS
    71.             DisposeSentinel.Create(out this.m_Safety, out this.m_DisposeSentinel, 1, allocator);
    72. #endif
    73.         }
    74.  
    75.         /// <summary>
    76.         /// Does the heap still have remaining nodes.
    77.         /// </summary>
    78.         /// <returns>
    79.         /// True if the min heap still has at least one remaining node, otherwise false.
    80.         /// </returns>
    81.         public bool HasNext()
    82.         {
    83. #if ENABLE_UNITY_COLLECTIONS_CHECKS
    84.             AtomicSafetyHandle.CheckReadAndThrow(this.m_Safety);
    85. #endif
    86.             return this.head >= 0;
    87.         }
    88.  
    89.         /// <summary>
    90.         /// Add a node to the heap which will be sorted.
    91.         /// </summary>
    92.         /// <param name="node"> The node to add. </param>
    93.         /// <exception cref="IndexOutOfRangeException"> Throws if capacity reached. </exception>
    94.         public void Push(MinHeapNode node)
    95.         {
    96. #if ENABLE_UNITY_COLLECTIONS_CHECKS
    97.             if (this.length == this.capacity)
    98.             {
    99.                 throw new IndexOutOfRangeException("Capacity Reached");
    100.             }
    101.  
    102.             AtomicSafetyHandle.CheckReadAndThrow(this.m_Safety);
    103. #endif
    104.             if (this.head < 0)
    105.             {
    106.                 this.head = this.length;
    107.             }
    108.             else if (node.ExpectedCost < this.Get(this.head).ExpectedCost)
    109.             {
    110.                 node.Next = this.head;
    111.                 this.head = this.length;
    112.             }
    113.             else
    114.             {
    115.                 var currentPtr = this.head;
    116.                 var current = this.Get(currentPtr);
    117.  
    118.                 while (current.Next >= 0 && this.Get(current.Next).ExpectedCost <= node.ExpectedCost)
    119.                 {
    120.                     currentPtr = current.Next;
    121.                     current = this.Get(current.Next);
    122.                 }
    123.  
    124.                 node.Next = current.Next;
    125.                 current.Next = this.length;
    126.  
    127.                 UnsafeUtility.WriteArrayElement(this.buffer, currentPtr, current);
    128.             }
    129.  
    130.             UnsafeUtility.WriteArrayElement(this.buffer, this.length, node);
    131.             this.length += 1;
    132.         }
    133.  
    134.         /// <summary>
    135.         /// Take the top node off the heap.
    136.         /// </summary>
    137.         /// <returns>The current node of the heap.</returns>
    138.         public MinHeapNode Pop()
    139.         {
    140. #if ENABLE_UNITY_COLLECTIONS_CHECKS
    141.             AtomicSafetyHandle.CheckWriteAndThrow(this.m_Safety);
    142. #endif
    143.             var result = this.head;
    144.             this.head = this.Get(this.head).Next;
    145.             return this.Get(result);
    146.         }
    147.  
    148.         /// <summary>
    149.         /// Clear the heap by resetting the head and length.
    150.         /// </summary>
    151.         /// <remarks>Does not clear memory.</remarks>
    152.         public void Clear()
    153.         {
    154.             this.head = -1;
    155.             this.length = 0;
    156.         }
    157.  
    158.         /// <summary>
    159.         /// Dispose of the heap by freeing up memory.
    160.         /// </summary>
    161.         /// <exception cref="InvalidOperationException"> Memory hasn't been allocated. </exception>
    162.         public void Dispose()
    163.         {
    164.             if (!UnsafeUtility.IsValidAllocator(this.allocator))
    165.             {
    166.                 return;
    167.             }
    168. #if ENABLE_UNITY_COLLECTIONS_CHECKS
    169.             DisposeSentinel.Dispose(ref this.m_Safety, ref this.m_DisposeSentinel);
    170. #endif
    171.             UnsafeUtility.Free(this.buffer, this.allocator);
    172.             this.buffer = null;
    173.             this.capacity = 0;
    174.         }
    175.  
    176.         public NativeMinHeap Slice(int start, int length)
    177.         {
    178.             var stride = UnsafeUtility.SizeOf<MinHeapNode>();
    179.  
    180.             return new NativeMinHeap()
    181.             {
    182.                 buffer = (byte*) ((IntPtr) this.buffer + stride * start),
    183.                 capacity = length,
    184.                 length = 0,
    185.                 head = -1,
    186. #if ENABLE_UNITY_COLLECTIONS_CHECKS
    187.                 m_Safety = this.m_Safety,
    188. #endif
    189.             };
    190.         }
    191.  
    192.         private MinHeapNode Get(int index)
    193.         {
    194. #if ENABLE_UNITY_COLLECTIONS_CHECKS
    195.             if (index < 0 || index >= this.length)
    196.             {
    197.                 this.FailOutOfRangeError(index);
    198.             }
    199.  
    200.             AtomicSafetyHandle.CheckReadAndThrow(this.m_Safety);
    201. #endif
    202.  
    203.             return UnsafeUtility.ReadArrayElement<MinHeapNode>(this.buffer, index);
    204.         }
    205.  
    206. #if ENABLE_UNITY_COLLECTIONS_CHECKS
    207.         private void FailOutOfRangeError(int index)
    208.         {
    209.             throw new IndexOutOfRangeException($"Index {index} is out of range of '{this.capacity}' Length.");
    210.         }
    211. #endif
    212.     }
    213.  
    214.     /// <summary>
    215.     /// The min heap node.
    216.     /// </summary>
    217.     public struct MinHeapNode
    218.     {
    219.         /// <summary>
    220.         /// Initializes a new instance of the <see cref="MinHeapNode"/> struct.
    221.         /// </summary>
    222.         /// <param name="position"> The position. </param>
    223.         /// <param name="expectedCost"> The expected cost. </param>
    224.         /// <param name="distanceToGoal">Remaining distance to the goal</param>
    225.         public MinHeapNode(int2 position, float expectedCost, float distanceToGoal)
    226.         {
    227.             this.Position = position;
    228.             this.ExpectedCost = expectedCost;
    229.             this.DistanceToGoal = distanceToGoal;
    230.             this.Next = -1;
    231.         }
    232.  
    233.         /// <summary>
    234.         /// Gets the position.
    235.         /// </summary>
    236.         public int2 Position { get; }
    237.  
    238.         /// <summary>
    239.         /// Gets the expected cost.
    240.         /// </summary>
    241.         public float ExpectedCost { get; }
    242.  
    243.         /// <summary>
    244.         /// Gets the expected cost.
    245.         /// </summary>
    246.         public float DistanceToGoal { get; }
    247.  
    248.         /// <summary>
    249.         /// Gets or sets the next node in the heap.
    250.         /// </summary>
    251.         public int Next { get; set; }
    252.     }
    253. }
    Cost array is reset here

    Code (CSharp):
    1. var buffer = costSoFar.GetUnsafePtr();
    2. UnsafeUtility.MemClear(buffer, (long)costSoFar.Length * UnsafeUtility.SizeOf<float>());
    Just doing a MemClear on the array to reset everything to 0.
    I actually use this in a few places, it's very handy and have since turned it into an extension method to hide the unsafe code.
     
    Last edited: Dec 3, 2018
  6. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    3,753
    I actually needed this today, so here is RemoveAt(int index) and RemoveRange(int index, int range) for NativeList<T> if anyone needs them. Pretty much based off the DynamicBuffer equivalent versions.

    Code (CSharp):
    1. public static void RemoveAt<T>(this NativeList<T> list, int index)
    2.             where T : struct
    3.         {
    4.             list.RemoveRange(index, 1);
    5.         }
    6.  
    7.    
    8.         public static unsafe void RemoveRange<T>(this NativeList<T> list, int index, int count)
    9.             where T : struct
    10.         {
    11. #if ENABLE_UNITY_COLLECTIONS_CHECKS
    12.             if ((uint)index >= (uint)list.Length)
    13.             {
    14.                 throw new IndexOutOfRangeException(
    15.                     $"Index {index} is out of range in NativeList of '{list.Length}' Length.");
    16.             }
    17. #endif
    18.  
    19.             int elemSize = UnsafeUtility.SizeOf<T>();
    20.             byte* basePtr = (byte*)list.GetUnsafePtr();
    21.  
    22.             UnsafeUtility.MemMove(basePtr + (index * elemSize), basePtr + ((index + count) * elemSize), elemSize * (list.Length - count - index));
    23.  
    24.             // No easy way to change length so we just loop this unfortunately.
    25.             for (var i = 0; i < count; i++)
    26.             {
    27.                 list.RemoveAtSwapBack(list.Length - 1);
    28.             }
    29.         }
    Unfortunately I have to loop the RemoveAtSwapBack to reduce the length.
     
    Last edited: Dec 3, 2018
  7. Filtiarn_

    Filtiarn_

    Joined:
    Jan 24, 2013
    Posts:
    173
    I'm not sure why Unity goes into a constant loop(freezes) if my Grid2DUtilties.grid2DpathReqeust has more than one element.

    Code (CSharp):
    1. public class Grid2DPathfindingSystem : JobComponentSystem
    2. {
    3.     private int workerCount = 8;
    4.     private NativeArray<Grid2DPathRequest> grid2DPathRequests;
    5.     private NativeList<int2> openSet;
    6.     private NativeArray<float> costs;
    7.     private NativeArray<int2> cameFroms;
    8.  
    9.     protected override void OnCreateManager()
    10.     {
    11.         int gridSize = Grid2DUtilites.GetMaxGrid2DSize();
    12.         openSet = new NativeList<int2>(gridSize, Allocator.Persistent);
    13.         costs = new NativeArray<float>(gridSize, Allocator.Persistent);
    14.         cameFroms = new NativeArray<int2>(gridSize, Allocator.Persistent);
    15.     }
    16.  
    17.  
    18.     protected override void OnDestroyManager()
    19.     {
    20.         this.openSet.Dispose();
    21.         this.costs.Dispose();
    22.         this.cameFroms.Dispose();
    23.     }
    24.  
    25.     protected override JobHandle OnUpdate(JobHandle handle)
    26.     {
    27.         if (!Grid2DUtilites.IsGrid2DInitalized() || Grid2DUtilites.grid2DPathRequests.Count == 0)
    28.             return handle;
    29.  
    30.  
    31.         int l = 0;
    32.         l = math.clamp(l,Grid2DUtilites.grid2DPathRequests.Count,workerCount);
    33.         grid2DPathRequests = new NativeArray<Grid2DPathRequest>(Grid2DUtilites.grid2DPathRequests.GetRange(0,l).ToArray(),Allocator.TempJob);
    34.  
    35.  
    36.         var findPathJob = new FindPathJob
    37.         {
    38.             grid2DPathRequests = grid2DPathRequests,
    39.             openSet = openSet,
    40.             costs = costs,
    41.             cameFroms = cameFroms
    42.         };
    43.  
    44.         //Do Job
    45.         var findPathHandle = findPathJob.Schedule(grid2DPathRequests.Length,1);
    46.         findPathHandle.Complete();
    47.  
    48.         //Dispose of grid2Dpath Request arrays
    49.         grid2DPathRequests.Dispose();
    50.         Grid2DUtilites.grid2DPathRequests.RemoveRange(0,l);
    51.  
    52.         return findPathHandle;
    53.     }
    54.  
    55.     private unsafe struct FindPathJob : IJobParallelFor
    56.     {
    57.         [ReadOnly] public NativeArray<Grid2DPathRequest> grid2DPathRequests;
    58.         [NativeDisableParallelForRestriction]
    59.         public NativeList<int2> openSet;
    60.         [NativeDisableParallelForRestriction]
    61.         public NativeArray<float> costs;
    62.         [NativeDisableParallelForRestriction]
    63.         public NativeArray<int2> cameFroms;
    64.  
    65.         public void Execute(int index)
    66.         {
    67.             //Dont find paths if there is no requests
    68.             if (!Grid2DUtilites.IsGrid2DInitalized() || Grid2DUtilites.grid2DPathRequests.Count == 0)
    69.                 return;
    70.  
    71.             //Clear open
    72.             var buffer = costs.GetUnsafePtr();
    73.             UnsafeUtility.MemClear(buffer, (long)costs.Length * UnsafeUtility.SizeOf<float>());
    74.  
    75.             //MemClear Costs
    76.             buffer = costs.GetUnsafePtr();
    77.             UnsafeUtility.MemClear(buffer, (long)costs.Length * UnsafeUtility.SizeOf<float>());
    78.  
    79.             //Clear came froms
    80.             buffer = cameFroms.GetUnsafePtr();
    81.             UnsafeUtility.MemClear(buffer, (long)cameFroms.Length * UnsafeUtility.SizeOf<float>());
    82.  
    83.             //Set Current to start | Add current to open set
    84.             int2 current = grid2DPathRequests[index].start;
    85.             openSet.Add(current);
    86.  
    87.             int iterTries = 2000;
    88.  
    89.             //Find Path
    90.             for (; ; )
    91.             {
    92.                 //Were at the End | Or open Set Count is 0
    93.                 if (current.Equals(grid2DPathRequests[index].end) || openSet.Length == 0 || iterTries == 0)
    94.                 {
    95.                     RetracePath(index, current);
    96.                     return;
    97.                 }
    98.  
    99.                 //Set Current
    100.                 current = openSet[0];
    101.                 openSet.RemoveAtSwapBack(0);
    102.  
    103.                 //Expand
    104.                 foreach (var i in Grid2DUtilites.GetNeigbours(current, grid2DPathRequests[index].canMoveDiagonal))
    105.                     Expand(i, current);
    106.              
    107.                 iterTries--;
    108.             }
    109.         }
    110.  
    111.         private unsafe void Expand(int2 i, int2 current)
    112.         {
    113.             //Get Index
    114.             int gridNodeIndex = Grid2DUtilites.To1D(i);
    115.  
    116.             //Check for Bounds | In Closed List | Is Solid
    117.             if (!Grid2DUtilites.IsGrid2DNodeInBounds(i) || costs[gridNodeIndex] != 0 || Grid2DUtilites.DoesGrid2DNodeHaveComponent(i, typeof(Grid2DSolid)))
    118.                 return;
    119.  
    120.             //Update Costing and best path
    121.             costs[gridNodeIndex] = 1;
    122.             cameFroms[gridNodeIndex] = current;
    123.  
    124.             //Add To Open | Sort
    125.             openSet.Add(i);
    126.         }
    127.  
    128.         private void RetracePath(int index, int2 current)
    129.         {
    130.             //New Waypoints
    131.             Grid2DPath grid2DPath = new Grid2DPath() { worldPoints = new List<float3>() };
    132.  
    133.             //var
    134.             var currentPosition = current;
    135.  
    136.             //Retrace Path
    137.             while (!currentPosition.Equals(grid2DPathRequests[index].start))
    138.             {
    139.                 int gridNodeIndex = Grid2DUtilites.To1D(currentPosition);
    140.                 grid2DPath.worldPoints.Add(Grid2DUtilites.GetGrid2DNodePosition(currentPosition));
    141.                 currentPosition = cameFroms[gridNodeIndex];
    142.             }
    143.  
    144.             //Add first waypoint back into path
    145.             grid2DPath.worldPoints.Add(Grid2DUtilites.GetGrid2DNodePosition(grid2DPathRequests[index].start));
    146.  
    147.             //Reverse path
    148.             grid2DPath.worldPoints.Reverse();
    149.  
    150.             //Add to paths found
    151.             Grid2DUtilites.AddGridPathFound(grid2DPathRequests[index].id, grid2DPath);
    152.         }
    153.     }
    154. }
     
  8. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    3,753
    Firstly random note,

    if (!Grid2DUtilites.IsGrid2DInitalized() || Grid2DUtilites.grid2DPathRequests.Count == 0)


    Are you meant to be using your static version of grid2DPathRequests, shouldn't you be using your local copy

    [ReadOnly] public NativeArray<Grid2DPathRequest> grid2DPathRequests;


    Otherwise what happens when your Grid2DUtilites.grid2DPathRequests changes when you're in your job (also burst doesn't like static values if you start using it.)

    Onto the actual problem you have, every thread seems to be writing to the points in the array.

    Code (CSharp):
    1.         public NativeList<int2> openSet;
    2.         public NativeArray<float> costs;
    3.         public NativeArray<int2> cameFroms;
    Code (CSharp):
    1. openSet.Add(current);
    2. costs[gridNodeIndex] = 1;
    3. cameFroms[gridNodeIndex] = current;
    This means each of your pathfinding algorithms are overriding other. I suspect when you have 2 paths it's causing the path to be invalid and being put into a infinite loop.

    You need to declare your arrays to be X * size required, where X is the maximum workers (threads) then slice them.

    This is what I'm doing here.

    Code (CSharp):
    1. var costSoFar = this.CostSoFar.Slice(index * size, size);
    2. var cameFrom = this.CameFrom.Slice(index * size, size);
    3. var openSetSize = (this.Iterations + 1) * NeighbourCount;
    4. var openSet = this.OpenSet.Slice(index * openSetSize, openSetSize);
    So first thread uses 0 -> size of array, next thread uses size -> size*2 etc
     
    Last edited: Dec 4, 2018
  9. Filtiarn_

    Filtiarn_

    Joined:
    Jan 24, 2013
    Posts:
    173
    Ok before I read your post I saw some things I should have fixed. Here they are. I cleaned up MemClear and got rid of the check in Job. That was supposed to be. taken out
    Code (CSharp):
    1. if (!Grid2DUtilites.IsGrid2DInitalized() || Grid2DUtilites.grid2DPathRequests.Count == 0)
    2.             return handle;
    Code (CSharp):
    1. using System;
    2. using System.Collections;
    3. using Unity.Burst;
    4. using Unity.Jobs;
    5. using Unity.Collections;
    6. using Unity.Collections.LowLevel.Unsafe;
    7. using Unity.Entities;
    8. using Unity.Mathematics;
    9. using Unity.Transforms;
    10. using UnityEngine;
    11. using System.Collections.Generic;
    12.  
    13. public class Grid2DPathfindingSystem : JobComponentSystem
    14. {
    15.     private int workerCount = 8;
    16.     private NativeArray<Grid2DPathRequest> grid2DPathRequests;
    17.     private NativeList<int2> openSet;
    18.     private NativeArray<float> costs;
    19.     private NativeArray<int2> cameFroms;
    20.  
    21.     protected override void OnCreateManager()
    22.     {
    23.         int gridSize = Grid2DUtilites.GetMaxGrid2DSize();
    24.         openSet = new NativeList<int2>(gridSize * workerCount, Allocator.Persistent);
    25.         costs = new NativeArray<float>(gridSize * workerCount, Allocator.Persistent);
    26.         cameFroms = new NativeArray<int2>(gridSize * workerCount, Allocator.Persistent);
    27.     }
    28.  
    29.  
    30.     protected override void OnDestroyManager()
    31.     {
    32.         this.openSet.Dispose();
    33.         this.costs.Dispose();
    34.         this.cameFroms.Dispose();
    35.     }
    36.  
    37.     protected unsafe override JobHandle OnUpdate(JobHandle handle)
    38.     {
    39.         if (!Grid2DUtilites.IsGrid2DInitalized() || Grid2DUtilites.grid2DPathRequests.Count == 0)
    40.             return handle;
    41.  
    42.         //Copy jobs to to Native Array
    43.         int l = 0;
    44.         l = math.clamp(l, Grid2DUtilites.grid2DPathRequests.Count, workerCount);
    45.         grid2DPathRequests = new NativeArray<Grid2DPathRequest>(Grid2DUtilites.grid2DPathRequests.GetRange(0, l).ToArray(), Allocator.TempJob);
    46.  
    47.         //MemClear Costs
    48.         var buffer = costs.GetUnsafePtr();
    49.         UnsafeUtility.MemClear(buffer, (long)costs.Length * UnsafeUtility.SizeOf<float>());
    50.  
    51.         //Create Job
    52.         var findPathJob = new FindPathJob
    53.         {
    54.             grid2DPathRequests = grid2DPathRequests,
    55.             openSet = openSet,
    56.             costs = costs,
    57.             cameFroms = cameFroms
    58.         };
    59.  
    60.         //Do Job
    61.         var findPathHandle = findPathJob.Schedule(l, 1);
    62.         findPathHandle.Complete();
    63.  
    64.         //Dispose of grid2Dpath Request arrays
    65.         grid2DPathRequests.Dispose();
    66.         Grid2DUtilites.grid2DPathRequests.RemoveRange(0, l);
    67.  
    68.         return findPathHandle;
    69.     }
    70.  
    71.     private unsafe struct FindPathJob : IJobParallelFor
    72.     {
    73.         [ReadOnly] public NativeArray<Grid2DPathRequest> grid2DPathRequests;
    74.         [NativeDisableParallelForRestriction]
    75.         public NativeList<int2> openSet;
    76.         [NativeDisableParallelForRestriction]
    77.         public NativeArray<float> costs;
    78.         [NativeDisableParallelForRestriction]
    79.         public NativeArray<int2> cameFroms;
    80.  
    81.         public void Execute(int index)
    82.         {
    83.             //Set Current to start | Add current to open set
    84.             int2 current = grid2DPathRequests[index].start;
    85.             openSet.Add(current);
    86.  
    87.             //Find Path
    88.             for (; ; )
    89.             {
    90.                 //Were at the End | Or open Set Count is 0
    91.                 if (current.Equals(grid2DPathRequests[index].end) || openSet.Length == 0)
    92.                 {
    93.                     RetracePath(index, current);
    94.                     return;
    95.                 }
    96.  
    97.                 //Set Current
    98.                 current = openSet[0];
    99.                 openSet.RemoveAtSwapBack(0);
    100.  
    101.                 //Expand
    102.                 foreach (var i in Grid2DUtilites.GetNeigbours(current, grid2DPathRequests[index].canMoveDiagonal))
    103.                     Expand(index,i, current);
    104.             }
    105.         }
    106.  
    107.         private unsafe void Expand(int index, int2 i, int2 current)
    108.         {
    109.             //Get Index
    110.             int gridNodeIndex = Grid2DUtilites.To1D(i) * (index + 1);
    111.  
    112.             //Check for Bounds | In Closed List | Is Solid
    113.             if (!Grid2DUtilites.IsGrid2DNodeInBounds(i) || costs[gridNodeIndex] != 0 || Grid2DUtilites.DoesGrid2DNodeHaveComponent(i, typeof(Grid2DSolid)))
    114.                 return;
    115.  
    116.             //Update Costing and best path
    117.             costs[gridNodeIndex] = 1;
    118.             cameFroms[gridNodeIndex] = current;
    119.  
    120.             //Add To Open | Sort
    121.             openSet.Add(i);
    122.         }
    123.  
    124.         private void RetracePath(int index, int2 current)
    125.         {
    126.             //New Waypoints
    127.             Grid2DPath grid2DPath = new Grid2DPath() { worldPoints = new List<float3>() };
    128.  
    129.             //var
    130.             var currentPosition = current;
    131.  
    132.             //Retrace Path
    133.             while (!currentPosition.Equals(grid2DPathRequests[index].start))
    134.             {
    135.                 int gridNodeIndex = Grid2DUtilites.To1D(currentPosition) * (index + 1);
    136.                 grid2DPath.worldPoints.Add(Grid2DUtilites.GetGrid2DNodePosition(currentPosition));
    137.                 currentPosition = cameFroms[gridNodeIndex];
    138.             }
    139.  
    140.             //Add first waypoint back into path
    141.             grid2DPath.worldPoints.Add(Grid2DUtilites.GetGrid2DNodePosition(grid2DPathRequests[index].start));
    142.  
    143.             //Reverse path
    144.             grid2DPath.worldPoints.Reverse();
    145.  
    146.             //Add to paths found
    147.             Grid2DUtilites.AddGridPathFound(grid2DPathRequests[index].id, grid2DPath);
    148.         }
    149.     }
    150. }
     
  10. Filtiarn_

    Filtiarn_

    Joined:
    Jan 24, 2013
    Posts:
    173
    First let me thank you for taking time out of your days to help me out. I do feel kinda dumb about the whole overriding thing and that I did not catch it :(. I got it working but with one minor bug and one concern.

    First this is what I changed other than just the Grid2DPathfindingSystem(Directly from GitHub)
    Code (CSharp):
    1.  
    2. -Rewrote Grid2DUtilites to be alot less bloated
    3. -Grid2DPathfindingSystem now uses a custom heap for pathfinding(This may change) given by tertle on unity forums here https://forum.unity.com/threads/ecs-grid2d-pathfinding-example-and-feedback-on-how-to-improve.591523/
    4. -Rewrote Grid2DInitalizeSystem to be much much faster. Can create grids that are 5000x5000 in less than 2 seconds
    5. -Readded option to have diagonal or straight paths that was taken out in last rewrite
    6. -Rewrote how Grid2D Nodes work.
    7.      -Grid2DNode is now a blank sharedComponentData that acts like a tag.
    8.      -Positions are generated when creating a path and rendering(WIP by far) rather than being stored in Grid2DNodeComponen
    9.       which should save data.
    10.      -Grid2D nodes are now solid when having a  blank shared component called Grid2DSolidComponent
    Grid2DIntalizeSystem

    Code (CSharp):
    1. using Unity.Burst;
    2. using Unity.Collections;
    3. using Unity.Entities;
    4. using Unity.Mathematics;
    5. using Unity.Transforms;
    6. using UnityEngine;
    7.  
    8. public class Grid2DInitalizeSystem : ComponentSystem
    9. {
    10.     protected override void OnCreateManager()
    11.     {
    12.         //Get Entity Manager
    13.         var entityManager = Unity.Entities.World.Active.GetOrCreateManager<EntityManager>();
    14.  
    15.         //Create Source
    16.         Entity grid2dNodeEntitySource = entityManager.CreateEntity();
    17.         entityManager.AddSharedComponentData(grid2dNodeEntitySource,new Grid2DNode());
    18.  
    19.         //Create Grid
    20.         Grid2DUtilites.grid2DEntity = entityManager.CreateEntity(typeof(Grid2D));
    21.    
    22.         //Create Grid Nodes
    23.         Grid2DUtilites.grid2DNodeEntities = new NativeArray<Entity>(Grid2DUtilites.GetMaxGrid2DSize(),Allocator.Persistent);
    24.         entityManager.Instantiate(grid2dNodeEntitySource,Grid2DUtilites.grid2DNodeEntities);
    25.  
    26.         //Destroy Source
    27.         entityManager.DestroyEntity(grid2dNodeEntitySource);
    28.     }
    29.  
    30.     protected override void OnDestroyManager()
    31.     {
    32.         //Destroy Entity
    33.         Grid2DUtilites.grid2DNodeEntities.Dispose();
    34.     }
    35.  
    36.     protected override void OnUpdate()
    37.     {
    38.         //Only need to run once
    39.         Enabled = false;
    40.     }
    41. }
    Grid2DPathfindgSystem

    So for the minor bug is I'm using a bool called loadedPathToPreventCrash. If I try to find more than one path the first time I request paths I get a infinite loop. Any time after that everything is fine. I tried loading 300 paths at once and it had no problem after loading the first blank path.

    The concern is does JobHandle OnUpdate only run when there is not Job running? If not then what happens if I request more paths while old ones are not done yet. Is this a problem? Would I need to write something to keep track if any paths are being calculated? From my testing it does not seem to be a problem

    Also I'm not using the static grid2DPathRequests in Job but just pulling requests from that into the grid2DPathRequests Native array in the system.

    Code (CSharp):
    1. using System;
    2. using System.Collections;
    3. using Unity.Burst;
    4. using Unity.Jobs;
    5. using Unity.Collections;
    6. using Unity.Collections.LowLevel.Unsafe;
    7. using Unity.Entities;
    8. using Unity.Mathematics;
    9. using Unity.Transforms;
    10. using UnityEngine;
    11. using System.Collections.Generic;
    12.  
    13. [UpdateAfter(typeof(UnityEngine.Experimental.PlayerLoop.PostLateUpdate))]
    14. public class Grid2DPathfindingSystem : JobComponentSystem
    15. {
    16.     private NativeArray<Grid2DPathRequest> grid2DPathRequests;
    17.     private Grid2DNativeMinHeap openSet;
    18.     private NativeArray<float> costs;
    19.     private NativeArray<int2> cameFroms;
    20.     private NativeArray<Grid2DNativeMinHeapNode> currents;
    21.     private int grid2DSize = 0;
    22.     private const int workerCount = 8;
    23.     private int grid2DPathRequestsLength = 0;
    24.     private bool loadedPathToPreventCrash;
    25.  
    26.     protected override void OnCreateManager()
    27.     {
    28.         grid2DSize = Grid2DUtilites.GetMaxGrid2DSize();
    29.         openSet = new Grid2DNativeMinHeap(grid2DSize * workerCount, Allocator.Persistent);
    30.         costs = new NativeArray<float>(grid2DSize * workerCount, Allocator.Persistent);
    31.         cameFroms = new NativeArray<int2>(grid2DSize * workerCount, Allocator.Persistent);
    32.         currents = new NativeArray<Grid2DNativeMinHeapNode>(workerCount, Allocator.Persistent);
    33.     }
    34.  
    35.     protected override void OnDestroyManager()
    36.     {
    37.         openSet.Dispose();
    38.         costs.Dispose();
    39.         cameFroms.Dispose();
    40.         currents.Dispose();
    41.     }
    42.  
    43.     protected unsafe override JobHandle OnUpdate(JobHandle handle)
    44.     {
    45.         //Dont Run if we have not Intalized Grid2D | No path requests
    46.         if (!Grid2DUtilites.IsGrid2DInitalized()) return handle;
    47.         if (Grid2DUtilites.grid2DPathRequests.Count == 0 && loadedPathToPreventCrash) return handle;
    48.  
    49.  
    50.  
    51.         //Create Temp Request Array
    52.         if (loadedPathToPreventCrash)
    53.         {
    54.             grid2DPathRequestsLength = Grid2DUtilites.grid2DPathRequests.Count;
    55.             grid2DPathRequestsLength = math.clamp(grid2DPathRequestsLength, 0, workerCount);
    56.             grid2DPathRequests = new NativeArray<Grid2DPathRequest>(grid2DPathRequestsLength, Allocator.TempJob);
    57.             for (int i = 0; i < grid2DPathRequestsLength; i++)
    58.                 grid2DPathRequests[i] = Grid2DUtilites.grid2DPathRequests[i];
    59.         }
    60.         else
    61.         {
    62.             grid2DPathRequestsLength = 1;
    63.             grid2DPathRequests = new NativeArray<Grid2DPathRequest>(grid2DPathRequestsLength, Allocator.TempJob);
    64.             grid2DPathRequests[0] = new Grid2DPathRequest() {start = new int2(0,0), end = new int2(0,0)};
    65.         }
    66.  
    67.  
    68.         //Clear Costs | OpenSet
    69.         var buffer = costs.GetUnsafePtr();
    70.         UnsafeUtility.MemClear(buffer, (long)costs.Length * UnsafeUtility.SizeOf<float>());
    71.         openSet.Clear();
    72.  
    73.         //Create Job
    74.         var findPathJob = new FindPathJob
    75.         {
    76.             grid2DPathRequests = grid2DPathRequests,
    77.             openSet = openSet,
    78.             costs = costs,
    79.             cameFroms = cameFroms,
    80.             currents = currents,
    81.             grid2DSize = grid2DSize
    82.  
    83.         };
    84.  
    85.         //Do Job
    86.         var findPathHandle = findPathJob.Schedule(grid2DPathRequestsLength, 1);
    87.         findPathHandle.Complete();
    88.  
    89.         //Dispose Request Array
    90.         if (loadedPathToPreventCrash)
    91.             Grid2DUtilites.grid2DPathRequests.RemoveRange(0, grid2DPathRequestsLength);
    92.         grid2DPathRequests.Dispose();
    93.  
    94.         //Set loaded path to prevent crash to true
    95.         loadedPathToPreventCrash = true;
    96.  
    97.         //Return Job Handle
    98.         return findPathHandle;
    99.    
    100.     }
    101.  
    102.     private unsafe struct FindPathJob : IJobParallelFor
    103.     {
    104.         [ReadOnly] public NativeArray<Grid2DPathRequest> grid2DPathRequests;
    105.         [NativeDisableParallelForRestriction]
    106.         public Grid2DNativeMinHeap openSet;
    107.         [NativeDisableParallelForRestriction]
    108.         public NativeArray<float> costs;
    109.         [NativeDisableParallelForRestriction]
    110.         public NativeArray<int2> cameFroms;
    111.         [NativeDisableParallelForRestriction]
    112.         public NativeArray<Grid2DNativeMinHeapNode> currents;
    113.         public int grid2DSize;
    114.  
    115.  
    116.         public void Execute(int index)
    117.         {
    118.             var openSetSlice = openSet.Slice(index * grid2DSize, grid2DSize);
    119.  
    120.             //Set Current to start | Add current to open set
    121.             openSetSlice.Push(new Grid2DNativeMinHeapNode(grid2DPathRequests[index].start, 0));
    122.  
    123.             //Find Path
    124.             for (; ; )
    125.             {
    126.                 //Were at the End | Or open Set Count is 0
    127.                 if (currents[index].position.Equals(grid2DPathRequests[index].end) || !openSetSlice.HasNext())
    128.                 {
    129.                     RetracePath(index);
    130.                     return;
    131.                 }
    132.  
    133.                 //Set Current
    134.                 currents[index] = openSetSlice.Pop();
    135.  
    136.                 //Expand
    137.                 foreach (var i in Grid2DUtilites.GetNeigbours(currents[index].position, grid2DPathRequests[index].canMoveDiagonal))
    138.                     Expand(index, i, ref openSetSlice);
    139.  
    140.                 iterMax--;
    141.             }
    142.         }
    143.  
    144.         private unsafe void Expand(int index, int2 i, ref Grid2DNativeMinHeap openSetSlice)
    145.         {
    146.             //Get Index
    147.             int grid2DNodeIndex = GetGrid2DNodeIndex(index, i);
    148.  
    149.             //Check for Bounds | In Closed List | Is Solid
    150.             if (!Grid2DUtilites.IsGrid2DNodeInBounds(i) || costs[grid2DNodeIndex] != 0 || Grid2DUtilites.DoesGrid2DNodeHaveComponent(i, typeof(Grid2DSolid)))
    151.                 return;
    152.  
    153.             //Update Costing and best path
    154.             costs[grid2DNodeIndex] = 1;
    155.             cameFroms[grid2DNodeIndex] = currents[index].position;
    156.  
    157.             //Add To Open | Sort
    158.             openSetSlice.Push(new Grid2DNativeMinHeapNode(i, 0));
    159.         }
    160.  
    161.         private void RetracePath(int index)
    162.         {
    163.             //New Waypoints
    164.             Grid2DPath grid2DPath = new Grid2DPath() { worldPoints = new List<float3>() };
    165.  
    166.             //var
    167.             var currentPosition = currents[index].position;
    168.  
    169.             //Retrace Path
    170.             while (!currentPosition.Equals(grid2DPathRequests[index].start))
    171.             {
    172.                 grid2DPath.worldPoints.Add(Grid2DUtilites.GetGrid2DNodePosition(currentPosition));
    173.                 currentPosition = cameFroms[GetGrid2DNodeIndex(index, currentPosition)];
    174.             }
    175.  
    176.             //Add first waypoint back into path
    177.             grid2DPath.worldPoints.Add(Grid2DUtilites.GetGrid2DNodePosition(grid2DPathRequests[index].start));
    178.  
    179.             //Reverse path
    180.             grid2DPath.worldPoints.Reverse();
    181.  
    182.             //Add to paths found
    183.             Grid2DUtilites.AddGridPathFound(grid2DPathRequests[index].id, grid2DPath);
    184.         }
    185.  
    186.         private int GetGrid2DNodeIndex(int index, int2 i)
    187.         {
    188.             return index * grid2DSize + Grid2DUtilites.To1D(i);
    189.         }
    190.     }
    191. }
     
    Last edited: Dec 5, 2018