1 #!/usr/bin/env python
   2 # -*- coding: utf-8 -*-
   3 # -*- mode: python -*-
   4 
   5 
   6 # Configuração de caracteres do mapa
   7 parede     = '#'
   8 corredor   = '.'
   9 percorrido = '='
  10 errado     = 'x'
  11 solucao    = '@'
  12 entrada    = 'E'
  13 saida      = 'S'
  14 
  15 
  16 class Labirinto( object ):
  17     def __init__( self ):
  18         self.mapa    = None
  19         self.entrada = None
  20         self.saida   = None
  21     # __init__()
  22 
  23 
  24     def le_mapa( self, texto ):
  25         """Lê um mapa, este deve ter uma entrada e uma saída."""
  26         self.mapa = texto.split( '\n' )
  27 
  28         for i, l in enumerate( self.mapa ):
  29             # encontra entrada:
  30             p = l.find( entrada )
  31             if p >= 0:
  32                 self.entrada = ( i, p )
  33             # encontra saida:
  34             p = l.find( saida )
  35             if p >= 0:
  36                 self.saida = ( i, p )
  37 
  38             # converte string para lista
  39             self.mapa[ i ] = list( l )
  40 
  41         if not self.entrada:
  42             raise ValueError( "O mapa não possui uma entrada!" )
  43         if not self.saida:
  44             raise ValueError( "O mapa não possui uma saída!" )
  45     # le_mapa()
  46 
  47 
  48     def le_mapa_arquivo( self, arquivo ):
  49         """Lê um mapa de um arquivo"""
  50         f = open( arquivo )
  51         self.le_mapa( f.read() )
  52         f.close()
  53     # le_mapa_arquivo()
  54 
  55 
  56 
  57     def __str__( self ):
  58         m = []
  59         for l in self.mapa:
  60             m.append( ''.join( l ) )
  61         return '\n'.join( m )
  62     # __str__()
  63 
  64 
  65     def resolve( self ):
  66         """Resolve o labirinto, tenta encontrar a saída.
  67 
  68         Se a saída foi encontrada, retorna True, caso contrário False.
  69         """
  70         def posicao_valida( linha, coluna ):
  71             "Função utilizada para conferir se a posição está dentro do mapa"
  72             if linha > len( self.mapa ) or \
  73                    coluna > len( self.mapa[ linha ] ):
  74                 "Posição inválida, sai fora do mapa"
  75                 return False
  76             else:
  77                 return True
  78         # posicao_valida()
  79 
  80 
  81         def encontra_saida( linha, coluna ):
  82             """Função recursiva para encontrar a saída."""
  83 
  84             if self.mapa[ linha ][ coluna ] == saida:
  85                 "Caso base da recursão, estamos em cima da saída"
  86                 return True
  87             else:
  88                 """Marque como percorrido e entre em recursão
  89 
  90                 No caso iremos pela direita, depois para cima, para esquerda e
  91                 então para baixo.
  92 
  93                 Lembrando que isto é uma recursão e que marcamos nosso caminho,
  94                 temos magicamente a lembrança dos caminhos já testados.
  95                 """
  96                 self.mapa[ linha ][ coluna ] = percorrido
  97                 achou = False
  98 
  99                 if not achou and \
 100                        posicao_valida( linha, coluna + 1 ) and \
 101                        self.mapa[ linha ][ coluna + 1 ] in ( corredor, saida ):
 102                     """Ainda não encontrou e
 103                     a posição à direita é corredor ou é a saída.
 104                     Prossiga pela direita."""
 105                     achou = encontra_saida( linha, coluna + 1 )
 106 
 107                 if not achou and \
 108                        posicao_valida( linha - 1, coluna ) and \
 109                        self.mapa[ linha - 1 ][ coluna ] in ( corredor, saida ):
 110                     """Ainda não encontrou e
 111                     a posição acima é corredor ou é a saída.
 112                     Prossiga para cima."""
 113                     achou = encontra_saida( linha - 1, coluna )
 114 
 115                 if not achou and \
 116                        posicao_valida( linha, coluna - 1 ) and \
 117                        self.mapa[ linha ][ coluna - 1 ] in ( corredor, saida ):
 118                     """Ainda não encontrou e
 119                     a posição à esquerda é corredor ou é a saída.
 120                     Prossiga para esquerda."""
 121                     achou = encontra_saida( linha, coluna - 1 )
 122 
 123                 if not achou and \
 124                        posicao_valida( linha + 1, coluna ) and \
 125                        self.mapa[ linha + 1 ][ coluna ] in ( corredor, saida ):
 126                     """Ainda não encontrou e
 127                     a posição abaixo é corredor ou é a saída.
 128                     Prossiga para baixo."""
 129                     achou = encontra_saida( linha + 1, coluna )
 130 
 131                 # Caso o caminho adotado foi correto, marque como solução
 132                 # senão marque como errado
 133                 if achou:
 134                     self.mapa[ linha ][ coluna ] = solucao
 135                 else:
 136                     self.mapa[ linha ][ coluna ] = errado
 137                     
 138                 return achou
 139         # encontra_saida()
 140         
 141         return encontra_saida( self.entrada[ 0 ], self.entrada[ 1 ] )
 142     # resolve()
 143 # Labirinto
 144 
 145 
 146 # Exemplo de uso:
 147 l = Labirinto()
 148 l.le_mapa(
 149     """
 150 ############## ####################
 151 #E.#.S#..#...###.....#.#..........#
 152 #..#.............###.#............#
 153 ##...##...######## #...#..........# 
 154 ##############     ################
 155 """ )
 156 print l
 157 print "achou?",l.resolve()
 158 print l

   1 #!/usr/bin/python
   2 # -*- coding: iso-8859-1 -*-
   3 
   4 """ Implementação do algoritmo AStar utilizando uma Priority Queue.
   5 
   6 Foi escrito para a solução de labirintos, encontrando o menor caminho
   7 para sair de E e chegar a S. O labirinto é composto por:
   8    # significando que não pode andar nesta posição
   9    . significando que pode andar nesta posição
  10    E ponto de início (Entrada)
  11    S ponto de destino (Saída)
  12 
  13 """
  14 
  15 import Queue, bisect
  16 
  17 class PriorityQueue(Queue.Queue):
  18   def _put(self, item):
  19     bisect.insort(self.queue, item)
  20     
  21 
  22 def AStar(mapa):
  23   """ Algoritmo AStar.
  24 
  25   mapa deve ser um vetor de strings ou uma matriz de caracteres de
  26   tamanho NxM.
  27   """
  28   # listas do algoritmo AStar
  29   aberta = PriorityQueue(0)
  30   fechada = [] # PriorityQueue(0)
  31   
  32   n = len(mapa)    #linhas
  33   m = len(mapa[0]) #colunas
  34  
  35   # procurar pela entrada e saída
  36   entrada = None
  37   saida = None
  38   for i, linha in enumerate(mapa):
  39     for j, char in enumerate(linha):
  40       if char == 'E':
  41         entrada = [i, j]
  42       elif char == 'S':
  43         saida = [i, j]
  44 
  45   # ajuda a calcular a distância
  46   def dist(orig, dest):
  47     return abs(orig[0] - dest[0]) + abs(orig[1] - dest[1])
  48 
  49   # retorna os vizinhos de um nó no mapa, caso possa caminhar por eles
  50   def vizinhos(no):
  51     pos = no.pos
  52     res = []
  53     if pos[0] > 0 and mapa[pos[0]-1][pos[1]] in ('.','S'): # tenta ir para cima
  54       novo = No([pos[0]-1, pos[1]], no, no.g+1, dist([pos[0]-1,pos[1]], saida))
  55       res.append(novo)
  56     if pos[0] < n-1 and mapa[pos[0]+1][pos[1]] in ('.','S'): # tenta ir para baixo
  57       novo = No([pos[0]+1, pos[1]], no, no.g+1, dist([pos[0]+1,pos[1]], saida))
  58       res.append(novo)
  59     if pos[1] > 0 and mapa[pos[0]][pos[1]-1] in ('.','S'): # tenta ir para esquerda
  60       novo = No([pos[0], pos[1]-1], no, no.g+1, dist([pos[0],pos[1]-1], saida))
  61       res.append(novo)
  62     if pos[1] < m-1 and mapa[pos[0]][pos[1]+1] in ('.','S'): # tenta ir para direita
  63       novo = No([pos[0], pos[1]+1], no, no.g+1, dist([pos[0],pos[1]+1], saida))
  64       res.append(novo)
  65     return res 
  66  
  67   # representação de cada nó do AStar
  68   class No(object):
  69     def __init__(self, pos=None, pai=None, g=0, h=0):
  70       self.pos = pos
  71       self.pai = pai
  72       self.g = g
  73       self.h = h
  74 
  75     def __eq__(self, other):
  76       return self.pos == other.pos
  77 
  78     def __ne__(self, other):
  79       return self.pos != other.pos
  80 
  81     def __le__(self, other):
  82       return self.g+self.h <= other.g+other.h
  83 
  84     def __ge__(self, other):
  85       return self.g+self.h >= other.g+other.h
  86 
  87     def __str__(self):
  88       return 'pos = %s, g = %d, h = %d' % (self.pos, self.g, self.h)
  89     
  90   at = No()
  91   at.h = dist(entrada, saida)
  92   at.pos = entrada[:]
  93   at.pai = None
  94   aberta.put(at, False)
  95   mapa1 = [list(l) for l in mapa]
  96   achou = False
  97   while not aberta.empty():
  98     at = aberta.get(False)
  99     fechada.append(at)
 100     if at.pos == saida: # achou
 101       achou = True
 102       break
 103     viz = vizinhos(at)
 104     for no in viz:
 105       if not no in fechada:
 106         if not no in aberta.queue:
 107           aberta.put(no)
 108 
 109   # reconstrução do caminho
 110   if achou:
 111     caminho = [at.pos]
 112     while True:
 113       at = at.pai
 114       if at is None:
 115         break
 116       caminho.insert(0, at.pos)
 117     print caminho
 118   else:
 119     print 'Caminho não encontrado'
 120 
 121 AStar([
 122   '##########',
 123   '#E..#...S#',
 124   '#..#.#..##',
 125   '#.......##',
 126   '##########'])
 127 
 128 AStar([
 129   '############## ####################',
 130   '#E.#.S#..#...###.....#.#..........#',
 131   '#..#.............###.#............#',
 132   '##...##...######## #...#..........#',
 133   '##############     ################'])