[comp.sources.wanted] maze generator

dg@wrs.UUCP (David Goodenough) (06/25/87)

In a recent request sdh@thumper.UUCP asks:
>wanted:
>source to generate a maze.  Simple, right?  not quite.  You must be
>able to get from any point in the maze to any other point, and ideally,
>I would like it to work by starting off with a grid of segments and
>selectively removing them.
>
>Anybody have something that will do this (or something close)?

Hope this is close to what you want .....

To all others on the net: This is public domain - so you may copy it, sell it,
or do whatever you like with it.

--- cut here --------------------- cut here ---
#define DEBUG 1

/* The maze will be generated as a two dimensional array of integers: each
 * integer represents a cell in the maze as a bitmap of four bits - each bit
 * represents a wall: where a 0 bit means the wall is present, and a 1 bit
 * means it is absent.
 * the four bits are:
 * 1 - the wall going to the cell with a X coordinate one less
 * 2 - the wall going to the cell with a Y coordinate one less
 * 4 - the wall going to the cell with a X coordinate one greater
 * 8 - the wall going to the cell with a Y coordinate one greater
 */

#define MAZEX	10		/* width */
#define MAZEY	10		/* height */

#define UNUSED	0x80		/* cell that has never been referenced */
#define CAND	0x40		/* cell that is a candidate for addition */

maze(array)
int array[MAZEY][MAZEX];
 {
    int i, j;
    int done;
    int num_left;

    for (i = 0; i < MAZEY; i++)
      for (j = 0; j < MAZEX; j++)
	array[i][j] = UNUSED;		/* put in all walls & flag all cell as
					 * available */
    num_left = MAZEX * MAZEY - 1;
    i = rand() % MAZEY;
    j = rand() % MAZEX;			/* use of srand will probably help to 
					 * get a different maze each time */
    array[i][j] = 0;			/* create first cell in maze */
    work_round(array, i, j);
    while (num_left)			/* loop till all cells processed */
     {
	for (i = 0; i < MAZEY; i++)
	 {
	    for (j = 0; j < MAZEX; j++)	/* repeatedly scan entire array */
	     {
		if (array[i][j] == CAND && (rand() & 0x1480) == 0)
					/* if we found a candidate && a 1
					 * in 8 random chance succeeds */
		 {
		    do
		     {
			done = 0;	/* haven't added a cell (yet) */
			switch ((rand() & 0x0300) >> 8)
			 {
			    case 0:	/* y coord less 1 */
			     {
				if (i && !(array[i - 1][j] & (CAND | UNUSED)))
				 {	/* neighbour cell belongs to maze */
				    array[i][j] = 2;	/* add new cell */
				    array[i - 1][j] |= 8; /* mark cell it's
							   * attached to */
				    work_round(array, i, j); /* mark all it's
							      * neighbors */
				    done = 1;	/* finish do while loop */
				    num_left--; /* one less cell to add */
				 }
			     }
			    break;
			    case 1:	/* x coord less 1 */
			     {
				if (j && !(array[i][j - 1] & (CAND | UNUSED)))
				 {
				    array[i][j] = 1;
				    array[i][j - 1] |= 4;
				    work_round(array, i, j);
				    done = 1;
				    num_left--;
				 }
			     }
			    break;
			    case 2:	/* y coord plus 1 */
			     {
				if (i != MAZEY - 1 &&
					!(array[i + 1][j] & (CAND | UNUSED)))
				 {
				    array[i][j] = 8;
				    array[i + 1][j] |= 2;
				    work_round(array, i, j);
				    done = 1;
				    num_left--;
				 }
			     }
			    break;
			    case 3:	/* x coord plus 1 */
			     {
				if (j != MAZEX - 1 &&
					!(array[i][j + 1] & (CAND | UNUSED)))
				 {
				    array[i][j] = 4;
				    array[i][j + 1] |= 1;
				    work_round(array, i, j);
				    done = 1;
				    num_left--;
				 }
			     }
			    break;
			 }
		     } while (!done);
		 }
	     }
	 }
     }
 }

work_round(array, i, j)			/* takes a cell, and marks all
					 * neighbours of that cell as possible
					 * candidates for addition to maze */
int array[MAZEY][MAZEX];
 {
    if (i && array[i - 1][j] == UNUSED)
      array[i - 1][j] = CAND;		/* mark first neighbour as possible */
    if (j && array[i][j - 1] == UNUSED)
      array[i][j - 1] = CAND;		/* mark second neighbour as possible */
    if (i != MAZEY - 1 && array[i + 1][j] == UNUSED)
      array[i + 1][j] = CAND;		/* mark third neighbour as possible */
    if (j != MAZEX - 1 && array[i][j + 1] == UNUSED)
      array[i][j + 1] = CAND;		/* mark second neighbour as possible */
 }

#ifdef DEBUG

main()
 {
    int array[MAZEY][MAZEX];
    int i, j;

    maze(array);		/* generate the maze */
    for (i = 0; i < MAZEX; i++)
      printf("+--");
    printf("+\n");		/* print top line */
    for (i = 0; i < MAZEY; i++)
     {
	putchar('|');		/* left wall always there */
	for (j = 0; j < MAZEX; j++)
	  printf((array[i][j] & 4) ? "   " : "  |");
				/* print right walls of cells as needed */
	printf("\n+");
	for (j = 0; j < MAZEX; j++)
	  printf((array[i][j] & 8) ? "  +" : "--+");
				/* and print bottom walls as needed */
	putchar('\n');
     }
 }

#endif