This is a maze solver built in React by Daniel Pages and Justin Austria.
-
It randomly generates mazes when the user clicks "reset".
-
The user can also click on tiles to customize the maze.
-
It can then solve the maze using breadth-first-search, depth-first-search, greedy search, or A* search.
First, choose a type of search algorithm. Second, click solve (normal), or solve (slow). Third, you can click reset to start again.
Slow solving delays the processing of the maze so you can better observe and understand how the algorithm is working. You can watch the nodes be processed, as a list at the bottom of the screen, and note that they each search exhibits the correct behavior for its own abstract data type (stack, queue or priority queue).
Depth first search requires the simplest abstract data type (a stack), which would be powered by a dynamic array as the underlying data structure. Depth first search does guarantee a solution if one exists, but does not guarantee an -optimal- solution.
The second option is breadth first search. Breadth first search uses a queue as its abstract data type, which would be implemented with a ring buffer as the data structure. Breadth first search does guarantee an optimal solution if one exists, but it can also be slower than the other search types.
The third option is the greedy search. This uses a priority queue as its abstract data type, which could be implemented with a heap as its data structure. Greedy search is usually the fastest type of search to find a solution for this particular problem in terms of the run time of the algorithm, but it may not be the optimal solution in terms of distance. Furthermore, Greedy searches require a heuristic to estimate the value of a given search node - in this app, it is easy to calculate the distance from the goal to estimate the value of the target, but a good and easily computable heuristic may not be available in all cases.
The final option is an A* search. Like Greedy Search, A* uses a priority queue as its abstract data type, which could be implemented with a heap as its data structure. A* search guarantees an optimal solution if one exists, and explores more efficiently than Breadth First Search by taking advantage of the heuristic to explore more promising nodes first. Like a greedy search, A* requires a heuristic, and the heuristic must be "admissible" if the A* is to guarantee an optimal solution. Read more in the link below to understand admissibility and A* searches.
-
At present, the abstract data types (ring buffer and priority queue) are implemented sub-optimally in the code. When time permits, we will replace them with the correct data structures.
-
We plan to perform additional styling to make the website itself more visually appealing, and additional refactoring to make the JavaScript code more modular and readable.