# Artificial truth

## The more you see, the less you believe.

Exams are over, I can do useless things again ! I always wondered how a perfect labyrinth could be generated in an elegant fashion, without recursion (unnecessary constraints always produces interesting stuffs). The answer is (surprisingly) straightforward : the growing tree algorithm.

# Growing tree

This amazingly complete site about maze says:

This is a general algorithm, capable of creating Mazes of different textures. It requires storage up to the size of the Maze. Each time you carve a cell, add that cell to a list. Proceed by picking a cell from the list, and carving into an unmade cell next to it. If there are no unmade cells next to the current cell, remove the current cell from the list. The Maze is done when the list becomes empty. The interesting part that allows many possible textures is how you pick a cell from the list.

# Implementation

``````#coding=utf-8
# Growing tree maze generation
# jvoisin - 2013 - WTFPL

from random import shuffle
import sys

if len(sys.argv) < 3:
print 'Usage: %s width height' % sys.argv[0]
sys.exit(0)

MAX_X, MAX_Y = int(sys.argv[1]), int(sys.argv[2])
MAX_X += MAX_X%2+1
MAX_Y += MAX_Y%2+1
DIRECTIONS = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def lab(maze):
maze[1][0] = ' ' # entrance is top left
maze[MAX_X-2][MAX_Y-1] = ' ' # exit is bottom right
cells = [(1, 1), ] # starts in (1, 1)
while cells:
x, y = cells.pop(-1) # I arbitrary choose the most recent cell, feel free to pick another one
shuffle(DIRECTIONS)
for i in DIRECTIONS: # pick a random direction
nx, ny = x + 2*i[0], y + 2*i[1] # pick the neighbor in the chosen direction
if 0 < nx < MAX_X-1 and 0 < ny < MAX_Y-1: # is this neighbor in the maze ?
if maze[nx][ny] != ' ': # is this neighbor already visited ?
cells.append((nx, ny)) # add it to the waitlist
maze[x + i[0]][y + i[1]] = maze[nx][ny] = ' ' # clear the way to it

def print_lab(maze):
for i in maze:
print ''.join([str(j) for j in i])

if __name__ == '__main__':
maze = [['█' for i in range(MAX_Y)] for j in range(MAX_X)]

lab(maze)
print_lab(maze)
``````

# Result

The result is nice (and best viewed with another font to squeeze vertical space between lines):

``````\$ python dev/maze3.py 10 20
██████████████████████
█ █ █                █
█ █ ███████ ███ ███ ██
█ █ █ █ █            █
███ █ █████ ███ █ █ ██
█ █ █ █ █ █ █ █ █    █
█ ███ ███ █ ███████ ██
█ █ █ █              █
█ █ █ █ █ █ ███ ███ ██
█ █ █ █ █ █ █        █
██████████████████████

\$ python dev/maze3.py 10 20
██████████████████████
█ █                  █
█ █ █████ ███ ███ █ ██
█ █ █ █ █ █ █        █
███ █ ███ ███ █████ ██
█ █ █ █ █ █ █ █      █
█ ███ █████ █ █████ ██
█ █ █ █ █            █
█ ███ █ ███ █████ █ ██
█ █ █ █              █
██████████████████████
``````