Maze generator

maze_generator.py

import random
import time

WALL = " "
GAP = "@"

def split(string, width):
    for i in range(0, len(string), width):
        yield string[i : i+width]

def random_point(width, height):
    return (random.randrange(width),
            random.randrange(height))

def favored_random(i):
    i -= 1
    while i and random.randrange(2):
        i -= 1
    return i

DIRECTIONS = [
    ( 0,  1),
    ( 0, -1),
    ( 1,  0),
    (-1,  0)
]

def perp(d):
    x, y = d
    return (add(d, (y, x)),
            d,
            add(d, (-y, -x)))

MOORE = [
    ( 1,  1),
    ( 1,  0),
    ( 1, -1),
    ( 0, -1),
    (-1, -1),
    (-1,  0),
    (-1,  1),
    ( 0,  1),
]

def add(pos1, pos2):
    x1, y1 = pos1
    x2, y2 = pos2
    return (x1 + x2, y1 + y2)

class Grid:
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.data = [WALL for _ in range(width * height)]
    def valid_index(self, x, y):
        return (x in range(self.width)
            and y in range(self.height))
    def translate_index(self, pos):
        x, y = pos
        if self.valid_index(x, y):
            return y * self.width + x
        else:
            raise IndexError(x, y)
    def __getitem__(self, pos):
        return self.data[self.translate_index(pos)]
    def __setitem__(self, pos, new):
        self.data[self.translate_index(pos)] = new
    def blank_neighbors(self, point, d):
        original_direction = tuple(-c for c in d)
        count = 0
        for d in MOORE:
            if d in perp(original_direction):
                continue
            try:
                neighbor = self[add(point, d)]
            except IndexError:
                pass
            else:
                count += (neighbor == GAP)
        return count
    def __str__(self):
        return "\n".join(
            "".join(s) for s in split(self.data, self.width))
    def __repr__(self):
        return str(self)
    def __len__(self):
        return len(self.data)

# Generates a maze.
#
# Guarantees that there is only one way to get from one point
# to another.
def generate_maze(width, height):
    points = [random_point(width, height)]
    grid = Grid(width, height)
    grid[points[0]] = GAP
    while points:
        # Pick an point randomly to expand upon, but favor points that
        # were more recently created.
        index = favored_random(len(points))
        point = points[index]
        valid_directions = 0
        for d in random.sample(DIRECTIONS, 4):
            neighbor = add(d, point)
            
            if neighbor in points:
                continue
            
            if not grid.valid_index(*neighbor):
                continue
                
            bn = grid.blank_neighbors(neighbor, d)
            if bn != 0:
                continue
            
            valid_directions += 1
            
            grid[neighbor] = GAP
            points.append(neighbor)
        if valid_directions == 0:
            del points[index]
    return grid

print(generate_maze(200, 100))