Adventures in labyrinth generation.

**guesst** · 10-10-2008

Since the moderators around here believe more militantly in calendar dates than relevance in determining the life of a thread, I'm going to start a new thread here for my adventures in labyrinth generation.

I got busy after my labyrinth generator thread, which gave me a lot of time to consider the problem on a theoretical level. Well, that and I just could not come up with a algorithm that I thought worked. Then it hit me. When we left the previous thread I had just pseudo-coded out what I figured would do the trick, a recursive pattern of trying stuff out, and backing up when it didn't work.

With psuedo-code in hand I hammered out (with a few hicups, naturally) a labyrinth generator. Check it out:

Code:

#include <curses.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 9
#define MAXSECS 1
#define NUMBENDS 8

enum Direction {NONE, UP, LEFT, DOWN, RIGHT, END, CHECK};
enum Direction board[SIZE * SIZE];
int start, end;

enum Direction bends[NUMBENDS][2][2][2] = {      /* [type][before/after][y][x]*/
{{{ NONE, DOWN},{ NONE,  END}},{{ DOWN, LEFT},{RIGHT,  END}}},
{{{ NONE, NONE},{  END, LEFT}},{{ DOWN, LEFT},{  END,   UP}}},
{{{  END, NONE},{   UP, NONE}},{{  END, LEFT},{RIGHT,   UP}}},
{{{RIGHT,  END},{ NONE, NONE}},{{ DOWN,  END},{RIGHT,   UP}}},
{{{ NONE,  END},{ NONE,   UP}},{{RIGHT,  END},{   UP, LEFT}}},
{{{ NONE, NONE},{RIGHT,  END}},{{RIGHT, DOWN},{   UP,  END}}},
{{{ DOWN, NONE},{  END, NONE}},{{RIGHT, DOWN},{  END, LEFT}}},
{{{  END, LEFT},{ NONE, NONE}},{{  END, DOWN},{   UP, LEFT}}}
};
int step[4] = {-SIZE, -1, SIZE, 1};
time_t timer, secs;

int debug=0;
int SIZEindex = 0;
void drawboard (int index) {
    int c;

  if (index > SIZEindex) SIZEindex = index;
  mvprintw(8,20,"Index: %d", index);
  mvprintw(9,20,"Max Index: %d", SIZEindex);
  for (c = 0; c < SIZE*SIZE; c++) {
    move (c/SIZE,(c%SIZE)*2);
    if (c == start) attron (COLOR_PAIR(2));
    else if (c == end) attron (COLOR_PAIR(3));
    else attron (COLOR_PAIR(1));
    switch (board[c]) {
      case NONE : addch('.'); break;;
      case UP   : addch(ACS_UARROW); break;
      case DOWN : addch(ACS_DARROW); break;
      case LEFT : addch(ACS_LARROW); break;
      case RIGHT: addch(ACS_RARROW); break;
      case END  : addch ('E'); break;
      default : printw("%2d",board[c]);
    }
  }
  c = start;
  attrset(COLOR_PAIR(4));
  while(c != end) {
    if (c != start) move (c/SIZE,(c%SIZE)*2);
    switch (board[c]) {
      case UP   : addch(ACS_UARROW); c -= SIZE; break;
      case LEFT : addch(ACS_LARROW); c -= 1; break;
      case DOWN : addch(ACS_DARROW); c += SIZE; break;
      case RIGHT: addch(ACS_RARROW); c += 1; break;
    }
  }
  attrset(COLOR_PAIR(1));
  refresh();
}

void init () {
    initscr ();
    start_color();
    init_pair(1, COLOR_WHITE, COLOR_BLACK);
    init_pair(2, COLOR_WHITE, COLOR_GREEN);
    init_pair(3, COLOR_WHITE, COLOR_RED);
    init_pair(4, COLOR_WHITE, COLOR_YELLOW);
    noecho();
}
        /* The funciton change() is the meat of the space-filling unicursal maze
                             generation that is manditory in Numbrix generation.
       It works by recursively trying different options to build the pattern. */
