'''
Maze module
Brief description:
Defines a maze class, has solve method that finds the path from the upper left
cell to down right cell.
Detailed description:
Classes contained:
Maze
attributes:
density: density of the obstacles in the maze
type: float
dim1: x-dimension of the maze
type: int
dim2: y-dimension of the maze
type: int
mode: graphics mode for the solve method
SILENT: no graphics
GRAPHICAL_FULL: display algorithm progess with full view
GRAPHICAL_LIMITED: display algorithm progess with limited view
path: path found by the robot
type: list of tuples (x,y)
maze: maze
type: list of lists
xCurrent: current x coordinate of the robot
type: int
yCurrent: current y coordinate of the robot
type: int
methods:
__init__(self): constructor of the class
generate_maze(self): generates self.maze randomly such that it
contains at least one path from upper left
cell to the down right cell
solve(self): generates path and produce graphical output
according to self.mode value. To change
display mode use self.set_mode() method.
if mode='silent': generates path with no
display
if mode='graphical_full': generates path and
shows algorithm progress with view of whole
maze
if mode='graphical_limited': generates path
and shows algorithm progress with limited
view of maze
game(self): displays partial maze, waits for user input
(arrow keys) to move the robot, pressing key
'a' uncovers the whole maze
get_new_coordinates(self):
generates the new coordinates by evaluating
the user input (used in game mode)
step(self):
returns to next coordinates of the robot by
evaluating the current coordinate and
the maze.
display_init(self): initialize display (pygame) related
parameters and functions
draw_maze(self): draws the whole self.maze to display
update_maze(self):
updates the status of the neighbors of cell
(self.xCurrent,self.yCurrent)
set_mode(self, mode): Sets mode attribute (see above)
Maze ASCII representation
' ' represents an empty cell
'X' represents an obstacle
'*' represents the path
Maze graphical representation
Grey represents an empty cell (not visited)
Green represents an empty cell (already visited)
Red represents an obstacle
Blue represents the path
White represents the current location of the robot
Meaning of entries in self.maze
0 represents empty (unexplored) cell
1 represents an obstacle
2 represents the path
3 represents a cell that has been explored, but is not on the path
4 represents the cell the robot is in
Created on Dec 25, 2011
Modified Feb 6, 2012
'''
__version__ = '1.0.0'
__author__ = 'Aykut Bulut, Ted Ralphs (ayb211@lehigh.edu,ted@lehigh.edu)'
__license__ = 'BSD'
__maintainer__ = 'Aykut Bulut'
__email__ = 'ayb211@lehigh.edu'
__url__ = None
__title__ = 'Maze class'
import pygame
from pygame.locals import *
from random import seed, random
from coinor.blimpy import Stack
# empty (unexplored) cell
EMPTY = 0
# cell with an obstacle
OBSTACLE = 1
# cell that is on the path
ON_PATH = 2
# cell that has been explored, but is not on the path
EXPLORED = 3
# cell the robot is in
ROBOT = 4
# graphical modes
SILENT = "silent"
GRAPHICAL_FULL = "graphical_full"
GRAPHICAL_LIMITED = "graphical_limited"
# Search directions
UP = {'x': -1, 'y': 0}
DOWN = {'x': 1, 'y': 0}
RIGHT = {'x': 0, 'y': 1}
LEFT = {'x': 0, 'y': -1}
# Order in which to try directions
SEARCH_ORDER = [DOWN, RIGHT, UP, LEFT]
KEY_PRESS_DIRECTION = {K_UP : UP,
K_DOWN : DOWN,
K_RIGHT : RIGHT,
K_LEFT : LEFT}
class Maze(object):
'''
Defines a maze class, has solve method that finds the path from the upper
left cell to down right cell.
'''
def __init__ (self, dimx=50, dimy=50, seedInput=0, density=0.5):
''' Constructor for Maze class
posts: self.destiny, self.dim1, self.dim2, self.mode, self.maze,
self.path, self.xCurrent, self.yCurrent
'''
seed(seedInput)
self.density = density
self.dimension = {'x' : dimx, 'y' : dimy}
self.mode = GRAPHICAL_LIMITED
self.generate_maze()
self.path = Stack()
self.location = (0, 0)
def generate_maze(self):
'''
Generates self.maze randomly such that it contains at least one path
from upper left cell to the down right cell
Post: updates self.maze
'''
x,y = 0,0
path = set()
path.add((x,y))
while (x, y) != (self.dimension['x']-1, self.dimension['y']-1):
if random() < 0.5:
if x