Maze Generation

Overview

In the first two projects we dealt with two-dimensional square mazes. Well, we're going to stick with two dimensions for now, but square mazes are sort of boring, don't you think? How interesting would games like Doom and Quake be if all the walls were at right angles? And what about if we want to model an arbitrary floor-plan to be used for robot navigation? Square mazes just won't cut it here, so in this assignment you will generate random mazes with rooms of arbitrary size and shape.

Assignment

For this assignment you will write a program that takes as input a desired width and height, and outputs a description of a maze with those dimensions (see "File Format" below). The general algorithm you will use has four parts, which may be implemented independently (or the first two steps may be performed simultaneously):

Part 1 - Use a Poisson-Disk Distribution to randomly generate a set of points in the rectangular region that will become the maze (x values should be in the range 0 to width-1, and y values should be in the range 0 to height-1).

Part 2 - Construct a Voronoi diagram for these points and the bounding rectangle.

Part 3 - Choose a start room and an exit room for the maze (they should be different).

Part 4 - Use the Disjoint Set Union/Find data type to repeatedly remove random walls until the maze is completely connected.

More detail:

Part 1

The basic algorithm for generating points with a Poisson-Disk Distribution is as follows:

Choose a small positive value for the diameter of the Poisson-Disks.
Choose a number of points to generate.
While there are still points left to generate, do:
Randomly (you can use non-uniform random distributions if you like, but use a uniform distribution to start with) pick a point within the bounding rectangle.
If this point does not lie within diameter distance of any point already in the set (ie, if the Poisson-disk determined by the new point does not intersect any other disk), add this point to the set.
Otherwise, try again.

Note that using this algorithm it is possible to get into an infinite loop, especially if both the number of points to generate and the diameter of the Poisson-Disks are large. You may handle this in whatever way you choose, as long as your program terminates in a reasonable amount of time and produces a set of points you can use in the next step.

There are several methods you may use to determine whether a new point is too close to an existing point. I recommend the easy but slow method. However, you may implement a faster method if you wish.

Part 2

Given a set of "centers" (ie, points) and a bounding rectangle, a Voronoi diagram is a partitioning of the rectangle into cells (one cell for each center) such that every point inside a given cell is closer to that center than to any other center. The edges of the Voronoi diagram are those points that are equidistant from two neighboring centers. Vertices of the Voronoi diagram are places where edges meet; points that are equidistant from three or more centers.

Your job is to construct a Voronoi diagram using the points from part 1 as the set of centers. You will need data structures to keep track of both the edges and the vertices of the resulting Voronoi diagram.

See http://www.msi.umn.edu/~schaudt/voronoi/voronoi.html for an applet showing an example of Voronoi diagrams.

Constructing Voronoi diagrams is probably the most complicated part of this project. There are several ways to do this and we will shortly (within the next few days) be sending out more detailed instructions describing the algorithm you should use.

Part 3

Use whatever method you like to choose the start and exit rooms, as long as they are distinct.

Part 4

From the previous parts you should have the following information:

the locations of the points generated in part 1 (each point corresponds to the center of a room)
a set of vertices of the voronoi diagram
a set of edges of the voronoi diagram (pairs of vertices)

You may or may not have (depending on your methods) a set of rooms corresponding to each region of the voronoi diagram. If you do not have such a data structure, create one now. Each room should have a reference to each of its bounding walls, and each wall should have a reference to the two rooms it borders.

The algorithm for maze generation is as follows:

Generate a random ordering of the edges
Generate a set of single-node up-trees, one for each room
While there is more than one tree in the forest, do:
- Consider the next edge in the ordering
- If the two rooms it borders are already connected, ignore it
- Otherwise remove this edge and union the two up-trees containing these two rooms

For each edge, you should keep track of whether it is a wall, or open. There are also two other options for the walls described under "File Format", below.

File Format:

The output of your program is a description of the maze you generated. Because another option for this project is to implement a visualization of these mazes, it is VITALLY IMPORTANT that the output of your program conform to the format described below. You are responsible for ensuring that your program gives legal output. Everything between (but not including) BEGIN and END is a description of the file format. Brackets ('<' and '>') are used to designate descriptions of the file text, rather than the text itself. Anything after a # is a comment; you do not have to implement comments!

BEGIN <width> <height> <number of points> #including the vertices of the bounding rectangle <number of lines> #lines with points in the middle should be divided # into the shortest possible line-segments such that each # line is described by two points in the set <number of rooms> <x0> <y0> #the first point <x1> <y1> #the second point #and so forth... <x_NumPoints-1> <y_NumPoints-1> #there should be "number of points" #points <p0> <q0> <t0> #p0 and q0 are the indices of the points defining #this edge; t0 has four possible values: #0=open, 1=wall, 2=half-wall, 3=wildcard #(let the visualizers worry about what this means) #Example: "3 0 1" describes the line connecting points #(x3,y3) and (x0,y0), and the 1 tells us that there is a wall <p_NumLines-1> <q_NumLines-1> <t_NumLines-1> #again, there should be #"number of lines" lines <deg0> <l0_0> <...> <l0_deg0-1> #deg0 is the number of edges this #borders; l0_0 is the index of the first of these edges, and #so forth up to l0_deg0-1 <deg_NumRooms> <l_NumRooms_0> <...> <l_NumRooms_deg_NumRooms-1> #and of course there are "number of rooms" rooms! <index of start room> <index of exit room> END

Extensions:

In the above description, your program should only take two arguments: a width and a height. This requires you to internally decide things such as the number of points to generate, the Poisson-diameter to use, where to place the start and exit rooms, etc. If you wish you may implement some of these as command line options. You may also want to give the user control over things such as what shape the distribution of points should take (uniform, normal, etc...), how open the resulting maze will be (ie, should there be only one path from start to exit, or several?), how many half-walls there will be, and so forth. If you choose any of these extentions, be sure that your program does not allow the user to choose any options which will cause your program to crash or to generate bogus output!