#!/usr/bin/env python
'''Generate a perfect maze, that is a maze with
* all included points connected (no isolated passages) and
* no loops (only one path between any two points).
The size and branching factor of the maze can be adjusted.
Coding by d.factorial [at] gmail.com.
'''
import random
#the dimensions of the maze
xwide, yhigh = 40, 20
#the grid of the maze
#each cell of the maze is one of the following:
# '#' is wall
# '.' is empty space
# ',' is exposed but undetermined
# '?' is unexposed and undetermined
field = []
for y in range(yhigh):
row = []
for x in range(xwide):
row.append('?')
field.append(row)
#list of coordinates of exposed but undetermined cells.
frontier = []
def carve(y, x):
'''Make the cell at y,x a space.
Update the fronteer and field accordingly.
Note: this does not remove the current cell from frontier, it only adds new cells.
'''
extra = []
field[y][x] = '.'
if x > 0:
if field[y][x-1] == '?':
field[y][x-1] = ','
extra.append((y,x-1))
if x < xwide - 1:
if field[y][x+1] == '?':
field[y][x+1] = ','
extra.append((y,x+1))
if y > 0:
if field[y-1][x] == '?':
field[y-1][x] = ','
extra.append((y-1,x))
if y < yhigh - 1:
if field[y+1][x] == '?':
field[y+1][x] = ','
extra.append((y+1,x))
random.shuffle(extra)
frontier.extend(extra)
def harden(y, x):
'''Make the cell at y,x a wall.
'''
field[y][x] = '#'
def check(y, x, nodiagonals = True):
'''Test the cell at y,x: can this cell become a space?
True indicates it should become a space,
False indicates it should become a wall.
'''
edgestate = 0
if x > 0:
if field[y][x-1] == '.':
edgestate += 1
if x < xwide-1:
if field[y][x+1] == '.':
edgestate += 2
if y > 0:
if field[y-1][x] == '.':
edgestate += 4
if y < yhigh-1:
if field[y+1][x] == '.':
edgestate += 8
if nodiagonals:
#if this would make a diagonal connecition, forbid it
#the following steps make the test a bit more complicated and are not necessary,
#but without them the mazes don't look as good
if edgestate == 1:
if x < xwide-1:
if y > 0:
if field[y-1][x+1] == '.':
return False
if y < yhigh-1:
if field[y+1][x+1] == '.':
return False
return True
elif edgestate == 2:
if x > 0:
if y > 0:
if field[y-1][x-1] == '.':
return False
if y < yhigh-1:
if field[y+1][x-1] == '.':
return False
return True
elif edgestate == 4:
if y < yhigh-1:
if x > 0:
if field[y+1][x-1] == '.':
return False
if x < xwide-1:
if field[y+1][x+1] == '.':
return False
return True
elif edgestate == 8:
if y > 0:
if x > 0:
if field[y-1][x-1] == '.':
return False
if x < xwide-1:
if field[y-1][x+1] == '.':
return False
return True
return False
else:
#diagonal walls are permitted
if [1,2,4,8].count(edgestate):
return True
return False
#choose a original point at random and carve it out.
xchoice = random.randint(0, xwide-1)
ychoice = random.randint(0, yhigh-1)
carve(ychoice,xchoice)
#parameter branchrate:
#zero is unbiased, positive will make branches more frequent, negative will cause long passages
#this controls the position in the list chosen: positive makes the start of the list more likely,
#negative makes the end of the list more likely
#large negative values make the original point obvious
#try values between -10, 10
branchrate = 0
from math import e
while(len(frontier)):
#select a random edge
pos = random.random()
pos = pos**(e**-branchrate)
choice = frontier[int(pos*len(frontier))]
if check(*choice):
carve(*choice)
else:
harden(*choice)
frontier.remove(choice)
#set unexposed cells to be walls
for y in range(yhigh):
for x in range(xwide):
if field[y][x] == '?':
field[y][x] = '#'
#print the maze
for y in range(yhigh):
s = ''
for x in range(xwide):
s += field[y][x]
print s