Course:CPSC312-2019-Maze-Generator
 | |
|---|---|
| Section: | |
| Instructor: | |
| Email: | |
| Office: | |
| Office Hours: | |
| Class Schedule: | |
| Classroom: | |
| Important Course Pages | |
| Syllabus | |
| Lecture Notes | |
| Assignments | |
| Course Discussion | |
| [[Category:]] | |
Authors: Eishan Lawrence, Nick Birtch, Aditya Chinchure
What is the problem?
We want to develop a Maze Generator.
A maze is a 2D game where you need to find a path to go from the starting point to the ending point, travelling through a unique path.
In our case, we will be implementing a generator algorithm based on the techniques that are highlighted here: https://en.wikipedia.org/wiki/Maze_generation_algorithm
The algorithm will take a value ‘N’ to create an NxN grid maze. We may also implement the ability to enter a generator seed, so that if the same seed is used, the same maze is returned.
What is the something extra?
We will develop a GUI to play the maze game. We will use the gtk3 or gloss Haskell packages to create the game. A player will be placed at the start position, and the user can use the arrow keys to navigate the player through the maze.
What did we learn from doing this?
The bottom line is that we were successful in implementing a maze generating algorithm and supporting a playable experience with our GUI using Haskell.
Maze generation:
We used randomized Prim’s algorithm to generate mazes. We represented maze walls as triplets (r, c, w), where r is the row number and c is the column number of the cell in the grid, and w is one of ‘L’, ‘R’, ‘U’, ‘D’, representing if it is the left, right, ceiling or floor wall of the cell.
Implementing the algorithm was not space efficient because Haskell does not allow us to save state in pure functions. So each recursive call created a new data structure for the next call instead of just utilizing the already evaluated structure. This made the space complexity of the algorithm to be exponential in the number of walls in the maze, because Haskell creates new arrays and sets on every iteration of the algorithm. The following data was collected:
| Size of Maze | Memory used |
|---|---|
| 10 | 4 MB |
| 20 | 26 MB |
| 50 | 400 MB |
| 100 | 3 GB |
A screenshot of the terminal from where we got this data:
A language that allows saving state, such as Java, Python, etc. would be more space efficient to use over Haskell.
On the other hand, the time complexity of the algorithm is fairly reasonable. If there are n walls in a maze, the time complexity to generate that maze is .
GUI:
In terms of the GUI, Gloss made the setup and development process smoother. Because the algorithm produced a list of walls to be drawn, we were able to implement a recursive structure to place the walls at the right coordinates on the screen. Functional programming languages work great for these recursively build games. However, with each "update" of the game, i.e. every move, the entire game would be redrawn, which is not efficient.
Overall, Haskell has potential for small 2D games and the algorithms that drive these games. The benefits of using Haskell for this project was that Haskell was easily debuggable because it is strongly typed, and reasoning about and making changes to the current game state was very readable and simple to introduce. The major drawbacks, space and time complexity, are largely due to the nature of functional programming languages.
In terms of future improvements, building upon our GUI aesthetically and supporting additional game elements such as an in game menu (using gloss), music (http://hackage.haskell.org/package/haskell-player), etc. would be interesting and reasonable paths to pursue using Haskell. There is also potential for implementing alternative Maze generator algorithm.