maze.py

import sys
import random
import turtle


W = H = 10

def outer_walls(w, h):
    # Add some walls to confine the maze
    # And yield them in order of a perimeter walk
    for i in xrange(-1, w+1):
        yield i, -1
    for i in xrange(-1, h+2):
        yield w+1, i
    for i in xrange(w+1, -2, -1):
        yield i, h+1
    for i in xrange(h, -2, -1):
        yield -1, i

def maze(w, h, walls):
    current = (0, 0)
    # This is the random spanning tree implementation
    seen = set([current])

    seen = seen.union(set(walls))

    # Keep a stack for backtracking out path when we get stuck
    stack = [current]
    directions = (0,1), (0, -1), (1, 0), (-1, 0)

    def get_free(pos):
        for dx, dy in directions:
            if (pos[0] + dx, pos[1] + dy) not in seen:
                yield pos[0] + dx, pos[1] + dy

    # Edges will hold the connection between nodes.
    edges = set()

    while stack:
        free = list(get_free(current))
        if not free:
            current = stack.pop()
            continue

        # Make a new connection to a square we haven't visited.
        new = random.choice(free)
        stack.append(new)
        seen.add(new)

        # smash a hole when we arrive facing a wall
        diff = new[0] - current[0], new[1] - current[1]
        extension = new[0] + diff[0], new[1] + diff[1]
        if extension in walls:
            yield new, extension

        yield current, new

        current = new

def draw_lines(t, edges):
    # Cheat a bit by using turtle to draw absolute coordinates.
    for (ax, ay), (bx, by) in edges:
        t.up()
        t.goto(ax * 10, ay * 10)
        t.down()
        t.goto(bx * 10, by * 10)
    t.up()

def draw_maze(edges, walls):
    screen = turtle.Screen()
    t = turtle.Turtle()
    t.fillcolor("black")
    t.pensize(6)
    t.speed(0)
    wall_pairs = [(wall, walls[(i+1) % len(walls)]) for i, wall in enumerate(walls)]
    t.fill(True)
    t.pencolor("black")
    draw_lines(t, wall_pairs)
    t.fill(False)
    t.pencolor("white")
    draw_lines(t, edges)

if __name__ == '__main__':
    # replayable maze outcomes
    seed = sys.argv[1] if sys.argv[1:2] else random.randint(0, 999)
    print "Replay with python maze.py", seed
    random.seed(int(seed))

    walls = list(outer_walls(w=W, h=H))
    edge_gen = maze(w=W, h=H, walls=walls)
    draw_maze(edge_gen, walls)
    raw_input()