Wednesday, March 18, 2009

Braid Mazes - And Their Corners

Braid mazes sometimes called purely multiply connected maze, refers to a maze without any dead ends. In an orthogonal mazes (a maze made up of a square cell with four sided) this means that there are no cells with three sides.

Let's consider the corners of an orthogonal maze. Each corner by default has two sides (unless one of the sides is an exit or and entrance). Which means that the other two sides can not have a wall (hedge) in a braid maze. In other words, the cell in the upper left corner of the maze (Northwest) already has two walls, one to the north and one to the west. Adding a wall on the east or the south would create a dead end.

If we have a orthogonal braid maze without any rooms (vertexes without touching walls) the corners are always passages.

In an orthogonal braid maze where is the best place to put the exit (if this is an outside to outside solution)? If you put the exit in the corners, then you will have one of two scenarios:

1) There will be two solutions paths to the exit, since the corner has to be a passage, both sides of the corner cell could be a path to the solution.

2) There will be one solution path to the corner, and one will be a branch (non-solution path). This is probably the worst scenario of the two, since the solver will never take the non-solution path when they are at the exit. Which means that the branch is wasted space. By wasted I mean, not adding to the complexity of the puzzle.

In conclusion: if you are creating a orthogonal braid maze (no dead ends) and want to have a single solution path without wasted space the exit should not be in a corner.

1 comment:

  1. Actually you can have braid Mazes with exits in the corners, without any wasted space. It's true that in a braid Maze, every cell needs to have at least two passages leading from it. However when the exits are on the boundary wall (assuming you have actual exit openings in the boundary wall, as opposed to the exit location just being the cell itself) then the exit opening itself covers one of the two passages. In other words, you can have a long unbranching tunnel that goes straight to and out of a corner. See this braid Maze for an example.

    ReplyDelete