Pathfinding - Eishaaya/GMRDataStructuresTest GitHub Wiki

Finding the Best Path

Pathfinding is the calculation of a route between two given vertices. Pathfinding is used in many applications of computer science; examples include road mapping and network flow. Basic algorithms such as Breadth-First and Depth-First search find a path between two vertices by exhausting all possible possibilities. Though the paths they generate are normally sub-optimal. The following are two common pathfinding algorithms for finding the fastest path in weighted graphs. These algorithms and more can be tested at this visualizer.

Dijkstra's Algorithm

For a given vertex in the graph, Dijkstra's Algorithm will calculate the shortest path to all other vertices in the graph (there are many variations of the algorithm, this is just one of them). For each vertex in the graph we must store the following information:

  • The known cumulative distance from the start node.
  • The founder (parent) vertex of the current vertex.
  • Whether the vertex has been visited or not.

These extra variables can be stored in the vertex class or in separate data structures as part of the function. The steps of the algorithm are as follows:

  1. Initialize all the vertices by marking them not-visited, setting their known distance to ∞ (infinity), and setting their founder to null.
  2. Assign the start vertex's known distance to 0 (since it is a distance of 0 from the start vertex!) and add it to a PriorityQueue. The priority of the vertices is their cumulative distance.
  3. Pop from the priority queue to obtain the current vertex which has the smallest cumulative distance.
  4. For the current vertex, consider all of its neighbors and calculate their tentative distances. That is, the current vertex's cumulative distance plus the weight to travel to that neighbor. Compare the newly calculated tentative distance to the neighbors current cumulative distance. If the tentative distance is smaller, set the neighbors cumulative distance as the tentative distance and update the founder of the neighbor to be the current vertex. (also setting it to be un-visited will help if we revisit a vertex with a better path).
  5. Add all un-visited & un-queued neighbors to the priority queue.
  6. When we are done considering all the neighbors of the current vertex, mark the current vertex as visited. A visited vertex will never be checked again. If the end vertex has been marked visited, stop searching. The algorithm has finished. Otherwise, repeat from step 3 as long as vertices exist within the priority queue.

Once the algorithm is complete, each vertex will be marked with its cumulative distance to the start vertex. A route can be created by starting at the end vertex and following the path of 'founder' variables all the way back to the start vertex.

A* Search Algorithm

The A* (pronounced "A star") algorithm is an extension of Dijkstra's algorithm that achieves better performance by using heuristics to guide its search. Not only does A* keep track of each vertices cumulative distance to the start vertex, it estimates each vertices 'final distance' to the end vertex. This allows for a better selection of vertices when searching for a path. In order to estimate a vertices distance to the end point, we use a heuristics function to "guess" the distance. This can only be done if the graph exists in a Cartesian coordinate system (each vertex must be given a point in space). Then, math can be used to estimate the distance without checking for connections. So for each vertex we must store the following information:

  • The known cumulative distance from the start node.
  • The final distance from start vertex to end vertex if going through this vertex (known distance + heuristic).
  • The 'founder' vertex of the current vertex.
  • Whether the vertex has been visited or not.

The steps of the algorithm are as follows with differences from Dijkstra's algorithm highlighted:

  1. Initialize all the vertices by marking them un-visited, setting their known distance to ∞, their final distance to ∞, and their founder to null.
  2. Assign the start vertex's known distance to 0 (since it is a distance of 0 from the start vertex!), calculate it's final distance with a heuristics function and add it to a PriorityQueue. The priority of the vertices is their final distance.
  3. Pop from the priority queue to obtain the current vertex which has the smallest final distance.
  4. For the current vertex, consider all of its un-visited neighbors and calculate their tentative distances. That is, the current vertex's cumulative distance plus the weight to travel to that neighbor. Compare the newly calculated tentative distance to the neighbors current cumulative distance. If the tentative distance is smaller, assign the tentative distance as the neighbors new cumulative distance, update the founder of the neighbor to be the current vertex and calculate the final distance by taking the new cumulative distance and adding it the result of the heuristic function with the given neighbor vertex.
  5. Add all un-visited & un-queued neighbors to the priority queue.
  6. When we are done considering all the neighbors of the current vertex, mark the current vertex as visited. A visited vertex will never be checked again. If the end vertex has been marked visited, stop searching. The algorithm has finished. Otherwise, repeat from step 3 as long as vertices exist within the priority queue.

Once the algorithm is complete a route can be created by starting at the end vertex and following the path of 'founder' variables all the way back to the start vertex.

Heuristics

A heuristic function calculates an estimate from any vertex to the goal. There are multiple methods to choose from and each can be used to control A*'s behavior. The following are 3 popular heuristic functions and their use cases:

  • Manhattan: For grids allowing 4-directions of movement. It calculates distance by adding the difference in x and the difference in y and multiplying by a scalar D. D is chosen as the lowest cost between adjacent vertices.
function Manhattan(node, goal): 
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return D * (dx + dy)
  • Diagonal: For graphs that allow 8 directions of movement. It calculates distance by computing the number of steps you take if you can't take the diagonal, then subtracting the steps you save by using the diagonal. When D = 1 and D2 = 1, this is called the Chebyshev distance. When D = 1 and D2 = sqrt(2), this is called octile distance.
function Diagonal(node, goal):
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)
  • Euclidean: On a graph that allows any direction of movement. This uses straight-line distance between two points.
function Euclidean(node, goal):
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return D * sqrt(dx * dx + dy * dy)

More about Heuristics can be read here: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

Assignments to be done with Pathfinding

Airport

  • Here is a fictional directed graph of all the airports in the United States. The assignment is to be able to find the shortest path from one airport to another airport. You will be given a text file to parse through that will list all the edges and have the correct path for you to check your own path with.

  • Here is verticies text file: Airport Text File Verticies

  • Here is edges text file: Airport Text File Edges

The image below is the visual representation for the graph:

References

<-- Previous | Next -->