🔒 Locked

Not maze Labryinth generation

Started by guesst Jul 17, 2008 at 11:10 PM 6 replies 3.9k views

Original Post

Jul 17, 2008 at 11:10 PM

Now, don't read the title and think 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. In case you're wondering I want to make a numbrix generator. Are there any geniuses here that can help me with this non-trivial problem? [Edited by - guesst on July 18, 2008 1:18:46 PM]

Hodgman

Jul 17, 2008 at 11:32 PM

The first thing I thought of is simply to brute force it. Pick a start location, randomly choose a valid direction, repeat. If no valid direction can be chosen, then you're at the end. If there are blank spaces still (cells that aren't visited by the path), then you fail, so start the whole process again. Eventually, chance will give you a valid path.

According to this page, a term to search for might be "Unicursal maze".

Quote:
Unicursal: A unicursal Maze means one without any junctions. Sometimes the term Labyrinth is used to refer to constructs of this type, where "Maze" means a puzzle where choices are involved. A unicursal Maze has just one long snake-like passage that coils throughout the extent of the Maze. It's not really difficult unless you accidentally get turned around half way through and make your way back to the beginning again.

guesst

Jul 17, 2008 at 11:56 PM

Quote:
Original post by Hodgman
The first thing I thought of is simply to brute force it. Pick a start location, randomly choose a valid direction, repeat. If no valid direction can be chosen, then you're at the end. If there are blank spaces still (cells that aren't visited by the path), then you fail, so start the whole process again. Eventually, chance will give you a valid path.

According to this page, a term to search for might be "Unicursal maze".
Quote:
Unicursal: A unicursal Maze means one without any junctions. Sometimes the term Labyrinth is used to refer to constructs of this type, where "Maze" means a puzzle where choices are involved. A unicursal Maze has just one long snake-like passage that coils throughout the extent of the Maze. It's not really difficult unless you accidentally get turned around half way through and make your way back to the beginning again.

Woah, good resource there. Gotta get some sleep, but I'm definitely combing that over tomorrow.

Brute forcing would work okay, but you don't need to go back all the way, just to where you can fill in the blank. For that matter, you don't need to finish the maze, just check at every interval if you've made an unreachable space, and if you have back up 3 spaces.... no, that may not work entirely.

guesst

Jul 18, 2008 at 1:18 PM

Quote:
Unicursal: One way to create a random unicursal Maze is to take a perfect Maze, seal off the exit so there's only the one entrance, then add walls bisecting each passage. This will turn each dead end into a U-turn passageway, and there will be a unicursal passage starting and ending at the original Maze's beginning, that will follow the same path as someone wall following the original Maze. The new unicursal Maze will have twice the dimensions of the original perfect Maze it was based on. Small tricks may be done to have the start and end not always be next to each other: When creating the perfect Maze, never add segments attached to the right or bottom walls, so the resulting Maze will have an easy solution that follows that wall. Have the entrance at the upper right, and after bisecting to create the unicursal routing, remove the right and bottom wall. This will result in a unicursal Maze that starts at the upper right and ends at the lower left.

Hmmm, limited. Either the beginning and ending will be in the same place or on the edges. I don't like limitations. But they would work.

I've mapped out all the past numbrixs as unicursal mazes and am analizing them, trying to see what I can do to make it happen. Thorny problem, this.

umbrae

Jul 19, 2008 at 7:05 AM

Perhaps an idea is to start with a straight line from start to finish then continually look for ways to put 'kinks' in it, look at two adjacent empty squares and bend the path into it. Keep running this algorithm over the path until it's bent out of shape. Not only do you want to make additions to the path, but also move it for some modifications.

The key is to always have a valid path so you never have to validate it and try to solve.

guesst

Jul 19, 2008 at 8:44 AM

Quote:
Original post by Umbrae
Perhaps an idea is to start with a straight line from start to finish then continually look for ways to put 'kinks' in it, look at two adjacent empty squares and bend the path into it. Keep running this algorithm over the path until it's bent out of shape. Not only do you want to make additions to the path, but also move it for some modifications.

The key is to always have a valid path so you never have to validate it and try to solve.

That is a possibility and means that I simply insure that I never leave less than 2 spaces next to each other. It also means the in path has to meet up at the out path. It's an idea that bears some thinking out.

Pseudokai

Jul 22, 2008 at 10:28 PM

I'd recommend looking at Hamiltonian paths. If you treat each square in the grid as a vertex then it should be exactly what you're looking for.

guesst

Jul 23, 2008 at 2:18 PM

Quote:
Original post by Pseudokai
I'd recommend looking at Hamiltonian paths. If you treat each square in the grid as a vertex then it should be exactly what you're looking for.

Ooh, fits the description. However, I don't can't find any randomized Hamiltionian path generation algorithms yet. Have to keep looking.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.