**EDIT Here is an update on progress. I am moving it to the top for visibility
Optimization and cleanup may still be needed, please feel free to contribute.
Any input, feedback, problems or recommendations is always appreciated.
This was created strongly using examples from @tertle pathfinding that he shared to the forums, converted to IJobChunk. Thank you again, for your help.
Initializer for testing
Initializer Code
namespace Pathfinding
{
public class InitializePathfinding : MonoBehaviour
{
//Options
public int2 size;
public bool showGrid;
public bool showPaths;
public bool canMoveDiag;
public Color pathColor;
//Manual Path
[HideInInspector] public Vector2Int start;
[HideInInspector] public Vector2Int end;
[HideInInspector] public bool searchManualPath;
//Random Path
[HideInInspector] public int numOfRandomPaths;
[HideInInspector] public bool searchRandomPaths;
//Manual blocked
List<int2> blockedNodes = new List<int2>();
[HideInInspector] public Vector2Int blockedNode;
[HideInInspector] public bool addManualBlockedNode;
//Random blocked
[HideInInspector] public int numbOfRandomBlockedNodes = 1;
[HideInInspector] public bool addRandomBlockedNode;
int previousSize; // Prevent GUI Errors
private void Awake()
{
World.Active.GetExistingSystem<PathfindingSystem>().canMoveDiag = canMoveDiag;
CreateGrid();
}
private void Update()
{
if(size.x * size.y != previousSize)
{
CreateGrid();
}
if(addManualBlockedNode)
{
blockedNodes.Add(new int2(blockedNode.x, blockedNode.y));
addManualBlockedNode = false;
CreateGrid();
}
if(searchManualPath)
{
CreateSearcher(new int2(start.x, start.y), new int2(end.x, end.y));
searchManualPath = false;
}
if (addRandomBlockedNode)
{
addRandomBlockedNode = false;
CreateBlockedNodes();
}
if(searchRandomPaths)
{
searchRandomPaths = false;
for (int i = 0; i < numOfRandomPaths; i++)
{
CreateSearcher(new int2(Random.Range(0, size.x), Random.Range(0, size.y)), new int2(Random.Range(0, size.x), Random.Range(0, size.y)));
}
}
}
public void CreateBlockedNodes()
{
EntityManager entityManager = World.Active.EntityManager;
var cells = RequiredExtensions.cells;
for (int i = 0; i < numbOfRandomBlockedNodes; i++)
{
int randomCell = Random.Range(0, size.x * size.y);
cells[randomCell] = new Cell { blocked = Convert.ToByte(true), Height = 0 };
}
}
public void CreateSearcher(int2 s, int2 e)
{
EntityManager entityManager = World.Active.EntityManager;
var pathSearcher = entityManager.CreateEntity(typeof(PathRequest), typeof(Translation), typeof(NavigationCapabilities));
var trans = entityManager.GetComponentData<Translation>(pathSearcher);
trans.Value = new float3(s.x, s.y, 0);
entityManager.SetComponentData<Translation>(pathSearcher, trans);
entityManager.AddBuffer<Waypoint>(pathSearcher);
PathRequest pathRequest = new PathRequest
{
Entity = pathSearcher,
start = s,
end = e,
Destination = NodeToWorldPosition(e),
NavigateToBestIfIncomplete = true,
NavigateToNearestIfBlocked = true
};
entityManager.SetComponentData(pathSearcher, pathRequest);
}
private void OnDisable()
{
RequiredExtensions.cells.Dispose();
}
public void CreateGrid()
{
if(RequiredExtensions.cells.IsCreated)
RequiredExtensions.cells.Dispose();
RequiredExtensions.cells = new Unity.Collections.NativeArray<Cell>(size.x * size.y, Unity.Collections.Allocator.Persistent);
previousSize = size.x * size.y;
for (int y = 0; y < size.y; y++)
{
for (int x = 0; x < size.x; x++)
{
Cell cell = new Cell
{
blocked = Convert.ToByte(blockedNodes.Contains(new int2(x, y)))
};
RequiredExtensions.cells[GetIndex(new int2(x, y))] = cell;
}
}
World.Active.GetExistingSystem<PathfindingSystem>().worldSize = size;
}
void OnDrawGizmos()
{
if (!showGrid && !showPaths) return;
if (Application.isPlaying)
{
if (showGrid && size.x * size.y == previousSize)
{
var cells = RequiredExtensions.cells;
for (int x = 0; x < size.x; x++)
{
for (int y = 0; y < size.y; y++)
{
Gizmos.color = cells[GetIndex(new int2(x, y))].Blocked ? Color.grey : Color.white;
Gizmos.DrawCube(NodeToWorldPosition(new int2(x, y)), new Vector3(.90f, .90f));
}
}
}
if (showPaths)
{
EntityManager entityManager = World.Active.EntityManager;
var query = entityManager.CreateEntityQuery(ComponentType.ReadOnly<Waypoint>());
if (query.CalculateEntityCount() > 0)
{
var actualGroup = query.ToEntityArray(Unity.Collections.Allocator.TempJob);
foreach (Entity entity in actualGroup)
{
var buffer = entityManager.GetBuffer<Waypoint>(entity);
if (buffer.Length > 0)
{
Gizmos.color = pathColor;
for (int i = 0; i < buffer.Length - 1; i++)
{
Gizmos.DrawLine(buffer[i].waypoints - .5f, buffer[i + 1].waypoints - .5f);
}
}
}
actualGroup.Dispose();
}
}
}
}
public float3 NodeToWorldPosition(int2 i) => new float3(i.x, i.y, 0);
int GetIndex(int2 i)
{
if (size.y >= size.x)
return (i.x * size.y) + i.y;
else
return (i.y * size.x) + i.x;
}
}
}
Pathfinding Job
Pathfinding Job Code
namespace Pathfinding
{
public class PathfindingSystem : JobComponentSystem
{
NativeArray<Neighbour> neighbours;
EntityQuery pathRequests;
const int IterationLimit = 1000;
public int2 worldSize;
public bool canMoveDiag;
protected override void OnCreate()
{
pathRequests = GetEntityQuery(typeof(Waypoint), ComponentType.ReadOnly<PathRequest>(), ComponentType.ReadOnly<Translation>(), ComponentType.ReadOnly<NavigationCapabilities>());
pathRequests.SetFilterChanged(typeof(PathRequest));
if (canMoveDiag)
{
neighbours = new NativeArray<Neighbour>(8, Allocator.Persistent)
{
[0] = new Neighbour(-1, -1), // Bottom left
[1] = new Neighbour(0, -1), // Bottom
[2] = new Neighbour(1, -1), // Bottom Right
[3] = new Neighbour(-1, 0), // Left
[4] = new Neighbour(1, 0), // Right
[5] = new Neighbour(-1, 1), // Top Left
[6] = new Neighbour(0, 1), // Top
[7] = new Neighbour(1, 1), // Top Right
};
}
else
{
neighbours = new NativeArray<Neighbour>(4, Allocator.Persistent)
{
[0] = new Neighbour(0, -1), // Bottom
[1] = new Neighbour(-1, 0), // Left
[2] = new Neighbour(1, 0), // Right
[3] = new Neighbour(0, 1), // Top
};
}
}
protected override void OnDestroy()
{
neighbours.Dispose();
}
protected override JobHandle OnUpdate(JobHandle inputDeps)
{
int numberOfRequests = pathRequests.CalculateChunkCount();
if (numberOfRequests == 0) return inputDeps;
//Schedule the findPath to build <Waypoints> Job
FindPathJobChunk findPathJob = new FindPathJobChunk()
{
WaypointChunkBuffer = GetArchetypeChunkBufferType<Waypoint>(false),
PathRequestsChunkComponent = GetArchetypeChunkComponentType<PathRequest>(true),
CellArray = RequiredExtensions.cells,
TranslationsChunkComponent = GetArchetypeChunkComponentType<Translation>(true),
NavigationCapabilitiesChunkComponent = GetArchetypeChunkComponentType<NavigationCapabilities>(true),
Neighbors = neighbours,
DimY = worldSize.y,
DimX = worldSize.x,
Iterations = IterationLimit,
NeighborCount = neighbours.Length
};
JobHandle jobHandle = findPathJob.Schedule(pathRequests, inputDeps);
return jobHandle;
}
[BurstCompile]
struct FindPathJobChunk : IJobChunk
{
[ReadOnly] public int DimX;
[ReadOnly] public int DimY;
[ReadOnly] public int Iterations;
[ReadOnly] public int NeighborCount;
[ReadOnly] public NativeArray<Cell> CellArray;
[WriteOnly] public ArchetypeChunkBufferType<Waypoint> WaypointChunkBuffer;
[ReadOnly] public ArchetypeChunkComponentType<PathRequest> PathRequestsChunkComponent;
[ReadOnly] public NativeArray<Neighbour> Neighbors;
[ReadOnly] public ArchetypeChunkComponentType<Translation> TranslationsChunkComponent;
[ReadOnly] public ArchetypeChunkComponentType<NavigationCapabilities> NavigationCapabilitiesChunkComponent;
public void Execute(ArchetypeChunk chunk, int chunkIndex, int firstEntityIndex)
{
int size = DimX * DimY;
BufferAccessor<Waypoint> Waypoints = chunk.GetBufferAccessor(WaypointChunkBuffer);
NativeArray<PathRequest> PathRequests = chunk.GetNativeArray(PathRequestsChunkComponent);
NativeArray<Translation> Translations = chunk.GetNativeArray(TranslationsChunkComponent);
NativeArray<NavigationCapabilities> NavigationCapabilities = chunk.GetNativeArray(NavigationCapabilitiesChunkComponent);
NativeArray<float> CostSoFar = new NativeArray<float>(size * chunk.Count, Allocator.Temp);
NativeArray<int2> CameFrom = new NativeArray<int2>(size * chunk.Count, Allocator.Temp);
NativeMinHeap OpenSet = new NativeMinHeap((Iterations + 1) * Neighbors.Length * chunk.Count, Allocator.Temp);
for (int i = chunkIndex; i < chunk.Count; i++)
{
NativeSlice<float> costSoFar = CostSoFar.Slice(i * size, size);
NativeSlice<int2> cameFrom = CameFrom.Slice(i * size, size);
int openSetSize = (Iterations + 1) * NeighborCount;
NativeMinHeap openSet = OpenSet.Slice(i * openSetSize, openSetSize);
PathRequest request = PathRequests[i];
Translation currentPosition = Translations[i];
NavigationCapabilities capability = NavigationCapabilities[i];
// cache these as they're used a lot
int2 start = currentPosition.Value.xy.FloorToInt();
int2 goal = request.end;
DynamicBuffer<float3> waypoints = Waypoints[i].Reinterpret<float3>();
waypoints.Clear();
// Special case when the start is the same point as the goal
if (start.Equals(goal))
{
// We just set the destination as the goal, but need to get the correct height
int gridIndex = this.GetIndex(goal);
Cell cell = CellArray[gridIndex];
float3 point = new float3(request.Destination.x, request.Destination.y, cell.Height);
waypoints.Add(point);
continue;
}
var stash = new InstanceStash
{
Grid = CellArray,
CameFrom = cameFrom,
CostSoFar = costSoFar,
OpenSet = openSet,
Request = request,
Capability = capability,
CurrentPosition = currentPosition,
Start = start,
Goal = goal,
Waypoints = waypoints,
};
if (this.ProcessPath(ref stash))
this.ReconstructPath(stash);
}
CostSoFar.Dispose();
CameFrom.Dispose();
OpenSet.Dispose();
}
static float H(float2 p0, float2 p1)
{
float dx = p0.x - p1.x;
float dy = p0.y - p1.y;
float sqr = (dx * dx) + (dy * dy);
return math.sqrt(sqr);
}
bool ProcessPath(ref InstanceStash stash)
{
// Push the start to NativeMinHeap openSet
float hh = H(stash.Start, stash.Goal);
MinHeapNode head = new MinHeapNode(stash.Start, hh, hh);
stash.OpenSet.Push(head);
int iterations = this.Iterations;
MinHeapNode closest = head;
// While we still have potential nodes to explore
while (stash.OpenSet.HasNext())
{
MinHeapNode current = stash.OpenSet.Pop();
if (current.DistanceToGoal < closest.DistanceToGoal)
closest = current;
// Found our goal
if (current.Position.Equals(stash.Goal))
return true;
// Path might still be obtainable but we've run out of allowed iterations
if (iterations == 0)
{
if (stash.Request.NavigateToBestIfIncomplete)
{
// Return the best result we've found so far
// Need to update goal so we can reconstruct the shorter path
stash.Goal = closest.Position;
return true;
}
return false;
}
iterations--;
var initialCost = stash.CostSoFar[this.GetIndex(current.Position)];
var fromIndex = this.GetIndex(current.Position);
// Loop our potential cells - generally neighbours but could include portals
for (var i = 0; i < this.Neighbors.Length; i++)
{
var neighbour = this.Neighbors[i];
var position = current.Position + neighbour.Offset;
// Make sure the node isn't outside our grid
if (position.x < 0 || position.x >= this.DimX || position.y < 0 || position.y >= this.DimY)
continue;
var index = this.GetIndex(position);
// Get the cost of going to this cell
var cellCost = this.GetCellCost(stash.Grid, stash.Capability, fromIndex, index, neighbour, true);
// Infinity means the cell is un-walkable, skip it
if (float.IsInfinity(cellCost))
continue;
var newCost = initialCost + (neighbour.Distance * cellCost);
var oldCost = stash.CostSoFar[index];
// If we've explored this cell before and it was a better path, ignore this route
if (!(oldCost <= 0) && !(newCost < oldCost))
continue;
// Update the costing and best path
stash.CostSoFar[index] = newCost;
stash.CameFrom[index] = current.Position;
// Push the node onto our heap
var h = H(position, stash.Goal);
var expectedCost = newCost + h;
stash.OpenSet.Push(new MinHeapNode(position, expectedCost, h));
}
}
if (stash.Request.NavigateToNearestIfBlocked)
{
stash.Goal = closest.Position;
return true;
}
// All routes have been explored without finding a route to destination
return false;
}
void ReconstructPath(InstanceStash stash)
{
var current = stash.CameFrom[this.GetIndex(stash.Goal)];
var from = this.GetPosition(stash.Grid, current);
stash.Waypoints.Add(from);
var next = this.GetPosition(stash.Grid, current);
while (!current.Equals(stash.Start))
{
current = stash.CameFrom[this.GetIndex(current)];
var tmp = next;
next = this.GetPosition(stash.Grid, current);
if (!this.IsWalkable(stash.Grid, from.xy, next.xy))
{
// skip
stash.Waypoints.Add(tmp);
from = tmp;
}
}
stash.Waypoints.Reverse();
stash.Request.fufilled = true;
}
bool IsWalkable(NativeArray<Cell> buffer, float2 from, float2 to)
{
const float step = 0.25f;
var vector = to - from;
var length = math.length(vector);
var unit = vector / length;
var iterations = length / step;
var currentCell = buffer[this.GetIndex(from.FloorToInt())];
for (var i = 0; i < iterations; i++)
{
var point = (i * step * unit) + from;
var index = this.GetIndex(point.FloorToInt());
var cell = buffer[index];
if (cell.Blocked)
return false;
if (cell.Height != currentCell.Height)
return false;
}
return true;
}
float GetCellCost(NativeArray<Cell> grid, NavigationCapabilities capabilities, int fromIndex, int toIndex, Neighbour neighbour, bool areNeighbours)
{
var target = grid[toIndex];
if (target.Blocked)
return float.PositiveInfinity;
// If we're not neighbours, then we're a portal and can just go straight there
if (!areNeighbours)
return 1;
var from = grid[fromIndex];
var heightDiff = target.Height - from.Height;
var absDiff = math.abs(heightDiff);
// TODO Should precompute this
var dropHeight = 0;
var climbHeight = 0;
if (heightDiff > 0)
climbHeight = absDiff;
else
dropHeight = absDiff;
var slope = math.degrees(math.atan(absDiff / neighbour.Distance));
// TODO End precompute
if ((capabilities.MaxClimbHeight < climbHeight || capabilities.MaxDropHeight < dropHeight) &&
capabilities.MaxSlopeAngle < slope)
return float.PositiveInfinity;
return 1;
}
float3 GetPosition(NativeArray<Cell> grid, int2 point)
{
var index = this.GetIndex(point);
var cell = grid[index];
var fPoint = point + new float2(0.5f, 0.5f);
return new float3(fPoint.x, fPoint.y, cell.Height);
}
int GetIndex(int2 i)
{
if (DimY >= DimX)
return (i.x * DimY) + i.y;
else
return (i.y * DimX) + i.x;
}
struct InstanceStash
{
public Translation CurrentPosition;
public PathRequest Request;
public NavigationCapabilities Capability;
public DynamicBuffer<float3> Waypoints;
public int2 Start;
public int2 Goal;
public NativeArray<Cell> Grid;
public NativeSlice<float> CostSoFar;
public NativeSlice<int2> CameFrom;
public NativeMinHeap OpenSet;
}
}
}
}
— Old Original question starts here —
Content from original post
Greetings all, I have recently started researching and moving my project to ECS for performance and organization reasons, and have really had an enjoyable time. The performance boost is just insane, and it feels like an entirely different level of complexity in programming.
I normally shy away from asking forum questions and help in general, as I think most resources are out there on subjects and the answers can be found with enough searching… but in this particular scenario I have struggled to find what I think I need.
I have searched through numerous sites and forum posts to try to find a close enough example to reference for use in my own project, but have fallen short as I feel like people are taking the easy way out, or maybe I am just over-complicating things. I am still newer to complex programming, so its very possible that the later is the case.
A few months ago when I started I originally wanted a simple solution to pathfinding because I knew it was more advanced than I was ready for, so I started with using arongranberg’s A* pathfinding project. This allowed me to simply set a grid size, flip a few Boolean’s, and rotate 90 degrees and I could toss a few scripts on Game Objects and I had resolved the problem for the time being. Later on I researched and built my own system, but never put it in place because I knew performance wouldn’t be as good, and I wanted to make the leap to ECS anyway.
I am now trying to create a solution in Pure ECS for 2d grid based A* pathfinding, and I have a few questions about what I have found so far. First I was wondering what the current best standard likely is for this scenario if there is one. I have seen many people posts with people taking their already in place NavMesh systems or other Pathfinding and converting portions of it to ECS, while still keeping the core content on the Game Objects in the Scene. The large majority of posts on any subject has been 3D, but not a lot on 2D, which I assume is because its much easier dealing with 2D grid, so less questions. In my case overall I am aiming for an almost zero Game Object approach. From the start I choose 2D thinking its the easy way out and the best way to start learning, but I feel cheated on the amount of compatibly unity provides, or the difficulty to make 2D compatible.
I have considered the following and would like to know the best option…
- Create a system where each node is Essentially an Entity holding the ComponentData that I may normally have in a node struct.
- Create a single Entity buffer and attempt to keep all nodes in that entity.
- Use a NativeHashMap to search through entities (Obstacles or Blocked paths) that actually exist in quadrants and just avoid them by offsetting transforms (Doesn’t seem like its going to go well)
- Use NavMeshPlus to use the built in systems converted to work for 2D, have a hybrid ECS approach, and have to keep all entities in sync with game objects (My least favorite and likely easiest?)
I have looked at the three following forum posts along with others, and they have helped me gather some concepts of what I am supposed to do, but I am also a little hesitant to dive into them because I see the “Unsafe” word getting tossed around a lot, and I am a little worried about production with this.
100,000 entities traversing navmesh (3D using Navmesh)
Pathfinding & ECS
ECS Grid2D Pathfinding Example and feedback on how to improve (Using Entites as Nodes, also using much more than needed)
Along with many comments in other posts by @tertle , @jdtec , @Antypodish , @zulfajuniadi
These guys have been a really great help and its amazing to see the support they provide publicly for others.
I have also seen a few external sites, but I am not sure the policy on posting those, so I will hold off on that.
-Dave
