Thread: Labyrinth generation

  1. #16
    Registered User guesst's Avatar
    Join Date
    Feb 2008
    Lehi, UT
    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:

      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.
    Type-ins are back! Visit Cymon's Games at for a new game every week!

  2. #17
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Start a new thread and let this one die.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Vertex normal generation
    By SyntaxError in forum Game Programming
    Replies: 4
    Last Post: 06-08-2009, 12:27 PM
  2. Adventures in labyrinth generation.
    By guesst in forum Game Programming
    Replies: 8
    Last Post: 10-12-2008, 01:30 PM
  3. Diablo's random level generation
    By glo in forum Game Programming
    Replies: 7
    Last Post: 07-19-2008, 03:04 AM
  4. C Program with Tone Generation. HELP
    By LaVieEnRose in forum C Programming
    Replies: 1
    Last Post: 11-22-2007, 08:37 PM
  5. Grid generation from scattered points?
    By canada-paul in forum C Programming
    Replies: 6
    Last Post: 12-12-2003, 05:46 PM