Graph Search Algorithms

Repo

I have implemented three different graph search algorithms for 2D path planning in a discrete state-space. These are implemented in C++ using SFML to visualize the search process. Each search class is instantiated using a search algorithm factory method that takes an enum object as an argument, and returns the corresponding search implementation. All three searches have the following general update process:

Pop a node out of the frontier data structure
- The data structure chosen to hold the frontier nodes is the main difference between these three search algorithms. By simply changing the way in which frontier nodes are stored and retrieved, the way the algorithm searches the state space can change dramatically.
If this node is the goal, the algorithm has concluded. The path from start to goal can be found by traversing from the goal node to each parent node, as each node object has a pointer to its parent.
Add all neighbors of this node that are not obstacles to the frontier.
Start again at step 1

The below visualizations show each search algorithm implementation. Frontier nodes are magenta. Nodes that have been searched (already popped out of the frontier) are shown in grey. The chain of nodes back to the start node from the current node is shown in cyan. The black cells are unexplored nodes in the state space, and yellow cells are obstacles. Finally, the start node is green and the goal node is red.

Breadth First Search

Breadth first search is implemented using a queue to store the frontier of the search. As a result, nodes are searched in a first-in-first-out sequence, causing the frontier to fan out across the state space. This algorithm can find more optimal routes at the cost of expanding more nodes in the state space, requiring more resources.

Depth First Search

Depth first search uses a stack to hold frontier nodes. Nodes are searched in a last-in-first-out sequence. This causes the algorithm to follow one path until it gets stuck. This algorithm can find a path much faster than breadth first, but the path may not be as optimal as the algorithm tends to snake across the state space.

A*

A* attempts to find a middle ground of path optimality and resource efficiency by using a heuristic to determine which node in the frontier to explore each iteration. It is implemented using a priority queue to store the frontier. The priority queue returns the node that has the most optimal value according to the heuristic. For my implementation, I am using a Manhattan distance heuristic.