import svg
import random
\'\'\' Adds a colored box to SVG file class \'\'\'
def addBox(x, y, w, h, clr):
global svg_scene
svg_scene.add(svg.Rectangle([x,y],w,h,clr))
\'\'\' Maze box node - stores index, parent & path(=True if node belongs to a path) \'\'\'
class node:
def __init__(self, i, j, parent=None):
self.i = i
self.j = j
self.p = parent
self.isPath = False
\'\'\' Global settings - can modify \'\'\'
MAX_CORRIDOR_LENGTH = 20 # limits the length of fake corridors
BLOCK_SIZE = 20 # base block size in pixels
\'\'\' Global settings - dont modify! \'\'\'
svg_scene = None # svg class
maxTreeSize = MAX_CORRIDOR_LENGTH # limit
treeSize = 0 # counts the lengthon corridors
N = 0 # num of cells in row/col
table = [] # NxN maze table
finish = [] # finishing cell position
path = [] # array of nodes that belong to the maze path from start to finish
\'\'\' Picks item randomly from array & removes the value from array. \'\'\'
def pickdel(arr):
indx = random.randint(0,len(arr)-1)
data = arr[indx]
del arr[indx]
return data
\'\'\' Validates indexes to maze table size. Returns False if indexes are valid. \'\'\'
def badRange(i, j):
global N
if i < 0 or j < 0: return True
if i >= N or j >= N: return True
return False
\'\'\' Use DFS to find path from Start to Finish. Found path is placed in path array. \'\'\'
def depthwalk(pos, parent=None):
global table
global finish
global path
# set as visited
i, j = pos
table[i][j] = node(i, j, parent)
# reached end
if pos == finish:
path.append(table[i][j])
table[i][j].isPath = True
return True
# move in cross - dx, dy, flag_dir, flag_forward
# flag_dir => neighbour check flag (horiz == True)
# flag_forward => movement direction flag (forward == True)
next = [[i+1, j, True], [i-1, j, True], [i, j-1, False], [i, j+1, False]]
while len(next) > 0:
# visit randomly
dest = pickdel(next)
# new tile to check
ni, nj, flag = dest
# check range
if badRange(ni, nj): continue
if table[ni][nj]: continue # already visited
# check neighbours - cant touch their walls (no loops in maze!)
if flag:
# moving: up/down, neighbour check - horizontal
j_left = nj-1
j_right = nj+1
if j_left >= 0 and table[ni][j_left]: continue;
if j_right < N and table[ni][j_right]: continue;
# cant touch wall by moving in the desired direction
if ni-i < 0:
next_up = ni-1 # check one more tile up
if next_up >= 0 and table[next_up][nj]: continue;
else:
next_down = ni+1 # check one more tile down
if next_down < N and table[next_down][nj]: continue;
else:
# moving: left/right, neighbour check - vertical
i_up = ni-1
i_down = ni+1
if i_up >= 0 and table[i_up][nj]: continue;
if i_down < N and table[i_down][nj]: continue;
# cant touch wall by moving in the desired direction
if nj-j < 0:
next_left = nj-1 # check one more tile left
if next_left >= 0 and table[ni][next_left]: continue;
else:
next_right = nj+1 # check one more tile right
if next_right < N and table[ni][next_right]: continue;
if depthwalk([ni, nj], table[i][j]): #check deeper
path.append(table[i][j]) #path found
table[i][j].isPath = True
return True
return False
\'\'\' Use BFS to generate dead-end corridors in the maze \'\'\'
def growTree(i, j, pi = -1, pj = -1):
global table
global N
global treeSize
global maxTreeSize
if table[i][j]:
print \'ERROR: invalid tile passed!\'
return
# check if this tile can be made empty
next = [[i+1, j], [i-1, j], [i, j-1], [i, j+1]]
for tile in next:
if tile == [pi, pj]: continue # dont check parent
ni, nj = tile
if badRange(ni, nj): continue
# cant use as corridor - dont make loops to other paths or corridors
if table[ni][nj]: return
# tests passed - make node as a corridor
table[i][j] = node(i, j)
treeSize += 1
# generate further
while len(next) > 0 and treeSize < maxTreeSize:
# visit randomly
dest = pickdel(next)
ni, nj = dest
if dest == [pi, pj]: continue # dont check parent
if badRange(ni, nj): continue
if table[ni][nj]: continue # dont check paths & corridors
growTree(ni, nj, i, j)
\'\'\' Generate dead-end corridors starting from current path nodes \'\'\'
def makeWalls():
global path
global table
global N
global treeSize
global MAX_CORRIDOR_LENGTH
global maxTreeSize
maxTreeSize = MAX_CORRIDOR_LENGTH
for p in path:
x, y = p.i, p.j
treeSize = 0
# move in cross
next = [[x+1, y], [x-1, y], [x, y-1], [x, y+1]]
while len(next) > 0:
# visit directions randomly
ni, nj = pickdel(next)
if badRange(ni, nj): continue
if table[ni][nj]: continue # cant start from other path or corridor
# grow other paths from the path nodes
growTree(ni, nj, x, y)
#double check empty places
maxTreeSize = 99999999 # dont count
for i in range(0, N):
for j in range(0, N):
if not table[i][j]: growTree(i, j)
\'\'\' Generates a maze & builds a SVG file from the data \'\'\'
def buildMaze(scene, size, block):
global svg_scene
global finish
global BLOCK_SIZE
global N
global table
global path
BLOCK_SIZE = block
# setup scene(the svg file class)
svg_scene = scene
svg_scene.setDims(size, size) # pixels
addBox(0,0,size,size,[0,0,0]) # background
N = size / BLOCK_SIZE
# clear table
table = [[None for i in range(0, N)] for j in range(0, N)]
path = [] # clear old path
# create path from Start to Finish
finish = [N-1, N-1]
start = [0, 0]
depthwalk(start)
print "path length = %d" % len(path)
if len(path) == 0:
print "could not create maze, retry!"
# clear junk
for i in range(0, N):
for j in range(0, N):
if table[i][j] and table[i][j].isPath == False:
table[i][j] = None
# generate dead-end corridors
makeWalls()
pathColor = [255,128,0]
corridorColor = [255,255,255]
startColor = [0,0,255]
finishColor = [255,0,0]
# paint - show corridors
for i in range(0, N):
for j in range(0, N):
if table[i][j] and table[i][j].isPath == False:
addBox(i*BLOCK_SIZE, j*BLOCK_SIZE, BLOCK_SIZE, BLOCK_SIZE, corridorColor)
# paint - mark path
for p in path:
addBox(p.i*BLOCK_SIZE, p.j*BLOCK_SIZE, BLOCK_SIZE, BLOCK_SIZE, pathColor)
# show start/finish
addBox(start[0]*BLOCK_SIZE, start[1]*BLOCK_SIZE, BLOCK_SIZE, BLOCK_SIZE, startColor)
addBox(finish[0]*BLOCK_SIZE, finish[1]*BLOCK_SIZE, BLOCK_SIZE, BLOCK_SIZE, finishColor)