From: court+@CMU.EDU (Court Demas)
Newsgroups: rec.games.programmer
Subject: Maze FAQ
Date: 11 Jan 93 13:04:38 GMT
Article-I.D.: andrew.QfITo6C00WB=EVtKIP
Organization: Carnegie Mellon, Pittsburgh, PA


I'm the "maintainer" of the maze semi-faq.  If anybody has additions please
send them to me (I'm only connected to the net by modem, so I often miss
postings..).  Enjoy..



========================================


Oh, you're really going to love this one.  It's an obfuscated C code
mazegenerator.  Fun fun fun.  Well, if you can figure it out, there's
youralgorithm.  Fun fun fun.

char*M,A,Z,E=40,J[40],T[40];main(C){for(*J=A=scanf(M="%d",&C);
--            E;             J[              E]             =T
[E   ]=  E)   printf("._");  for(;(A-=Z=!Z)  ||  (printf("\n|"
)    ,   A    =              39              ,C             --
)    ;   Z    ||    printf   (M   ))M[Z]=Z[A-(E   =A[J-Z])&&!C
&    A   ==             T[                                  A]
|6<<11<rand()||!C&!Z?J[T[E]=T[A]]=E,J[T[A]=A-Z]=A,"_.":" |"];}

Pretty cute, no?
--
Brad Threatt | MISSING! Single white male Jesus look-alike in blue
       | Members Only jacket.  Answers to the name 'Dave Gillespie'.
Safe sex is  | Last seen with roller-skating couple in Pasadena.
for wimps.   | If found, please return to the cs10 lab immediately.


========================================


In <1992Mar5.210706.24104@wpi.WPI.EDU> rcarter@wpi.WPI.EDU (Randolph
Carter (nee. Joseph H. Allen)) writes:


>>char*M,A,Z,E=40,J[40],T[40];main(C){for(*J=A=scanf(M="%d",&C);
>>--            E;             J[              E]             =T
>>[E   ]=  E)   printf("._");  for(;(A-=Z=!Z)  ||  (printf("\n|"
>>)    ,   A    =              39              ,C             --
>>)    ;   Z    ||    printf   (M   ))M[Z]=Z[A-(E   =A[J-Z])&&!C
>>&    A   ==             T[                                  A]
>>|6<<11<rand()||!C&!Z?J[T[E]=T[A]]=E,J[T[A]=A-Z]=A,"_.":" |"];}
      ^^
This should be 28 if rand() returns a 32-bit quantity.
>>Pretty cute, no?

>No style at all.... :-)

========================================

