124 lines
4.1 KiB
Python
124 lines
4.1 KiB
Python
#!/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()
|