The Labyrinth

Today we are going to make javascript ASCII maze text generator. Why? Labyrinths and ASCII mazes are cool and we can incorporate them into other designs, video games, and artwork. This js maze algorithm 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.

These mazes are not static pictures. They are blocks of ASCII text. I made a js widget, called Amaze, to generate them. It lets you put a random maze on your page, too. Notice that the mazes change on every visit. Refresh the page to see. Visit the Amaze page to customize size and colors and grab the code to embed them on your web site.

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. 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.

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 these. This is an example of how a complicated-looking construction can be fabricated from relatively simple steps.

The formula goes like this:

Look for two stones to break down.
Choose a direction at random.
Knock down those two stones.
Repeat

This is one of the first C / C++ programs I wrote, which I later translated into JavaScript. The function is recursive in that it makes a call to itself. It's a function within a function! I learned a trick to debugging these. Just make a few copies of the function with other names and then when it works right, 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 we put our ingress and egress, there is always one and only one route between them!

function mazeStep(r,c){

    var i,vector=[[0,0],[0,0],[0,0]]; /* 3 possible directions */

    function R(val){

        if(typeof val=="undefined")return vector[i][0];

        vector[i][0]=val;

    }

    function C(val){

        if(typeof val=="undefined")return vector[i][1];

        vector[i][1]=val;

    }

    while(1){

        i=0; /* create a list of possible options */

        if(r>1            &&a[r-2][c]!==" "){R(r-2);C(c);i++;}

        if(r< id.rows*2-1 &&a[r+2][c]!==" "){R(r+2);C(c);i++;}

        if(c>1            &&a[r][c-2]!==" "){R(r);C(c-2);i++;}

        if(c< id.cols*2-1 &&a[r][c+2]!==" "){R(r);C(c+2);i++;}

        /* i is never > 3 because path behind is cleared */

        if(i==0)break; /* check for dead end */

        i=Math.floor((Math.random()*i))|0; /* random direction */

        a[R()][C()]=" "; /* knock out block */

        a[(R()+r)/2|0][(C()+c)/2|0]=" "; /* clear to it */

        mazeStep(R(),C());

    }

}

This algorithm carves out a random maze by erasing nearby blocks.



  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

You can still get the cross-platform C program source code to draw mazes from the command line. Compile with any standard C compiler. Put it in the "My Documents" folder, then go to Start->Run and type "cmd" in the box. type "amaze" for instructions. Terminal-savvy users may redirect the output to a file using a command like amaze 10 25 > maze.txt.

Is ASCII art not good enough? Would an image be better? 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

Programming

Writing JavaScript or C programs 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.

Those looking to get started with computer programming should pick whatever language interests them. I prefer Python, C, PHP, and 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 the extra work setting aside memory to put things and then freeing it later. Other languages do this automatically; however, C is often many times faster and more optimized for the hardware. C gives the programmer more control over the internal workings of the computer. For this reason, C compilers exist for almost any type of hardware, making it inherently cross-platform. C will probably remain the dominant language for operating system developers.