Pathfinding algorithms are methods that explore routes between nodes in a graph, starting at one node and traversing through relationships(adjacent nodes) until the destination has been reached. These algorithms are used to identify optimal routes(shortest paths) through a graph for uses such as web mapping websites (such as google maps), IP routing, and gaming simulation.
I built this app as a fun side project using typescript/html/css in order to 'visualize searching a path from a source to a destination'.
Here is a demo of what the app looks like after exploring some nodes and finding a path from a source to a destination:
Here is the url for the app: https://alae-touba.github.io/pathfinding-visualisation/index.html
For this app i implemented 4 well known graph algorithms:
- Depth first search:
DFS is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at a root node and explores as far as possible along each branch before backtracking. So the basic idea is to start from a node and mark the node as visited and move to the adjacent unmarked node and continue this loop until there is no unmarked adjacent node. Then backtrack and check for other unmarked nodes and traverse them. Finally print the nodes in the path. It finds JUST a path, not necessarily the shortest path.
-
Breath First search:
BFS visits the nodes in increasing order of their distance from the starting node. Thus, we can calculate the distance from the starting node to all other nodes using BFS. BFS search goes through the nodes one level after another. First the search explores the nodes whose distance from the starting node is 1, then the nodes whose distance is 2, and so on. This process continues until all nodes have been visited. It finds the shortest path. -
Bellman ford:
The Bellman–Ford algorithm finds shortest paths from a starting node to all nodes of the graph. The algorithm keeps track of distances from the starting node to all nodes of the graph. Initially, the distance to the starting node is 0 and the distance to all other nodes in infinite. The algorithm reduces the distances by finding edges that shorten the paths until it is not possible to reduce any distance. It finds the shortest path.
- Dijkstra’s algorithm:
Dijkstra’s algorithm finds shortest paths from the starting node to all nodes of the graph, like the Bellman–Ford algorithm. Like the Bellman–Ford algorithm, Dijkstra’s algorithm maintains distances to the nodes and reduces them during the search. It finds the shortest path.
-
selecting a starting node:
click on the "select start" button in the bottom navbar and then click on the grid. (you will see the start node, at the clicked position) -
selecting an ending node:
click on the "select end" button in the bottom navbar and then click on the grid. (you will see the end node, at the clicked position) -
selecting blocked nodes:
click on the "select blocked" button in the bottom navbar, then click once in the grid and hover over a bunch of grid cells and then click on the grid again. there you are, your blocked cells are marked as red. -
selecting an algorithm to visualize:
click on the "select an algorithm" button, a little window will pop-up, select the wanted algorithm. -
visualize the path:
click on the "visualize" button in the botton navbar (really?). If there is a path, it will be shown with an orange color. -
I will let you explore the other two options yourselves.