RTS Pathfinding and unit spacing

MadboyJames · Sep 19, 2019

What do people think would be the best way to implement an entity based pathfinding system+unit spacing?
Currently I only have simple movement (click on ground, translate to point), and then all my units condense into a single point like a horrifying singularity. And then my framerate crashes when they all shoot from the same position. I don't know if a navMesh and navAgents are performent with entities, or how to implement them.

So, any ideas, suggestions, resource links, or miscellaneous information/ opinions?

Abbrew · Sep 19, 2019

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.

Code (CSharp):

[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

jdtec · Sep 20, 2019

There are some good ideas pertaining specifically to spacing in this article https://www.gamasutra.com/blogs/And..._Pathfinding__Movement_in_RTS_Style_Games.php

pal_trefall · Sep 20, 2019

Maybe there's something useful to mine from this video as well:

eizenhorn · Sep 20, 2019

Just look at my pinned post in this forum branch, on second page I discribe our approach with links to papers.
https://forum.unity.com/threads/unity-ecs-and-job-system-in-production.561229/page-2

At bottom you can see latest actual gameplay and how navigation looks (and compare how it's evolved through development)

MadboyJames · Sep 21, 2019

Thank you all for your responses! @pal_trefall I have been following CodeMonkey's videos to help me out, but I'm shooting for a more comprehensive pathfinding system (ideally replicating what Warcraft I, II, III and Starcraft I and II have). On that note, @eizenhorn what you showcased is pretty much exactly what I am trying to accomplish with regards to mass unit movement and structure/ obstacle avoidance. @jdtec Thanks for the link! That is a very helpful DYI solution, which I may end up implementing. Right now I'm hoping I can utilize some optimized pathfinding solutions rather than building my own. @Abbrew I used code from the A* Project (Basic) when I needed pathfinding for classic gameObjects. So I'll see if I can get that to work.

Search Unity

Unity ID

Useful Searches

RTS Pathfinding and unit spacing

MadboyJames

Abbrew

jdtec

pal_trefall

eizenhorn

MadboyJames