Simple Algorithms
Other algorithms exist that require only enough memory to store one line of a 2D maze or one plane of a 3D maze. They prevent loops by storing which cells in the current line are connected through cells in the previous lines, and never remove walls between any two cells already connected.
Most maze generation algorithms require maintaining relationships between cells within it, to ensure the end result will be solvable. Valid simply connected mazes can however be generated by focusing on each cell independently. A binary tree maze is a standard orthogonal maze where each cell always has a passage leading up or leading left, but never both. To create a binary tree maze, for each cell flip a coin to decide whether to add a passage leading up or left. Always pick the same direction for cells on the boundary, and the end result will be a valid simply connected maze that looks like a binary tree, with the upper left corner its root.
A related form of flipping a coin for each cell is to create an image using a random mix of forward slash and backslash characters. This doesn't generate a valid simply connected maze, but rather a selection of closed loops and unicursal passages. (The manual for the Commodore 64 presents a BASIC program using this algorithm, but using PETSCII diagonal line graphic characters instead for a smoother graphic appearance.)
Read more about this topic: Maze Generation Algorithm
Famous quotes containing the word simple:
“Whenever a person strives, by the help of dialectic, to start in pursuit of every reality by a simple process of reason, independent of all sensuous information—never flinching, until by an act of the pure intelligence he has grasped the real nature of good—he arrives at the very end of the intellectual world.”
—Plato (c. 427–347 B.C.)