Description
General
This site is for simple demonstrations of some basic graph algorithms by applying them on maze.
Currently, it can generate maze using Prim, Kruskal or DFS algorithms, and
solve it using DFS, DFS*, BFS, A* or Greedy algorithms. However,
since I'm not very good at JavaScript, so the implementation is rather clumsy.
Tutorial
To generate the maze, just select the size and the color of the map, or just click "Random" button to
pick one randomly. And don't forget the algorithm you want. Then, click "Generate" and the maze will
be generated step by step. You can also adjust the speed slider to accelerate or decelerate. The
same thing goes with solving the maze. What's more, the steps of each method will be shown on the
right.
If you just want the answer, you can just press batch button. Batch solve will automatically generate
a map with selected algorithm, and then run each method to solve the same one for given times. When
finished, it will give the average run steps. It may take a while, so be patient. However, batch
generate will only generate a map without delay.
Algorithms
For map generation, the algorithms will not create any loop. That is to say, the entire maze
is actually a tree. For Prim and Kruskal, they are originally algorithms for
minimum-spanning-tree, so we can just assign random weight to the edges in the graph to create a
random tree. As for me, I think the results of these two methods are quite similar. The only slight
difference might be that the tree of Prim may have a more obvious root, which is the starting point.
However, for DFS algorithm, the result is quite different. The solution for the maze that generated
by DFS is often devious, unlike the other two whose result is relatively smooth.
To find the pathway, we now provide five algorithms. For DFS and BFS, there is
nothing special, and the efficiency of these two are even, I think. Since DFS can get deeper quickly
while BFS can reach more possible solutions, they are good at maze with different structures. For
DFS*, it optimize DFS to go right and down first, according the the position relation with
the starting and ending point. For A*, it can be regarded as enhanced BFS, since it will make
choices when choosing next candidate. Here, the heuristic function is the Manhattan distance to the
exit of the maze. And for Greedy, it can also be regarded as enhanced BFS, and is actually
very similar to A*, but it doesn't count for the taken steps, it only consider the distance to the
exit, which makes it extremely fast in mazes that has a smooth pathway that is close to a line.
Generally speaking, DFS and BFS are even, while DFS*, A* and Greedy are better than them in most
cases. However, A* may took more steps since it considers the steps in the past, which plays an
essential role in finding the shortest path, not here. So, usually Greedy algorithm seems to be the
most efficient, and DFS* is not that bad, at least compared with its brother. However, if
the maze unfortunately got a devious solution, A* and Greedy might take longer as their evaluation
function will mis-lead them to unexpected dead-ends.
Notice
Since the code is not perfect, there are some flaws in it. Please be patient when generating and
solving the maze. Generate maze when solving is not complete will trigger a serious error.