1. Sami Loone
  2. Fat x Fast

Source

Fat x Fast / FatxFast / tilemap / maze / solver.py


# This file is part of FatxFast.
#
#    FatxFast is free software: you can redistribute it and/or modify
#    it under the terms of the GNU General Public License as published by
#    the Free Software Foundation, either version 3 of the License, or
#    (at your option) any later version.
#
#    FatxFast is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#    GNU General Public License for more details.
#
#    You should have received a copy of the GNU General Public License
#    along with FatxFast.  If not, see <http://www.gnu.org/licenses/>.

# Versioning based on: 
# http://en.wikipedia.org/wiki/Versioning#Designating_development_stage
__author__ = "dryatu (c) 2013"
__version__ = "1.2.5"

from FatxFast.tilemap.maze import mazegen
from FatxFast.tilemap.maze.mazecell import CELL_ID

def get_linear_tiles(tiles):
    """Return all of the maze cells in a one dimensional list"""
    return [tile for grid in tiles for tile in grid]

def get_dead_ends(maze):
    des = [tile for tile in get_linear_tiles(maze.cellcontainer)
        if (len(get_legal_moves(maze, tile)) == 1 and
        tile.entity_id == CELL_ID)]
    return des 

def get_legal_moves(maze, tile):
    return [move for move, dir in mazegen.DIRS.items()
        if not maze.get_wall(tile, dir)]
    
class BacktrackSolver(object):
    """Solving algorithm"""
    moves = mazegen.Backtrack.moves
    def __init__(self):
        self._maze = None
        self._solution = []
        self._des = []
        self._cell = None
        self._moves = [self._cell]
    
    def get_linear_solution(self):
        """Returns a linear - sorted - solution. Useful when start->end
        solution is needed"""
        solution = [
            cell for cell in get_linear_tiles(self._maze.cellcontainer) 
                if cell.solution]
        self._cell = self._maze.startcell
        while solution:
            solution.remove(self._cell)
            moving = True
            moves = get_legal_moves(self._maze, self._cell)
            while moving and moves:
                move = moves.pop()
                _cell = self._maze.get_cell(
                    (self._cell.column+move[0], self._cell.row+move[1]))
                if _cell in solution:
                    self._cell = _cell
                    self._solution.append((self._cell.x,self._cell.y))
                    moving = False
        self._solution.reverse()
        return self._solution
    
    def run(self, maze):
        """Runs a solving algorithm on the given maze"""
        self._maze = maze
        self._cell = self._maze.startcell
        self._des = get_dead_ends(maze)
        self._set_solutions()
  
    def _set_solutions(self):
        # Determines cell's viability as a solution cell
        for deadend in self._des:
            self._cell = deadend
            self._moves = [self._cell]
            while len(self._moves) == 1:    
                
                self._cell.solution = False
                self._cell = self._moves[0]
                self._moves = []

                for move in get_legal_moves(self._maze, self._cell):
                    _cell = self._maze.get_cell(
                        (self._cell.column+move[0], self._cell.row+move[1]))
                    if (_cell and _cell.solution and self._cell.id == CELL_ID): 
                        self._moves.append(_cell)