Pathfinding Algorithms

Pathfinding 

Pathfinding is the plotting and solving of the shortest route from one point to another.
There are many different pathfinding algorithms, most of them based on Dijkstra's algorithm,  which finds the shortest paths between nodes in a graph.

Basic Pathfinding using Breadth-first search

One of the most basic pathfinding algorithms would be the Breadth-first search method. An iterative system which starts either at the root node or an arbitrary node of the tree/graph and explores the neighbouring nodes, then moves on to the next level and recycles this process.

The Pseudocode for this algorithm:

1     for each node n in Graph:            
2         n.distance = INFINITY        
3         n.parent = NIL
4 
5     create empty queue Q      
6 
7     root.distance = 0
8     Q.enqueue(root)                      
9 
10     while Q is not empty:        
11     
12         current = Q.dequeue()
13     
14         for each node n that is adjacent to current:
15             if n.distance == INFINITY:
16                 n.distance = current.distance + 1
17                 n.parent = current
18                 Q.enqueue(n)

The problem with an algorithm such as Breadth-first is that it's slow and has to iteratively go through all nodes, instead an algorithm that explores the graph would reach its destination sooner.

Dijkstra's algorithm

Similarly to the Breadth-first algorithm, Dijkstra's concept was to starts at the root node and explores its neighbours, however it chooses undiscovered nodes with the lowest distance from the previous node and calculates the distance through it and its unvisited neighbours, then updates the distance if it's smaller and keeps it unused if it's greater.

To build an algorithm around this concept we use a similar approach to the previous pseudocode.
Each node has an infinite distance from the root node, and the root node has distance 0.
The root node is the current node, and all other nodes are in a set of "undiscovered nodes"
Then start iterating for the current node, calculate the distance to all its unvisited neighbours and compare the newly calculated distances to the currently assigned value, if the new distance is smaller, replace, if not continue.
Once the destination has been reached, stop the algorithm.

To put this in Pseudocode:

 1  function Dijkstra(Graph, root):
 2
 3      create empty queue Q
 4
 5      for each vertex n in Graph:             
 6          dist[n] = INFINITY                  
 7          prev[n] = NIL
 8          add n to Q                          
 9
10      dist[root] = 0                        
11      
12      while Q is not empty:
13          u = node in Q with min dist[u]    
14          remove u from Q 
15          
16          for each neighbor n of u:           
17              alt = dist[u] + length(u, n)
18              if alt < dist[n]:               
19                  dist[n] = alt 
20                  prev[n] = u 
21
22      return dist[], prev[]

A* Algorithm

The A* (pronounced A Star) algorithm is another algorithm based off of Dijkstra's algorithm. It's used in multiple pathfinding systems. It performs better then Dijkstra's algorithm, although is similar in how it works.






 This animation shows Dijkstra's algorithm reaching it's goal, as we can see, it checks all neighbouring nodes before reaching its destination.

In contrast, A* tries to directly reach it's goal by using a priority queue system. A priority queue is known as the "Open Set". At each step of the algorithm, the node with the lowest cost and estimated cost value is removed from the queue, the cost values of its neighbours are updated accordingly, these neighbours are added to the queue.

------------------------------------------------------------------------------------------------