maze_sol.py

'''Maze Solver.

Uses the left-hand rule to solve the maze.

Coder@Sonnack.com
September 16, 2014
'''
####################################################################################################
from sys import argv
from logger import logger, info, debug, trace
from colors import ixColorFaintBlue, ixColorLightYellow
from maze_obj import MazeObject
from maze_nav import MazeNavigator
from maze_gif import MazeImage
from maze_gen import MazeGen1
####################################################################################################
Log = logger('Maze/Sol')


##~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~##
## MAZE SOLVER
##~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~##
class MazeSolver (MazeNavigator):
    '''\
Maze Solving class.

methods:
    solve_maze      ():maze_path    - front-end for .solve() method.

internal methods:
    solve           (maze_path)     - solve the maze using left-hand rule.

'''
    def __init__ (self, mz, row=0, col=0):
        super(MazeSolver,self).__init__(mz, row, col)
        self.messages = []

    def solve_maze (self):
        a = []
        Log.info('SOLVE MAZE')
        self.reset_curr_cell()
        self.solve(a)
        Log.info('Maze Solved!  (path-length: %d)' % len(a))
        return a

    def solve (self, maze_path):
        '''Solve maze using left-hand rule. [RECURSIVE!]'''
        Log.debug('[%d,%d]' % (self.curr_row, self.curr_col))
        c = self.get_curr_cell()
        # If we found the exit, we're done!!!
        if c == MazeObject.MazeExit:
            return True
        # If this cell is new, mark it visited...
        if c == MazeObject.EmptyCell:
            self.set_curr_cell(ixColorFaintBlue)

        # Can we move left?
        if self.get_left_wall() == 0:
            Log.trace('[%d,%d] turn left' % (self.curr_row, self.curr_col))
            t = (self.curr_row, self.curr_col, self.direction)
            self.turn_left()
            self.move_to_next_cell()
            maze_path.append(t)
            # *** Recurse! ***
            rv = self.solve(maze_path)
            if rv: return True ## Solved!!
            self.curr_row, self.curr_col, self.direction = maze_path.pop()

        # How about moving forward?
        if self.get_next_wall() == 0:
            Log.trace('[%d,%d] go straight' % (self.curr_row, self.curr_col))
            t = (self.curr_row, self.curr_col, self.direction)
            self.move_to_next_cell()
            maze_path.append(t)
            # *** Recurse! ***
            rv = self.solve(maze_path)
            if rv: return True ## Solved!!
            self.curr_row, self.curr_col, self.direction = maze_path.pop()

        # Can we at least move right?
        if self.get_right_wall() == 0:
            Log.trace('[%d,%d] turn right' % (self.curr_row, self.curr_col))
            t = (self.curr_row, self.curr_col, self.direction)
            self.turn_right()
            self.move_to_next_cell()
            maze_path.append(t)
            # *** Recurse! ***
            rv = self.solve(maze_path)
            if rv: return True ## Solved!!
            self.curr_row, self.curr_col, self.direction = maze_path.pop()

        # Can't advance; must back up!
        Log.trace('STUCK! Gotta back up now!')
        return False




####################################################################################################
if __name__ == '__main__':
    print('autorun: %s' % argv[0])
    Log.start('maze_sol.log')
    Log.level(info())

    mz = MazeObject(25, 40)
    mi = MazeImage(mz)
    mg = MazeGen1(mz)
    ms = MazeSolver(mz)

    # Create a Maze...
    mg.generate_maze()

    mi.draw_maze()
    mi.save('solver-maze.gif')

    # Solve the Maze...
    a = []
    ms.solve(a)
    for t in a:
        if t[0] or t[1]:
            mz.set_cell(t[0], t[1], ixColorLightYellow)
    mz.print_maze(Log.fp())

    # Create Maze GIF...
    mi.draw_maze()
    mi.show()
    mi.save('solver-path.gif')

    Log.end()

####################################################################################################
'''eof'''