Artificial truth

The more you see, the less you believe.

[archives] [latest] | [homepage] | [atom/rss]

Labyrinth
Thu 17 January 2013 — download

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
██████████████████████
█ █                  █
█ █ █████ ███ ███ █ ██
█ █ █ █ █ █ █        █
███ █ ███ ███ █████ ██
█ █ █ █ █ █ █ █      █
█ ███ █████ █ █████ ██
█ █ █ █ █            █
█ ███ █ ███ █████ █ ██
█ █ █ █              █
██████████████████████

Tadaaaa !