int change () {
  int xy, c, d, index, mods[50][2]; /* mods[][location/type] */

            /* We perform a checks for completeness and for isolated squares. */
drawboard(0);
  time(&timer);
  if (difftime(timer, secs) > MAXSECS) return 0;
  d = 0;
  for (xy = 0; xy < (SIZE * SIZE); xy++) {
    if (board[xy] == NONE) {
      c = 0; d++;
      for (d = 0; d < 4; d++) {                  /* check for going off edges */
        if (((xy + step[d]) >= 0) && (xy + step[d] < (SIZE * SIZE))/* up & down */
          && ((xy % SIZE) || ((xy + step[d] + 1) % SIZE))           /* left and */
          && (((xy + step[d]) % SIZE) || ((xy + 1) % SIZE)))           /* right */
            if ((board[xy + step[d]] == NONE) /* see if empty sqaure is alone */
              || (xy + step[d] == start) || (xy + step[d] == end))
              c++;
      }
      if (c == 0) return 0;
    }
  }
  if (d == 0) return 1;
       /* Now we make a list of all possible modifications. First the bends...*/
  index = 0;
  for (xy = 0; xy < (SIZE * SIZE) - SIZE; xy++) {
    if ((xy % SIZE) == (SIZE - 1)) continue;
    for (c = 0; c < NUMBENDS; c++) {
      if ((bends[c][0][0][0] != END) && (bends[c][0][0][0] != board[xy])) continue;
      if ((bends[c][0][0][1] != END) && (bends[c][0][0][1] != board[xy + 1])) continue;
      if ((bends[c][0][1][0] != END) && (bends[c][0][1][0] != board[xy + SIZE])) continue;
      if ((bends[c][0][1][1] != END) && (bends[c][0][1][1] != board[xy + SIZE + 1])) continue;
      mods[index][0] = xy; mods[index][1] = c; index++;
    }
  }
  for (d = 0; d < 4; d++) {           /* ...then extending the beginning... */
    if (((start + step[d]) >= 0) && (start + step[d] < (SIZE * SIZE))/* up & down */
      && ((start % SIZE) || ((start + step[d] + 1) % SIZE))           /* left and */
      && (((start + step[d]) % SIZE) || ((start + 1) % SIZE)))           /* right */
      if (board[start + step[d]] == NONE) {
        mods[index][0] = start + step[d];
        mods[index][1] = 100;
        index++;
      }
  }
  for (d = 0; d < 4; d++) {                     /* ...then extending the end. */
    if (((end + step[d]) >= 0) && (end + step[d] < (SIZE * SIZE))  /* up & down */
      && ((end % SIZE) || ((end + step[d] + 1) % SIZE))             /* left and */
      && (((end + step[d]) % SIZE) || ((end + 1) % SIZE)))             /* right */
        if (board[end + step[d]] == NONE) {
          mods[index][0] = end + step[d]; mods[index][1] = 101; index++;
        }
  }
  if (index == 0) return 0; /* no possbile moves */

  for (c = 0; c < index; c++) {                        /* randomize the list. */
    d = rand () % index;
    mods[index][0] = mods[c][0]; mods[index][1] = mods[c][1];
    mods[c][0] = mods[d][0];     mods[c][1] = mods[d][1];
    mods[d][0] = mods[index][0]; mods[d][1] = mods[index][1];
  }
  for (c = 0; c < index; c++) {                  /* iterate through the list. */
mvprintw(debug % 24,40 + 6 * (debug / 24),"%d:%d ",debug++,index-c);
    if(mods[c][1] < 100) {                          /* apply the modification */
      if (bends[mods[c][1]][0][0][0] != END) board[mods[c][0]]           = bends[mods[c][1]][1][0][0];
      if (bends[mods[c][1]][0][0][1] != END) board[mods[c][0] + 1]       = bends[mods[c][1]][1][0][1];
      if (bends[mods[c][1]][0][1][0] != END) board[mods[c][0] + SIZE]     = bends[mods[c][1]][1][1][0];
      if (bends[mods[c][1]][0][1][1] != END) board[mods[c][0] + SIZE + 1] = bends[mods[c][1]][1][1][1];
    } else if (mods[c][1] == 100) {
      if ((mods[c][0] - start) == -1) board[mods[c][0]] = RIGHT;
      if ((mods[c][0] - start) == 1) board[mods[c][0]] = LEFT;
      if ((mods[c][0] - start) == -SIZE) board[mods[c][0]] = DOWN;
      if ((mods[c][0] - start) == SIZE) board[mods[c][0]] = UP;
      d = mods[c][0];
      mods[c][0] = start;
      start = d;
    } else {
      if ((mods[c][0] - end) == -1) board[end] = LEFT;
      if ((mods[c][0] - end) == 1) board[end] = RIGHT;
      if ((mods[c][0] - end) == -SIZE) board[end] = UP;
      if ((mods[c][0] - end) == SIZE) board[end] = DOWN;
      d = mods[c][0];
      mods[c][0] = end;
      end = d; board[end] = END;
    }
drawboard (index); refresh ();/*debug*/
    if (change()) return 1;                         /* recursive call to self */
debug--;
           /* If that didn't work, undo the modification and try the next one */
    if(mods[c][1] < 100) {
      if (bends[mods[c][1]][1][0][0] != END) board[mods[c][0]]           = bends[mods[c][1]][0][0][0];
      if (bends[mods[c][1]][1][0][1] != END) board[mods[c][0] + 1]       = bends[mods[c][1]][0][0][1];
      if (bends[mods[c][1]][1][1][0] != END) board[mods[c][0] + SIZE]     = bends[mods[c][1]][0][1][0];
      if (bends[mods[c][1]][1][1][1] != END) board[mods[c][0] + SIZE + 1] = bends[mods[c][1]][0][1][1];
    } else if (mods[c][1] == 100) {
      board[start] = NONE;
      start = mods[c][0];
    } else {
      board[end] = NONE;
      end = mods[c][0];
      board[end] = END;
    }
refresh ();
  } /* end of loop through list */

  return 0;    /* None of the modifications worked, so back up and try again. */
}

