Thread: Labyrinth generation

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.