random maze generator

[Dave Kirsch]

> smarison writes:
> Does anyone have any good random maze generators written in C? I'm
> writing a program and need to generate a random maze but I have no
> idea how to do it.

Here is a little maze program I hacked out a while ago:


#include <stdio.h>
#include <stdlib.h>

int maze[10][10];

#define NORTH 0x01
#define SOUTH 0x02
#define WEST  0x04
#define EAST  0x08

int dirs[4] = {0x01, 0x02, 0x04, 0x08};
int cdirs[4];

void generate(void)
{
int x, y;
int n;
int i, j, k, l;

  x = random(10);
  y = random(10);
  n = 99;

  for (i = 0; i < 10; i++)
    for (j = 0; j < 10; j++)
      maze[i][j] = 0;

  while (n > 0) {
    printf("%d  ", n);

    for (i = 0; i < 4; i++)
      cdirs[i] = dirs[i];
    for (i = 0; i < 10; i++) {
      do {
        j = random(4);
        k = random(4);
      } while (j == k);
      l = cdirs[j];
      cdirs[j] = cdirs[k];
      cdirs[k] = l;
    }

    for (i = 0; i < 4; i++)
      switch (cdirs[i]) {
        case NORTH :
          if (y == 0 || maze[x][y - 1] != 0)
            break;
          maze[x][y--] |= NORTH;
          maze[x][y] |= SOUTH;
          goto next;
        case SOUTH :
          if (y == 9 || maze[x][y + 1] != 0)
            break;
          maze[x][y++] |= SOUTH;
          maze[x][y] |= NORTH;
          goto next;
        case WEST :
          if (x == 0 || maze[x - 1][y] != 0)
            break;
          maze[x--][y] |= WEST;
          maze[x][y] |= EAST;
          goto next;
        case EAST :
          if (x == 9 || maze[x + 1][y] != 0)
            break;
          maze[x++][y] |= EAST;
          maze[x][y] |= WEST;
          goto next;
      }

    /* if here... no place to go */
    if (x == 9) {
      x = 0;
      if (y == 9)
        y = 0;
      else
        y++;
    } else
      x++;

    while (maze[x][y] == 0) {
      if (x == 9) {
        x = 0;
        if (y == 9)
          y = 0;
        else
          y++;
      } else
        x++;
    }

    continue;

    next :

    n--;
  }
  printf("\n\n");
}

void printmaze(void)
{
int i, j;

  printf("+");
  for (i = 0; i < 10; i++)
    printf("-+");
  printf("\n");

  for (i = 0; i < 10; i++) {
    printf("|");
    for (j = 0; j < 10; j++)
      if (maze[j][i] & EAST)
        printf("  ");
      else
        printf(" |");
    printf("\n+");
    for (j = 0; j < 10; j++)
      if (maze[j][i] & SOUTH)
        printf(" +");
      else
        printf("-+");
    printf("\n");
  }

}

void main(void)
{
  generate();
  printmaze();
}

It generates a 10x10 maze with bits set on each int in the maze array
indicating openings in that direction (the #defines list what bits coorespond
to what direction).

This is a interesting little algorithm in that it only generates one solution
to a maze, though it may not be the most effeicent.

Yes, I know there is a goto in the code, but, like I said, I just played one
day on how to generate a maze and came up with this, it was just a quick hack
:)

It's written in portable ANSI C, except for the random() function I think. I'm
using Turbo C under MSDOS and it has a random function.  random() is a macro
defined as: #define random(n) (rand() % (n))
So all it does is take the value from the rand() function (which returns 0 to
32767) and mods it to the range n.  So random(10) will return a random number
from 0 to 9.

Have fun.

Dave Kirsch -- a563 at mindlink.UUCP