Source

Fat x Fast / FatxFast / tilemap / maze / mazegen.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"

import random

from FatxFast.tilemap.maze.mazecell import WEAVE_ID
from FatxFast.tilemap.editor import tile

# Enumerated directions
NORTH = 0
WEST = 1
EAST = 2
SOUTH = 3

DIRS = {(0, -1): NORTH, (-1,0): WEST, (1,0): EAST, (0,1): SOUTH}
DIRECTIONS = [(0,-1), (-1,0), (1,0), (0,1)]

def evaluate_direction(direction):
    return DIRECTIONS.index(direction)

def distance(cell, _cell):
    return (_cell.column-cell.column, _cell.row-cell.row)

def get_direction(cell, direction):
    return (cell.column+direction[0], cell.row+direction[1])

class MazeAlgorithm(object):
    moves = []
    def __init__(self):
        self._maze = None
        self.floor_width = 2
        self.floor_height = 2

    def _choose_adjacency(self):
        """Takes a cell randomizes a neighbour from the given container and 
        creates a pathway between them"""
        try:
            _cell = random.choice(self._adjacencies)
        except IndexError:
            pass
        else:
            self._create_pathway(_cell)
            self._cell = _cell

    def _create_pathway(self, _cell):
        direction = DIRS[distance(self._cell, _cell)]
        self._maze.destroy_wall(self._cell.x, self._cell.y, direction)   

    def _set_adjacencies(self):
        adjs = [
            self._maze.get_cell(get_direction(self._cell, direction)) 
            for direction in self.moves]
        adjs = filter(None, adjs)
        self._adjacencies = adjs

    def run(self, maze, **kwargs):
        self._maze = maze
        maze.floor_width = kwargs.get("floor_width", self.floor_width)
        maze.floor_height = kwargs.get("floor_height", self.floor_height)
        self._maze.we.new_map(
            (self._maze.columns*(
                self._maze.north_wall_size[0]+self._maze.west_wall_size[0]))+1, 
            (self._maze.rows*(
                self._maze.north_wall_size[1]+self._maze.west_wall_size[1]))+1)
        self._maze.we.load_tileset(self._maze.tilesheet_imagename)
        self._maze.we.create_layer(
            visible=1, default_image=self._maze.tiles["floor2"], 
            entity_id=tile.FLOOR_ID)
        self._maze.we.create_layer()
        self._maze.we.create_layer()
        self._maze.we.create_object_layer()
        self._maze.create_cells(self._maze.columns, self._maze.rows)

class BinaryTree(MazeAlgorithm):
    moves = [(0, -1), (-1, 0)]

    def run(self, maze, **kwargs):
        super(BinaryTree, self).run(maze, **kwargs)

        cells = maze.cellcontainer

        for y in xrange(maze.rows):
            for x in xrange(maze.columns):
                self._cell = cells[y][x]
                self._set_adjacencies()
                self._cell.visited = True
                self._choose_adjacency()

class FourMoveAlgorithm(MazeAlgorithm):
    moves = [(0,-1), (-1,0), (1,0), (0,1)]

    def __init__(self):
        super(FourMoveAlgorithm, self).__init__() 
        self._cell = None

    def run(self, maze, **kwargs):
        super(FourMoveAlgorithm, self).run(maze, **kwargs)
        self._cell = maze.get_cell(
            (random.randint(0,maze.columns-1), random.randint(0,maze.rows-1)))

class RandomPrim(FourMoveAlgorithm):
 
    def run(self, maze, **kwargs): 
        """Total instructions for this algorithm:
        4+t(choose_adj)+t(get_adjs)+t(visited_adjs)+t(uv_adjs)"""
        super(RandomPrim, self).run(maze, **kwargs)
        self._cell.visited = True

        self._set_adjacencies()
        adj_list = self._adjacencies
        while adj_list:
            self._cell = random.choice(adj_list)
            adj_list.remove(self._cell)
            if not self._cell.visited:
                self._cell.visited = True
                self._set_adjacencies()  
                adj_list.extend([
                    adj for adj in self._adjacencies if not adj.visited])
                self._adjacencies = [
                    adj for adj in self._adjacencies if adj.visited] 
                self._choose_adjacency()


class Backtrack(FourMoveAlgorithm): 
    """Acts as a base class for backtrack generation algorithms"""
    def __init__(self):
        super(Backtrack, self).__init__()
        self._uv_cells = None
        self._temp_stack = []
    
    def _remove_from_stack(self):
        self._cell = self._temp_stack.pop()

    def run(self, maze, **kwargs):
        """Expects a maze instance as an argument
        "Moulds" the maze according to the algorithm below.
        This algorithm is implemented with local variables for speed.
        A few class methods are implemented to keep the code readable yet fast.
        
        Total instructions for this algorithm:
        Min: 4+t(get_adjs)+t(uv_adjs), 
        Max: 5+t(get_adjs)+t(uv_adjs)+t(choose_adj)
        """
        super(Backtrack, self).run(maze, **kwargs)
        
        self._uv_cells = (maze.columns*maze.rows)-1

        while self._uv_cells:
         
            self._cell.visited = True
            
            self._set_adjacencies()
            uv_adjs = [uv_adj for uv_adj in 
                self._adjacencies if not uv_adj.visited]
            
            if uv_adjs:
                self._adjacencies = uv_adjs
                self._temp_stack.append(self._cell)
                self._choose_adjacency()
                self._uv_cells -= 1
            else:
                self._remove_from_stack()

class WeaveBacktrack(Backtrack):
    """Weave extension for backtracking algorithm. 
    Generates a "2.5D" maze with passages running under/over cells. 
    
    These passage cells are represented with cell attribute special= 'weave'.
    """

    def __init__(self):
        super(WeaveBacktrack, self).__init__()
        self.floor_width = 3
        self.floor_height = 3

    def _check_weaveability(self, _cell):
        """Core mechanism to evaluate the weaving possibility from the
        selected neighbour cell"""
        passages = {direction:self._maze.get_wall(self._cell, direction) 
            for direction, move in enumerate(DIRECTIONS)}
        north_south = filter(None, (passages[NORTH], passages[SOUTH]))
        west_east = filter(None, (passages[WEST], passages[EAST]))
        try:    
            return (not _cell.visited and 
                (len(north_south) == 2 or len(west_east) == 2))
        except AttributeError:
            pass
    
    def _create_pathway(self, _cell):
        if self._cell.entity_id != WEAVE_ID and _cell.entity_id != WEAVE_ID:
            super(WeaveBacktrack, self)._create_pathway(_cell) 

    def _remove_from_stack(self):
        if not self._weave():
            super(WeaveBacktrack, self)._remove_from_stack()

    def _weave(self):
        # Iterates the adjacencies. If weavable adjacency is found returns true
        random.shuffle(self._adjacencies) 
        cell = self._cell
        for adj in self._adjacencies:
            self._cell = adj
            direction = distance(cell, self._cell)
            _cell = self._maze.get_cell(get_direction(self._cell,direction))
            if _cell and self._check_weaveability(_cell):
                self._maze.create_weave(_cell, 
                    DIRS[(-direction[0], -direction[1])])
                self._maze.create_weave(cell, 
                    DIRS[direction])
                self._cell.entity_id = WEAVE_ID
                return True