Presentation for BUAA 2023 Algorithm course.
This is a simple demonstration 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.
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.
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.
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.