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.