Gerador de labirinto e buscador de caminho usando busca em profundidade.

labirinto.py

# -*- coding: utf-8 -*-
'''
Gerador de Labirinto e busca A*
Aplicativo que gera labirinto e monstra o caminho da origem ao destino utilizando o algoritmo de busca A*

@author: Marcos Filipe Lino
@contact: [email protected]

'''
import string
import random
import operator


route = {}
rooms = {}

class Room(object):
    '''
    Class que representa as salas do labirinto
    '''
    def __init__(self, name, pos_x, pos_y):
        self.__name = name
        self.__posicao = (pos_x, pos_y)
        self.__visitado = False
        self.fn = 0
    
    def getposicao(self):
        return self.__posicao
    
    @property
    def visitado(self):
        return self.__visitado
    
    @visitado.setter
    def visitado(self, v):
        self.__visitado = v
    
    def __str__(self):
        return str(self.__name)
    
    def __repr__(self):
        return self.__str__()
    
        

def get_neighbor(room, maze):
    neighbor = []
    max_x = len(maze)
    max_y = len(maze[0])
    x, y = room.getposicao()
    if y > 0:
        neighbor.append(maze[x][y - 1])
    if x > 0:
        neighbor.append(maze[x - 1][y])
    if x < max_x - 1: 
        neighbor.append(maze[x + 1][y])
    if y < max_y - 1:
        neighbor.append(maze[x][y + 1])
    return neighbor

def create_view_maze(m, n):
    linha = 2 * m + 1
    coluna = 2 * n + 1
    lista = sorted(route.keys())
    mapa = [['#' for _ in range(coluna)] for _ in range( linha) ]
    for i in range(1, linha-1, 2):
        for j in range(1, coluna, 2):
            mapa[i][j] = lista.pop(0)
    return mapa

def get_neighborNoVisited(room, maze):
    
    def isVisitado(n):
        if n.visitado == False:
            return n
        
    neighbors = get_neighbor(room, maze)    
    return filter(isVisitado, neighbors)

def create_routes(maze):
    maze[0][0].visitado = True
    stack = []
    stack.append(maze[0][0])
    while stack != []:
        room = stack.pop()
        neighbor_nv = get_neighborNoVisited(room, maze)
        if neighbor_nv != []:
            neighbor = random.choice(neighbor_nv)
            neighbor.visitado = True
            route[room].append(neighbor)
            stack.append(room)
            stack.append(neighbor)
            
def create_rooms(m, n):
    '''
    Cria as roms do labirinto de m x n dimensoes
    '''
    maze = [ [None for _ in range(n)] for _ in range(m)]
    names = list(string.uppercase)
    for i in range(m):
        for j in range(n):
            name = names.pop(0)
            maze[i][j] = Room(name, i, j)
            rooms[name] = maze[i][j]
            route[maze[i][j]] = []
            
    return maze


def delwall(maze_view, maze):
    for i in range(1, len(maze_view) -1, 2):
        for j in range(1, len(maze_view[0]), 2):
            if maze_view[i][j] != '#':
                room = maze_view[i][j]
                neighbors = route[room]
                for n in neighbors:
                    x, y = retiraWall(room, n, maze)
                    maze_view[i + x][ j + y] = ' '                
                
def retiraWall(room, neighbor, maze):
    x, y = room.getposicao()
    max_x = len(maze)
    max_y = len(maze[0])
    if y > 0 and neighbor == maze[x][y -1] :
        return (0, -1)
    if x > 0 and neighbor == maze[x - 1][y]:
        return (-1, 0)
    if x < max_x - 1 and neighbor == maze[x + 1][ y]: 
        return (1, 0)
    if y < max_y - 1 and neighbor == maze[x][y + 1]:
        return (0, 1)
    return (0,0)


def print_view(maze_view):
    for linha in maze_view:
        for c in linha:
            print c,
        print
    print

def hn(origem, destino, maze):
    x0, y0  = origem.getposicao()
    x1, y1 = destino.getposicao()
    dx = 0
    dy = 0
    if x1 > x0:
        dx = x1 - x0
    else:
        dx = x0 - x1
    if y1 > y0:
        dy = y1 - y0
    else:
        dy = y0 - y1
    return dx + dy

def Astar(origem, destino, maze):
    custo = 1
    fila = []
    print origem,
    while origem != destino:
        visinhos = route[origem]
        for v in visinhos:
            v.fn = hn(v, destino, maze) + custo
        fila += visinhos
        fila.sort(key=operator.attrgetter('fn'))
        origem = fila.pop(0)
        print origem,
    

def main():
    '''
    Função main resposavel por iniciar a aplicação 
    '''
    maze = create_rooms(5, 5)
    maze_view = create_view_maze(5, 5)
    print_view(maze_view)
    create_routes(maze)
    delwall(maze_view, maze)
    print_view(maze_view)
    while True:
        origem = str(raw_input("Digite a origem"))
        print
        destino = str(raw_input("Digite o destino"))
        print
        Astar(rooms[origem], rooms[destino], maze)
        print
    
    
    
    #print route
    

if __name__ == '__main__':
    '''
    Identifica se o arquivo foi executado corretamente com os argumentos corretos
    ''' 
    main()
    
    

Valeu @cpusam, eu tinha até me esquecido desse código