I became interested in the problem of writing a program that would draw a simple maze on the screen or to a printer. These mazes would be the sort that one could draw on a sheet of graph paper, i.e. rectangular outer wall, rectangular passages, unique solution, no open rooms (maximal number of walls) no inaccessable sections (not too many walls).

 

All of the maze drawing algoritms that I have seen basically involve building a 2D array to describe the cells and then crawling over the array knocking down enough of the wass so that the entire maze becomes accessible, but not too many so that it becomes disconnected, leaving either multiple solutions or open rooms. The method I use requires musck less space by using only a 1 dimensional array as long as one side of the maze. If one is constructing a huge 1000 x 1000 maze, the traditional method requires a million units of storage whereas this method only requires 1000. I don’t pretend that there is great demand for space efficient maze construction but 20 years of hacking leaves one a bit of a space miser and an admirer of local algorithms that produce global behavior. I offer this as a sample.

 

The algorithm arose out of some observations about mazes and practically wrote itself once these observations were made. First, however, some hopefully obvious terminology.

 

 

Observations:

 

  1. Every vertex is part of a wall. If there are no open rooms then every vertex must be connected to some other vertex. Unconnected verteicies are open spaces.
  2. There are at least 2 walls (the stalactites and the stlagmites). If there is to be any way through the maze there cannot be a wall running from the top to the bottom. Thus the stlactites and the stalagmites are not connected to one another. Note and obvious solution to the maze is to walk form the entrance to the exit remembering to step over the stalagmites and to duck under the stalactites. If you flood fill the bottom wall, so that the bottom wall is a different color from the top wall you can see the solution easily.
  3. There are at most 2 walls (in a maze with a unique solution) If a maze is to have an unique solution then every vertex must be connected to either the stalgmites or to the stalactites. If there is some group of walls that is not connected to either,  then if floats somewhere in the middle of the maze. You would have one solution by going over that group and a second by going under that group.
  4. If the maze is to have not inaccessible parts then verticies that are connected by some path must be connected by a unique path. If a vertex was connected to the top wall by more than one path then the stuff inbetween those two paths would be inaccessible. Thus there can be only one chain connecting a vertex to a wall.

 

And with that last observation we are ready to write the algorithm. We will keep and array that describes a single column of verticies. It will keep track of whether or not a vertex is connected to anything yet and if it is connected to anything, it will keep track of who it is connected to. We will initialize the array by choosing an entrance at random and marking everything above the entrance as belonging to the top and everything below as belonging to the bottom. Then we advance to the next column of verticies making some horizontal connections at random and then connecting some of them vertically at random, making sure that we never violate any of the observations.. The last column is a special case since we connect out to the exit. Througout this process we are free to start floating groups as long as we ultimately tie them into either the top or the bottom group. Each floating group will have a name (a number) until it is connected into the top or the bottom. These names are used to determine whether two vertices have been connected yet. Any two berticies with the same name are already connected by some wall and thus cannot be connected again without violating observation 4. Any two with different names (except for the top and the bottom) have not yet been connected and may be connected. Once connected, they must all take on the same name to prevent them from later being connected a second time.

 

The outline is this:

 

    Choose entrance, draw left hand wall, initialize array of owners

    Choose exit and draw right hand wall.

    FOR each column

      Connect the top and bottom edges (i.e. emit horizontal edges)

      Draw some horizontal lines (special case the last column)

          Horizontal lines move us from one column to the next, if we draw a line the

          owner stays the same. Otherwise the new vertex is unowned.

      Draw some vertical lines

          Never connect verticies with the same owner. If you do connect, give them

          a common owner name.

     ROF

 

We will draw horizontal lines on three conditions:

  1. If the vertix is unowned. Observation 1: we are leaving this column and moving to the next. This point must be connected to something so draw a line leaving from it to the next vertex and give it a brand new owner name since it is now a floater with a single horizontal one unit wall.
  2. If the dice says draw the line, then draw the line. The new vertex has the same owner as the vertex we just connected so don’t change the owner name.
  3. If  the point we are leaving is the last vertex that is owned by that owner (last surviving family member) it must be connected out, othwise we have just left a floating group and will not have a unique solution.
  4. If we don’t draw a horizontal line then we mark the new vertex as unowned.

 

We will draw vertical lines when the dice tells us to and when it is premited (.e. the verticeis have different owners.)

 

Note the conditions in the algorithm correspond nicely to features of the maze. For example if you want to build easier mazes that have multiple solutions you simply omit 3 from the horizontal rules and you will get floater groups (with a little help from the random number generator) If you want to have rooms in the maze, simply omit rule 1. In fact, you can force rooms by simply declaring blocks of vertices as off limits for connection.

 

That is roughly the entire algorithm. In my implementation of it in BASIC I used the value 0 to indicate unowned, 1 to indicate both top and bottom. This was a cheesy to insure that I never connect the top to the bottom because the algorithm mistakenly draws the conclusion that they are already connected because they have the same name and thus will not connecte them. Whenever I need a new owner name for a new floating group I take the value of a counter, n, then bump up the counter. When I connect a group and rename, I always use the least of the two old names for the new name. This is convenient in debugging because it means that the top and the bottom always retain the name of 1 when connected to a floating group. Two variables, za and zd, which are real to match the random number generator, are separate decision constants used so that I can seperately make across (za) connections more frequent or make down (zd) connections more frequent. Also, I zigzag the direction of scan when making the vertical connections to break up the bias generated by always scanning in one direction. (If you always scan top to bottom then the maze starts to get top heavy toward the end.)

 

Conclusions:

 

It works. It is small. It runs fast. The mazes are good but not totally awesome. The reason I make the last statement is because after drawing a bunch of mazes with this program I concluded that the solutions all have roughly the same shape. They are all W shaped, lots of ups and downs, but mostly going rather directly from the lfet to the right. I have not yet generated one that has more of an S-shape. There is something more Psychologically anoying about an S-shaped maze because first you head toward the goal and then must walk away from it before you can actually get there. Making the necessary modification to bias the algorithm in that direction would obsure the underlying simplicity which made this program suitable for exposition.

 

As always, when a difficult problem arrises in the process of showing someone how to do something like drawing a maze, the wisest course if to offer it as an exercise to the astute reader.