Pathfinding Visualization

This project is a visualization of what the Dijkstra's and A* pathfinding algorithms do to find the shortest path to a target node from a starting node. Dijkstra's Algorithm is less complex in that it doesn't use heuristics to influence its successor nodes - this means it doesn't need to know where the ending node is to be able to find the shortest path, however it is much slower. A* uses heuristics called f, g, h. These heuristics are values that influence the nodes' decisions in choosing a new successor node. The g is the distance from the starting point and h is the distance from the ending point. h can be calculated using many approaches. The way I did it was using the exact distance, finding it with simple trigonometry (Pythagorean theorem). Once g and h are calculated, f is just the sum of g and h and the nodes are picked based on the lowest f number.

Dijkstra's algorithm works as follows:

1. Start with the initial node, and let the distance of node X be the distance from the initial node to node X. Assign all initial distances to infinity, besides the initial node's distance, which is 0.
2. Create an unvisited list, with all nodes in the graph added to the list.
3. Create a current node and set it to the start/initial node.
4. For the current node, consider all of its unvisited neighbours and calculate their tentative distances through the current node. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one.
5. When done considering all unvisited neighbours of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again.
6. If the destination node has been marked visited or if the smallest tentative distance among the nodes in the unvisited set is infinity, then stop. The algorithm has finished.
7. Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node", and go back to step 4.

A* uses heuristics to guide the search more efficiently toward the goal, making it faster than Dijkstra's algorithm while still guaranteeing the shortest path when the heuristic is admissible.

The A* algorithm maintains an open list and a closed list. It selects the node with the lowest f value from the open list, calculates g (distance from start) and h (heuristic distance to goal) for each neighbor, and adds them to the open list if they're not already visited. The algorithm uses the Pythagorean theorem to calculate the exact distance for the heuristic h, making it more efficient than Dijkstra's while still finding optimal paths.

The visualization shows both algorithms in action, allowing users to see how A* explores fewer nodes by using the heuristic to guide toward the goal, while Dijkstra's explores more uniformly in all directions.

• Add more pathfinding algorithms, such as BFS (Breadth-First Search)
• Add more customization like buttons for changing the size of the graph, erasable walls