Prim's Algorithm
The maze is generated using Prim's algorithm, a greedy algorithm that grows a minimum spanning tree from a starting source node until it covers the entire graph. Each of the edges in the graph is assigned a random weight and the tree is built by selecting the cheapest edge that doesn't create a cycle. Prim's algorithm does not, however, select the cheapest edge that will connect any pair of vertices, but rather edges that will connect to the existing tree.
Learn More
BFS Algorithm
Breadth-first search (BFS) is a search algorithm for traversing a graph or tree. It starts by visiting a node, then adds all of that node's neighbors into the queue. Each time it adds a neighbor to the queue, it adds a pointer that references the neighboring node's parent. Once the queue is empty, which means all nodes have been visited, or the goal node is found (for early-exit implementations), the pointers are traced from the goal back to the source.
Learn More
DFS Algorithm
Depth-first search (DFS) is a search algorithm for traversing a graph or tree. Rather than considering its shallow neighbors first like BFS, it plunges all the way to the bottom of a given branch before considering the next neighbor. Once the stack is empty, which means all nodes have been visited, or the goal node is found (for early-exit implementations), the pointers are traced from the goal back to the source.
Learn More
A* Algorithm (Manhattan)
Unlike Dijkstra's algorithm, BFS and DFS, A* is an informed search algorithm.
A* is implemented by searching the possible paths to the goal and opting for the one that incurs the smallest cost. The cost used by A* is the actual distance incremented from the start to the current node plus the estimated distance to the goal. In this implementation, the Manhattan distance is used for the estimate, which is the distance to the goal in the vertical direction plus the distance to the goal in the horizontal direction.
Learn More
A* Algorithm (Straight-Line)
Unlike Dijkstra's algorithm, BFS and DFS, A* is an informed search algorithm.
A* is implemented by searching the possible paths to the goal and opting for the one that incurs the smallest cost. The cost used by A* is the actual distance incremented from the start to the current node plus the estimated distance to the goal. In this implementation, the straight-line distance to the goal is used as the estimate.
Learn More
Dijkstra's Algorithm
Dijkstra's algorithm is similar to BFS, except it incorporates a cost heuristic that tracks the cost of different moves and evaluates that before deciding which node to visit next. Dijkstra's algorithm results in a shortest-path tree to every node in the graph. The implementation displayed here incorporates an early exit, where the algorithm stops when the goal node is found, and the pointers are traced from the goal back to the start.
Learn More