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.

You could look into space-filling curves, although that might get a bit too regular/predictable for your purposes.

Originally Posted by tabstop

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.)

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.

Originally Posted by Bubba

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.

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;
};

Originally Posted by Bubba

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.

Originally Posted by tabstop

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.

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.

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.

Apparently the term of art is unicursal maze, or at least it is according to this page.

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.

Originally Posted by Thantos

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.

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.

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.