1
\$\begingroup\$

Is it possible to create a random maze that is solvable and uses a group of cells or single cells that do not depend on the cells around them?

I am using a visual language that uses self contained objects so it’s difficult to tell the other cells/objects what is next to them. I tried using a group of four cells that can only have walls on the right or bottom of the group but it can create areas that are not accessible. The example below has + for the outside border X for walls and 0 for the paths:

Valid groups:

0 X
0 X

and

0 0
X X

A small maze that has paths that are inaccessible

+ + + + + +
+ 0 X 0 0 +
+ 0 X X X +
+ 0 0 0 X +
+ X X 0 X +
+ + + + + +
\$\endgroup\$
2
1
\$\begingroup\$

You're going to have trouble

And you're going to have to suck it up and deal with it. There is no possibility of ensuring that no areas are inaccessible without knowing what's around each cell. If a cell can block access in a given direction, then inaccessible areas must exist unless cells can talk to each other.

Heck, at the moment you aren't even guaranteed a solvable maze:

+ S + + + +
+ 0 X 0 0 +
+ 0 X X X +
+ X X 0 X +
+ 0 0 0 X +
+ + + E + +

The best I was able to do under similar circumstances (the Source engine) was for each cell to have two states:

  • Block South
  • Block East

Then starting from the North-West corner randomly pick between those two states. It would create inaccessible areas in the NE and SW corners, but that was an acceptable loss because the start was always NW corner1 and the exit was always in the SE corner.

This method will always generate a generally South-Eastern solve path, but it is guaranteed to have a path. There will be the occasional inaccessible area, but they're specifically only in the corners.

For example (with S and E tiles completely open):

+ S + + + + + + + +
+ 0 0 0 0 0 X 0 0 +
+ 0 0 X X 0 X X X +
+ 0 X 0 X 0 0 0 X +
+ 0 X 0 X X X 0 X +
+ 0 0 0 X 0 0 0 X +
+ X X 0 X X X 0 X +
+ 0 X 0 0 0 X 0 0 +
+ 0 X X X 0 X 0 0 +
+ + + + + + + + E +

This can still generate unsolvable mazes if you require a specific end square, otherwise you are guaranteed to terminate somewhere along the South or Eastern edge. You said you had the ability (albeit difficult) to perform checks against neighboring cells. This would be where you do it: insuring that not every cell along the N and W walls are all identically aligned (very boring maze) and insuring that the SE corner is connected. The interior though is free to be perfectly random.

Try flipping any 2x2 cell in my example that isn't along an edge: it will always result in a new path.

1Actually it wasn't, it was in the north-center, but I flipped the E-W direction of the NW corner cells so that it was always connected to the start position. Similarly the goal was "anywhere on the South edge"

\$\endgroup\$
3
  • \$\begingroup\$ Awesome! I think I will use a grouping of empty cells in all corners. I am adding destroyable rocks on the paths so I will need every 0 to connect. I am not too concerned about straight lines just as long as I can destroy all of the rocks. \$\endgroup\$
    – Jon White
    Mar 2 '17 at 22:16
  • \$\begingroup\$ Okay I just tried above and there are still areas that are not accessible. The only thing I can think of is to have a path around the whole maze that way all of the rocks are accessible. \$\endgroup\$
    – Jon White
    Mar 3 '17 at 1:29
  • \$\begingroup\$ I did say that there would still be isolated areas. The only way to not have them requires knowing something about the neighboring cells. \$\endgroup\$ Mar 3 '17 at 4:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .