Pathfinding In A Dynamic World

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?

 

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.

 

So, my dijsktra should be faster than 2 seconds ?...

 

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.

 

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.     }

 

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