misc/maze.py

#!/usr/bin/env python
#
# maze.py
# Generating Maze using Python
# http://mornie.org/blog/2007/08/02/Generating-Maze-using-Python/
#
# Copyright (C) 2007  Daniele Tricoli aka Eriol <eriol@mornie.org>
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version 2
# of the License, or (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

import random

class Cell(object):
    '''A square cell'''

    def __init__(self, x, y):
        self.walls = [1, 1, 1, 1]
        self.x = x
        self.y = y

    def has_all_walls_intact(self):
        if 0 in self.walls:
            return False
        else:
            return True

    def find_adjacent_wall(self, cell):
        if cell.x == self.x:
            if cell.y < self.y:
                return 0 # left
            else:
                return 2 # right
        else:
            if cell.x < self.x:
                return 1 # above
            else:
                return 3 # below

    def destroy_wall(self, cell=None, wall=None):
        if cell is not None:
            wall_to_destroy = self.find_adjacent_wall(cell)
            self.walls[wall_to_destroy] = 0
            cell.walls[(wall_to_destroy + 2) % 4] = 0 # The opposite wall
        elif wall is not None:
            self.walls[wall] = 0

    def neighbors_coords(self):
        return ((self.x - 1, self.y),  # above
                (self.x + 1, self.y),  # below
                (self.x, self.y - 1),  # left
                (self.x, self.y + 1))  # right


class Maze(object):

    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.cells = [[None for x in range(self.width)]
                            for x in range(self.height)]
        self.total_cells = self.width * self.height

        for i in range(self.height):
            for j in range(self.width):
                self.cells[i][j] = Cell(i,j)

        self.current_cell = self.cells[0][0]
        self.visited_cells = 1

    def find_neighbors_with_walls(self, cell):
        coords = self.cells[cell.x][cell.y].neighbors_coords()
        all_neighbors = [self.cells[i][j] for i, j in coords
                                                 if self.isinside(i, j)]
        return [neighbors for neighbors in all_neighbors
                                         if neighbors.has_all_walls_intact()]

    def isinside(self, x, y):
        if (0 <= x < self.height) and (0 <= y < self.width):
            return True

    def create(self):
        cell_stack = []
        while self.visited_cells < self.total_cells:
            neighbors = self.find_neighbors_with_walls(self.current_cell)
            if neighbors:
                new_cell = random.choice(neighbors)
                self.current_cell.destroy_wall(cell=new_cell)
                cell_stack.append(self.current_cell)
                self.current_cell = new_cell
                self.visited_cells += 1
            else:
                self.current_cell = cell_stack.pop()

    def draw_ascii(self):
        canvas = []
        for x in range(self.height):
            line = []
            line2 = []
            for y in range(self.width):
                cell = self.cells[x][y]
                line.append(' -'[cell.walls[1]] * 2)
                line2.append(' |'[cell.walls[0]] + '  ')
            canvas.append('+' + '+'.join(line) + '+\n')
            canvas.append(''.join(line2) + '|\n')
        canvas.append('+--' * self.width + '+\n')
        return ''.join(canvas)

if __name__ == '__main__':
    x = Maze(10,6)
    x.create()
    print x.draw_ascii()