Welcome, guest | Sign In | My Account | Store | Cart
"""
Amaze - A completely object-oriented Pythonic maze generator/solver.
This can generate random mazes and solve them. It should be
able to solve any kind of maze and inform you in case a maze is
unsolveable.

This uses a very simple representation of a mze. A maze is
represented as an mxn matrix with each point value being either
0 or 1. Points with value 0 represent paths and those with
value 1 represent blocks. The problem is to find a path from
point A to point B in the matrix.

The matrix is represented internally as a list of lists.

Have fun :-)

"""

import sys
import random
import optparse

pass

""" Read a maze from different input sources """

STDIN = 0
FILE = 1
SOCKET = 2

def __init__(self):
self.maze_rows = []
pass

""" Read a maze from standard input """

print 'Enter a maze'
print 'You can enter a maze row by row'
print

data = raw_input('Enter the dimension of the maze as Width X Height: ')
w, h = data.split()
w, h  = int(w), int(h)

for x in range(h):
row = ''
while not row:
row = raw_input('Enter row number %d: ' % (x+1))
row = row.split()
if len(row) != w:
raise MazeReaderException,'invalid size of maze row'
self.maze_rows.append(row)

""" Read a maze from an input file """

fname = raw_input('Enter maze filename: ')
try:
f = open(fname)
f.close()
# See if this is a valid maze
lines = [ line for line in lines if line.strip() ]
w = len(lines.split())
for line in lines:
row = line.split()
if len(row) != w:
raise MazeReaderException, 'Invalid maze file - error in maze dimensions'
else:
self.maze_rows.append(row)
except (IOError, OSError), e:

def getData(self):
return self.maze_rows

""" Read a maze from the input source """

return self.getData()

class MazeFactory(object):
""" Factory class for Maze object """

""" Create a maze and return it. The source is
read from the 'source' argument """

def makeRandomMaze(self, dimension):
""" Generate a random maze of size dimension x dimension """

rows = []
for x in range(dimension):
row = []
for y in range(dimension):
row.append(random.randrange(2))
random.shuffle(row)
rows.append(row)

return Maze(rows)

class MazeError(Exception):
""" An exception class for Maze """

pass

class Maze(object):
""" A class representing a maze """

def __init__(self, rows=[[]]):
self._rows = rows
self.__validate()
self.__normalize()

def __str__(self):

s = '\n'
for row in self._rows:
for item in row:
s = ''.join((s,' ',str(item),' '))
s = ''.join((s,'\n\n'))

return s

def __validate(self):
""" Validate the maze """

# Get length of first row
width = len(self._rows)
widths = [len(row) for row in self._rows]
if widths.count(width) != len(widths):
raise MazeError, 'Invalid maze!'

self._height = len(self._rows)
self._width = width

def __normalize(self):
""" Normalize the maze """

# This converts any number > 0 in the maze to 1
for x in range(len(self._rows)):
row = self._rows[x]
row = map(lambda x: min(int(x), 1), row)
self._rows[x] = row

def getHeight(self):
""" Return the height of the maze """

return self._height

def getWidth(self):
""" Return the width of the maze """

return self._width

def validatePoint(self, pt):
""" Validate the point pt """

x,y = pt
w = self._width
h = self._height

# Don't support Pythonic negative indices
if x > w - 1 or x<0:
raise MazeError, 'x co-ordinate out of range!'

if y > h - 1 or y<0:
raise MazeError, 'y co-ordinate out of range!'

pass

def getItem(self, x, y):
""" Return the item at location (x,y) """

self.validatePoint((x,y))

w = self._width
h = self._height

# This is based on origin at bottom-left corner
# y-axis is reversed w.r.t row arrangement
# Get row
row = self._rows[h-y-1]
return row[x]

def setItem(self, x, y, value):
""" Set the value at point (x,y) to 'value' """

h = self._height

self.validatePoint((x,y))
row = self._rows[h-y-1]
row[x] = value

def getNeighBours(self, pt):
""" Return a list of (x,y) locations of the neighbours
of point pt """

self.validatePoint(pt)

x,y = pt

h = self._height
w = self._width

# There are eight neighbours for any point
# inside the maze. However, this becomes 3 at
# the corners and 5 at the edges
poss_nbors = (x-1,y),(x-1,y+1),(x,y+1),(x+1,y+1),(x+1,y),(x+1,y-1),(x,y-1),(x-1,y-1)

nbors = []
for xx,yy in poss_nbors:
if (xx>=0 and xx<=w-1) and (yy>=0 and yy<=h-1):
nbors.append((xx,yy))

return nbors

def getExitPoints(self, pt):
""" Return a list of exit points at point pt """

# Get neighbour list and return if the point value
# is 0

