maze-maker-1.py
'''\
Python Maze Maker.
Experimenting with computer maze generation.
Maze model splits doors into North/South and West/East arrays.
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
0| # # # # # # # |
+-@-+-@-+-@-+-@-+-@-+-@-+-@-+-@-+ @ n/s door
1| # # # X # # # # |
+-@-+-@-+-@-+-@-+-@-+-@-+-@-+-@-+
2| # # # # # # # | # e/w door
+-@-+-@-+-@-+-@-+-@-+-@-+-@-+-@-+
3| # # # # # # # |
+---+---+---+---+---+---+---+---+
Cells = [4,8] X = [1,3]
NS Doors = [3,8] N/S = [0,3] / [1,3]
WE Doors = [4,7] W/E = [1,2] / [1,3]
Coder@Sonnack.com
November 2013
'''
from sys import argv, stdout, stderr, path as syspath
from datetime import datetime, date, timedelta
from random import random, shuffle
import Image, ImageDraw
from logger import logger, info, debug, trace
from colors import *
Log = logger('MazeMaker1')
NumberCols = 40
NumberRows = 30
RandomWall = lambda f: random() < f
DirectionString = ['North', 'East', 'South', 'West']
DirectionAbbrev = ['N', 'E', 'S', 'W']
ShowImageBeforeSave = False
class RandomWalk1 (object):
max_steps = 100
wall_change = 0.1
occu_change = 0.1
dir_change = 1
def __init__ (self, mz):
self.mz = mz
self.row = 0
self.col = 0
self.direction = 2
self.tot_steps = 0
self.dir_steps = 0
self.path_list = []
def carve_a_path (self, path_color):
Log.debug()
Log.debug('NEW PATH...')
if 0 < len(self.path_list):
if not self.find_a_path():
return
Log.debug('using: (%d, %d)' % (self.row, self.col))
self.tot_steps = 0
self.dir_steps = 0
current_path = []
while self.tot_steps < self.max_steps:
s = DirectionAbbrev[self.direction]
t = (self.tot_steps, self.dir_steps, s, self.row, self.col)
Log.debug('STEP: %d (%d:%s) [%d, %d]' % t)
current_path.append([self.row, self.col, 2])
tc = self.test_cell[self.direction](self)
if tc < 0:
Log.trace('Hit the wall!')
if self.wall_change < random():
if self.change_direction():
continue
break
if 0 < tc:
Log.trace('Hit another path!')
if self.occu_change < random():
if self.change_direction():
continue
break
mc = self.move_to_next_cell[self.direction](self)
self.mz.set_cell(self.row,self.col, path_color)
self.tot_steps = self.tot_steps + 1
self.dir_steps = self.dir_steps + 1
if self.dir_change < (random() * self.dir_steps):
if self.change_direction():
self.dir_steps = 0
self.path_list.append(current_path)
def find_a_path (self):
'''Travel existing paths to find a new row,col and direction.'''
maze_path_seq = [x for x in range(len(self.path_list))]
shuffle(maze_path_seq)
for mx,maze_path in map(lambda ix: (ix, self.path_list[ix]), maze_path_seq):
Log.trace('MazePath: %d (%d cells)' % (mx, len(maze_path)))
maze_cell_seq = [x for x in range(len(maze_path))]
shuffle(maze_cell_seq)
for cx,path_cell in map(lambda ix: (ix,maze_path[ix]), maze_cell_seq):
Log.trace('PathCell: %d [%d,%d (%d)]' % (cx, path_cell[0], path_cell[1], path_cell[2]))
if path_cell[2] < 4:
self.row = path_cell[0]
self.col = path_cell[1]
Log.trace('testing: (%d, %d)' % (self.row, self.col))
if self.test_north_cell() == 0:
self.direction = 0
path_cell[2] = path_cell[2] + 1
return True
if self.test_east_cell() == 0:
self.direction = 1
path_cell[2] = path_cell[2] + 1
return True
if self.test_south_cell() == 0:
self.direction = 2
path_cell[2] = path_cell[2] + 1
return True
if self.test_west_cell() == 0:
self.direction = 3
path_cell[2] = path_cell[2] + 1
return True
Log.debug('Unable to find a path!')
return False
def change_direction (self):
if random() < 0.5:
d = (self.direction - 1) % 4
if self.test_cell[d](self):
d = (self.direction + 1) % 4
if self.test_cell[d](self):
return False
Log.debug('NEW DIRECTION: %d' % d)
self.direction = d
else:
d = (self.direction + 1) % 4
if self.test_cell[d](self):
d = (self.direction - 1) % 4
if self.test_cell[d](self):
return False
Log.debug('NEW DIRECTION: %d' % d)
self.direction = d
return True
def test_north_cell (self):
if self.row == 0:
return -1
return self.mz.get_cell(self.row-1, self.col)
def test_south_cell (self):
if self.row == (NumberRows - 1):
return -1
return self.mz.get_cell(self.row+1, self.col)
def test_west_cell (self):
if self.col == 0:
return -1
return self.mz.get_cell(self.row, self.col-1)
def test_east_cell (self):
if self.col == (NumberCols - 1):
return -1
return self.mz.get_cell(self.row, self.col+1)
def move_to_north_cell (self):
self.mz.set_north_door(self.row, self.col, 0)
self.row = self.row - 1
def move_to_south_cell (self):
self.mz.set_south_door(self.row, self.col, 0)
self.row = self.row + 1
def move_to_west_cell (self):
self.mz.set_west_door(self.row, self.col, 0)
self.col = self.col - 1
def move_to_east_cell (self):
self.mz.set_east_door(self.row, self.col, 0)
self.col = self.col + 1
test_cell = [test_north_cell, test_east_cell, test_south_cell, test_west_cell]
move_to_next_cell = [move_to_north_cell, move_to_east_cell, move_to_south_cell, move_to_west_cell]
class Maze (object):
'''\
Maze class.
The maze is stored as three two-dimensional arrays:
cells - stores the state of the maze cell
ns_doors - stores the state of the north and south doors
we_doors - stores the state of the west and east doors
All data values are integers. Array[row][col]: each row is an array of cols.
A cell non-zero cell value indicates some non-default status.
A non-zero value for a door means the door is closed (locked).
The value -1 indicates a maze outer wall, values above 0 indicate a locked state.
(The potential exists for multiple locked states; e.g. closed, closed+locked.)
The NS_Doors array has one less row -- no south-edge doors.
The WE_Doors array has one less column -- no east-edge doors.
There are no west-edge or north-edge doors, either, but the Doors arrays can
be thought of as EastDoors and SouthDoors arrays; except for the eastern and
southern edges, all cells have an east and south door. The west and north
doors are the east and south doors of the west and north cells, respectively.
For a given cell(row,col), the doors to that cell are:
north door = NS_Doors(row-1, col ) {{south door of north cell}}
south door = NS_Doors(row , col )
west door = WE_Doors(row , col-1) {{east door of west cell}}
east door = WE_Doors(row , col )
'''
def __init__ (self, rows, cols):
self.dims = (rows, cols)
self.cells = [ [int(0) for col in range(self.dims[1]) ] for row in range(self.dims[0]) ]
self.ns_doors = [ [int(1) for col in range(self.dims[1]) ] for row in range(self.dims[0]-1) ]
self.we_doors = [ [int(1) for col in range(self.dims[1]-1) ] for row in range(self.dims[0]) ]
def write_image(self, fn):
im = MazeImg(self.dims)
for rx,row in enumerate(self.cells):
for cx,col in enumerate(row):
im.set_current_cell(rx, cx)
if 1 < col:
im.paint_cell(ColorPalette[col])
if (rx == 0) and self.get_north_door(rx,cx):
im.draw_north_wall()
if self.get_south_door(rx,cx):
im.draw_south_wall()
if (cx == 0) and self.get_west_door(rx,cx):
im.draw_west_wall()
if self.get_east_door(rx,cx):
im.draw_east_wall()
im.save(fn)
if ShowImageBeforeSave: im.show()
return im
def all_cells_occupied (self):
for maze_row in self.cells:
for maze_cell in maze_row:
if maze_cell == 0:
return False
return True
def get_cell (self, row, col):
'''Get state of cell(row,col).'''
self._test_row_col(row, col)
return self.cells[row][col]
def set_cell (self, row, col, state):
'''Set state of cell(row,col).'''
self._test_row_col(row, col)
self.cells[row][col] = state
def set_north_door (self, row, col, state):
'''Set state of north door of cell(row,col).'''
self._test_row_col(row, col)
if row == 0:
raise Exception, "Can't set north wall door!"
self._test_ns_door_row_col(row-1,col)
self.ns_doors[row-1][col] = state
def get_north_door (self, row, col):
'''Get state of north door of cell(row,col).'''
if row == 0:
return -1
self._test_ns_door_row_col(row-1,col)
return self.ns_doors[row-1][col]
def set_south_door (self, row, col, state):
'''Set state of south door of cell(row,col).'''
self._test_row_col(row, col)
if (self.dims[0]-1) <= row:
raise Exception, "Can't set south wall door!"
self._test_ns_door_row_col(row,col)
self.ns_doors[row][col] = state
def get_south_door (self, row, col):
'''Get state of south door of cell(row,col).'''
if (self.dims[0]-1) == row:
return -1
self._test_ns_door_row_col(row,col)
return self.ns_doors[row][col]
def set_west_door (self, row, col, state):
'''Set state of west door of cell(row,col).'''
self._test_row_col(row, col)
if col <= 0:
raise Exception, "Can't set west wall door!"
self._test_we_door_row_col(row,col-1)
self.we_doors[row][col-1] = state
def get_west_door (self, row, col):
'''Get state of west door of cell(row,col).'''
if col == 0:
return -1
self._test_we_door_row_col(row,col-1)
return self.we_doors[row][col-1]
def set_east_door (self, row, col, state):
'''Set state of east door of cell(row,col).'''
self._test_row_col(row, col)
if (self.dims[1]-1) <= col:
raise Exception, "Can't set east wall door!"
self._test_we_door_row_col(row,col)
self.we_doors[row][col] = state
def get_east_door (self, row, col):
'''Get state of east door of cell(row,col).'''
if (self.dims[1]-1) == col:
return -1
self._test_we_door_row_col(row,col)
return self.we_doors[row][col]
def _test_row_col (self, row, col):
'''Test (row,col) for access to cell state data.'''
if (row < 0) or (self.dims[0] <= row):
raise Exception, ("Row (%d) is out of bounds!" % row)
if (col < 0) or (self.dims[1] <= col):
raise Exception, ("Col (%d) is out of bounds!" % col)
def _test_ns_door_row_col (self, row, col):
'''Test (row,col) for access to north/south door data.'''
if (row < 0) or ((self.dims[0]-1) <= row):
raise Exception, ("Row (%d) is out of bounds!" % row)
if (col < 0) or (self.dims[1] <= col):
raise Exception, ("Col (%d) is out of bounds!" % col)
def _test_we_door_row_col (self, row, col):
'''Test (row,col) for access to east/west door data.'''
if (row < 0) or (self.dims[0] <= row):
raise Exception, ("Row (%d) is out of bounds!" % row)
if (col < 0) or ((self.dims[1]-1) <= col):
raise Exception, ("Col (%d) is out of bounds!" % col)
class MazeImg (object):
'''Image class.'''
HorzSpace = 20
VertSpace = 20
WallColor = ColorBlack
def __init__ (self, _dims):
'''Create new Maze Image instance. NOTE: x=cols, y=rows!'''
self.dims = _dims
self.pixels = (self.HorzSpace * (self.dims[1]+2), self.VertSpace * (self.dims[0]+2))
self.pmin = (self.HorzSpace, self.VertSpace)
self.pmax = (self.pixels[0] - self.HorzSpace, self.pixels[1] - self.VertSpace)
self.p0 = (self.pmin[0] , self.pmin[1])
self.p1 = (self.pmin[0]+self.HorzSpace, self.pmin[1]+self.VertSpace)
self.im = Image.new('RGB', self.pixels, ColorWhite)
self.draw = ImageDraw.Draw(self.im)
self.draw.rectangle((0,0)+(self.pixels[0]-1,self.pixels[1]-1), outline=ColorBlack)
self.draw.rectangle((1,1)+(self.pixels[0]-2,self.pixels[1]-2), outline=ColorGray100)
self.draw.rectangle((2,2)+(self.pixels[0]-3,self.pixels[1]-3), outline=ColorGray200)
for ix in range(1, self.dims[1]):
pp = ix * self.HorzSpace
self.draw.line([(self.pmin[0]+pp, self.pmin[1]), (self.pmin[0]+pp, self.pmax[1])], fill=ColorLightBlue)
for ix in range(1, self.dims[0]):
pp = ix * self.VertSpace
self.draw.line([(self.pmin[0], self.pmin[1]+pp), (self.pmax[0], self.pmin[1]+pp)], fill=ColorLightBlue)
self.draw.line([(self.pmin[0], self.pmin[1]), (self.pmax[0], self.pmin[1])], fill=ColorDarkGreen, width=2)
self.draw.line([(self.pmin[0], self.pmax[1]), (self.pmax[0], self.pmax[1])], fill=ColorDarkGreen, width=2)
self.draw.line([(self.pmin[0], self.pmin[1]), (self.pmin[0], self.pmax[1])], fill=ColorDarkGreen, width=2)
self.draw.line([(self.pmax[0], self.pmin[1]), (self.pmax[0], self.pmax[1])], fill=ColorDarkGreen, width=2)
def set_current_cell (self, row, col):
'''Set current cell for drawing operations.'''
if (row < 0) or (self.dims[0] <= row):
raise Exception, "Row is out of bounds!"
if (col < 0) or (self.dims[1] <= col):
raise Exception, "Col is out of bounds!"
cx = self.pmin[0] + (col * self.HorzSpace)
cy = self.pmin[1] + (row * self.VertSpace)
self.p0 = (cx,cy)
self.p1 = (cx+self.HorzSpace, cy+self.VertSpace)
def paint_cell (self, color):
self.draw.rectangle([self.p0, self.p1], fill=color, outline=ColorBlack)
def draw_north_wall (self):
'''Draw north wall in current cell.'''
self.draw.line([(self.p0[0], self.p0[1]), (self.p1[0], self.p0[1])], fill=self.WallColor, width=3)
def draw_south_wall (self):
'''Draw south wall in current cell.'''
self.draw.line([(self.p0[0], self.p1[1]), (self.p1[0], self.p1[1])], fill=self.WallColor, width=3)
def draw_west_wall (self):
'''Draw west wall in current cell.'''
self.draw.line([(self.p0[0], self.p0[1]), (self.p0[0], self.p1[1])], fill=self.WallColor, width=3)
def draw_east_wall (self):
'''Draw east wall in current cell.'''
self.draw.line([(self.p1[0], self.p0[1]), (self.p1[0], self.p1[1])], fill=self.WallColor, width=3)
def show (self):
self.im.show()
return self
def save (self, fn, mode='GIF'):
self.im.save(fn, mode)
return self
def __str__ (self):
s = '%s (%d,%d) %s'
t = (self.im.format, self.im.size[0], self.im.size[1], self.im.mode)
return s % t
def __repr__ (self):
s = '{Img:{format:"%s", size:%s, mode:"%s", addr:%x}}'
t = (self.im.format, str(self.im.size), self.im.mode, self.__hash__())
return s % t
def simple_manual_demo (mz):
mz.set_east_door (0,0, 0)
mz.set_east_door (0,1, 0)
mz.set_east_door (0,2, 0)
mz.set_south_door(0,3, 0)
mz.set_west_door (1,3, 0)
mz.set_south_door(1,2, 0)
mz.set_south_door(2,2, 0)
mz.set_south_door(3,2, 0)
mz.set_west_door (4,2, 0)
mz.set_south_door(4,1, 0)
mz.set_south_door(5,1, 0)
mz.set_south_door(6,1, 0)
mz.set_east_door (7,1, 0)
mz.set_north_door(7,2, 0)
mz.set_north_door(6,2, 0)
mz.set_north_door(4,1, 0)
mz.set_north_door(3,1, 0)
mz.set_north_door(2,1, 0)
mz.set_west_door (1,1, 0)
mz.set_south_door(1,0, 0)
mz.set_south_door(2,0, 0)
mz.set_south_door(3,0, 0)
mz.set_south_door(4,0, 0)
mz.set_south_door(5,0, 0)
mz.set_south_door(6,0, 0)
def Main ():
fns = []
for tx in range(50):
Log.info(tx)
mz = Maze(NumberRows, NumberCols)
mz.set_cell(0,0, ixColorGreen)
mz.set_cell(NumberRows-1, NumberCols-1, ixColorLightMagenta)
mz.set_north_door (NumberRows-1, NumberCols-1, 0)
maze_maker = RandomWalk1(mz)
Log.info()
for ix in range(2000):
maze_maker.carve_a_path(1)
if mz.all_cells_occupied():
Log.info('Finished after %d iterations.' % ix)
break
Log.info('Path List:')
for ix,p in enumerate(maze_maker.path_list):
Log.info(p)
Log..info()
Log.info()
fn = 'out\\maze-%02d.gif' % tx
fns.append(fn)
mz.write_image(fn)
return fns
if __name__ == '__main__':
print 'autorun:',argv[0]
Log.start('maze-maker-1.log')
Log.level(trace())
try:
obj = Main()
Log.info()
Log.info('done:',type(obj))
except Exception as e:
print >> stderr, e
Log.error(e)
finally:
Log.end()
'''eof'''