Shawn Tice and I developed a random maze generator for the M.U.D. project. The purpose of our design was to generate a closed world of arbitrary size, where all rooms are accessible from any other.
We restricted the world's shape to square with sides that measure as powers of two. That way, we could recursively generate the world with the following rules:
- for all rooms larger than a unit room (1x1)
- the room posesses four rooms, one in each quadrant
- the room posesses four exits that are either passable or walled
- any exit that is passable may be divided in half, closed in by a wall on either side
- between each quadrant is a partition
- at most, one partition is a wall
- all other partitions are passable, guaranteeing that all quadrants are accessible by at least one path.
- for all rooms
- all surrounding partitions are walls if they do not lead to a room
Here's how one maze turned out:
The numbers represent the width of each room in the following diagram. Each successive maze is a more detailed version of the previous.
For the purpose of testing, we'll probably populate this maze with two warring clans, Red versus Blue. I doctored an image off of Eight Bit Theatre with Macromedia Fireworks for the purpose. For kicks, I made the layers functional.
The first image is the PNG. The original image probably belongs to Square-Enix.