In a simple connected maze (also called a perfect maze) there is one solution path and every cell on the maze can be reached. Every path besides the solution ends in a dead end. In other words the way you can tell you are not headed to the solution is that you come to a dead end. Which means you need to backtrack to the next branch and choose another path.
To make a multiply connected maze (also called a braid maze) you need to remove the dead ends. I wrote a dead end remover that works like this:
1) Find the solution path.
2) From the solution path find all the branches off the solution, and mark all the cells with the branch number that they are on. This can be seen below as the number in the cell. The number is the branch number.
3) Iterate over the whole grid (yellow cursor) looking for dead ends.
4) If a dead end is encountered then remove the opposite wall as the entrance to the dead end cell.
5) If the remove of that wall leads two branches to be connected seal one of the entrances to the solution path and merge both branches.
6) Do not remove walls that remove the dead end, but open the branch to the solution path.
This algorithm leads to several things:
1) There is still only one solution path.
2) There is only one way to enter a branch from the solution path.
3) It is harder to figure out that you are down the wrong path, since you are less likely to encounter a dead-end.
However, the algorithm fails in a number of ways:
1) The solution path has lots of passages and few branches making it visual stand out from the maze.
2) The branches appear like Swiss cheese and are not hard to get lost in.
Posts
Not all multiply connected Mazes with loops are "braid" Mazes. A braid Maze is a Maze with zero dead ends (otherwise it's a partially braid Maze). The result here is mostly braid, but as you can see there are still some dead ends adjacent to the edges and the solution path.
ReplyDelete