Interactive Pathfinding Simulator

Welcome to my interactive pathfinding simulator! After recently playing a game with a really cool quest tracker showing a path in the game world, I became interested in pathfinding algorithms and seeing how paths update in real time based on waypoints and obstacles. From there, I researched and implemented 4 of the most common pathfinding algorithms. I decided to make it more interactive by being able to choose the start and goal waypoints as well as add and remove obstacles to path around. The visited nodes and path will update in real time as you edit the world so you can see the changes that occur, and you can animate the search at any time to see how the algorithm goes about finding the goal node.

Algorithm Descriptions

Breadth-First Search

This algorithm searches all nodes at the current depth from the current node before moving onto the nodes at the next level. To do this, it uses a data structure called a queue to store the nodes needing to be visited. A queue uses a First-In-First-Out principle, meaning the first nodes to enter the structure get removed before the later ones, and can be thought of similar to a standard line at a bakery. The first guest in line gets to order first. This algorithm is not guaranteed to find the shortest path between 2 nodes.

Depth-First Search

This algorithm is similar to breadth-first search, but searches all nodes down one branch before backtracking and searching other branches. It uses a structure called a stack instead of a queue, which employs a First-In-Last-Out principle. This means the first nodes to enter the stack get removed later than ones that get added after. This is similar to a stack of dinner plates in the cabinet where the last plate you put on the stack will be removed and used first. This algorithm is not guaranteed to find the shortest path between 2 nodes.

A*

A* is one of the most commonly-used algorithms for pathfinding due to its completeness and efficiency. This efficiency, however, comes with a tradeoff of a larger than usual space requirement since it stores all generated nodes. A* is an informed search, meaning it knows the location of the goal and evaluates which node to visit next using a heuristic function that determines the cost of the move, typically a combination of least distance traveled and distance from the goal. This algorithm is guaranteed to find the shortest path between 2 nodes.

Dijkstra's

Dijkstra's is very similar to Breadth-First Search, except it uses a priority queue instead of a normal queue. With a priority queue, every entry has a movement cost, so rather than picking a node off the top to visit, it picks the node with the lowest movement cost. This algorithm is guaranteed to find the shortest path between 2 nodes.