exits = []
for xx,yy in self.getNeighBours(pt):
if self.getItem(xx,yy)==0:
exits.append((xx,yy))

return exits

def getRandomExitPoint(self, pt):
""" Return a random exit point at point (x,y) """

return random.choice(self.getExitPoints(pt))

def getRandomStartPoint(self):
""" Return a random point as starting point """

return random.choice(self.getAllZeroPoints())

def getRandomEndPoint(self):
""" Return a random point as ending point """

return random.choice(self.getAllZeroPoints())

def getAllZeroPoints(self):
""" Return a list of all points with
zero value """

points = []
for x in range(self._width):
for y in range(self._height):
if self.getItem(x,y)==0:
points.append((x,y))

return points

def calcDistance(self, pt1, pt2):
""" Calculate the distance between two points """

# The points should be given as (x,y) tuples
self.validatePoint(pt1)
self.validatePoint(pt2)

x1,y1 = pt1
x2,y2 = pt2

return pow( (pow((x1-x2), 2) + pow((y1-y2),2)), 0.5)

def calcXDistance(self, pt1, pt2):
""" Calculate the X distance between two points """

# The points should be given as (x,y) tuples
self.validatePoint(pt1)
self.validatePoint(pt2)

x1, y1 = pt1
x2, y2 = pt2

return abs(x1-x2)

def calcYDistance(self, pt1, pt2):
""" Calculate the Y distance between two points """

# The points should be given as (x,y) tuples
self.validatePoint(pt1)
self.validatePoint(pt2)

x1, y1 = pt1
x2, y2 = pt2

return abs(y1-y2)

def calcXYDistance(self, pt1, pt2):
""" Calculate the X-Y distance between two points """

# The points should be given as (x,y) tuples
self.validatePoint(pt1)
self.validatePoint(pt2)

x1, y1 = pt1
x2, y2 = pt2

return abs(y1-y2) + abs(x1-x2)

def getData(self):
""" Return the maze data """

return self._rows

class MazeSolver(object):
""" Maze solver class """

def __init__(self, maze):
self.maze = maze
self._start = (0,0)
self._end = (0,0)
# Current point
self._current = (0,0)
# Solve path
self._path = []
# Number of cyclic loops
self._loops = 0
# Solvable flag
self.unsolvable = False
# xdiff
self._xdiff = 0.0
# ydiff
self._ydiff = 0.0
# List keeping cycles (generations)
self.cycles = []
# Number of retraces
self._numretrace = 0
# Map for exit points
self._pointmap = {}
# Number of all zero points
self._numzeropts = 0
# Map for retraced points
self._retracemap = {}
# Cache for keys of above
self._retracekeycache = []
# Number of times retracemap is not updated
# with a new point
self._lastupdate = 0

def setStartPoint(self, pt):

self.maze.validatePoint(pt)
self._start = pt

def setEndPoint(self, pt):

self.maze.validatePoint(pt)
self._end = pt

def boundaryCheck(self):
""" Check boundaries of start and end points """

exits1 = self.getExitPoints(self._start)
exits2 = self.getExitPoints(self._end)

if len(exits1)==0 or len(exits2)==0:
return False

return True

def setCurrentPoint(self, point):
""" Set the current point """

# print 'Current point is',point
self._current = point
self._xdiff = abs(self._current - self._end)
self._ydiff = abs(self._current - self._end)

self._path.append(point)

def isSolved(self):
""" Whether the maze is solved """

return (self._current == self._end)

pt1 = self.getClosestPoint(self.getExitPoints(point1))
pt2 = self.getClosestPoint(self.getExitPoints(point2))

if pt1==point2 and pt2==point1:
return True

return False

def getExitPoints(self, point):
""" Get exit points for 'point' """

points = self._pointmap.get(point)

if points==None:
# We are using shortest-distance algorithm
points = self.maze.getExitPoints(point)
self._pointmap[point] = points

return points

def getNextPoint(self):
""" Get the next point from the current point """

points = self.getExitPoints(self._current)
point = self.getBestPoint(points)

while self.checkClosedLoop(point):

if self.endlessLoop():
point = None
break

# Save point
point2 = point

point = self.getNextClosestPointNotInPath(points, point2)
if not point:
# Try retracing path
point = self.retracePath()

return point

def retracePath(self):

# Retrace point by point in path, till
# you get to a point which provides an
# alternative.

print 'Retracing...'
path = self._path[:]
path.reverse()

self._numretrace += 1

try:
idx = path[1:].index(self._current)
except:
idx = path.index(self._current)

pathstack = []

for x in range(idx+1, len(path)):
p = path[x]
if p in pathstack: continue

pathstack.append(p)
if p != self._path[-1]:
# print 'Current point is',p
self._path.append(p)

