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