Search Unity

Pathfinding In A Dynamic World

Discussion in 'Scripting' started by Zavalichi, Apr 15, 2019.

  1. Zavalichi

    Zavalichi

    Joined:
    Oct 13, 2018
    Posts:
    162
    Hi guys,

    Have you use a pathfinding algorithm in your games?
    I have a graph with over 5000 waypoints (nodes). The cost between two nodes is the last time taken by a car to drive from these nodes, so this cost is updated all time.

    For now I am using a dijsktra algorithm but it seems to be expensive (14 seconds), do you know any optimisation method or another algorithm?
     
  2. ensiferum888

    ensiferum888

    Joined:
    May 11, 2013
    Posts:
    265
    Maybe switch to A* instead of Dijsktra? It's exactly the same thing but uses heuristics to speed it up. But running a Dijsktra on 5000 nodes should be faster.. My game map is a grid of 1 048 576 nodes and it takes about 2 seconds at most to get a path from the furthest points apart.
     
    lordofduct likes this.
  3. Zavalichi

    Zavalichi

    Joined:
    Oct 13, 2018
    Posts:
    162
    So, my dijsktra should be faster than 2 seconds ?...
     
  4. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    6,775
    Well it'd be hard to say how many seconds it should take considering that it depends on the performance of the system you're running it on.

    But yeah, dijkstra should faster technically... assuming you're on a mid-range contemporary computer. What does your code for dijkstra look like?

    With that said though... I'd still upgrade to A*. It's nearly the same algorithm, just with heuristics added. This way it checks for routes to the goal since it tries to pick a route that heuristically is closer before it tests those farther. This means A* on average should solve quicker unless you just happen to be on a map that always has you needing to backtrack/move away from the goal, to get to the goal.
     
  5. Zavalichi

    Zavalichi

    Joined:
    Oct 13, 2018
    Posts:
    162
    Code (CSharp):
    1.  public static List<Waypoint> Dijsktra(Waypoint start, Waypoint end)
    2.     {
    3.         // We don't accept null arguments
    4.         if (start == null || end == null)
    5.             return null;
    6.  
    7.         // The final path
    8.         List<Waypoint> path = new List<Waypoint>();
    9.  
    10.         // If the start and end are same node, we can return the start node
    11.         if (start == end)
    12.         {
    13.             path.Add(start);
    14.             return path;
    15.         }
    16.  
    17.         // The list of unvisited nodes
    18.         List<Waypoint> unvisited = new List<Waypoint>();
    19.  
    20.         // Previous nodes in optimal path from source
    21.         Dictionary<Waypoint, Waypoint> previous = new Dictionary<Waypoint, Waypoint>();
    22.  
    23.         // The calculated distances, set all to Infinity at start, except the start Node
    24.         Dictionary<Waypoint, float> distances = new Dictionary<Waypoint, float>();
    25.  
    26.         for (int i = 0; i < Graph.Count; i++)
    27.         {
    28.             Waypoint node;
    29.             node = Graph[i];
    30.             unvisited.Add(node);
    31.  
    32.             // Setting the node distance to Infinity
    33.             distances.Add(node, float.MaxValue);
    34.         }
    35.  
    36.         // Set the starting Node distance to zero
    37.         distances[start] = 0f;
    38.  
    39.         while (unvisited.Count != 0)
    40.         {
    41.             // Ordering the unvisited list by distance, smallest distance at start and largest at end
    42.             unvisited = unvisited.OrderBy(node => distances[node]).ToList();
    43.  
    44.             // Getting the Node with smallest distance
    45.             Waypoint current = unvisited[0];
    46.  
    47.             // Remove the current node from unvisisted list
    48.             unvisited.Remove(current);
    49.  
    50.             // When the current node is equal to the end node, then we can break and return the path
    51.             if (current == end)
    52.             {
    53.                 // Construct the shortest path
    54.                 while (previous.ContainsKey(current))
    55.                 {
    56.                     // Insert the node onto the final result
    57.                     path.Insert(0, current);
    58.  
    59.                     // Traverse from start to end
    60.                     current = previous[current];
    61.                 }
    62.  
    63.                 // Insert the source onto the final result
    64.                 path.Insert(0, current);
    65.                 break;
    66.             }
    67.  
    68.             // Looping through the Node connections (neighbors) and where the connection (neighbor) is available at unvisited list
    69.             for (int i = 0; i < current.Nodes.Count; i++)
    70.             {
    71.  
    72.                 Waypoint neighbor = current.Nodes[i].Waypoint;
    73.  
    74.                 // Getting the distance between the current node and the connection (neighbor)
    75.                 float length = current.Nodes[i].Distance;
    76.  
    77.                 // The distance from start node to this connection (neighbor) of current node
    78.                 float fullLength = distances[current] + length;
    79.  
    80.                 // A shorter path to the connection (neighbor) has been found
    81.                 if (fullLength < distances[neighbor])
    82.                 {
    83.                     distances[neighbor] = fullLength;
    84.                     previous[neighbor] = current;
    85.                 }
    86.             }
    87.         }
    88.         return path;
    89.     }
     
  6. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    6,775
    So for starters I can see some major memory over-usage in your implementation. You create lists willy nilly. You even create a new list every time you sort 'unvisited' instead of sorting the existing list in place. This is very costly not just on the GC, but because every time you create a list the code has to iterate the existing collection and fill said new list.

    So that 'OrderBy' is doing the large number of operations to order that list, but then tacking on the iteration of filling the new list.

    There are other optimizations I would suggest. Like using a BinaryHeap instead of a list for the unvisited collection, which does shorter sorts on entry of items. But implementing a BinaryHeap at this point is probably a bit much when just reducing all that list creation would probably save you a bunch.

    To give you an example here are my Dijkstra and A* implementations:

    Dijkstra:
    https://github.com/lordofduct/space.../SPPathfinding/Graphs/DijkstraPathResolver.cs

    A*:
    https://github.com/lordofduct/space...ter/SPPathfinding/Graphs/AStarPathResolver.cs
     
    SparrowsNest likes this.