Maze2D: 2D Maze Generator
Chee Haw Chan, Math 198
Overview
This program generates randomized 2D rectangular mazes with varying attributes. It was written in Python using OpenGL.
Output and console windows of Maze2D
Algorithm
Maze2D uses a slightly modified randomized Kruskal's algorithm to generate mazes. Kruskal's algorithm is as follows:
1. Start with a grid of walls
a. Create a list of all walls
b. Create a set for each cell
2. Select a random wall
3. If cells divided by wall belong to distinct sets
a. Remove wall
b. Join the sets of the cells
4. Repeat steps 2-3 until all cells are in the same set
Generation
The algorithm is modified for Maze2D so that the generated maze will have boundary walls. As a side effect, it seems that only the wall farthest away from the boundary of boundary cells can be removed.
It should also be noted that the generated mazes are not connected. This means that there are regions that are isolated from the rest of the maze.
I'm not sure if this is how Kruskal's algorithm is supposed to work or if this was a mistake in the coding.
Usage
The user is able to modify the dimensions of the maze as well as the size of the cells. I attempted to make the maze look three-dimensional at one point but never got anywhere with it.
The "fake dimension" option is a left-over from this attempt. All it does is turn the wall lines into squares that extend into the depth dimension.
Links
Powerpoint presentation on Maze2D and maze generation in general
Source code for Maze2D
maze4Dcube
___
Last edited: 12/10/2011