Description
This project uses 2 algorithms for finding a path between a source and a destination, namely dijkstra's and astar algorithm, both of which rely on different algorithms to predict or find the path
Idea Credit: The Coding Train A* Pathfinding Algorithm.
One of the coolest things about intelligence in machines is that even though we are not at a level where machines attain consciousness but the things we can code them to perform just absolutely blows my mind. During my DS and algo class i came across such an algorithm djikstra's algorithm, from the surface it is a pretty straight forward algorithm but just finding the path is not cool enough, i wanted to visualise how it worked and that's when i came across this awesome library in javascript P5.js.
p5.js is written in JavaScript but originally it is the library Processing. Processing is a visual coding tool for visual arts. The interesting is that processing is not only for developers but also artists, designers, researchers and those who want to enjoy making arts. p5.js is used in JavaScript so we can use it with DOM. Recently it started getting a lot of attention from developers and designers alike and i even used it to create this car chasing game(insert link) which interested me in going about this project and lo and behold, 1 day i decided to visualise djikstra algorithm along with another improvement i came across- the a* algorithm
A heuristic technique often called simply a heuristic, is any approach to problem solving, learning, or discovery that employs a practical method, not guaranteed to be optimal, perfect, logical, or rational, but instead sufficient for reaching an immediate goal. Where finding an optimal solution is impossible or impractical, heuristic methods can be used to speed up the process of finding a satisfactory solution. This is where our fundamental problem comes in- the path finding algorithms. Path finding requires algorithms to solve computational problems where we need to find the shortest distance between 2 points. This can be essential in many problems, such as solving mazes, building navigation systems and even in social networks to find the closest connections between any 2 people on the network
For a given source node in the graph, the algorithm finds the shortest path between that node and every other. It can also be used for finding the shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined. This can be considered as a greedy algorithm as at every point in time it chooses the node with the combined distance of the previous node plus this one and keeps on continuing till it reaches the end or if no path is possible.
The reason why Dijkstra's algorithm works the way it does is in part because it exploits the fact that the shortest path between node u and w that includes point v also contains the shortest path from u to v and from v to w. If there existed something shorter between u to v, then it wouldn't be the shortest path
for coding this algorithm i directly used the steps in the pseudocode section of the wikipedia page. The code for this project can be found on the github link above. However, as we can see many of the paths it discovers in its quest for the shortest path are unnecessary, so it's far better than random guesses but still not good enough which is why we come across a better algorithm- a* (cool name tho).
The major difference between a star and dijkstra is that the former takes more of an educated guess as opposed to exploring all the possibilities before finding the shortest one.
This can be explained by using a heuristic measure in addition to the distance of the node from the source. This heuristic can be the absolute distance between the current node and the destination, therefore, we can speed up the algorithm even more and avoid visiting nodes that increase the heuristic distance, which in this case is self evident if we look at both the gif here.
Thre pseudocode again was taken from wikipedia page and the code can be found on the github link.