if p != self._start:
points = self.getExitPoints(p)
point = self.getNextClosestPointNotInPath(points, self.getClosestPoint(points))
self._retracemap[p] = self._retracemap.get(p, 0) + 1
else:
path = self.sortPointsByXYDistance(self._path[:-1])
self.cycles.append((path, self._path[:-1]))
# Reset solver state
self._path = []
self._loops = 0
self._retracemap[p] = self._retracemap.get(p, 0) + 1

return p

def endlessLoop(self):

if self._retracemap:
# If the retrace map has not been updated for a while
# increment lastupdate count
if self._retracemap.keys() == self._retracekeycache:
self._lastupdate += 1
self._retracekeycache = self._retracemap.keys()

# If lastupdate count reaches the total number of points
# it could mean we exhausted all possible paths.
if self._lastupdate > self.maze.getWidth()*self.maze.getHeight():
print 'Exited because of retracekeycache overflow'
return True

# If retrace has gone through all zero points and not
# yet found a solution, then we are hitting a dead-lock.
elif len(self._retracemap.keys())> self._numzeropts - 1:
print 'Exited because number of points exceeded zero points'
return True
else:
# If the retrace path contains only one point
if len(self._retracemap.keys())==1:
val = self._retracemap.get(self._retracemap.keys())
# If we hit the same point more than the number of
# zero points in the maze, it signals a dead-lock.
if val>self._numzeropts:
print 'Exited because we are oscillating'
return True

return False

def checkClosedLoop(self, point):
""" See if this point is causing a closed loop """

l = range(0, len(self._path)-1, 2)
l.reverse()

for x in l:
if self._path[x] == point:
self._loops += 1
# loop = tuple(self._path[x:])
# print 'Point=>',point, len(self._path)
return True

return False

def getBestPoint(self, points):

if len(self.cycles)==0:
# First try min point
point = self.getClosestPoint(points)
# Save point
point2 = point
# Point for trying alternate
altpoint = point

point = self.getNextClosestPointNotInPath(points, point2)
if not point:
point = point2
else:
allcycles=[]
map(allcycles.extend, [item for item in self.cycles])
if self._current==self._start or self._current in allcycles:
# print 'FOUND IT =>',self._current
history = []
for path in [item for item in self.cycles]:
path.reverse()
try:
idx = path.index(self._current)
next = path[idx-1]
history.append(next)
except:
pass
point = self.getDifferentPoint(points, history)
if not point:
point = self.getAlternatePoint(points, history[-1])
else:
# Not there
point2 = self.getClosestPoint(points)
point = self.getNextClosestPointNotInPath(points, point2)
if not point:
point = point2

altpoint = point

return point

def sortPointsByXYDistance(self, points):
""" Sort list of points by X+Y distance """

distances = [(self.maze.calcXYDistance(point, self._end), point) for point in points]
distances.sort()

points2 = [item for item in distances]

return points2

def sortPointsByDistances(self, points):
""" Sort points according to distance from end point """

if self._xdiff>self._ydiff:
distances = [(self.maze.calcXDistance(point, self._end), point) for point in points]
elif self._xdiff<self._ydiff:
distances = [(self.maze.calcYDistance(point, self._end), point) for point in points]
else:
distances = [(self.maze.calcXYDistance(point, self._end), point) for point in points]

distances.sort()
points2 = [item for item in distances]

return points2

def sortPoints(self, points):

return self.sortPointsByDistances(points)

def getClosestPoint(self, points):
""" Return the closest point from current
to the end point from a list of exit points """

points2 = self.sortPoints(points)

# Min distance point
closest = points2
return closest

def getDifferentPoint(self, points1, points2):
""" Return a random point in points1 which is not
in points2 """

l = [pt for pt in points1 if pt not in points2]
if l:
return random.choice(l)

return None

def getAlternatePoint(self, points, point):
""" Get alternate point """

print 'Trying alternate...',self._current, point
points2 = points[:]

if point in points2:
points2.remove(point)
if points2:
return random.choice(points2)
else:
return point

return None

def getNextClosestPoint(self, points, point):
""" After point 'point' get the next closest point
to the end point from list of points """

points2 = self.sortPoints(points)
idx = points2.index(point)

try:
return points2[idx+1]
except:
return None

def getNextClosestPointNotInPath(self, points, point):

point2 = point
while point2 in self._path:
point2 = self.getNextClosestPoint(points, point2)

return point2

def solve(self):
""" Solve the maze """

print 'Starting point is', self._start
print 'Ending point is', self._end

# First check if both start and end are same
if self._start == self._end:
print 'Start/end points are the same. Trivial maze.'
print [self._start, self._end]
return None

# Check boundary conditions
if not self.boundaryCheck():
print 'Either start/end point are unreachable. Maze cannot be solved.'
return None

