https://github.com/npretto/pathfinding Skip to content Sign up * Why GitHub? Features - + Code review + Project management + Integrations + Actions + Packages + Security + Team management + Hosting + Mobile + Customer stories - + Security - * Team * Enterprise * Explore + Explore GitHub - Learn & contribute + Topics + Collections + Trending + Learning Lab + Open source guides Connect with others + Events + Community forum + GitHub Education + GitHub Stars program * Marketplace * Pricing Plans - + Compare plans + Contact Sales + Nonprofit - + Education - [ ] [search-key] * # In this repository All GitHub | Jump to | * No suggested jump to results * # In this repository All GitHub | Jump to | * # In this user All GitHub | Jump to | * # In this repository All GitHub | Jump to | Sign in Sign up {{ message }} npretto / pathfinding * Watch 1 * Star 79 * Fork 2 Visual explanation of pathfinding algorithms and how a*, Dijkstra and BFS can be seen as the same algorithm with different parameter/data structures used under the hood interactive-pathfinding.netlify.com 79 stars 2 forks Star Watch * Code * Issues 1 * Pull requests 0 * Actions * Projects 0 * Security * Insights More * Code * Issues * Pull requests * Actions * Projects * Security * Insights master 1 branch 0 tags Go to file Code Clone HTTPS GitHub CLI [https://github.com/n] Use Git or checkout with SVN using the web URL. [gh repo clone nprett] Work fast with our official CLI. Learn more. * Open with GitHub Desktop * Download ZIP Launching GitHub Desktop If nothing happens, download GitHub Desktop and try again. Go back Launching GitHub Desktop If nothing happens, download GitHub Desktop and try again. Go back Launching Xcode If nothing happens, download Xcode and try again. Go back Launching Visual Studio If nothing happens, download the GitHub extension for Visual Studio and try again. Go back Latest commit @npretto npretto added link in readme ... 929dfc9 Jan 18, 2021 added link in readme 929dfc9 Git stats * 33 commits Files Permalink Failed to load latest commit information. Type Name Latest commit message Commit time gif added gifs Jan 24, 2019 public updated notes Jan 24, 2019 src fix small bug causing nodes to be colored wrongly if start == 0 Jan 22, 2019 .gitignore Initial commit from Create React App Jan 2, 2019 README.md added link in readme Jan 18, 2021 package.json popup and theory Jan 21, 2019 yarn.lock popup and theory Jan 21, 2019 View code README.md Interactive pathfinding Link to hosted demo: https://interactive-pathfinding.netlify.com/ Breadth-first search, Dijkstra and A* are three famous path-planning algorithms that run on graphs. They can all be seen as a specialised version of a graph search with two different parameters, the queue used and the heuristic used. The aim of this project is to explore and visualise how the different algorithms explore through the graph depending of the parameters chosen. The general algorithm works as follow: A frontier is initialised as a queue containing the start node. While the frontier is not empty a node (called "current") is removed from the queue and gets "visited". Each of the neighbours of the visited node gets added to the frontier with a cost which is the current cost of getting to the current node plus the cost of visiting the neighbour from the current node plus the value of an heuristic function applied to the neighbour and the goal node. The heuristic function is an estimation of the cost of the path from the two nodes. A reference of the direction of the visit is stored (usually in a cameFrom map) in order to be able to reconstruct the path when the algorithm stops. If the neighbour is already in the frontier its cost can be changed if the new path has a cheaper cost. The algorithm stops when it finds a path to the goal (early exit) or when the frontier is empty. BFS BFS can be implemented by using a First-In-First-Out queue. This kind of queue ignores the cost of the links in the path and it expands based on the number of hops. Because of this it's guaranteed to find the shortest path in terms of hops, nut not in terms of costs associated with the hops. The heuristic used can be whatever we want, as it will be ignored by the queue. The fifo has been implemented using an array, appending elements to the end and removing them from the start. bfs animation Animation of BFS, notice how in a grid the frontier (yellow nodes) expand as a square, because a square is the set of the nodes at the same "hop-distance" Dijkstra By passing a PriorityQueue instead of a FIFO to the graph and a heuristic function which always returns 0 we get the Dijkstra algorithm. The main difference from the BFS is that Dijkstra takes into account the costs, the algorithm can now find the actual shortest path considering costs of traveling from node to node. The priority queue has been implemented with an array that get sorted after every insertion. While not being the most efficient implementation of a priority queue, it was easier to implement and is fast enough for this application. Dijkstra animation Animation of Dijkstra, notice how the frontier is now a circle. A* To obtain the A* algorithm from our generalised graph search we just need to pass an actual heuristic function, let's use the euclidean distance between the two nodes as example. By weighting the nodes based on "cost to the node" + "estimation of cost from node to goal" we can speed up the search by going first into nodes that look promising. a* animation Thanks to the heuristic, A* can find the correct path faster than Dijkstra or BFS Non admissible heuristics A* is guaranteed to find the shortest path only if the heuristic is admissible, which means that it never overestimates the actual path length. The euclidean distance cannot overestimate, as the euclidean distance is the shortest distance/path between two points. But what if we multiply it by a constant k > 0 ? By doing so it would overestimate making the heuristic non-admissible. non admissible heuristic animation The more we increase the value of k the more the algorithm goes towards the goal. This also makes it less accurate, making the resulting path not always the shortest. Implementation The project was implemented in javascript in order to be more accessible on the web. I used react for rendering the UI and react-konva for rendering the graph. The pathfinder is implemented as a function that accepts the queue type, the heuristic, and returns another function which is the actual pathfinder (this concept is known as currying). In this way every time the user changes the settings, a new pathfinder function is created with the correct parameters and can be used to navigate the graph. In order to show every step of the exploration, the function is a javascript generator, meaning that it returns an iterator and not just a single value. This allows me to yield the entire state of the algorithm at every step, save it into an array and then show a specific state based on the value of the slider at the top of the page. About Visual explanation of pathfinding algorithms and how a*, Dijkstra and BFS can be seen as the same algorithm with different parameter/data structures used under the hood interactive-pathfinding.netlify.com Topics pathfinding heuristic dijkstra bfs Resources Readme Releases No releases published Packages 0 No packages published Languages * JavaScript 77.6% * HTML 17.6% * CSS 4.8% * (c) 2021 GitHub, Inc. * Terms * Privacy * Security * Status * Help * Contact GitHub * Pricing * API * Training * Blog * About You can't perform that action at this time. You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.