maze.py

import random, turtle

def maze(w=10, h=10):
    # This is the random spanning tree implementation
    seen = set()

    # Add some walls to confine the maze
    for i in xrange(-1, w+1):
        seen.add((i, -1))
        seen.add((i, h+1))
    for i in xrange(-1, h+1):
        seen.add((-1, i))
        seen.add((w+1, i))

    # Keep a stack for backtracking out path when we get stuck
    current = (0, 0)
    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)
        edges.add((current, new))

        current = new

    return edges

def draw_maze(edges):
    screen = turtle.Screen()
    t = turtle.Turtle()
    t.speed(0)
    # 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()

if __name__ == '__main__':
    edges = maze()
    draw_maze(edges)
    raw_input()