# Proper maze
print 'Maze is a proper maze.'

# Initialize solver
self.setCurrentPoint(self._start)
self._numzeropts = len(self.maze.getAllZeroPoints())

self.unsolvable = False

print 'Solving...'
while not self.isSolved():
pt = self.getNextPoint()

if pt:
self.setCurrentPoint(pt)
else:
self.unsolvable = True
break

if not self.unsolvable:
print 'Final solution path is',self._path
print 'Length of path is',len(self._path)
else:
print 'Length of path is',len(self._path)

# if self.cycles:
#    print 'Path with all cycles is',
#    l = []
#    map(l.extend, [item for item in self.cycles])
#    l.extend(self._path)
#    print l

self.printResult()

def printResult(self):
""" Print the maze showing the path """

for x,y in self._path:
self.maze.setItem(x,y,'*')

self.maze.setItem(self._start, self._start, 'S')
self.maze.setItem(self._end, self._end, 'E')

if self.unsolvable:
print 'Maze with final path'
else:
print 'Maze with solution path'

print self.maze

class MazeGame(object):

def __init__(self, w=0, h=0):
self._start = (0,0)
self._end = (0,0)

def createMaze(self):
return None

def getStartEndPoints(self, maze):
return None

def runGame(self):

maze = self.createMaze()
if not maze:
return None

print maze
self.getStartEndPoints(maze)

# Dump it to maze.txt
open('maze.txt','w').write(str(maze))

solver = MazeSolver(maze)

open ('maze_pts.txt','w').write(str(self._start) + ' ' + str(self._end) + '\n')
solver.setStartPoint(self._start)
solver.setEndPoint(self._end)
solver.solve()

class InteractiveMazeGame(MazeGame):

def createMaze(self):
f = MazeFactory()
return f.makeMaze()

def getStartEndPoints(self, maze):

while True:
try:
pt1 = raw_input('Enter starting point: ')
x,y = pt1.split()
self._start = (int(x), int(y))
maze.validatePoint(self._start)
break
except:
pass

while True:
try:
pt2 = raw_input('Enter ending point: ')
x,y = pt2.split()
self._end = (int(x), int(y))
maze.validatePoint(self._end)
break
except:
pass

class FilebasedMazeGame(MazeGame):

def createMaze(self):
f = MazeFactory()

def getStartEndPoints(self, maze):

filename = raw_input('Enter point filename: ')
try:
l = line.split(')')
self._start = eval(l.strip() + ')')
self._end = eval(l.strip() + ')')
except (OSError, IOError, Exception), e:
print e
sys.exit(0)

class RandomMazeGame(MazeGame):

def __init__(self, w=0, h=0):
super(RandomMazeGame, self).__init__(w, h)
self._dimension = w

def createMaze(self):
f = MazeFactory()
return f.makeRandomMaze(self._dimension)

def getStartEndPoints(self, maze):

pt1, pt2 = (0,0), (0,0)
while pt1 == pt2:
pt1 = maze.getRandomStartPoint()
pt2 = maze.getRandomEndPoint()

self._start = pt1
self._end = pt2

class RandomMazeGame2(RandomMazeGame):
""" Random maze game with distant points """

def getStartEndPoints(self, maze):

pt1, pt2 = (0,0), (0,0)
flag = True
while flag:
pt1 = maze.getRandomStartPoint()
pt2 = maze.getRandomEndPoint()
# Try till points are at least
# half maze apart
xdist = maze.calcXDistance(pt1, pt2)
ydist = maze.calcYDistance(pt1, pt2)
if xdist>=float(maze.getWidth())/2.0 or \
ydist>=float(maze.getHeight())/2.0:
flag = False

self._start = pt1
self._end = pt2

def main():

p = optparse.OptionParser()
dest='random',action='store_true',default=False)
p.add_option('-R','--random2',help='Play the random game with distant points',
dest='Random',action='store_true',default=False)
dest='file',action='store_true',default=False)
dest='interact',action='store_true',default=False)
p.add_option('-d','--dimension',help='Matrix dimension (required for random games)',
dest='dimension', metavar="DIMENSION")

options, args = p.parse_args()
d = options.__dict__

if d.get('random') or d.get('Random'):
dim = d.get('dimension')
if not dim:
sys.exit('Random games require -d or --dimension option.')
if d.get('random'):
game = RandomMazeGame(int(dim))
game.runGame()
elif d.get('Random'):
game = RandomMazeGame2(int(dim))
game.runGame()
elif d.get('file'):
game = FilebasedMazeGame()
game.runGame()
elif d.get('interactive'):
game = InteractiveMazeGame()
game.runGame()

if __name__ == "__main__":
if len(sys.argv)==1:
sys.argv.append('-h')

main()