********************* *******************
*     *   *                     *   *   *
* * * * *** *********** ******* * * * * *
* * * *             * *       *   *   * *
* * * ************* * ******* ********* *
* * * *     *         *   *   *   *     *
* * * * *** ********* * *** ***** * *****
* * *   * *   *   *   * *   *   *     * *
* * ***** *** * * *** * * *** * ***** * *
* *     *   *   *   * * * *   *   *     *
* ***** * * ******* * * * * ***** ***** *
* *     * *         *   * *     *   * * *
*** ***** *************** ***** *** * * *
* * *     *       *       *   *   * *   *
* * *** *** ***** * ***** * * *** * *****
* *   *   *     * *     * * *   * *     *
* * * *** * *** * ***** *** *** * ***** *
* * * *   * *   *     * *     *   *   * *
* * * *** *** ******* * * ***** *** *** *
* * *   *   *   *   * *   *   *     *   *
* ***** *** * * * *** ***** * ***** * ***
* *   * *   * * *   *   *   * *   * *   *
* * * * * ***** * * *** * *** * * ***** *
*   *   *       * *       *     *       *
********************* *******************

The Labyrinth

Today we are going to design a labyrinth. Why, you say? Labyrinths and mazes are cool and you can incorporate them into other designs, video games and artwork. This maze is not unlike the one the mythical artificer, Daedalus, crafted for King Minos of Crete. No ordinary corral, the labyrinth was a maze so complex that even its creator could barely escape it.

I've doodled maybe two or three mazes with pencil and paper in my lifetime and never really had an interest in them. But I had a dream one night after drinking too much Mountain Dew and I remember seeing beautiful mazes swirling around in psychedelic color. I know what you're thinking but I've never done drugs, although I've heard that DMT is naturally released while dreaming.

Drawing a maze by hand is one thing but instructing a computer to do it is another matter. It is as though the mythical minotaur is representative of our creative abilities and the labyrinth is the maze of modern technology that surrounds us enabling only a select few to accomplish something while the rest of us struggle with technical jargon and manuals. Perhaps this ancient myth has some meaning even today. Fret not, however, for it turns out that the formula is very simple. Like any complex problem, it can be broken down into a few easy steps. To demonstrate, we will need to introduce a simple character from the realm of myth and lore.

The Minotaur

What a terrible creature. One can only imagine the disposition of such a thing, half man and half cow, condemned to wander around forever in a twisted Greek housing project. But how did such bovine architecture come to be? Daedalus wasn't keen to let slip the details of its creation. Perhaps he didn't create it after all. I submit that it was the Minotaur who actually did most the work in carving out the labyrinth and I will even advance a formula to support it.

Suppose we have a field of standing stones, denoted by @ characters below. It doesn't matter where the Minotaur enters the field. What does matter is he can only step in any of the 4 compass directions, North, South, East or West. Now suppose this bull-headed creature is so strong he can knock down two stones in a row. He chooses a random direction and promptly breaks down one stone and then another one by ramming them with his head and then he has to rest. This isn't rocket science. Eventually he will reach the edge where the stones are reinforced or he will run out of pairs of stones to break (evidently he feels that knocking down just one stone is somehow beneath him), at which point he will backtrack until another direction can be taken where two stones block the way. The result is a maze exactly like you see at the beginning of this article. This is an example of how a complicated-looking thing can be constructed from relatively simple steps.

The formula goes like this:
  1. Look for two stones to break down.
  2. Choose a direction at random.
  3. Knock down those two stones.
  4. Repeat

This translates into the following "C" function. (My own style, of course.) Click to see the full source code. The function is recursive in that it makes a call to itself. It's a function within a function! I discovered a trick to debugging these. I just make a few copies of the function with other names and then when it works right I combine them all together.

What's really "amazing" about this algorithm is it generates a spanning tree, with branches. Because it's a tree, there are no closed loops. This means that no matter where you put your ingress and egress, there is always one and only one route between them!

void mazestep(char **a,int *rows,int *cols,int r,int c){
    int i,vector[3][2];
    #define ROW vector[i][0]
    #define COL vector[i][1]
    while(1){
        i=0; /* look around */
        if(r>1          &&a[r-2][c] !=' '){ROW=r-2;COL=c;i++;}
        if(r<*rows*2-1  &&a[r+2][c] !=' '){ROW=r+2;COL=c;i++;}
        if(c>1          &&a[r][c-2] !=' '){ROW=r;COL=c-2;i++;}
        if(c<*cols*2-1  &&a[r][c+2] !=' '){ROW=r;COL=c+2;i++;}
        if(!i)break; /* check for dead end */
        i=(int)(i*(rand()/(RAND_MAX+1.0))); /* choose a path */
        a [(ROW+r)/2]   [(COL+c)/2]=' ';    /* knock out a wall */
        a [ROW]         [COL]=' ';          /* clear to it */
        mazestep(a,rows,cols,ROW,COL);      /* repeat */
    }
}
  step 1     step 2     step 3     step 4     step 5     step 6
