Thread: Labyrinth generation

  1. #1
    Registered User guesst's Avatar
    Join Date
    Feb 2008
    Location
    Lehi, UT
    Posts
    179

    Labyrinth generation

    Now, don't read the title and thing you know what I'm talking about. I mean labyrinth generation, not maze generation. I'm distinguishing it by the definition that a maze is multi-branching and a labyrinth is a single winding path.

    What I'm going to try to figure out is how to fill a grid with a single winding path. There must be no empty spaces left. It can begin and end anywhere.

    The labyrinth can be stored as nothing but a pointer to the next direction, the walls aren't that important. In fact for what I have in mind the walls are only going to get in the way. I want to make a numbrix generator.
    Type-ins are back! Visit Cymon's Games at http://www.cymonsgames.com for a new game every week!

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    You could look into space-filling curves, although that might get a bit too regular/predictable for your purposes.

  3. #3
    Registered User guesst's Avatar
    Join Date
    Feb 2008
    Location
    Lehi, UT
    Posts
    179
    Quote Originally Posted by tabstop View Post
    You could look into space-filling curves, although that might get a bit too regular/predictable for your purposes.
    Now all I need is a random space-filling curve.

    As I puzzle over this problem I've got a couple of ideas:
    • Each grid point points one direction and you keep spinning them until you get a straight path. (How do you determine which one to spin?)
    • Build the path from a randomly chosen middle, backing up if a block gets isoloated. (All that flailing's got to pay off at some point)
    • Break walls randomly until they're all connected to only 2 other blocks. (Somehow I don't see this one working.)
    • Think about the wall. (I need to make some illustrations.)
    Type-ins are back! Visit Cymon's Games at http://www.cymonsgames.com for a new game every week!

  4. #4
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    There are plenty of algorithms for 'maze' generation and 'maze' path finding. Regardless of the nomenclature you choose to abide by in the end it's the same old thing. A maze.

  5. #5
    Registered User guesst's Avatar
    Join Date
    Feb 2008
    Location
    Lehi, UT
    Posts
    179
    Quote Originally Posted by Bubba View Post
    There are plenty of algorithms for 'maze' generation and 'maze' path finding. Regardless of the nomenclature you choose to abide by in the end it's the same old thing. A maze.
    True, but I think you'll find the problem of maze generation with a single continuous path is a different problem than multi-branching paths of normal mazes. True that Maze and Labyrinth are often used interchangeably, there is a distinction in art made for labyrinths.
    Type-ins are back! Visit Cymon's Games at http://www.cymonsgames.com for a new game every week!

  6. #6
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    There is no difference in computers between them. A multi branching path maze can be both solved and created extremely fast using a stack. I would consider a labyrinth a complex connection of smaller mazes. So you might have a 4x4 array of mazes all interconnecting all creating just one correct path through the complete labyrinth.

    Code:
    class maze_cell
    {
      ...
      unsigned int maze_id;
      unsigned int row;
      unsigned int col;
      bool walls[4];
    };
    
    class maze
    {
      ...
      int height;
      int width;
      maze_cell *maze_data;
    };
    
    class labyrinth
    {
      ...
      int height;
      int width;
      maze *labyrinth_data;
    };
    Last edited by VirtualAce; 07-17-2008 at 08:20 PM.

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Bubba View Post
    There is no difference in computers between them. A multi branching path maze can be both solved and created extremely fast using a stack. I would consider a labyrinth a complex connection of smaller mazes. So you might have a 4x4 array of mazes all interconnecting all creating just one correct path through the complete labyrinth.
    I would be surprised if that got anywhere near the "all squares must lie on the path" criterion -- any dead end and its wrong.

  8. #8
    Registered User guesst's Avatar
    Join Date
    Feb 2008
    Location
    Lehi, UT
    Posts
    179
    Quote Originally Posted by tabstop View Post
    I would be surprised if that got anywhere near the "all squares must lie on the path" criterion -- any dead end and its wrong.
    Bubba , I think you missed that criteria in the original post. Every grid square must be a part of a single, non-branching path through the labyrinth. Like connecting every grid square with a single line without overlaps.

    Now what tabstop said is only true to a point. there are in fact 2, and exactly 2, dead ends; one that marks the start of the path, and one that marks the end.

    Dang it, I left the graph paper I printed out at work.
    Type-ins are back! Visit Cymon's Games at http://www.cymonsgames.com for a new game every week!

  9. #9
    Registered User
    Join Date
    May 2006
    Posts
    169
    I have found this site very useful by presenting you with several algorithms and explaining them step by step.
    For example, I chose the Growing Tree method for perfect maze creation that you can check out a few posts below.

  10. #10
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    There are maze solvers that will solve this problem. Non-branching means nothing. Of course it's not going to overlap and if it died at dead ends then it wouldn't be worth much.

    Google for maze algorithms.

  11. #11
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Apparently the term of art is unicursal maze, or at least it is according to this page.

  12. #12
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    If every point must be in the path what is the point of the maze? Someone navigating it would simply just walk from one end to the next with no decision making to be done.

  13. #13
    Registered User guesst's Avatar
    Join Date
    Feb 2008
    Location
    Lehi, UT
    Posts
    179
    Quote Originally Posted by Thantos View Post
    If every point must be in the path what is the point of the maze? Someone navigating it would simply just walk from one end to the next with no decision making to be done.
    I thought the same thing when I read about the labyrinths they have in churches the first time. But for producing Numbrixs this method is necessary. Basically, you make the path, number it from start to end, and delete all the numbers in the middle.
    Type-ins are back! Visit Cymon's Games at http://www.cymonsgames.com for a new game every week!

  14. #14
    Registered User guesst's Avatar
    Join Date
    Feb 2008
    Location
    Lehi, UT
    Posts
    179
    Just a quick update:
    I've set myself to the task of writing a Numbrix generator and wanted to give an update of the process. Making a Numbrix starts out by making a path that winds through a grid and occupies the whole grid. It turns out this is called a "unicursal" maze. I know this because two forums (pretty much at the same time) pointed me to the excellent Think Labyrinth website.

    The algorithm described on Think Labyrinth for generating Unicursal mazes I found entirely too restrictive, so I put myself in contact with Walter Pullen, the man behind Think Labyrinth. In an e-mail to me he had this to say:

    There's another technique of producing Unicursal Mazes in "Daedalus", although it takes a few steps. Starting with a single line across the Maze area (easiest way is to make a standard perfect Maze and then solve it, leaving just the solution path). Then make that line buckle in the middle, randomly spreading throughout the area like yarn being stuffed into a box (this is accomplished with the "Tweak Passages" command, when configured appropriately). This is slow, tends to produce a Maze with a texture similar to intestines, and leaves a few unfilled cells at the end, however it is a completely alternative approach.
    Now that's more like it, only I have to figure out how to avoid the few unfilled cells. I have a theory that involves insuring that there are no contiguous blocks of an odd number of unfilled cells. There are nuances that have to be worked out still, but on paper this approach looks pretty good.
    Last edited by guesst; 07-21-2008 at 11:10 AM.
    Type-ins are back! Visit Cymon's Games at http://www.cymonsgames.com for a new game every week!

  15. #15
    Registered User
    Join Date
    Oct 2007
    Posts
    166
    Making it fill all spaces might be hard but surely not impossible. At least humans can do it.:P

    What do you need this for? Do you want to go through a set of actions in a random way and make sure it goes through them all while always going to a neighboring action?

    Depending on what you need it for you could your self pretty quickly draw out any given number of labyrinths and store them away for use in your program. Then it can pick a random one at runtime, perhaps rotating it etc.

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