Maze Generation
Authors: Hiroki, Samad
What is the problem?
Previous CPSC-312 students in 2019 developed maze generator. However, since they used immutable list for the algorithm, the project resulted in bad performance in space complexity.
We want to improve the performance of maze generation algorithm by using mutable list (from MArray library) in Haskell to solve the issue.
What is the something extra?
We will implement a few algorithms (randomized DFS, randomized Prim's) from this wikipedia [1] to learn which algorithm suits Haskell's data structure with time and space usage.
What did we learn from doing this?
We learned that the approach with a mutable array was successful in DFS while not in Prim's. Our DFS algorithm got better performance in both time and memory usage than the previous student's work; however, the Prim's algorithm ended up performing worse.
| Size of maze | Time (secs) | Memory usage (MB) |
|---|---|---|
| 10 | 0.01 | 1 |
| 20 | 0.01 | 4 |
| 50 | 0.03 | 29 |
| 100 | 0.14 | 118 |
| Size of maze | Time (secs) | Memory usage (MB) |
|---|---|---|
| 10 | 0.02 | 19 |
| 20 | 0.24 | 315 |
| 50 | 10.80 | 12,903 |
| 100 | 178.03 | 208,681 |
| Size of maze | Time (secs) | Memory usage (MB) |
|---|---|---|
| 10 | 2.45 | 4 |
| 20 | 7.04 | 26 |
| 50 | 3.14 | 400 |
| 100 | 12.27 | 3000 |
This is because we could save states of a DFS tree with a mutable array for DFS. (Also, the version of Haskell may affect the performance since the records of the previous students' are from two years ago, and the code is not compilable currently.)
On the other hand, we could not filter already-visited neighbour cells before picking the next cell randomly with Prim's approach, and thus it ended up having needless traversals of the neighbours. We are not sure if this is the nature of Haskell or it is solvable in some way, but if we could, the performance of our Prim's algorithm will be significantly better.