Orthogonal mazes consists of square cells with four walls (hedges) in a square or rectangular maze. Each of the wall may be removed to create different exits from the cell. In a simply connected (perfect maze) where all the cells are reachable by definition each cells can have zero through three hedges, however no cell can have four hedges.
This leads to four basic constructions of the cells:
Dead End - a cell with three hedges (4 orientations)
Passage - a cell with two hedges (6 orientations). Passages can be divided into two types, straight corridor (2 orientations) and corners (4 orientations).
Fork - a cell with one hedge (4 orientations). Each fork presents a decision to the solver.
Cross Roads - a cell with no hedges. Each fork presents a decision to the solver, with two choices. (1 orientation)
{6230289B-5BEE-409e-932A-2F01FA407A92}
Friday, March 13, 2009
Subscribe to:
Post Comments (Atom)
Posts
There's one other cell type: the "hole", or a cell with four hedges (1 orientation). This is a trap with no way out, and an isolated point inaccessible from the rest of the Maze. Although usually considered a flaw (e.g. why not connect it to the rest of the Maze) they may be encountered when creating or solving Mazes.
ReplyDeleteNote that dead end and fork/junction are duals of each other, where inverting each hedge's state converts one to the other. Similarly, crossroads and hole are duals of each other. (Straightaways and corners are their own duals.)