Editing Maze generation algorithm (section)

== Simple algorithms ==
[[File:Prim Maze 3D.svg|right|thumb|3D version of Prim's algorithm. Vertical layers are labeled 1 through 4 from bottom to top. Stairs up are indicated with "/"; stairs down with "\", and stairs up-and-down with "x". Source code is included with the image description.]]
Other algorithms exist that require only enough memory to store one line of a 2D maze or one plane of a 3D maze. Eller's algorithm prevents loops by storing which cells in the current line are connected through cells in the previous lines, and never removes walls between any two cells already connected.<ref>{{cite web |author=Jamis Buck |title=Maze Generation: Eller's Algorithm |url=http://weblog.jamisbuck.org/2010/12/29/maze-generation-eller-s-algorithm |date=29 December 2010}}</ref> The Sidewinder algorithm starts with an open passage along the entire top row, and subsequent rows consist of shorter horizontal passages with one connection to the passage above. The Sidewinder algorithm is trivial to solve from the bottom up because it has no upward dead ends.<ref>{{cite web| author=Jamis Buck |title=Maze Generation: Sidewinder Algorithm |url=http://weblog.jamisbuck.org/2011/2/3/maze-generation-sidewinder-algorithm |date=3 February 2011}}</ref> Given a starting width, both algorithms create perfect mazes of unlimited height.

Most maze generation algorithms require maintaining relationships between cells within it, to ensure the 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 result will be a valid simply connected maze that looks like a [[binary tree]], with the upper left corner its root. As with Sidewinder, the binary tree maze has no dead ends in the directions of bias.

[[File:Commodore 64 maze.png|thumb|upright=1.3|Maze generated in Commodore 64 BASIC, using the code {{sxhl|10 PRINT CHR$(205.5+RND(1)); : GOTO 10|cbmbas}}]]
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, using [[PETSCII]] diagonal line graphic characters instead for a smoother graphic appearance.