>--
>/*  rcarter@wpi.wpi.edu */      /* Amazing */             /* Joseph H.
Allen */
>int
a[1817];main(z,p,q,r){for(p=80;q+p-80;p-=2*a[p])for(z=9;z--;)q=3&(r=time(0)
>+r*57)/7,q=q?q-1?q-2?1-p%79?-1:0:p%79-77?1:0:p<1659?79:0:p>158?-79:0,q?!a[p+q*
2
>]?a[p+=a[p+=q]=q]=q:0:0;for(;q++-1817;)printf(q%79?"%c":"%c\n","
#"[!a[q-1]]);}

Well, it doesn't produce a maze, but try this one...

int a=10000,b,c=2800,d,e,f[2801],g;main(){for(;b-c;)f[b++]=a/5;for(;d=0,g=c*2;c
-=14,printf("%.4d",e+d/a),e=d%a)for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b);}
(I disclaim any credit for this!)
--
John Brownie
School of Mathematics and Statistics
University of Sydney
Internet: jhb@maths.su.oz.au



========================================


Excerpts from programming: 6-Mar-92 Re: Algorithm to create a m.. Mark
Howell@movies.enet. (5723)
Here's the single level maze algorithm, solver and printer.

/*
 * MazeGen.c -- Mark Howell -- 8 May 1991
 *
 * Usage: MazeGen [width [height [seed]]]
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define WIDTH 39
#define HEIGHT 11

#define UP 0
#define RIGHT 1
#define DOWN 2
#define LEFT 3

#ifdef TRUE
#undef TRUE
#endif /* TRUE */

#define TRUE 1

#define cell_empty(a) (!(a)->up && !(a)->right && !(a)->down && !(a)->left)

typedef struct {
    unsigned int up      : 1;
    unsigned int right   : 1;
    unsigned int down    : 1;
    unsigned int left    : 1;
    unsigned int path    : 1;
    unsigned int visited : 1;
} cell_t;
typedef cell_t *maze_t;

void CreateMaze (maze_t maze, int width, int height);
void SolveMaze (maze_t maze, int width, int height);
void PrintMaze (maze_t maze, int width, int height);

int main (int argc, char *argv [])
{
    int width = WIDTH;
    int height = HEIGHT;
    maze_t maze;

    if (argc >= 2)
        width = atoi (argv [1]);

    if (argc >= 3)
        height = atoi (argv [2]);

    if (argc >= 4)
        srand (atoi (argv [3]));
    else
        srand ((int) time ((time_t *) NULL));

    if (width <= 0 || height <= 0) {
        (void) fprintf (stderr, "Illegal width or height value!\n");
        exit (EXIT_FAILURE);
    }
    maze = (maze_t) calloc (width * height, sizeof (cell_t));
    if (maze == NULL) {
        (void) fprintf (stderr, "Cannot allocate memory!\n");
        exit (EXIT_FAILURE);
    }
    CreateMaze (maze, width, height);

    PrintMaze (maze, width, height);

    (void) putchar ('\n');

    SolveMaze (maze, width, height);

    PrintMaze (maze, width, height);

    free (maze);

    exit (EXIT_SUCCESS);

    return (0);

}/* main */


void CreateMaze (maze_t maze, int width, int height)
{
    maze_t mp, maze_top;
    char paths [4];
    int visits, directions;

    visits = width * height - 1;
    mp = maze;
    maze_top = mp + (width * height) - 1;
    while (visits) {
        directions = 0;

        if ((mp - width) >= maze && cell_empty (mp - width))
            paths [directions++] = UP;
        if (mp < maze_top && ((mp - maze + 1) % width) && cell_empty (mp + 1))
            paths [directions++] = RIGHT;
        if ((mp + width) <= maze_top && cell_empty (mp + width))
            paths [directions++] = DOWN;
        if (mp > maze && ((mp - maze) % width) && cell_empty (mp - 1))
            paths [directions++] = LEFT;
        if (directions) {
            visits--;
            directions = ((unsigned) rand () % directions);

            switch (paths [directions]) {
                case UP:
                    mp->up = TRUE;
                    (mp -= width)->down = TRUE;
                    break;
                case RIGHT:
                    mp->right = TRUE;
                    (++mp)->left = TRUE;
                    break;
                case DOWN:
                    mp->down = TRUE;
                    (mp += width)->up = TRUE;
                    break;
                case LEFT:
                    mp->left = TRUE;
                    (--mp)->right = TRUE;
                    break;
                default:
                    break;
            }
        } else {
            do {
                if (++mp > maze_top)
                    mp = maze;
            } while (cell_empty (mp));
        }
    }
}/* CreateMaze */


void SolveMaze (maze_t maze, int width, int height)
{
    maze_t *stack, mp = maze;
    int sp = 0;

    stack = (maze_t *) calloc (width * height, sizeof (maze_t));
    if (stack == NULL) {
        (void) fprintf (stderr, "Cannot allocate memory!\n");
        exit (EXIT_FAILURE);
    }
    (stack [sp++] = mp)->visited = TRUE;

    while (mp != (maze + (width * height) - 1)) {
        if (mp->up && !(mp - width)->visited)
            stack [sp++] = mp - width;
        if (mp->right && !(mp + 1)->visited)
            stack [sp++] = mp + 1;
        if (mp->down && !(mp + width)->visited)
            stack [sp++] = mp + width;
        if (mp->left && !(mp - 1)->visited)
            stack [sp++] = mp - 1;

        if (stack [sp - 1] == mp)
            --sp;
        (mp = stack [sp - 1])->visited = TRUE;
    }
    while (sp--)
        if (stack [sp]->visited)
            stack [sp]->path = TRUE;

    free (stack);

}/* SolveMaze */


void PrintMaze (maze_t maze, int width, int height)
{
    int w, h;
    char *line, *lp;

    line = (char *) calloc ((width + 1) * 2, sizeof (char));
    if (line == NULL) {
        (void) fprintf (stderr, "Cannot allocate memory!\n");
        exit (EXIT_FAILURE);
    }
    maze->up = TRUE;
    (maze + (width * height) - 1)->down = TRUE;
    for (lp = line, w = 0; w < width; w++) {
        *lp++ = '+';
        if ((maze + w)->up)
            *lp++ = ((maze + w)->path) ? '.' : ' ';
        else
            *lp++ = '-';
    }
    *lp++ = '+';
    (void) puts (line);
    for (h = 0; h < height; h++) {
        for (lp = line, w = 0; w < width; w++) {
            if ((maze + w)->left)
                *lp++ = ((maze + w)->path && (maze + w - 1)->path) ? '.' : ' ';
            else
                *lp++ = '|';
            *lp++ = ((maze + w)->path) ? '.' : ' ';
        }
        *lp++ = '|';
        (void) puts (line);
        for (lp = line, w = 0; w < width; w++) {
            *lp++ = '+';
            if ((maze + w)->down)
                *lp++ = ((maze + w)->path && (h == height - 1 ||
                         (maze + w + width)->path)) ? '.' : ' ';
            else

                *lp++ = '-';
        }
        *lp++ = '+';
        (void) puts (line);
        maze += width;
    }
    free (line);

}/* PrintMaze */


========================================


Excerpts from programming: 6-Mar-92 Re: Algorithm to create a m.. "Jon
C. R. Bennett"@andr (4255)


gillies@m.cs.uiuc.edu (Don Gillies) writes:
> grid.  Mark each square in the grid with a unique number.  Make a list
what you want to do is make each grid in the maze into a set.

>
>     rooms = n*n         /* each spot in the grid is a unique room */
>
>     repeat
>         pick a random wall without replacement.
>         if the numbers X and Y in the grid on both sides of the wall
>             are different --
>                 delete the wall and use a recursive depth
>                 first search or brute-force loop to replace
>                 all Y in the grid with X's.
        what you do here is instead
        pick a wall
        if the rooms on either side of the wall belong to differnent sets
               delete the wall
               union the two sets together.

the rest is the same


the brute force solution runs in O(n^2) this runs in O(n) (where n is the
number of grids) so if you had a 100 x 100 maze, this method takes 10,000
time steps, the brute force could take as many as 100,000,000 steps.

jon

p.s. below you will find some code to generate a maze this way


---------------------------------------------------
/* maze.c   a maze generator
   Jon Bennett
        jcrb@cs.cmu.edu
   */
/* the maze is generated by making a list of all the internal hedges
   and randomizing it, then going lineraly through the list, we take a
   hedge and se if the maze squares adjacent to it are already connected
   (with find) is not the we connect them (with link), this prevents us
   from creating a maze with a cycle because we will not link two maze
   squares that are already connect by some path */

#include <stdio.h>

#define DOWN 1
#define RIGHT 2
struct maze_loc{
    int rank;
    int x,y;
    struct maze_loc *ptr;
};


struct hedge_loc{
    int x,y,pos,on;
};

struct maze_loc *maze;
struct hedge_loc *hedge;
struct hedge_loc **hedge_list;

void link(a,b)
 struct maze_loc *a,*b;
{
    if(a->rank == b->rank){
        a->ptr=b;
        b->rank++;
        return;
    }
    if(a->rank > b->rank){
        b->ptr=a;
        return;
    }
    a->ptr=b;
}


struct maze_loc *find(a)
 struct maze_loc *a;
{
    if(a != a->ptr){
        a->ptr = find(a->ptr);
    }
    return a->ptr;
}

main(argc,argv)
 int argc;
 char **argv;
{
    int x,y,i,j,k,l,tmp;
    struct maze_loc *a,*b;
    struct hedge_loc *htmp;
    if(argc!=3) exit(1);

    srandom(time(0));
    x=atoi(argv[1]);
    y=atoi(argv[2]);

    /*malloc the maze and hedges */
    maze=(struct maze_loc *)malloc(sizeof(struct maze_loc)*x*y);
    hedge=(struct hedge_loc *)malloc(sizeof(struct
hedge_loc)*((x*(y-1))+((x-1)*y)));
    hedge_list=(struct hedge_loc **)malloc(sizeof(struct hedge_loc
*)*((x*(y-1))+((x-1)*y)));

    /*init maze*/

    for(j=0;j<y;j++){
        for(i=0;i<x;i++){
            maze[x*j+i].x = i;
            maze[x*j+i].y = j;
            maze[x*j+i].ptr = &maze[x*j+i];
            maze[x*j+i].rank=0;
        }
    }
    /*init hedges*/
    for(j=0;j<(y-1);j++){
        for(i=0;i<x;i++){
            hedge[x*j+i].x = i;
            hedge[x*j+i].y = j;
            hedge[x*j+i].pos=DOWN;
            hedge[x*j+i].on=1;
            hedge_list[x*j+i]= &hedge[x*j+i];
        }
    }
    k=x*(y-1);
    for(j=0;j<y;j++){
        for(i=0;i<(x-1);i++){
            hedge[k+(x-1)*j+i].x = i;
            hedge[k+(x-1)*j+i].y = j;
            hedge[k+(x-1)*j+i].pos=RIGHT;
            hedge[k+(x-1)*j+i].on=1;
            hedge_list[k+(x-1)*j+i]= &hedge[k+(x-1)*j+i];
        }
    }

    k=(x*(y-1))+((x-1)*y);
    /*randomize hedges*/
    for(i=(k-1);i>0;i--){
        htmp=hedge_list[i];
        j=random()%i;
        hedge_list[i]=hedge_list[j];
        hedge_list[j]=htmp;
    }
    fflush(stdout);

    l=k;

    /*create maze*/
    for(i=0;i<l;i++){
        j=hedge_list[i]->x;
        k=hedge_list[i]->y;
        a=find(&maze[x*k+j]);
        if(hedge_list[i]->pos==DOWN){
            b=find(&maze[x*(k+1)+j]);
        } else {
            b=find(&maze[x*k+j+1]);
        }
        if(a!=b){
            link(a,b);
            hedge_list[i]->on=0;
        }
    }

    printf("+");
    for(i=0;i<x;i++){
        printf("-+");
    }
    printf("\n");

    l=x*(y-1);

    for(j=0;j<y;j++){
        printf("|");
        for(i=0;i<(x-1);i++){
            if(hedge[l+(x-1)*j+i].on){
               printf(" |");
            } else {
               printf("  ");
            }
        }
        printf(" |\n|");
        if(j<(y-1)){
            for(i=0;i<x;i++){
               if(hedge[j*x+i].on){
                   printf("--");
               } else {
                   printf(" -");
               }
            }
            printf("\n");
        }

    }

    for(i=0;i<x;i++){
        printf("-+");
    }
    printf("\n");

}



========================================



Excerpts from programming: 9-Mar-92 Re: Algorithm to create a m.. Don
Gillies@m.cs.uiuc.ed (609)

Here is another algorithm I just thought of -- how well does it work?

1.  create a GRAPH with n*n nodes.
2.  for each node in the graph create 4 edges, linking it to the
    node in the north, south, east, and west direction.
3.  Assign a random weight to every edge.
4.  Run a minimum spanning tree algorithm (take your choice
    from any algorithms textbook) to produce a graph.  A minimum
    spanning tree has a path from every node to every other node,
    and no cycles, hence, it corresponds to a perfect maze.

Don Gillies - gillies@cs.uiuc.edu - University of Illinois at Urbana-Champaign




========================================
Excerpts from programming: 8-Apr-92 re mazes Chris_Okasaki@LOCH.MESS. (5437)

Thanks for the messages.  FYI, here is the maze tutorial I used to send out.

Chris
--------------
This seems to come up every couple of months, doesn't it?  Maybe we
should make a FAQL for this group...

Anyway, maze generation--a topic near and dear to my heart!  I'm going
to describe the three most common methods.  Note that these will all
generate mazes without loops or rooms or anything like that.  Restricting
a maze to be a tree (in the graph-theoretical sense of the term) simplifies
things immensely.  Mazes with loops are much harder to generate automatically
in any nice way.  Perhaps the best way is start out generating a tree and
then knock a couple of extra walls (all the algorithms start out with all
walls present and then knock out walls as necessary).

Finally, note that all of these techniques are based on well-known graph
algorithms.  This isn't surprising since what is being generated is
really nothing more than a spanning tree.


Technique #1: Depth-first search

1. Pick a random starting location as the "current cell" and mark it
   as "visited".  Also, initialize a stack of cells to empty (the stack
   will be used for backtracking).  Initialize VISITED (the number of
   visited cells) to 1.
2. While VISITED < the total number of cells, do the following:
     If the current cell has any neighbors which haven't yet been visited,
       pick one at random.  Push the current cell on the stack and set the
       current cell to be the new cell, marking the new cell as visited.
       Knock out the wall between the two cells.  Increment VISITED.
     If all of the current cell's neighbors have already been visited, then
       backtrack.  Pop the previous cell off the stack and make it the current
       cell.


This algorithm is probably the simplest to implement, but it has a problem
in that there are many mazes which it cannot generate.  In particular, it will
continue generating one branch of the maze as long as there are unvisited cells
in the area instead of being able to give up and let the unvisited cells get
used by a different branch.  This can be partially remedied by allowing the
algorithm to randomly backtrack even when there are unvisited neighbors, but
this creates the possibility of (potentially large) dead spaces in the
maze.  For some applications, such as dungeon creation, this behavior
might be desirable.  A refinement which cuts down on the amount of dead space
is to vary the probability of backtracking as an increasing function on the
number of iterations since the last backtrack.



Technique #2: Prim's Algorithm

1. Maintain three sets of cells: IN, OUT, and FRONTIER.  Initially, choose
   one cell at random and place it in IN.  Place all of the cell's neighbors in
   FRONTIER and all remaining cells in OUT.
2. While FRONTIER is not empty do the following:  Remove one cell at random
   from FRONTIER and place it in IN.  If the cell has any neighbors in
   OUT, remove them from OUT and place them in FRONTIER.  The cell is
   guaranteed to have at least one neighbor in IN (otherwise it would
   not have been in FRONTIER); pick one such neighbor at random and connect
   it to the new cell (ie knock out a wall).

This algorithm works by growing a single tree (without concentrating
on any one particular branch like the previous algorithm).  An interesting
variation on this algorithm is to run two (or more) instances of it
at once, starting in different locations and generating non-interesecting
trees.  This can be useful, for instance, for generating multiple disjoint
areas on a single level of a dungeon (perhaps connected by secret doors
or perhaps requiring adventurers to blast through walls themselves).


Technique #3: Kruskal's Algorithm

This is perhaps the most advanced of the maze generation algorithms,
requiring some knowledge of the union-find algorithm.  It is also the
most fun to watch in progress!

Basically what the union-find algorithm does is give you a FAST
implementation of equivalence classes where you can do two things:
FIND which equivalence class a given object belongs to, or UNION
two equivalance classes into a single class.  Any moderately advanced
book on algorithms and data structures will have more details.
In this algorithm, the objects will be cells in the maze, and two
objects will be in the same equivalence class iff they are (perhaps
indirectly) connected.

1. Initialize the union-find structures so that every cell is in
   its own equivalence class.  Create a set containing all the interior
   walls of the maze (ie those walls which lie between neighboring cells).
   Set COUNT to the number of cells.  (COUNT is the number of connected
   components in the maze).
2. While COUNT > 1 do the following:
     Remove a wall from the set of walls at random.  If the two cells
     that this wall separates are already connected (test by doing a FIND
     on each), then do nothing; otherwise, connect the two cells (by
     UNIONing them and decrementing COUNT) and knock out the wall.



Note that none of these algorithms make any assumptions about the topology
of the maze.  They will work with 2-d or 3-d grids, toroids, hexagons,
whatever.  However, in the more highly connected topologies (such as 3-d
grids), the deficiencies of the first algorithm will become even more apparent
(it will tend to produce long, winding paths with very little branching).

Have fun with these!

Chris


================================
/*
 * maz.c - generate a maze
 *
 * algorithm posted to rec.games.programmer by jallen@ic.sunysb.edu
 * program cleaned and reorganized by mzraly@ldbvax.dnet.lotus.com
 *
 * don't make people pay for this, or I'll jump up and down and
 * yell and scream and embarass you in front of your friends...
 *
 * compile: cc -o maz -DDEBUG maz.c
 *
 */
#include <stdio.h>

static int      multiple = 57;  /* experiment with this? */
static int      offset = 1;     /* experiment with this? */
#ifdef __STDC__
int maze(char maz[], int y, int x, char vc, char hc, char fc);
void mazegen(int pos, char maz[], int y, int x, int rnd);
#else
int maze();
void mazegen();
#endif

/*
 * maze() : generate a random maze of size (y by x) in maz, using vc as the
 * vertical character, hc as the horizontal character, and fc as the floor
 * character
 *
 * maz is an array that should already have its memory allocated - you could
 * malloc a char string if you like.
 */
#ifdef __STDC__
int maze(char maz[], int y, int x, char vc, char hc, char fc)
#else
int maze(maz, y, x, vc, hc, fc)
char            maz[], vc, hc, fc;
int             y, x;
#endif
{
   int             i, yy, xx;
   int             max = (y * x);
   int             rnd = time(0L);

   /* For now, return error on even parameters */
   /* Alternative is to decrement evens by one */
   /* But really that should be handled by caller */
   if (!(y & 1) | !(x & 1))
      return (1);

   /* I never assume... */
   for (i = 0; i < max; ++i)
      maz[i] = 0;

   (void) mazegen((x + 1), maz, y, x, rnd);

   /* Now replace the 1's and 0's with appropriate chars */
   for (yy = 0; yy < y; ++yy) {
      for (xx = 0; xx < x; ++xx) {
         i = (yy * x) + xx;

         if (yy == 0 || yy == (y - 1))
            maz[i] = hc;
         else if (xx == 0 || xx == (x - 1))
            maz[i] = vc;
         else if (maz[i] == 1)
            maz[i] = fc;
         else if (maz[i - x] != fc && maz[i - 1] == fc
                 && (maz[i + x] == 0 || (i % x) == (y - 2)))
            maz[i] = vc;
         else
            maz[i] = hc;       /* for now... */
      }
   }
   return (0);
}


/*
 * mazegen : do the recursive maze generation
 *
 */
#ifdef __STDC__
void mazegen(int pos, char maz[], int y, int x, int rnd)
#else
void
mazegen(pos, maz, y, x, rnd)
   int             pos, y, x, rnd;
   char            maz[];
#endif
{
   int             d, i, j;

   maz[pos] = 1;

   while (d = (pos <= x * 2 ? 0 : (maz[pos - x - x] ? 0 : 1))
          | (pos >= x * (y - 2) ? 0 : (maz[pos + x + x] ? 0 : 2))
          | (pos % x == x - 2 ? 0 : (maz[pos + 2] ? 0 : 4))
          | (pos % x == 1 ? 0 : (maz[pos - 2] ? 0 : 8))) {
      do {
         rnd = (rnd * multiple + offset);
         i = 3 & (rnd / d);
      } while (!(d & (1 << i)));

      switch (i) {
      case 0:
         j = -x;
         break;
      case 1:
         j = x;
         break;
      case 2:
         j = 1;
         break;
      case 3:
         j = -1;
         break;
      default:
         break;
      }

      maz[pos + j] = 1;
      mazegen(pos + 2 * j, maz, y, x, rnd);
   }

   return;
}


#ifdef DEBUG
#define MAXY 24
#define MAXX 80

#ifdef __STDC__
main(int argc, char *argv[])
#else
main(argc, argv)
   int             argc;
   char           *argv[];
#endif
{
   extern int      optind;
   extern char    *optarg;
   int             x = 79;
   int             y = 23;
   char            hor = '-';
   char            ver = '|';
   char            flo = ' ';
   char            maz[MAXY * MAXX];
   int             i;

   while ((i = getopt(argc, argv, "h:v:f:y:x:m:o:")) != EOF)
      switch (i) {
      case 'h':
         hor = *optarg;
         break;
      case 'v':
         ver = *optarg;
         break;
      case 'f':
         flo = *optarg;
         break;
      case 'y':
         y = atoi(optarg);
         break;
      case 'x':
         x = atoi(optarg);
         break;
      case 'm':
         multiple = atoi(optarg);
         break;
      case 'o':
         offset = atoi(optarg);
         break;
      case '?':
      default:
         (void) fprintf(stderr, "usage: maz [xyhvfmo]\n");
         break;
      }

   if (maze(maz, y, x, ver, hor, flo) == 0) {
      for (i = 0; i < (x * y); ++i) {
         (void) putchar(maz[i]);
         if (((i + 1) % x) == 0)
            (void) putchar('\n');
      }
   } else {
      (void) fprintf(stderr, "Couldn't make the maze\n");
   }

   exit(0);
}
#endif DEBUG

============================

From: merlyn@digibd.com (Merlyn LeRoy)
Subject: Re: Maze generating algorithm (here's one)
Date: Mon, 10 Aug 1992 18:56:42 GMT

rossw@ccu1.aukuni.ac.nz (Ross Williamson) writes:
(wants a maze generator)

OK, here's mine.
---cut here---

#include <stdio.h>

/*
 * maze - a simple maze generator
 *   useage: maze [h] [v] [rooms] [style] [seed1] [seed2]
 *
 * h is horizontal, v is vertical dimensions
 *
 * rooms is number of 2x2 rooms to try to place before generating maze
 * (not all rooms may be placed)
 *
 * style is one of:
 *  -1: change style throughout maze
 *   0: normal maze
 *   1: staircase/zigzag
 *   2: twisty maze
 *   3: long zigzags/corridors
 *   4: spiral maze
 *
 * seed1 & seed2 are random number seeds to use
 *
 */

/* note: longs should be 32 bits */
/* random number seeds */
unsigned long tseed, cseed;

unsigned long turn, curve, random;

int h, v, size;               /* h&v dimensions, and total size */
int style, rooms;              /* maze style, #rooms */
char *maze;
extern char *malloc();         /* maze array; can just use maze[10000] */
/* each cell has bits for the right & bottom wall */
#define NOWALL  0x00
#define RWALL   0x01
#define BWALL  0x02
#define RBWALL 0x03

/* part of a room, and which cell of room prints out room number */
#define ROOM   0x04
#define ROOMNO (0x08|ROOM)
#define RDOOR  0x10
#define BDOOR  0x20
/* empty cells at start */
#define EMPTY  0x40

/*
 * This is a good random number generator
 * someone posted to comp.lang.c
 */
unsigned long
rnd()
{
    cseed *= 69069;
    tseed ^= ((tseed >> 15) & 0x0001FFFF);
    tseed ^= (tseed << 17);

    return(tseed ^ cseed);
}

main(argc, argv)
int argc;
char *argv[];
{
    /* grab args, or plug in default values */
    if (argc >= 4)
        rooms = atoi(argv[3]);
    else
        rooms = -1;
    if (argc >= 3)
        v = atoi(argv[2]);
    else
        v = 20;
    if (argc >= 2)
        h = atoi(argv[1]);
    else
        h = 38;
    if (argc >= 5)
        style = atoi(argv[4]);
    else
        style = -1;
    if (argc >= 6)
        cseed = atoi(argv[5]);
    else
        cseed = h-v+style+rooms;
    if (argc >= 7)
        tseed = atoi(argv[6]);
    else
        tseed = h^(v<<4)^(style<<8);

    /* Let's get small... NOT! */
    if (h < 7 && v < 7)
        h = 7;
    if (h < 3)
        h = 3;
    if (v < 3)
        v = 3;

    /* We pad the maze 1 cell all around so we don't have to check edges */
    h += 2;
    v += 2;
    size = h*v;
    maze = malloc(size);

    if (maze) {
        genmaze();
        printmaze();
    }
}

genmaze()
{
    int i,j,k,ok,n,on,row,count;
    int oi, oj;
    int a[2];

    /* eat up first couple of rnds() */
    rnd();
    rnd();

    /* zero out maze */
    for (i = size-1; i; i--)
        maze[i] = EMPTY;

    /* set up borders */
    for (i = h-1; i; i--)
        maze[i] = BWALL;
    for (i = size-1; i >= size-h; i--)
        maze[i] = NOWALL;

    for (i = size - 2*h; i >= h; i -= h)
        maze[i] = RWALL;
    for (i = size-1; i >= 0; i -= h)
        maze[i] = NOWALL;

    /* turn is likelyhood of turning; curve is direction to turn */
    turn  = 0xFFFFFFFF;
    curve = 0xFFFFFFFF;
    random = 0;
    switch (style) {
    default:
    case -1:
        random = (rnd()+rnd())>>5; /* how often we change styles in maze */
        turn = rnd();                /* totally random attributes */
        curve = rnd();
        break;
    case 0:
        turn  >>= 1;   /* 50% chance to turn */
        curve >>= 1;   /* 50% chance to turn same way */
        break;
    case 1:
        turn  >>= 3;   /* 87% chance to turn */
        curve >>= 3;   /* 87% chance to turn same way */
        break;        /* gives us zigzag maze */
    case 2:
        turn  >>= 3;   /* 87% chance to turn */
        curve >>= 1;   /* 50% chance to turn same way */
        break;        /* gives us twisty maze */
    case 3:
        turn  >>= 4;
        turn = ~turn;  /* 6% chance to turn */
        curve >>= 1;   /* 50% chance to turn same way */
        break;        /* gives us long corridors */
    case 4:
        turn  >>= 4;
        turn = ~turn;  /* 6% chance to turn */
        curve >>= 4;   /* 87% chance to turn same way */
        break;        /* gives us spirals */
    }

    /* count of how many cells we dig until done */
    count = (h-2)*(v-2);

    /* put rooms in first */
    if (rooms == -1)
        rooms = (rnd() & 15) + 1;

    /* occupy top left corner so I can start there */
    maze[1+h] = RBWALL;
    for (; rooms--;) {
        /* pick a rnd location: this needs 32-bit math to work */
        i = ((rnd() & 0xFFFF) * (h-3))>>16;
        j = ((rnd() & 0xFFFF) * (v-3))>>16;
        i++, j++;
        row = j*h;
        /* if I can, put a room there */
        if (count > 4 &&
          maze[i+row] == EMPTY &&
          maze[i+row+1] == EMPTY &&
          maze[i+row+h] == EMPTY &&
          maze[i+row+h+1] == EMPTY) {
            maze[i+row] = ROOMNO;
            maze[i+row+1] = RWALL|ROOM;
            maze[i+row+h] = BWALL|ROOM;
            maze[i+row+h+1] = RBWALL|ROOM;
            count -= 4;
        }
    }
    /* unfill starting cell */
    maze[1+h] = EMPTY;
    i = j = 1;
    row = j*h;

    /* ok & on are turn & curve state variables */
    ok = rnd() & 1;
    on = (rnd() & 2) - 1;

    /* don't branch out from a room unless I have no other choice */
    rooms = ROOM;
    for (; count--;) {
        oi = i; oj = j;
scan:
        a[0] = 3*(maze[i+row-1]!=EMPTY) + (maze[i+row+1]!=EMPTY);
        a[1] = 3*(maze[i+row-h]!=EMPTY) + (maze[i+row+h]!=EMPTY);
        /* This is an easy way to find an open direction */
        if (a[0]+a[1] == 8) {
            /* blocked; find a new place to dig from */
            do {
               i++;
               if (i >= h-1) {
                   i = 1;
                   j++;
                   row += h;
                   if (j >= v-1) {
                      j = 1;
                      row = h;
                   }
               }
               /* if we've scanned whole maze, there are undug places */
               /* that can only be gotten to by digging out rooms; do so */
               if (i== oi && j == oj)
                   rooms = 0;
            } while (maze[i+row] == EMPTY || (maze[i+row] & rooms));
            goto scan;
        }

        /* do I try to turn? */
        if (rnd() > turn)
            ok = 1-ok;
        k = ok;

        /* if a 4, I can't go that way; turn */
        if (a[k] == 4) {
            k = 1-k;
            if (style != 3)    /* this lets style 3 produce long zigzags */
               ok = k;
        }

        /* do I change direction of turn? */
        if (rnd() > curve)
            on = -on;
        n = on;
        /* if sum is 2, I can't go that way; go other way */
        if (a[k]+n == 2)
            n = -n;

        /* If I am going right or down, remove a wall from this cell */
        if (n == 1) {
            if (k == 0)
               maze[i+row] &= ~RWALL;
            else
               maze[i+row] &= ~BWALL;
        }

        /* change to new cell */
        if (k == 0)
            i += n;
        else {
            j += n;
            row = j*h;
        }

        /* new cell has walls */
        maze[i+row] = RBWALL;
        /* If I am going left or up, remove a wall from this cell */
        if (n == -1) {
            if (k == 0)
               maze[i+row] &= ~RWALL;
            else
               maze[i+row] &= ~BWALL;
        }

        /* If maze style is random, change styles occasionally */
        if (rnd() < random) {
            turn = rnd();
            curve = rnd();
        }
    }

    /* Now scan through and make doors out from rooms */
    row = 0;
    for (j = 1; j < v-1; j++) {
        row += h;
        for (i = 1; i < h-1; i++) {
            if (maze[i+row] != ROOMNO)
               continue;
            count = 0;
            do {
               if (rnd() & 1) {
                   k = ((rnd() & 1) ? i+1 : i-1);
                   n = row + (rnd() & 1) * h;
                   if (k > 0 && k < h-2) {
                      maze[k+n] &= ~RWALL;
                      maze[k+n] |= RDOOR;
                      count = 1;
                   }
               }
               else {
                   n = ((rnd() & 1) ? row+h : row-h);
                   k = i + (rnd() & 1);
                   if (n > 0 && n < (v-2)*h) {
                      maze[k+n] &= ~BWALL;
                      maze[k+n] |= BDOOR;
                      count = 1;
                   }
               }
            } while (!count || !(rnd() & 3));
        }
    }
}

printmaze()
{
    int i,j,row,room;

    room = 0;
    for (j = 0; j < v-1; j++) {
        row = h*j;
        for (i = 0; i < h; i++) {
            if (maze[i+row] == EMPTY) {
               putchar('?');
               putchar('?');
               continue;
            }
            if (maze[i+row] == ROOMNO) {
               putchar((room/10)+'A');
               putchar((room%10)+'0');
               room++;
               continue;
            }
            if (maze[i+row] & BWALL)
               putchar('_');
            else {
               if (maze[i+row] & BDOOR)
                   putchar('.');
               else
                   putchar(' ');
            }
            if (maze[i+row] & RWALL)
               putchar('|');
            else {
               if (maze[i+row] & RDOOR)
                   putchar(':');
               else {
                   if ((maze[i+row] & (BWALL|BDOOR)) &&
                     (maze[i+row+1] & (BWALL|BDOOR)))
                      putchar('_');
                   else
                      putchar(' ');
               }
            }
        }
        putchar('\n');
    }
}

---
Merlyn LeRoy


===================================
Newsgroups: rec.games.programmer