Adventures in labyrinth generation.

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?

Quote:

2. Please follow the forum structure when posting. Post threads on the board best suited for the topic. Please do not cross post (i.e. post the same question on multiple boards). Do not bump threads. (Bumping: Posting messages on threads to move them up the list or to post on a thread that has been inactive for two weeks or longer).

Sounds pretty clear to me.

Quote:

9. Moderators have been granted the right to use their best judgement in the pursuit of community prosperity and peaceful operation. They are permitted to police posts that do not directly infringe the technicalities of a Rule, yet fall outside the intended spirit of them. Also note; The administration reserves the right to modify these guidelines and rules, along with the terms and conditions of use for these forums, at any time, without notification.

Also quite clear.

I was well within the bounds of authority granted to me by the admin of this board when I closed your post. Should you feel I was outside of them you can contact any moderator and take your case up with them.

That's a definition of bumping you don't see every day.

Anyway: to answer the question, it's easy: you don't return an array from a function, not even in C++. (Arrays are second-class citizens like that.) I don't know what you mean by "return an array from an object". If an object owns an array, you can access it by dot notation: my_object.object_array[5].

Quote:

Originally Posted by tabstop

It's easy: you don't return an array from a function, not even in C++. (Arrays are second-class citizens like that.) I don't know what you mean by "return an array from an object". If an object owns an array, you can access it by dot notation: my_object.object_array[5].

Oh yeah. My C++ is so rusty. I find I'm having to relearn it every time I use it, and i end up reverting to plain C in the end.

Yeah, so, duh. Keep the array in the object and access it with dot notion. Okay, this'll be fun.

Am I missing something? Isn't

Code:

int*& array() { int test_array = new int[25]; return test_array; }

I realize that is bad, but is that not returning an array?

Quote:

Originally Posted by Raigne

Am I missing something? Isn't

Code:

int*& array() { int test_array = new int[25]; return test_array; }

I realize that is bad, but is that not returning an array?

IIRC there is a scope issue there where an array declared within a function will likely be overwritten. But maybe I'm wrong. You are allocating that memory, which may be different.

Well, it's returning a pointer to an int. Yes, it's something you can use array notation on, but it's not an array. (And since the memory was allocated by new, it's not a dangling pointer either.)

FWIW, I thought this was simply genius.

Quote:

#
# Unicursal: One way to create a random unicursal Maze is to take a perfect Maze, seal off the exit so there's only the one entrance, then add walls bisecting each passage. This will turn each dead end into a U-turn passageway, and there will be a unicursal passage starting and ending at the original Maze's beginning, that will follow the same path as someone wall following the original Maze. The new unicursal Maze will have twice the dimensions of the original perfect Maze it was based on. Small tricks may be done to have the start and end not always be next to each other: When creating the perfect Maze, never add segments attached to the right or bottom walls, so the resulting Maze will have an easy solution that follows that wall. Have the entrance at the upper right, and after bisecting to create the unicursal routing, remove the right and bottom wall. This will result in a unicursal Maze that starts at the upper right and ends at the lower left.

Image: http://www.astrolog.org/labyrnth/maze/unicursl.gif
Webpage: http://www.astrolog.org/labyrnth/algrithm.htm

But now I see that you've already seen that page. :(
http://www.gamedev.net/community/for...page=1�
[edit=2] Weird, that link was either copied or transmitted incorrectly. Here it is again.
http://www.gamedev.net/community/for...page=1� [/edit]
[edit=3] Urf, it happened again! I guess it's the sequence <ampersand><hash> in the link that makes vBulletin mess up.
Just go here and scroll down. :) http://www.gamedev.net/community/for...opic_id=501637 [/edit]

[edit] Anyway, here's my very ugly half-hour-to-code C++ labyrinth generator that gives you all of the possible labyrinths for a given size.

Yes, it takes forever to execute. And yes, I know positions are reversed. No, I can't be bothered to fix it. :)

Code:

#include <iostream> #include <cstdlib> #include <ctime> class Position { private: int xp, yp; public: Position(int xp, int yp) : xp(xp), yp(yp) {} void add_xp(int add) { xp += add; } void add_yp(int add) { yp += add; } int add_direction(int add, int dir); int get_dirs() { return 4; } void set_xp(int xp) { this->xp = xp; } void set_yp(int yp) { this->yp = yp; } int get_xp() { return xp; } int get_yp() { return yp; } }; int Position::add_direction(int add, int dir) { switch(dir) { case 0: xp += add; break; case 1: xp -= add; break; case 2: yp += add; break; case 3: yp -= add; break; } } class Map { private: static const int WIDTH = 6, HEIGHT = 6; char cell[WIDTH][HEIGHT]; public: Map() { clear(); } void set_cell(int x, int y, char c) { cell[x][y] = c; } char get_cell(int x, int y); bool is_empty(int x, int y) { return get_cell(x, y) == get_empty_char(); } char get_empty_char() { return '-'; } int get_width() { return WIDTH; } int get_height() { return HEIGHT; } void clear(); void display(); bool map_is_full(); }; char Map::get_cell(int x, int y) { if(x < 0 || y < 0 || x >= get_width() || y >= get_height()) { return -1; } return cell[x][y]; } void Map::clear() { for(int x = 0; x < get_width(); x ++) { for(int y = 0; y < get_height(); y ++) { set_cell(x, y, get_empty_char()); } } } void Map::display() { for(int x = 0; x < get_width(); x ++) { for(int y = 0; y < get_height(); y ++) { std::cout << get_cell(x, y); } std::cout << '\n'; } } bool Map::map_is_full() { for(int x = 0; x < get_width(); x ++) { for(int y = 0; y < get_height(); y ++) { if(get_cell(x, y) == get_empty_char()) return false; } } return true; } void trace_labyrinth(Map &map, Position &pos); int main() { std::srand((unsigned)std::time(0)); Map map; Position start( std::rand() % map.get_width(), std::rand() % map.get_height()); map.set_cell(start.get_xp(), start.get_yp(), '@'); trace_labyrinth(map, start); return 0; } void trace_labyrinth(Map &map, Position &pos) { Position next = pos; int startdir = rand() % next.get_dirs(); int dir = startdir; bool found_move = false; do { next = pos; next.add_direction(1, dir); if(map.is_empty(next.get_xp(), next.get_yp())) { map.set_cell(next.get_xp(), next.get_yp(), "v^><"[dir]); trace_labyrinth(map, next); found_move = true; } dir ++; dir %= next.get_dirs(); } while(dir != startdir); if(!found_move) { map.set_cell(pos.get_xp(), pos.get_yp(), '$'); if(map.map_is_full()) { map.display(); std::cout << std::endl; } } map.set_cell(pos.get_xp(), pos.get_yp(), map.get_empty_char()); }

[/edit]

I would start with a unicursal maze generator. I had high hopes for the one shown here:
http://en.wikipedia.org/wiki/Maze_generation_algorithm - about 3/4 the way down the page under "Simple algorithms".

Unfortunately in practice, the mazes generated are less than spectacular. Having numerous enclosed squares and crappy stuff all over. Maybe I need to recheck my code.

Anyhow, maybe there are better algorithms out there.

Then when it's done, use the traditional "right-hand" rule to traverse the path - at the same time start numbering the cells of an array sequentially. Oh, the numeric array is probably twice the rows and cols as the maze - because you are going to travel all around the maze going in and then going out in the same halls.