maze_gen.py

'''Maze Generator #1.

Coder@Sonnack.com
September 16, 2014
'''
####################################################################################################
from sys import argv
from random import random, shuffle
from logger import logger, info, debug, trace
from maze_obj import MazeObject
from maze_nav import MazeNavigator
from maze_img import MazeImage
####################################################################################################
Log = logger('Maze/Gen')

RandomWall = lambda f: random() < f


##================================================================================================##
## MAZE GENERATOR #1
##================================================================================================##
class MazeGen1 (MazeNavigator):
    '''\
Maze Generator #1.

methods:
    generate_maze   ()

internal methods:
    carve_a_path        (cell_value)    - carve a single path in the maze
    find_a_path         ()              - find a random cell on a path for branching to a new path
    change_direction    ()              - turn left or right (50/50 either way)

'''
    max_steps   = 100   # max steps allows for a given path
    wall_change = 0.1   # probability of NOT changing direction when hitting wall
    occu_change = 0.1   # probability of NOT changing direction when hitting an occupied cell
    dir_change  = 1     ##TODO: this obviously needs rethinking

    def __init__ (self, mz, row=0, col=0):
        super(MazeGen1,self).__init__(mz, row, col)
        self.mz = mz
        self.tot_steps = 0
        self.dir_steps = 0
        self.path_list = []

    def generate_maze (self):
        '''Generate a maze by carving paths in it.'''
        self.mz.set_all_cells(MazeObject.EmptyCell)
        self.mz.set_cell(self.curr_row, self.curr_col, MazeObject.MazeEntry)
        self.reset_curr_cell()

        # Start carving paths. When when maze fully explored (or max attempts)...
        for ix in range(self.mz.dims[0] * self.mz.dims[1]):
            self.carve_a_path(1)
            if self.mz.all_cells_occupied():
                Log.info('Finished after %d iterations.' % ix)
                # Reset the maze cells and set the Entry way...
                self.mz.set_all_cells(MazeObject.EmptyCell)
                self.mz.set_entry_and_exit()
                return
        # If we fell through, something's very, very wrong!...
        Log.error('NOT DONE AFTER %d ITERATIONS!' % ix)

    def carve_a_path (self, cell_value):
        '''Carve a path through the maze. Set each cell in the path to cell_value.'''
        Log.debug()
        Log.debug('NEW PATH...')

        if 0 < len(self.path_list):
            if not self.find_a_path():
                return
            Log.debug('using: (%d, %d)' % (self.curr_row, self.curr_col))

        # loop while forging a path...
        self.tot_steps = 0
        self.dir_steps = 0
        current_path = []
        while self.tot_steps < self.max_steps:
            s = self.Abbrev[self.direction]
            t = (self.tot_steps, self.dir_steps, s, self.curr_row, self.curr_col)
            Log.trace('STEP: %d (%d:%s)  [%d, %d]' % t)
            current_path.append([self.curr_row, self.curr_col, 2])

            # test next cell...
            tc = self.get_next_cell()
            if tc < 0:
                # hit a wall...
                Log.trace('Hit the wall!')
                if self.wall_change < random():
                    if self.change_direction():
                        continue
                break
            if 0 < tc:
                # hit a traveled cell...
                Log.trace('Hit another path!')
                if self.occu_change < random():
                    if self.change_direction():
                        continue
                break

            # next cell isn't occupied, knock down the wall and go there...
            self.set_next_wall(MazeObject.NoWall)
            self.move_to_next_cell()
            # tag new cell...
            self.set_curr_cell(cell_value)

            # increment counters...
            self.tot_steps = self.tot_steps + 1
            self.dir_steps = self.dir_steps + 1

            # consider a change of direction...
            if self.dir_change < (random() * self.dir_steps):
                if self.change_direction():
                    self.dir_steps = 0

        # add path to pat list...
        n = len(current_path)
        Log.debug('New Path: %d step%s' % (n, '' if n == 1 else 's'))
        self.path_list.append(current_path)

    def find_a_path (self):
        '''Randomly pick a cell on an existing path to branch from. Set the new row,col and direction.'''

        # create a random order to try paths from the path list...
        maze_path_seq = [x for x in range(len(self.path_list))]
        shuffle(maze_path_seq)

        # pick a maze path (from the random list)...
        for mx,maze_path in map(lambda ix: (ix, self.path_list[ix]), maze_path_seq):
            Log.trace('MazePath: %d  (%d cells)' % (mx, len(maze_path)))

            # create a ramdom order to try cells from the maze path...
            maze_cell_seq = [x for x in range(len(maze_path))]
            shuffle(maze_cell_seq)

            # pick a maze cell (from the random list)...
            for cx,path_cell in map(lambda ix: (ix,maze_path[ix]), maze_cell_seq):
                Log.trace('PathCell: %d  [%d,%d (%d)]' % (cx, path_cell[0], path_cell[1], path_cell[2]))

                # test the cell for a possible branch...
                if path_cell[2] < 4:
                    self.curr_row = path_cell[0]
                    self.curr_col = path_cell[1]
                    Log.trace('testing: (%d, %d)' % (self.curr_row, self.curr_col))
                    if self.get_north_cell() == 0:
                        self.direction = self.North
                        ###TODO###junk code### path_cell[2] = path_cell[2] + 1
                        return True
                    if self.get_east_cell() == 0:
                        self.direction = self.East
                        ###TODO###junk code### path_cell[2] = path_cell[2] + 1
                        return True
                    if self.get_south_cell() == 0:
                        self.direction = self.South
                        ###TODO###junk code### path_cell[2] = path_cell[2] + 1
                        return True
                    if self.get_west_cell() == 0:
                        self.direction = self.West
                        ###TODO###junk code### path_cell[2] = path_cell[2] + 1
                        return True

        Log.debug('Unable to find a path!')
        return False

    def change_direction (self):
        '''Turn Left/Right (50% random choice) or Right/Left if first choice not possible. Return True if successful.'''
        if random() < 0.5:
            # try turning left...
            if self.get_left_cell() == MazeObject.EmptyCell:
                # cell is clear, this is good...
                d = self.turn_left()
            else:
                # can't, try right...
                if self.get_right_cell() == MazeObject.EmptyCell:
                    # cell is clear, this is good...
                    d = self.turn_right()
                else:
                    # nope!
                    return False
        else:
            # try turning right...
            if self.get_right_cell() == MazeObject.EmptyCell:
                # cell is clear, this is good...
                d = self.turn_right()
            else:
                # can't, try left...
                if self.get_left_cell() == MazeObject.EmptyCell:
                    # cell is clear, this is good...
                    d = self.turn_left()
                else:
                    # nope!
                    return False
        # Successful...
        Log.trace('NEW DIRECTION: %d' % d)
        return True




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

    mz = MazeObject(12, 20)
    mi = MazeImage(mz)
    mg = MazeGen1(mz)

    mg.generate_maze()
    mz.print_maze(Log.fp())

    mi.draw_maze()
    mi.show()
    mi.save('maze_gen.png')

    Log.end()

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