@@@@@@@@@  @@@@@@@@@  @@@@@@@@@  @@@@@@@@@  @@@@@@@@@  @@@@@@@@@
@@@@@@@@@  @@@@@@@@@  @@@@@@@@@  @@@@@@@@@  @@@@@@@@@  @@@@@@@@@
@@@@@@@@@  @@@@@@@@@  @@@@@@@@@  @@@@@@@@@  @@@@@@@@@  @@@@@@@@@
@@@@@@@@@  @@@@@@@@@  @@@@@ @@@  @@@   @@@  @@@   @@@  @     @@@
@@@@@@@@@  @@@@@@@@@  @@@@@ @@@  @@@@@ @@@  @@@ @ @@@  @@@ @ @@@
@@@@@@@ @  @@@@@   @  @@@@@   @  @@@@@   @  @@@ @   @  @@@ @   @
@@@@@@@ @  @@@@@@@ @  @@@@@@@ @  @@@@@@@ @  @@@@@@@ @  @@@@@@@ @
                                                      
  step 7     step 8     step 9    step 10    step 11    step 12
@@@@@@@@@  @@@@@@@@@  @@@@@@@@@  @@@@@@@@@  @@@@@@@@@  @@@@@@@@@
@@@@@@@@@  @ @@@@@@@  @   @@@@@  @     @@@  @       @  @       @
@@@@@@@@@  @ @@@@@@@  @ @@@@@@@  @ @@@@@@@  @ @@@@@@@  @ @@@@@ @
@     @@@  @     @@@  @     @@@  @     @@@  @     @@@  @     @ @
@@@ @ @@@  @@@ @ @@@  @@@ @ @@@  @@@ @ @@@  @@@ @ @@@  @@@ @ @@@
@   @   @  @   @   @  @   @   @  @   @   @  @   @   @  @   @   @
@@@@@@@ @  @@@@@@@ @  @@@@@@@ @  @@@@@@@ @  @@@@@@@ @  @@@@@@@ @
********************* *******************
* *         * *     *           *       *
* * *** *** * * *** * *** ******* *** * *
*   * * *     *   * * * *       *   * * *
* *** * ***** *** * * * ******* *** * * *
* *   *   *   *   *   * *     *   * * * *
* *** *** * *** ******* * * ***** * * ***
*       * *   *   *     * *   *   * *   *
******* * *** *** * ***** *** * *** *** *
*     * *   * *   *     *   * * *   * * *
* *** * *** *** *** *** * *** * * *** * *
*   *   * *     * *   *   *   *   *   * *
*** ***** ******* *** ***** * ***** * * *
*   *       *           *   * *     * * *
* *** ***** * *********** *** * ***** ***
*     *   * *       * *   * * * *   *   *
******* * * ******* * * *** * * * * *** *
* *     * *   *       *   *   * * *   * *
* * ***** *** *********** * *** *** *** *
* * *   *   *   *   *   * *   * *   *   *
* * * ***** *** * * * * * *** * * *** ***
* *   *       *   * * *   * *   *   * * *
* *** * *********** * ***** ***** * * * *
*     *               *           *     *
********************* *******************

Amaze Your Friends

These mazes are not static pictures. They are blocks of text characters. I made a special cgi version of my program, amaze, to generate them. You will notice that there are new ones every time you visit. Visit the maze lab to generate your own custom mazes. There is also a windows version with command line options. Or get the cross-platform source code and compile with any standard C compiler. Put it in your "My Documents" folder, then go to Start->Run and type "cmd" in the box. type "amaze" for instructions. If you know how to use a terminal, you can redirect the output to a file using a command like amaze 10 25 > maze.txt. The algorithm I used has a weakness and once you figure out what it is you can solve most of the mazes easily, much to the amazement of your friends.

Is ASCII art not good enough for you? Would you rather have it generate an image? This complicated line will convert the output into a .gif image on linux: (requires installation of netpbm-progs and ImageMagick)

./amaze 40 69 >maz~tmp&&asciitopgm `wc -lL maz~tmp`|convert - maze.gif&&rm maz~tmp

Writing a computer program is not much different than giving a set of simple instructions or writing a shopping list. It's just a bit more exact since the computer is more selective about what commands it understands.

If you are looking to get started with computer programming I recommend Python, C, PHP or JavaScript. Python code is clean and easy to read. It has its own help system and the on line manuals and tutorials are fairly good. C is more complicated. The main difference that I have encountered with C is you wind up doing more work setting aside memory to put stuff and then freeing it later whereas other languages do this for you. However, C is often many times faster and it gives the programmer more control over the internal workings of the computer, which makes it the language of choice for operating system developers.

Another language that is fun to learn is HTML/CSS, although it doesn't "do" anything by itself except arrange other content. For example, this page was coded by hand and stored in a database. It is retrieved through MySQL and PHP and other dynamically-generated content is added in. The publishing date is cross-linked to my calendar app. You can look at the source by pressing CTRL-U. You may want to also click the "View" menu and check the box that says, "Wrap Long Lines." The source of most web sites is a mess but over the years I have developed a coding style that separates text from code so it is easier to read. I don't even use those WYSIWYG editors any more.