Folks are still finding this thread, I assume because of the title, so I thought I'd post here since I have had some small breakthru. I hope the mods will forgive some possible thread necromancy.
I've got it. I'm writing the code now. Well, not right now, but you get my drift. The trick is a recursive algorithm, I don't know what took me so long. Once I figured that out the hardest part was how to represent the data. I want to psuedo code out the solution I have made here, for anyone else searching Labyrinth Generation in the future.
Before I start, let me reiterate a labyrinth is a single winding path, no branches like a maze, and I'm trying to make a space filling labyrinth:
Code:
Globals:
enum direction = {NONE, UP, DOWN, LEFT, RIGHT, END}
directions board[SIZE*SIZE];
int start, end;
void start_generation () {
clear the board[];
start = any random square;
board[start] = any random direction provided it doesn't point at the edge;
end = the square start points at;
board[end] = END;
change ()
}
int change () {
Check the board for isolated squares that the start or end can not extend to;
If there are isolated squares return 0;
/* The above check is not technically necessary,
but will cut down some of the maze generation time.
There are other checks that can be made, but I don't
foresee them paying off as much. */
Check to see if the board is filled;
If the board is filled return 1;
Fill a list of all possible modifications that can be made to the code including:
- Entending the start or end into empty squares
- redirecting the middle of the path into empty squares (bend)
/* The following should take into account that the
list could be 0 in length. If not a check will need to be made */
Randomize the list;
Iterate through the list {
Apply the modification;
call change ();
if change() returned 1 return 1;
else undo the modification;
}
return 0;
}
I can't wait to watch this thing in action. It will be like watching a worm grow and shrink until it fills the space.
I'll notify this thread (assuming I don't tick of the mods too much) when the program that uses this goes live.