Search Unity

RTS Pathfinding and unit spacing

Discussion in 'Data Oriented Technology Stack' started by MadboyJames, Sep 19, 2019.

  1. MadboyJames

    MadboyJames

    Joined:
    Oct 28, 2017
    Posts:
    159
    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?
     
  2. Abbrew

    Abbrew

    Joined:
    Jan 1, 2018
    Posts:
    166
    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):
    1. [BurstCompile]
    2.     private struct SubProblemBatchPathfind : IJob
    3.     {
    4.         [ReadOnly]
    5.         public NativeArray<int2> destinations;
    6.  
    7.         public int2 finder;
    8.         public int gridDimX;
    9.         public int gridDimY;
    10.         public int2 worldOffset;
    11.         public int nodeSize;
    12.         public int maxPathLength;
    13.         public int heapCapacity;
    14.  
    15.         public PhysicsConverter converter;
    16.  
    17.         [ReadOnly]
    18.         public NativeArray<MapNodeResult> mapGrid;
    19.         [ReadOnly]
    20.         public NativeArray<int> weights;
    21.  
    22.         [DeallocateOnJobCompletion]
    23.         public NativeArray<int> costsSoFar;
    24.  
    25.         [DeallocateOnJobCompletion]
    26.         public NativeArray<int> lengthSoFar;
    27.         [DeallocateOnJobCompletion]
    28.         public NativeArray<int2> cameFrom;
    29.         [DeallocateOnJobCompletion]
    30.         public NativeArray<int> heapIndices;
    31.  
    32.         [WriteOnly]
    33.         public NativeList<byte> successes;
    34.         public NativeList<int2> results;
    35.         public NativeList<int> resultsLengthsIncremental;
    36.  
    37.         public void Execute()
    38.         {
    39.             var startGridLocation = WorldToChunk(finder);
    40.             var requestsLength = destinations.Length;
    41.             if(requestsLength == 0)
    42.             {
    43.                 return;
    44.             }
    45.             var remainingGridDestinations = new NativeHashMap<int2, byte>(requestsLength, Allocator.Temp);
    46.  
    47.             var originalIndices = new NativeHashMap<int2, int>(requestsLength, Allocator.Temp);
    48.  
    49.             var remainingDestinationsSortable = new NativeArray<int2>(requestsLength, Allocator.Temp);
    50.             var alignedDestinations = new NativeArray<int2>(requestsLength, Allocator.Temp);
    51.             var gridToWorldCoords = new NativeHashMap<int2, int2>(requestsLength, Allocator.Temp);
    52.             for (int i = 0; i < requestsLength; i++)
    53.             {
    54.                 var alignedDestination = AlignWorldCoord(destinations[i]);
    55.                 remainingGridDestinations.TryAdd(WorldToChunk(alignedDestination), 0);
    56.                 gridToWorldCoords.TryAdd(WorldToChunk(alignedDestination), alignedDestination);
    57.                 originalIndices.TryAdd(alignedDestination, i);
    58.                 remainingDestinationsSortable[i] = alignedDestination;
    59.                 alignedDestinations[i] = alignedDestination;
    60.             }
    61.             remainingDestinationsSortable.Sort(new FurthestComparer
    62.             {
    63.                 start = finder
    64.             });
    65.             var remainingDestinationsQueue = new NativeList<int2>(Allocator.Temp);
    66.             for (int i = requestsLength - 1; i >= 0; i--)
    67.             {
    68.                 var destination = AlignWorldCoord(remainingDestinationsSortable[i]);
    69.                 remainingDestinationsQueue.Add(destination);
    70.             }
    71.  
    72.             var destinationToFirstIndex = new NativeHashMap<int2, int>(requestsLength, Allocator.Temp);
    73.             var firstSuccesses = new NativeList<byte>(Allocator.Temp);
    74.             var firstResults = new NativeList<int2>(Allocator.Temp);
    75.             var firstResultLengths = new NativeList<int>(Allocator.Temp);
    76.             var firstResultLengthsIncremental = new NativeList<int>(Allocator.Temp);
    77.  
    78.             int* pathCounter = (int*)UnsafeUtility.Malloc(
    79.                 sizeof(int), sizeof(int), Allocator.Temp
    80.             );
    81.             *pathCounter = 0;
    82.  
    83.             do
    84.             {
    85.                 var destination = default(int2);
    86.                 var needsToBeComputed = false;
    87.                 do
    88.                 {
    89.                     var position = remainingDestinationsQueue.Length - 1;
    90.                     destination = remainingDestinationsQueue[position];
    91.                     remainingDestinationsQueue.RemoveAt(position);
    92.                     needsToBeComputed =
    93.                         remainingGridDestinations.TryGetValue(WorldToChunk(destination), out _);
    94.                 } while (remainingGridDestinations.Length != 0 && !needsToBeComputed);
    95.  
    96.                 remainingGridDestinations.Remove(WorldToChunk(destination));
    97.  
    98.                 if (needsToBeComputed)
    99.                 {
    100.                     var endGridLocation = WorldToChunk(destination);
    101.                     FindPath(
    102.                         startGridLocation,
    103.                         endGridLocation,
    104.                         destination,
    105.                         remainingGridDestinations,
    106.                         destinationToFirstIndex,
    107.                         gridToWorldCoords,
    108.                         firstSuccesses,
    109.                         firstResults,
    110.                         firstResultLengths,
    111.                         firstResultLengthsIncremental,
    112.                         pathCounter
    113.                     );
    114.                 }
    115.             } while (remainingGridDestinations.Length != 0);
    116.  
    117.             for (int i = 0; i < requestsLength; i++)
    118.             {
    119.                 var destination = alignedDestinations[i];
    120.                 destinationToFirstIndex.TryGetValue(destination, out var indexInFirst);
    121.                 successes.Add(firstSuccesses[indexInFirst]);
    122.                 var firstResultLength = firstResultLengths[indexInFirst];
    123.                 var resultsLengthsIncrementalLength = resultsLengthsIncremental.Length;
    124.                 resultsLengthsIncremental.Add(
    125.                     firstResultLength + (resultsLengthsIncrementalLength == 0 ? 0 : resultsLengthsIncremental[resultsLengthsIncrementalLength - 1])
    126.                 );
    127.                 var start = indexInFirst == 0 ? 0 : firstResultLengthsIncremental[indexInFirst - 1];
    128.                 var end = firstResultLengthsIncremental[indexInFirst];
    129.  
    130.                 //var prev = default(int2);
    131.                 for (int j = start; j < end; j++)
    132.                 {
    133.                     results.Add(firstResults[j]);
    134.  
    135.                     //if(j > start && prev.DistanceFrom(firstResults[j]) > 3)
    136.                     //{
    137.                     //    Debug.Log(prev + " " + firstResults[j] + " " + i + " " + j + " " + destination);
    138.                     //}
    139.                     //prev = firstResults[j];
    140.                 }
    141.             }
    142.             //PathfinderVisualizer.Visualize();
    143.         }
    144.  
    145.         private int2 AlignWorldCoord(int2 worldCoord)
    146.         {
    147.             var x = worldCoord.x;
    148.             var y = worldCoord.y;
    149.             x = (x - (x % nodeSize)) + nodeSize / 2;
    150.             y = (y - (y % nodeSize)) + nodeSize / 2;
    151.             return new int2(x, y);
    152.         }
    153.  
    154.         private struct FurthestComparer : IComparer<int2>
    155.         {
    156.             public int2 start;
    157.  
    158.             public int Compare(int2 x, int2 y)
    159.             {
    160.                 return -(x.DistanceFrom(start) - y.DistanceFrom(start));
    161.             }
    162.         }
    163.  
    164.         private void FindPath(
    165.             int2 start,
    166.             int2 end,
    167.             int2 originalEnd,
    168.             NativeHashMap<int2, byte> remainingGridDestinations,
    169.             NativeHashMap<int2, int> destinationToFirstIndex,
    170.             NativeHashMap<int2,int2> gridToWorldCoords,
    171.             NativeList<byte> firstSuccesses,
    172.             NativeList<int2> firstResults,
    173.             NativeList<int> firstResultsLengths,
    174.             NativeList<int> firstResultsLengthsIncremental,
    175.             int* pathCounter
    176.         )
    177.         {
    178.             //// Debugging
    179.             ///
    180.             var costsSoFarPtr = costsSoFar.GetUnsafePtr();
    181.             UnsafeUtility.MemClear(costsSoFarPtr, (long)costsSoFar.Length * UnsafeUtility.SizeOf<int>());
    182.             var cameFromPtr = cameFrom.GetUnsafePtr();
    183.             UnsafeUtility.MemClear(cameFromPtr, (long)cameFrom.Length * UnsafeUtility.SizeOf<int2>());
    184.             var lengthSoFarPtr = lengthSoFar.GetUnsafePtr();
    185.             UnsafeUtility.MemClear(lengthSoFarPtr, (long)lengthSoFar.Length * UnsafeUtility.SizeOf<int>());
    186.             for(int i = 0; i < heapIndices.Length; i++)
    187.             {
    188.                 heapIndices[i] = -1;
    189.             }
    190.  
    191.             var neighbors = CreateNeighbors();
    192.  
    193.             if (start.Equals(end))
    194.             {
    195.                 //Debug.Log("failed due to same start and end");
    196.                 FailedPath(
    197.                     originalEnd,
    198.                     destinationToFirstIndex,
    199.                     firstSuccesses,
    200.                     firstResultsLengths,
    201.                     firstResultsLengthsIncremental,
    202.                     pathCounter
    203.                 );
    204.                 return;
    205.             }
    206.  
    207.             var gridSize = gridDimX * gridDimY;
    208.             var head = new PathfinderNode(start, 0, H(start, end),0,0);
    209.             var openSet = new PathfinderHeap(gridSize);
    210.             var closedSet = new NativeHashMap<int2, byte>(gridSize,Allocator.Temp);
    211.             openSet.Add(head);
    212.             while (openSet.Count > 0)
    213.             {
    214.                 var current = openSet.RemoveFirst();
    215.                 var currentPosition = current.Position;
    216.                 var currentGridIndex = GetGridIndex(current.Position);
    217.  
    218.                 closedSet.TryAdd(current.Position, 0);
    219.  
    220.                 if (lengthSoFar[currentGridIndex] > maxPathLength)
    221.                 {
    222.                     continue;
    223.                 }
    224.  
    225.                 if (current.Position.Equals(end))
    226.                 {
    227.                     //Debug.Log("succeeded");
    228.                     //PathfinderVisualizer.Done();
    229.                     TraceAndAddPath(
    230.                         start,
    231.                         end,
    232.                         originalEnd,
    233.                         destinationToFirstIndex,
    234.                         firstSuccesses,
    235.                         firstResults,
    236.                         firstResultsLengths,
    237.                         firstResultsLengthsIncremental,
    238.                         pathCounter
    239.                     );
    240.                     return;
    241.                 }
    242.  
    243.                 if (remainingGridDestinations.TryGetValue(current.Position, out _))
    244.                 {
    245.                     //Debug.Log("suboptimal succeeded: " + gridToWorldCoords[current.Position]);
    246.                     remainingGridDestinations.Remove(current.Position);
    247.                     TraceAndAddPath(
    248.                         start,
    249.                         current.Position,
    250.                         gridToWorldCoords[current.Position],
    251.                         destinationToFirstIndex,
    252.                         firstSuccesses,
    253.                         firstResults,
    254.                         firstResultsLengths,
    255.                         firstResultsLengthsIncremental,
    256.                         pathCounter
    257.                     );
    258.                 }
    259.                 var initialCost = current.GCost;
    260.                 var neighborLength = neighbors.Length;
    261.                 //Debug.Log(initialCost);
    262.  
    263.                 for (int i = 0; i < neighborLength; i ++)
    264.                 {
    265.                     var neighbor = neighbors[i];
    266.                     var neighbourLocation = current.Position + neighbor.offset;
    267.                     if(neighbourLocation.x < 0 || neighbourLocation.x >= gridDimX
    268.                         || neighbourLocation.y < 0 || neighbourLocation.y >= gridDimY)
    269.                     {
    270.                         continue;
    271.                     }
    272.  
    273.  
    274.                     var neighborIndex = GetGridIndex(neighbourLocation);
    275.                     var neighborNode = mapGrid[neighborIndex];
    276.                     if (neighborNode.isWalkable == 0
    277.                         || closedSet.TryGetValue(neighbourLocation, out _))
    278.                     {
    279.                         continue;
    280.                     }
    281.  
    282.  
    283.  
    284.                     var newStrategyCost =
    285.                         GetCellCost(currentGridIndex, neighborIndex, true);
    286.                     var newPhysicalGCost = current.GCost + neighbor.cost;
    287.                     var newMovementCostToNeighbour =
    288.                         newPhysicalGCost + newStrategyCost;
    289.  
    290.                     var heapIndex = heapIndices[neighborIndex];
    291.                     var newNeighborNode =
    292.                         new PathfinderNode(
    293.                             neighbourLocation,
    294.                             newPhysicalGCost,
    295.                             H(neighbourLocation,end),
    296.                             newStrategyCost,
    297.                             //0,
    298.                             heapIndex
    299.                         );
    300.  
    301.                     if (newMovementCostToNeighbour < current.GCost || !openSet.Contains(newNeighborNode))
    302.                     {
    303.                         cameFrom[neighborIndex] = current.Position;
    304.                         lengthSoFar[neighborIndex] = lengthSoFar[currentGridIndex] + 1;
    305.  
    306.                         if (!openSet.Contains(newNeighborNode))
    307.                         {
    308.                             var newIndex = openSet.Add(newNeighborNode);
    309.                             heapIndices[neighborIndex] = newIndex;
    310.                             //PathfinderVisualizer.Visit(ChunkToWorld(newNeighborNode.Position));
    311.                         }
    312.                         else
    313.                         {
    314.                             //Debug.Log("Updating");
    315.                             var newIndex = openSet.UpdateItem(newNeighborNode);
    316.                             heapIndices[neighborIndex] = newIndex;
    317.                         }
    318.                     }
    319.                 }
    320.             }
    321.             //PathfinderVisualizer.Done();
    322.  
    323.            // Debug.Log("failed");
    324.             FailedPath(
    325.                 originalEnd,
    326.                 destinationToFirstIndex,
    327.                 firstSuccesses,
    328.                 firstResultsLengths,
    329.                 firstResultsLengthsIncremental,
    330.                 pathCounter
    331.             );
    332.         }
    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
     
    MadboyJames likes this.
  3. jdtec

    jdtec

    Joined:
    Oct 25, 2017
    Posts:
    89
    MadboyJames likes this.
  4. pal_trefall

    pal_trefall

    Joined:
    Feb 5, 2019
    Posts:
    40
    Maybe there's something useful to mine from this video as well:
     
    MadboyJames likes this.
  5. eizenhorn

    eizenhorn

    Joined:
    Oct 17, 2016
    Posts:
    1,521
    MadboyJames and MostHated like this.
  6. MadboyJames

    MadboyJames

    Joined:
    Oct 28, 2017
    Posts:
    159
    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. :)
     
    pal_trefall likes this.