Drawing Walls
You can draw walls by selecting the option on the navbar and then clicking and hovering on the grid. Click again to stop drawing. A wall can not go over any other special point.
Wall
Visited
Path
Start
End Point
PathFinding Visualizer
Set Points
Draw Walls
Mazes
Recursive Division
Recursive Backtracker
Random Kruskal
Random Prim
Aldous-Broder
Algorithms
Astar
Breadth First Search
Depth First Search
Uniform Cost Search
Optimal Meeting Point
Fight the algorithm!
Clear
Clear Board
Clear Path
Clear Walls
Clear Paths and Points
Visualize
Guide
Welcome!!
Welcome to the Path Finding Visualizer!. In this project you can see in action various algorithms for path finding and perfect maze generation!.
For the visualization a 2D grid graph was used and each movement can have a vertical or a horizontal direction. Moreover a node can have up to 4 neighbors, and the cost of each edge is 1.
Maze Generation
You can generate mazes by selecting an algorithm from the Mazes dropdown menu. Note that you can't generate mazes when the Fight the algorithm option is selected.
PathFinding Algorithms
A*: A modified version of dijkstra's algorithm that chooses the best node to visit based on an heuristic function.
BFS/DFS: BFS starts exploring all nodes from the closest to the furthest away nodes and guarantees the shortest path. DFS on the other hand starts from the furthest away nodes and does not guarantee the shortest path.
Uniform Cost Search: The algorithm starts with a priority queue that contains only one item, and inserts new items as they are discovered.
Best Meeting Point
For this problem a combination of Non Random Access algorithm and an incremental version of Dijkstra's algorithhm was used. NRA is an algorithm used for topK queries and in this case we will be doing a top1 query. Each time the algorithm gets the next closest node from every starting node and checks if every starting node has reached one of those next closest nodes, updating the minimum distance as well as the maximum. If a node has been visited by all the starting nodes it is compared with the previous meeting point based on the maximum distance. The result is a node that has the minimum maximum distance. Due to the nature of NRA the worst case is O(k(V + ElogV)). However if the starting nodes are close the algorithm will terminate very fast. Up to ten points can be selected and you can also add walls or mazes to see the algorithm in action.
Fight the algorithm!
For this problem Astar was used. Since the process is a separate thread it is possible to draw walls while the algorithm is running and redirect it to find the next closest path.You can drag and drop the end point to a different location or just click on the grid to move it around.
