What I did was implement my own pathfinding system with its own grid. When choosing destinations, have a single-threaded job pick open spots, one at a time. This will result in a cluster of destinations. You can then trace all the paths required, and during movement, only advance a unit one cell forward if it’s unoccupied. Here’s code for a batch pathfinding job based on @tertle 's pathfinding job.
[BurstCompile]
private struct SubProblemBatchPathfind : IJob
{
[ReadOnly]
public NativeArray<int2> destinations;
public int2 finder;
public int gridDimX;
public int gridDimY;
public int2 worldOffset;
public int nodeSize;
public int maxPathLength;
public int heapCapacity;
public PhysicsConverter converter;
[ReadOnly]
public NativeArray<MapNodeResult> mapGrid;
[ReadOnly]
public NativeArray<int> weights;
[DeallocateOnJobCompletion]
public NativeArray<int> costsSoFar;
[DeallocateOnJobCompletion]
public NativeArray<int> lengthSoFar;
[DeallocateOnJobCompletion]
public NativeArray<int2> cameFrom;
[DeallocateOnJobCompletion]
public NativeArray<int> heapIndices;
[WriteOnly]
public NativeList<byte> successes;
public NativeList<int2> results;
public NativeList<int> resultsLengthsIncremental;
public void Execute()
{
var startGridLocation = WorldToChunk(finder);
var requestsLength = destinations.Length;
if(requestsLength == 0)
{
return;
}
var remainingGridDestinations = new NativeHashMap<int2, byte>(requestsLength, Allocator.Temp);
var originalIndices = new NativeHashMap<int2, int>(requestsLength, Allocator.Temp);
var remainingDestinationsSortable = new NativeArray<int2>(requestsLength, Allocator.Temp);
var alignedDestinations = new NativeArray<int2>(requestsLength, Allocator.Temp);
var gridToWorldCoords = new NativeHashMap<int2, int2>(requestsLength, Allocator.Temp);
for (int i = 0; i < requestsLength; i++)
{
var alignedDestination = AlignWorldCoord(destinations[i]);
remainingGridDestinations.TryAdd(WorldToChunk(alignedDestination), 0);
gridToWorldCoords.TryAdd(WorldToChunk(alignedDestination), alignedDestination);
originalIndices.TryAdd(alignedDestination, i);
remainingDestinationsSortable[i] = alignedDestination;
alignedDestinations[i] = alignedDestination;
}
remainingDestinationsSortable.Sort(new FurthestComparer
{
start = finder
});
var remainingDestinationsQueue = new NativeList<int2>(Allocator.Temp);
for (int i = requestsLength - 1; i >= 0; i--)
{
var destination = AlignWorldCoord(remainingDestinationsSortable[i]);
remainingDestinationsQueue.Add(destination);
}
var destinationToFirstIndex = new NativeHashMap<int2, int>(requestsLength, Allocator.Temp);
var firstSuccesses = new NativeList<byte>(Allocator.Temp);
var firstResults = new NativeList<int2>(Allocator.Temp);
var firstResultLengths = new NativeList<int>(Allocator.Temp);
var firstResultLengthsIncremental = new NativeList<int>(Allocator.Temp);
int* pathCounter = (int*)UnsafeUtility.Malloc(
sizeof(int), sizeof(int), Allocator.Temp
);
*pathCounter = 0;
do
{
var destination = default(int2);
var needsToBeComputed = false;
do
{
var position = remainingDestinationsQueue.Length - 1;
destination = remainingDestinationsQueue[position];
remainingDestinationsQueue.RemoveAt(position);
needsToBeComputed =
remainingGridDestinations.TryGetValue(WorldToChunk(destination), out _);
} while (remainingGridDestinations.Length != 0 && !needsToBeComputed);
remainingGridDestinations.Remove(WorldToChunk(destination));
if (needsToBeComputed)
{
var endGridLocation = WorldToChunk(destination);
FindPath(
startGridLocation,
endGridLocation,
destination,
remainingGridDestinations,
destinationToFirstIndex,
gridToWorldCoords,
firstSuccesses,
firstResults,
firstResultLengths,
firstResultLengthsIncremental,
pathCounter
);
}
} while (remainingGridDestinations.Length != 0);
for (int i = 0; i < requestsLength; i++)
{
var destination = alignedDestinations[i];
destinationToFirstIndex.TryGetValue(destination, out var indexInFirst);
successes.Add(firstSuccesses[indexInFirst]);
var firstResultLength = firstResultLengths[indexInFirst];
var resultsLengthsIncrementalLength = resultsLengthsIncremental.Length;
resultsLengthsIncremental.Add(
firstResultLength + (resultsLengthsIncrementalLength == 0 ? 0 : resultsLengthsIncremental[resultsLengthsIncrementalLength - 1])
);
var start = indexInFirst == 0 ? 0 : firstResultLengthsIncremental[indexInFirst - 1];
var end = firstResultLengthsIncremental[indexInFirst];
//var prev = default(int2);
for (int j = start; j < end; j++)
{
results.Add(firstResults[j]);
//if(j > start && prev.DistanceFrom(firstResults[j]) > 3)
//{
// Debug.Log(prev + " " + firstResults[j] + " " + i + " " + j + " " + destination);
//}
//prev = firstResults[j];
}
}
//PathfinderVisualizer.Visualize();
}
private int2 AlignWorldCoord(int2 worldCoord)
{
var x = worldCoord.x;
var y = worldCoord.y;
x = (x - (x % nodeSize)) + nodeSize / 2;
y = (y - (y % nodeSize)) + nodeSize / 2;
return new int2(x, y);
}
private struct FurthestComparer : IComparer<int2>
{
public int2 start;
public int Compare(int2 x, int2 y)
{
return -(x.DistanceFrom(start) - y.DistanceFrom(start));
}
}
private void FindPath(
int2 start,
int2 end,
int2 originalEnd,
NativeHashMap<int2, byte> remainingGridDestinations,
NativeHashMap<int2, int> destinationToFirstIndex,
NativeHashMap<int2,int2> gridToWorldCoords,
NativeList<byte> firstSuccesses,
NativeList<int2> firstResults,
NativeList<int> firstResultsLengths,
NativeList<int> firstResultsLengthsIncremental,
int* pathCounter
)
{
//// Debugging
///
var costsSoFarPtr = costsSoFar.GetUnsafePtr();
UnsafeUtility.MemClear(costsSoFarPtr, (long)costsSoFar.Length * UnsafeUtility.SizeOf<int>());
var cameFromPtr = cameFrom.GetUnsafePtr();
UnsafeUtility.MemClear(cameFromPtr, (long)cameFrom.Length * UnsafeUtility.SizeOf<int2>());
var lengthSoFarPtr = lengthSoFar.GetUnsafePtr();
UnsafeUtility.MemClear(lengthSoFarPtr, (long)lengthSoFar.Length * UnsafeUtility.SizeOf<int>());
for(int i = 0; i < heapIndices.Length; i++)
{
heapIndices[i] = -1;
}
var neighbors = CreateNeighbors();
if (start.Equals(end))
{
//Debug.Log("failed due to same start and end");
FailedPath(
originalEnd,
destinationToFirstIndex,
firstSuccesses,
firstResultsLengths,
firstResultsLengthsIncremental,
pathCounter
);
return;
}
var gridSize = gridDimX * gridDimY;
var head = new PathfinderNode(start, 0, H(start, end),0,0);
var openSet = new PathfinderHeap(gridSize);
var closedSet = new NativeHashMap<int2, byte>(gridSize,Allocator.Temp);
openSet.Add(head);
while (openSet.Count > 0)
{
var current = openSet.RemoveFirst();
var currentPosition = current.Position;
var currentGridIndex = GetGridIndex(current.Position);
closedSet.TryAdd(current.Position, 0);
if (lengthSoFar[currentGridIndex] > maxPathLength)
{
continue;
}
if (current.Position.Equals(end))
{
//Debug.Log("succeeded");
//PathfinderVisualizer.Done();
TraceAndAddPath(
start,
end,
originalEnd,
destinationToFirstIndex,
firstSuccesses,
firstResults,
firstResultsLengths,
firstResultsLengthsIncremental,
pathCounter
);
return;
}
if (remainingGridDestinations.TryGetValue(current.Position, out _))
{
//Debug.Log("suboptimal succeeded: " + gridToWorldCoords[current.Position]);
remainingGridDestinations.Remove(current.Position);
TraceAndAddPath(
start,
current.Position,
gridToWorldCoords[current.Position],
destinationToFirstIndex,
firstSuccesses,
firstResults,
firstResultsLengths,
firstResultsLengthsIncremental,
pathCounter
);
}
var initialCost = current.GCost;
var neighborLength = neighbors.Length;
//Debug.Log(initialCost);
for (int i = 0; i < neighborLength; i ++)
{
var neighbor = neighbors[i];
var neighbourLocation = current.Position + neighbor.offset;
if(neighbourLocation.x < 0 || neighbourLocation.x >= gridDimX
|| neighbourLocation.y < 0 || neighbourLocation.y >= gridDimY)
{
continue;
}
var neighborIndex = GetGridIndex(neighbourLocation);
var neighborNode = mapGrid[neighborIndex];
if (neighborNode.isWalkable == 0
|| closedSet.TryGetValue(neighbourLocation, out _))
{
continue;
}
var newStrategyCost =
GetCellCost(currentGridIndex, neighborIndex, true);
var newPhysicalGCost = current.GCost + neighbor.cost;
var newMovementCostToNeighbour =
newPhysicalGCost + newStrategyCost;
var heapIndex = heapIndices[neighborIndex];
var newNeighborNode =
new PathfinderNode(
neighbourLocation,
newPhysicalGCost,
H(neighbourLocation,end),
newStrategyCost,
//0,
heapIndex
);
if (newMovementCostToNeighbour < current.GCost || !openSet.Contains(newNeighborNode))
{
cameFrom[neighborIndex] = current.Position;
lengthSoFar[neighborIndex] = lengthSoFar[currentGridIndex] + 1;
if (!openSet.Contains(newNeighborNode))
{
var newIndex = openSet.Add(newNeighborNode);
heapIndices[neighborIndex] = newIndex;
//PathfinderVisualizer.Visit(ChunkToWorld(newNeighborNode.Position));
}
else
{
//Debug.Log("Updating");
var newIndex = openSet.UpdateItem(newNeighborNode);
heapIndices[neighborIndex] = newIndex;
}
}
}
}
//PathfinderVisualizer.Done();
// Debug.Log("failed");
FailedPath(
originalEnd,
destinationToFirstIndex,
firstSuccesses,
firstResultsLengths,
firstResultsLengthsIncremental,
pathCounter
);
}
It works by finding paths at the furthest destination from the start, and whenever it encounters another destination on the way, it adds that path to a list, preventing unnecessary pathfinding attempts
