Maze generation

[M Darrin Chaney]

In article <1215 at syacus.acus.oz> martins at syacus.acus.oz (Martin Schwenke) writes:
>I am interested in software or algorithms for generating mazes with
>unique solutions. I am also, but less, interested in maze solving
>algorithms, and programs.
>
>Any useful info would be appreciated.

Martin (and other gamers)-

	I have included at the bottom of this message a small
recursive program/routine that will generate random mazes.  It should
run on an Ultrix/Unix platform with no modifications, or on a VMS
platform with the "random/srandom" functions renamed to "rand/srand"
(or, better yet, write the functions for VMS to use the built-in
mth$random).

	Here is how it works.  The maze is stored as a large array, in
this case 500x500.  You enter the maze size with command line options.
Each piece of the array represents a cell.  Each cell has four walls,
numbered clockwise from 0 to 3.  The wall is represented by its corresponding
bit.  If the bit is on, then the wall exists.  Otherwise, the wall
doesn't exist, and one can travel in that direction to the next cell.
Keep in mind, then, that an unoccupied cell has a value of 15 decimal,
or 1111 binary.

	To generate the maze, we must think recursively.  First, we
start at the upper left-hand corner (1,1).  We'll call our maze
generating function make_maze, and it will be called with 2 arguments,
which are an x,y coordinate pair.   So, to start the maze, we'll use
make_maze(1,1).

	The first thing the function does is to pick a random
permutation.  For the four directions, taken one at a time, there are
4*3*2*1, 24, ways that they could be taken.  So, we pick a number from
0 to 23.  Then, we go through each of the four ways in that order.  At
each one, we test whether or not we can go that direction.  If so, we
call make_maze with that coordinate pair.  If not, we simply try the
next direction.  The maze generating loop is only 16 lines.

	I included another piece of code that picks a suitable exit.
As a matter of fact, the exit it picks is the edge cell that is
farthest from the beginning (through the maze, that is).

	The version at the bottom will display its maze with the VT100
graphics set, which is available on almost all emulators.  The picture
isn't perfect, as I needed 4 little pieces that weren't there, but I
think you'll get the picture.  If you'd like, I also have a ReGIS
version which draws the maze, then solves it, all graphically, and
slow enough to watch how it works.  I can make no guarantees that it
works perfectly on a VT240, but it should for mazes down to 50x30 or
so.  If you'd like that version, just drop some email.  If you have
any questions, just write.

	Cheers-

		Darrin

M Darrin Chaney
mdchaney at bronze.ucs.indiana.edu
mdchaney at rose.ucs.indiana.edu
mdchaney at iubacs

-------------------------------------------------------------------------------
/*
  M Darrin Chaney

  Command line options:

	-x : set nummber of columns
	-y : set number of rows
	-r : specify seed for random number generator

  make_maze -x 20 -y 20 -r 4
*/

#include <stdio.h>
#include <math.h>
#include <time.h>

#define MAXX 500
#define MAXY 500

int deltax[4]={0,1,0,-1};
int deltay[4]={-1,0,1,0};

unsigned char maze[MAXX+1][MAXY+1];

int perms[24][4]={{0,1,2,3},{0,1,3,2},{0,2,1,3},{0,2,3,1},{0,3,1,2},{0,3,2,1},
                  {1,0,2,3},{1,0,3,2},{1,2,0,3},{1,2,3,0},{1,3,0,2},{1,3,2,0},
                  {2,0,1,3},{2,0,3,1},{2,1,0,3},{2,1,3,0},{2,3,0,1},{2,3,1,0},
                  {3,0,1,2},{3,0,2,1},{3,1,0,2},{3,1,2,0},{3,2,0,1},{3,2,1,0}};

/* pieces array is just for the VT100 graphics viewer */
char pieces[16]={32,32,32,109,32,120,108,116,
                 32,106,113,118,107,117,119,110};

int maxx=21,maxy=21;

int max_level=0,max_level_x,max_level_y;

int srandom();
int random();

main(argc,argv)
int argc;
char *argv[];
{
  int i,j,k,x,y;
  char line[202];
  int ran,gran=0,dir;

  for (i=1 ; i<argc ; i++)
  {
    if (*argv[i]=='-')
    {
      switch (*(argv[i]+1))
      {
      case 'x':
        maxx=atoi(argv[++i])+1;
        break;
      case 'y':
        maxy=atoi(argv[++i])+1;
        break;
      case 'r':
        ran=atoi(argv[++i]);
        gran=1;
        break;
      default:
        fprintf(stderr,"Unknown flag: %s\n",argv[i]);
        break;
      }
    }
    else
    {
      fprintf(stderr,"Unknown flag: %s\n",argv[i]);
    }
  }

  if (gran==1)
    srandom(ran);
  else
    srandom(time(0));

  for (x=0 ; x<maxx+1 ; x++)
    for (y=0 ; y<maxy+1 ; y++)
      if ((x==0) || (x==maxx) || (y==0) || (y==maxy))
        maze[x][y]=0;
      else
        maze[x][y]=15;

  make_maze(1,1,0,2);

/* The rest of this is just for the viewer */
   for (y=0 ; y<maxy+1 ; y++)
   {
      maze[0][y]=2;
      maze[maxx][y]=8;
   }

   for (x=1 ; x<maxx ; x++)
   {
      maze[x][0]=4;
      maze[x][maxy]=1;
   }

   maze[0][0]=maze[maxx][0]=maze[maxx][maxy]=maze[0][maxy]=0;

   for (y=0 ; y<maxy ; y++)
   {
      for (i=0,x=0 ; x<maxx ; x++,i++)
         {
            line[i]=0;
            if (maze[x][y] & 2) line[i] += 1;
            if (maze[x][y] & 4) line[i] += 8;
            if (maze[x+1][y+1] & 1) line[i] += 2;
            if (maze[x+1][y+1] & 8) line[i] += 4;
            line[i]=pieces[line[i]];
         }
      line[i]=0;
      printf("\033(0%s\033(B\n",&line[0]);
   }
}

make_maze(x,y,level,dir)
int x,y,level,dir;
{
  int i,j,k;
  int direction,perm_num;

  if ((level>max_level) && ((x==1) || (y==1) || (x==maxx-1) || (y==maxy-1)))
  {
    max_level=level;
    max_level_x=x;
    max_level_y=y;
  }

  perm_num = random() % 24;

  for (k=0 ; k<4 ; k++)
  {
    direction=perms[perm_num][k];

    i=x+deltax[direction];
    j=y+deltay[direction];

    if (maze[i][j]==15)
    {
      maze[x][y] -= (1 << direction);
      maze[i][j] -= (1 << (direction ^ 2));
      make_maze(i,j,level+1,direction);
    }
  }
}

fatal_error(str)
char *str;
{
  fprintf(stderr,"Error: %s\n",str);
  exit(0);
}

-------------------------------------------------------------------------------

mdchaney at iubacs
mdchaney at bronze.ucs.indiana.edu
mdchaney at rose.ucs.indiana.edu