void start_generating () {
  int c;

  do {
    time(&secs);
    for (c = 0; c < SIZE * SIZE; c++) board[c] = NONE;     /* Clear the board */
    start = rand() % (SIZE * SIZE);
    do {
      switch (rand() % 4) {
        case 0 : if (start - SIZE >= 0) {
                   board[start] = UP;
                   end = start - SIZE;
                } break;
        case 1 : if (start % SIZE) {
                   board[start] = LEFT;
                   end = start - 1;
                 } break;
        case 2 : if (start + SIZE < SIZE * SIZE) {
                   board[start] = DOWN;
                   end = start + SIZE;
                 } break;
        case 3 : if ((start + 1) % SIZE) {
                   board[start] = RIGHT;
                   end = start + 1;
                 } break;
      }
    } while (board[start] == NONE);
    board[end] = END;
  } while (change () == 0);
}

int main () {
  init();
  srand (time (NULL));
  start_generating ();
  drawboard (0);
  move (20,0);getch();
  endwin();
  return 0;
}

This version has some rudimentary output so you can see the maze as it's being generated. Perusing over the code you may discover there is a timer involved? Why? The recursiveness of the algorithm should mean the pattern never gets stuck.

Theoretically.

In actual practice, while a search for isolated squares limits a certain amount of "getting trapped" that can occur there are still scenarios which will cause there to be squares that can never get filled. If these problems happen early it can mean that the program is testing every single wrong possibility to change things meaning (apparently) thousands of iterations before getting back far enough to fix the problem, which on my computer was taking a really long time. The real solution would be to make a more rigorous check before moving on. The bandaid solution is to time the process and kill it if it takes to long.

I went with the bandaid solution for now.

So now it will allow the comptuer to run through 1.99 seconds of attempts (which is still in the thousands of attempts) before starting over.

You know, a more robust bandaid solution would be to make the distance it goes back related to how long it's been taking so that hopefully it will just roll back far enough to solve the problem. Naa, better find a more rigorous check.

The more rigorous check I have in mind would check 2 things:

Odd numbered groups of squares to which the start or end can not be extended into to.
Isolated pairs of squares that can not be bent into.

Both of which require I figure out some sort of fill method.

So while I ponder this I look over that spaghetti code up there and think... know what? That'd be about the perfect sort of thing for C++ encapsulation. So I figure that's going to be my next step. To make a labyrinth generator object.

I can never remember. How do you return an array from an object?

Thread: Adventures in labyrinth generation.

Thread Tools

Search Thread

Display

Threaded View

Adventures in labyrinth generation.

Similar Threads

Labyrinth generation

Diablo's random level generation

C Program with Tone Generation. HELP

Grid generation from scattered points?

Random number generation