associação pythonbrasil[11] django zope/plone planet Início Logado como (Entrar)

Você não tem permissão para executar esta ação.

Excluir mensagem

ResolvedorLabirintoGrafico

Esta é a versão gráfica do ResolvedorLabirinto e possibilitaver o funcionamento passo-a-passo do algoritmo.

Requerimentos

  • Python >= 2.3 (usa enumerate)

  • PyGame >= 1.3

Download

A versão mais nova se encontra sempre em http://www.gustavobarbieri.com.br/labirinto_grafico.py

Instruções de Uso

  1. Execute o aplicativo. Pode passar um arquivo de mapa como argumento (--help para mais info).
  2. Pressione F3 para resolver o labirinto
  3. Pressione F2 para reiniciar o labirinto

Para Fazer (TODO)

  • Deixar o usuário resolver o labirinto

Código

   1 #!/usr/bin/env python
   2 # -*- coding: utf-8 -*-
   3 # -*- mode: python -*-
   4 
   5 import sys
   6 import pygame
   7 from pygame.locals import *
   8 from pygame.sprite import Sprite, RenderUpdates
   9 from math import floor
  10 
  11 
  12 
  13 def desenha_quadrado( tamanho, cor ):
  14     img = pygame.Surface( tamanho )
  15 
  16     cinza = Color( "#808080" )
  17     cor1 = pygame.color.add( cor, cinza )
  18     cor2 = pygame.color.subtract( cor, cinza )
  19 
  20     r = Rect( ( 0, 0 ), tamanho )
  21     r.inflate_ip( -2, -2 )
  22     r.topleft = ( 1, 1 )
  23 
  24     img.fill( cor )
  25 
  26     line = pygame.draw.line
  27     line( img, cor1, r.topleft, r.topright )
  28     line( img, cor1, r.topleft, r.bottomleft )
  29     line( img, cor2, r.bottomleft, r.bottomright )
  30     line( img, cor2, r.bottomright, r.topright )
  31 
  32     return img
  33 # desenha_quadrado()
  34 
  35 
  36 
  37 
  38 class Quadrado( Sprite ):
  39     grupos = None # Grupos ao qual este sprite pertence
  40                   # depois esta variavel de classe sera atribuida
  41                   # para lembrar dos objetos nao desenhados
  42     tamanho = ( 50, 50 )
  43     def __init__( self, pos=( 0, 0 ) ):
  44         Sprite.__init__( self, self.grupos )
  45         self.rect = Rect( pos, self.tamanho )
  46     # __init__()
  47 # Quadrado
  48 
  49 
  50 class Parede( Quadrado ):
  51     pass
  52 # Parede
  53 
  54 class Vazio( Quadrado ):
  55     pass
  56 # Vazio
  57 
  58 class Caminho( Quadrado ):
  59     pass
  60 # Caminho
  61 
  62 class Entrada( Quadrado ):
  63     pass
  64 # Entrada
  65 
  66 class Saida( Quadrado ):
  67     pass
  68 # Saida
  69 
  70 class CaminhoErrado( Caminho ):
  71     pass
  72 # CaminhoErrado
  73 
  74 class CaminhoCerto( Caminho ):
  75     pass
  76 # CaminhoCerto
  77 
  78 class CaminhoPercorrido( Caminho ):
  79     pass
  80 # CaminhoPercorrido
  81 
  82 
  83 CHR_CAMINHO = "."
  84 CHR_PAREDE = "#"
  85 CHR_ENTRADA = "E"
  86 CHR_SAIDA = "S"
  87 CHR_CAMINHO_ERRADO = "!"
  88 CHR_CAMINHO_PERCORRIDO = "-"
  89 CHR_CAMINHO_CERTO = "@"
  90 CHR_VAZIO = " "
  91 
  92 class Labirinto( object ):
  93     tipos_mapa = {
  94         CHR_CAMINHO: Caminho,
  95         CHR_PAREDE: Parede,
  96         CHR_ENTRADA: Entrada,
  97         CHR_SAIDA: Saida,
  98         CHR_CAMINHO_ERRADO: CaminhoErrado,
  99         CHR_CAMINHO_PERCORRIDO: CaminhoPercorrido,
 100         CHR_CAMINHO_CERTO: CaminhoCerto,
 101         CHR_VAZIO: Vazio,
 102         }
 103 
 104     def __init__( self, tela, descricao_mapa=None ):
 105         self.tela     = tela
 106         self.entrada  = None
 107         self.saida    = None
 108         self.tamanho  = None
 109         self.mapa     = None
 110         self.tam_peca = None
 111 
 112         # grupo que contem objetos nao desenhados
 113         self.nao_desenhados = RenderUpdates()
 114 
 115         if descricao_mapa:
 116             self.monta_labirinto( descricao_mapa )
 117     # __init__()
 118 
 119 
 120     def monta_labirinto( self, descricao_mapa ):
 121             self.__le_mapa( descricao_mapa )
 122             self.__arruma_posicoes()
 123             self.__le_imagens()
 124     # monta_labirinto()
 125 
 126 
 127     def __le_imagens( self ):
 128         """Lê as imagens para cada tipo de peça.
 129 
 130         Usa-se variavel de classe para evitar que cada objeto tenha uma copia
 131         da mesma imagem, economizando memoria.
 132         """
 133         t = self.tam_peca
 134 
 135         if t is None:
 136             raise Exception( "Você deve usar __arruma_posicoes() primeiro!" )
 137         
 138         Quadrado.tamanho = t
 139 
 140         # Lê imagens:
 141         Parede.image            = desenha_quadrado( t, Color( "gray35" ) )
 142         Caminho.image           = desenha_quadrado( t, Color( "wheat" ) )
 143         Entrada.image           = desenha_quadrado( t, Color( "magenta" ) )
 144         Saida.image             = desenha_quadrado( t, Color( "green" ) )
 145         CaminhoCerto.image      = desenha_quadrado( t, Color( "cyan" ) )
 146         CaminhoErrado.image     = desenha_quadrado( t, Color( "red" ) )
 147         CaminhoPercorrido.image = desenha_quadrado( t, Color( "yellow" ) )
 148         Vazio.image             = pygame.Surface( t )
 149         Vazio.image.set_colorkey( Color( "black" ) )
 150         Vazio.image.fill( Color( "black" ) )
 151     # __le_imagens()
 152 
 153 
 154 
 155     def __le_mapa( self, descricao ):    
 156         mapa       = []
 157         max_x      = 0
 158         tipos_mapa = self.tipos_mapa
 159 
 160         # esvazia grupo de sprites nao desenhados
 161         self.nao_desenhados.empty()
 162         Quadrado.grupos = self.nao_desenhados
 163 
 164         for i, linha in enumerate( descricao.split( "\n" ) ):
 165             l = []
 166             for j, letra in enumerate( linha ):
 167                 tipo = tipos_mapa.get( letra, Vazio )
 168 
 169                 if   tipo == Entrada:
 170                     self.entrada = ( i, j )
 171                 elif tipo == Saida:
 172                     self.saida   = ( i, j )
 173                     
 174                 
 175                 l.append( tipo() )
 176                 max_x = max( max_x, j )
 177             mapa.append( l )
 178         max_x += 1
 179 
 180         self.mapa    = mapa
 181         self.tamanho = ( max_x, i )
 182     # __le_mapa()
 183 
 184 
 185     def __arruma_posicoes( self ):
 186         if self.mapa is None:
 187             raise Exception( "Você deve usar __le_mapa() primeiro!" )
 188 
 189         tw, th = self.tela.get_size()
 190         mw, mh = self.tamanho
 191         w = int( floor( float( tw ) / mw ) )
 192         h = int( floor( float( th ) / mh ) )
 193 
 194         ## Para ter aspecto quadrado das peças, descomente a linha abaixo
 195         # w = h = min( w, h )
 196 
 197         tamanho = ( w, h )
 198 
 199         for i, l in enumerate( self.mapa ):
 200             for j, c in enumerate( l ):
 201                 pos = ( j * w, i * h )
 202                 c.rect = Rect( pos, tamanho )
 203 
 204         for tipo in self.tipos_mapa.itervalues():
 205             tipo.tamanho = tamanho
 206         
 207         self.tam_peca = tamanho
 208     # __arruma_posicoes()
 209 
 210 
 211     def desenhe( self, tudo=False ):
 212         tela = self.tela
 213         nao_desenhados = self.nao_desenhados
 214         if tudo:
 215             for l in self.mapa:
 216                 for p in l:
 217                     tela.blit( p.image, p )
 218         else:
 219             nao_desenhados.draw( self.tela )
 220 
 221         nao_desenhados.empty()
 222     # desenhe()
 223 
 224 
 225     def resolve( self, callback=None ):
 226         """Resolve o labirinto.
 227 
 228         callback pode ser uma função que recebe o estágio do processo
 229         recursivo, são eles:
 230           0: entrou em um estagio da recursao
 231           1: passou da condicao base (continua recursao)
 232           2: termino da funcao (saiu da recursao)
 233         """
 234         mapa  = self.mapa
 235         w, h  = self.tamanho
 236 
 237         if not callback:
 238             callback = lambda x: x
 239 
 240         def resolve_recursivo( x, y ):
 241             callback( 0 )
 242 
 243             achou = False
 244             if 0 <= x < w and 0 <= y < h:
 245                 callback( 1 )
 246 
 247                 peca = mapa[ y ][ x ]
 248                 tipo_peca = type( peca )
 249 
 250                 if tipo_peca in ( Caminho, Entrada ):
 251                     pos = peca.rect.topleft
 252                     mapa[ y ][ x ] = CaminhoPercorrido( pos )
 253                     if resolve_recursivo( x + 1,     y ) or \
 254                        resolve_recursivo(     x, y - 1 ) or \
 255                        resolve_recursivo( x - 1,     y ) or \
 256                        resolve_recursivo(     x, y + 1 ):
 257                         mapa[ y ][ x ] = CaminhoCerto( pos )
 258                         achou = True
 259                     else:
 260                         mapa[ y ][ x ] = CaminhoErrado( pos )
 261                 elif tipo_peca == Saida:
 262                     achou = True
 263             # fim do if
 264             callback( 2 )
 265             return achou
 266         # resolve_recursivo()
 267 
 268         ex, ey = self.entrada
 269         # resolve a partir da entrada
 270         achou = resolve_recursivo( ex, ey )
 271         # marque a entrada
 272         pos = mapa[ ex ][ ey ].rect.topleft
 273         mapa[ ex ][ ey ] = Entrada( pos )
 274         return achou
 275     # resolve()
 276 # Labirinto
 277 
 278 
 279 
 280 class Jogo( object ):
 281     FPS = 24
 282     RESOLVE_PASSOS_POR_SEG = 0
 283 
 284     def __init__( self, mapa, tamanho=( 800, 600 ) ):
 285         self.clock = pygame.time.Clock()
 286         self.tela  = pygame.display.set_mode( tamanho )
 287         self.mapa  = mapa
 288         self.le_labirinto()
 289     # __init__()
 290 
 291 
 292     def le_labirinto( self ):
 293         self.labirinto = Labirinto( self.tela, self.mapa )
 294     # le_labirinto()
 295 
 296 
 297     def termine( self ):
 298         raise StopIteration
 299     # termine()
 300 
 301 
 302     def atualize( self, tudo=False ):
 303         if tudo:
 304             pygame.display.flip()
 305         else:
 306             pygame.display.update() # XXXXXX usar lista de retangulos!
 307     # atualize()
 308 
 309 
 310     def trata_eventos( self ):
 311         for e in pygame.event.get( [ KEYDOWN, QUIT, ACTIVEEVENT ] ):
 312             if   e.type == QUIT:
 313                 self.termine()
 314 
 315             elif e.type == KEYDOWN:
 316                 if   e.key == K_F2:
 317                     self.le_labirinto()
 318 
 319                 elif e.key == K_F3:
 320                     def callback( estagio ):
 321                         self.trata_eventos()
 322                         if   estagio == 0:
 323                             self.labirinto.desenhe()
 324                             self.atualize()
 325                         elif estagio == 1:
 326                             self.clock.tick( self.RESOLVE_PASSOS_POR_SEG )
 327                         elif estagio == 2:
 328                             self.labirinto.desenhe()
 329                             self.atualize()
 330                     # callback()
 331                     self.labirinto.resolve( callback )
 332                     self.labirinto.desenhe()
 333                     self.atualize()
 334 
 335                 elif e.key == K_ESCAPE:
 336                     self.termine()
 337 
 338             elif e.type == ACTIVEEVENT:
 339                 self.labirinto.desenhe( True )
 340                 self.atualize( True )
 341     # trata_eventos()
 342 
 343 
 344     def rode( self ):
 345         try:
 346             # ActiveEvent faz desenhar a tela de novo
 347             pygame.event.post( pygame.event.Event( ACTIVEEVENT ) )
 348             while True:
 349                 self.clock.tick( self.FPS )
 350                 self.trata_eventos()
 351                 #self.labirinto.desenhe()
 352                 self.atualize()
 353         except StopIteration:
 354             return
 355     # rode()
 356 # Jogo
 357 
 358 
 359 if __name__ == "__main__":
 360     def uso():
 361         print "Uso:\n\t%s [arquivo.mapa]\n\n" % sys.argv[ 0 ]
 362         print "Caracteres que compoe um mapa:"
 363         for k, v in globals().iteritems():
 364             if k.startswith( "CHR_" ):
 365                 legenda = k[ 4: ].replace( "_", " " ).capitalize()
 366                 print "   '%s'   %s" % ( v, legenda )
 367         print
 368     # uso()
 369 
 370     if len( sys.argv ) < 2:
 371         mapa = """\
 372 ############## ####################
 373 #E.#.S#..#...###.....#.#..........#
 374 #..#.............###.#............#
 375 ##...##...######## #...#..........# 
 376 ##############     ################
 377 """
 378     else:
 379         if sys.argv[ 1 ] in ( "-h", "-help", "--help" ):
 380             uso()
 381             raise SystemExit
 382         else:
 383             f = open( sys.argv[ 1 ] )
 384             mapa = f.read()
 385             f.close()
 386     
 387     pygame.init()
 388     jogo = Jogo( mapa )
 389     jogo.rode()

Screenshot

resolvedorlabirinto-grafico.jpg

Versão com AStar

   1 #!/usr/bin/env python
   2 # -*- coding: utf-8 -*-
   3 # -*- mode: python -*-
   4 
   5 import sys
   6 import pygame
   7 from pygame.locals import *
   8 from pygame.sprite import Sprite, RenderUpdates
   9 from math import floor
  10 
  11 
  12 
  13 def desenha_quadrado( tamanho, cor ):
  14     img = pygame.Surface( tamanho )
  15 
  16     cinza = Color( "#808080" )
  17     cor1 = pygame.color.add( cor, cinza )
  18     cor2 = pygame.color.subtract( cor, cinza )
  19 
  20     r = Rect( ( 0, 0 ), tamanho )
  21     r.inflate_ip( -2, -2 )
  22     r.topleft = ( 1, 1 )
  23 
  24     img.fill( cor )
  25 
  26     line = pygame.draw.line
  27     line( img, cor1, r.topleft, r.topright )
  28     line( img, cor1, r.topleft, r.bottomleft )
  29     line( img, cor2, r.bottomleft, r.bottomright )
  30     line( img, cor2, r.bottomright, r.topright )
  31 
  32     return img
  33 # desenha_quadrado()
  34 
  35 
  36 
  37 
  38 class Quadrado( Sprite ):
  39     grupos = None # Grupos ao qual este sprite pertence
  40                   # depois esta variavel de classe sera atribuida
  41                   # para lembrar dos objetos nao desenhados
  42     tamanho = ( 50, 50 )
  43     def __init__( self, pos=( 0, 0 ) ):
  44         Sprite.__init__( self, self.grupos )
  45         self.rect = Rect( pos, self.tamanho )
  46     # __init__()
  47 # Quadrado
  48 
  49 
  50 class Parede( Quadrado ):
  51     pass
  52 # Parede
  53 
  54 class Vazio( Quadrado ):
  55     pass
  56 # Vazio
  57 
  58 class Caminho( Quadrado ):
  59     pass
  60 # Caminho
  61 
  62 class Entrada( Quadrado ):
  63     pass
  64 # Entrada
  65 
  66 class Saida( Quadrado ):
  67     pass
  68 # Saida
  69 
  70 class CaminhoErrado( Caminho ):
  71     pass
  72 # CaminhoErrado
  73 
  74 class CaminhoCerto( Caminho ):
  75     pass
  76 # CaminhoCerto
  77 
  78 class CaminhoPercorrido( Caminho ):
  79     pass
  80 # CaminhoPercorrido
  81 
  82 
  83 CHR_CAMINHO = "."
  84 CHR_PAREDE = "#"
  85 CHR_ENTRADA = "E"
  86 CHR_SAIDA = "S"
  87 CHR_CAMINHO_ERRADO = "!"
  88 CHR_CAMINHO_PERCORRIDO = "-"
  89 CHR_CAMINHO_CERTO = "@"
  90 CHR_VAZIO = " "
  91 
  92 class Labirinto( object ):
  93     tipos_mapa = {
  94         CHR_CAMINHO: Caminho,
  95         CHR_PAREDE: Parede,
  96         CHR_ENTRADA: Entrada,
  97         CHR_SAIDA: Saida,
  98         CHR_CAMINHO_ERRADO: CaminhoErrado,
  99         CHR_CAMINHO_PERCORRIDO: CaminhoPercorrido,
 100         CHR_CAMINHO_CERTO: CaminhoCerto,
 101         CHR_VAZIO: Vazio,
 102         }
 103 
 104     def __init__( self, tela, descricao_mapa=None ):
 105         self.tela     = tela
 106         self.entrada  = None
 107         self.saida    = None
 108         self.tamanho  = None
 109         self.mapa     = None
 110         self.tam_peca = None
 111 
 112         # grupo que contem objetos nao desenhados
 113         self.nao_desenhados = RenderUpdates()
 114 
 115         if descricao_mapa:
 116             self.monta_labirinto( descricao_mapa )
 117     # __init__()
 118 
 119 
 120     def monta_labirinto( self, descricao_mapa ):
 121             self.__le_mapa( descricao_mapa )
 122             self.__arruma_posicoes()
 123             self.__le_imagens()
 124     # monta_labirinto()
 125 
 126 
 127     def __le_imagens( self ):
 128         """Lê as imagens para cada tipo de peça.
 129 
 130         Usa-se variavel de classe para evitar que cada objeto tenha uma copia
 131         da mesma imagem, economizando memoria.
 132         """
 133         t = self.tam_peca
 134 
 135         if t is None:
 136             raise Exception( "Você deve usar __arruma_posicoes() primeiro!" )
 137 
 138         Quadrado.tamanho = t
 139 
 140         # Lê imagens:
 141         Parede.image            = desenha_quadrado( t, Color( "gray35" ) )
 142         Caminho.image           = desenha_quadrado( t, Color( "wheat" ) )
 143         Entrada.image           = desenha_quadrado( t, Color( "magenta" ) )
 144         Saida.image             = desenha_quadrado( t, Color( "green" ) )
 145         CaminhoCerto.image      = desenha_quadrado( t, Color( "cyan" ) )
 146         CaminhoErrado.image     = desenha_quadrado( t, Color( "red" ) )
 147         CaminhoPercorrido.image = desenha_quadrado( t, Color( "yellow" ) )
 148         Vazio.image             = pygame.Surface( t )
 149         Vazio.image.set_colorkey( Color( "black" ) )
 150         Vazio.image.fill( Color( "black" ) )
 151     # __le_imagens()
 152 
 153 
 154 
 155     def __le_mapa( self, descricao ):
 156         mapa       = []
 157         max_x      = 0
 158         tipos_mapa = self.tipos_mapa
 159 
 160         # esvazia grupo de sprites nao desenhados
 161         self.nao_desenhados.empty()
 162         Quadrado.grupos = self.nao_desenhados
 163 
 164         for i, linha in enumerate( descricao.split( "\n" ) ):
 165             l = []
 166             for j, letra in enumerate( linha ):
 167                 tipo = tipos_mapa.get( letra, Vazio )
 168 
 169                 if   tipo == Entrada:
 170                     self.entrada = ( i, j )
 171                 elif tipo == Saida:
 172                     self.saida   = ( i, j )
 173 
 174 
 175                 l.append( tipo() )
 176                 max_x = max( max_x, j )
 177             mapa.append( l )
 178         max_x += 1
 179 
 180         self.mapa    = mapa
 181         self.tamanho = ( max_x, i )
 182     # __le_mapa()
 183 
 184 
 185     def __arruma_posicoes( self ):
 186         if self.mapa is None:
 187             raise Exception( "Você deve usar __le_mapa() primeiro!" )
 188 
 189         tw, th = self.tela.get_size()
 190         mw, mh = self.tamanho
 191         w = int( floor( float( tw ) / mw ) )
 192         h = int( floor( float( th ) / mh ) )
 193 
 194         ## Para ter aspecto quadrado das peças, descomente a linha abaixo
 195         # w = h = min( w, h )
 196 
 197         tamanho = ( w, h )
 198 
 199         for i, l in enumerate( self.mapa ):
 200             for j, c in enumerate( l ):
 201                 pos = ( j * w, i * h )
 202                 c.rect = Rect( pos, tamanho )
 203 
 204         for tipo in self.tipos_mapa.itervalues():
 205             tipo.tamanho = tamanho
 206 
 207         self.tam_peca = tamanho
 208     # __arruma_posicoes()
 209 
 210 
 211     def desenhe( self, tudo=False ):
 212         tela = self.tela
 213         nao_desenhados = self.nao_desenhados
 214         if tudo:
 215             for l in self.mapa:
 216                 for p in l:
 217                     tela.blit( p.image, p )
 218         else:
 219             nao_desenhados.draw( self.tela )
 220 
 221         nao_desenhados.empty()
 222     # desenhe()
 223 
 224 
 225     def resolve( self, callback=None ):
 226         """Resolve o labirinto.
 227 
 228         callback pode ser uma função que recebe o estágio do processo
 229         recursivo, são eles:
 230           0: entrou em um estagio da recursao
 231           1: passou da condicao base (continua recursao)
 232           2: termino da funcao (saiu da recursao)
 233         """
 234         mapa  = self.mapa
 235         w, h  = self.tamanho
 236 
 237         if not callback:
 238             callback = lambda x: x
 239 
 240         def resolve_recursivo( x, y ):
 241             callback( 0 )
 242 
 243             achou = False
 244             if 0 <= x < w and 0 <= y < h:
 245                 callback( 1 )
 246 
 247                 peca = mapa[ y ][ x ]
 248                 tipo_peca = type( peca )
 249 
 250                 if tipo_peca in ( Caminho, Entrada ):
 251                     pos = peca.rect.topleft
 252                     mapa[ y ][ x ] = CaminhoPercorrido( pos )
 253                     if resolve_recursivo( x + 1,     y ) or \
 254                        resolve_recursivo(     x, y - 1 ) or \
 255                        resolve_recursivo( x - 1,     y ) or \
 256                        resolve_recursivo(     x, y + 1 ):
 257                         mapa[ y ][ x ] = CaminhoCerto( pos )
 258                         achou = True
 259                     else:
 260                         mapa[ y ][ x ] = CaminhoErrado( pos )
 261                 elif tipo_peca == Saida:
 262                     achou = True
 263             # fim do if
 264             callback( 2 )
 265             return achou
 266         # resolve_recursivo()
 267 
 268         ex, ey = self.entrada
 269         # resolve a partir da entrada
 270         achou = resolve_recursivo( ex, ey )
 271         # marque a entrada
 272         pos = mapa[ ex ][ ey ].rect.topleft
 273         mapa[ ex ][ ey ] = Entrada( pos )
 274         return achou
 275     # resolve()
 276 # Labirinto
 277 
 278 
 279 
 280 class Jogo( object ):
 281     FPS = 24
 282     RESOLVE_PASSOS_POR_SEG = 0
 283 
 284     def __init__( self, mapa, tamanho=( 800, 600 ) ):
 285         self.clock = pygame.time.Clock()
 286         self.tela  = pygame.display.set_mode( tamanho )
 287         self.mapa  = mapa
 288         self.le_labirinto()
 289     # __init__()
 290 
 291 
 292     def le_labirinto( self ):
 293         #self.labirinto = Labirinto( self.tela, self.mapa )
 294         self.labirinto = AStar( self.tela, self.mapa )
 295     # le_labirinto()
 296 
 297 
 298     def termine( self ):
 299         raise StopIteration
 300     # termine()
 301 
 302 
 303     def atualize( self, tudo=False ):
 304         if tudo:
 305             pygame.display.flip()
 306         else:
 307             pygame.display.update() # XXXXXX usar lista de retangulos!
 308     # atualize()
 309 
 310 
 311     def trata_eventos( self ):
 312         for e in pygame.event.get( [ KEYDOWN, QUIT, ACTIVEEVENT ] ):
 313             if   e.type == QUIT:
 314                 self.termine()
 315 
 316             elif e.type == KEYDOWN:
 317                 if   e.key == K_F2:
 318                     self.le_labirinto()
 319 
 320                 elif e.key == K_F3:
 321                     def callback( estagio ):
 322                         self.trata_eventos()
 323                         if   estagio == 0:
 324                             self.labirinto.desenhe(True)
 325                             self.atualize()
 326                         elif estagio == 1:
 327                             self.clock.tick( self.RESOLVE_PASSOS_POR_SEG )
 328                         elif estagio == 2:
 329                             self.labirinto.desenhe(True)
 330                             self.atualize()
 331                     # callback()
 332                     self.labirinto.resolve( callback )
 333                     self.labirinto.desenhe(True)
 334                     self.atualize()
 335 
 336                 elif e.key == K_ESCAPE:
 337                     self.termine()
 338 
 339             elif e.type == ACTIVEEVENT:
 340                 self.labirinto.desenhe( True )
 341                 self.atualize( True )
 342     # trata_eventos()
 343 
 344 
 345     def rode( self ):
 346         try:
 347             # ActiveEvent faz desenhar a tela de novo
 348             pygame.event.post( pygame.event.Event( ACTIVEEVENT ) )
 349             while True:
 350                 self.clock.tick( self.FPS )
 351                 self.trata_eventos()
 352                 #self.labirinto.desenhe()
 353                 self.atualize()
 354         except StopIteration:
 355             return
 356     # rode()
 357 # Jogo
 358 
 359 
 360 from heapq import heappush, heappop
 361 
 362 # representação de cada nó do AStar
 363 class No(object):
 364     def __init__(self, pos=None, pai=None, g=0, h=0):
 365         self.pos = pos
 366         self.pai = pai
 367         self.g = g
 368         self.h = h
 369 
 370     def __eq__(self, other):
 371         return self.pos == other.pos
 372 
 373     def __ne__(self, other):
 374         return self.pos != other.pos
 375 
 376     def __le__(self, other):
 377         return self.g+self.h <= other.g+other.h
 378 
 379     def __ge__(self, other):
 380         return self.g+self.h >= other.g+other.h
 381 
 382     def __str__(self):
 383         return 'pos = %s, g = %d, h = %d' % (self.pos, self.g, self.h)
 384 
 385 
 386 class AStar(Labirinto):
 387 
 388     """ Algoritmo AStar.
 389 
 390     mapa deve ser um vetor de strings ou uma matriz de caracteres de
 391     tamanho NxM.
 392     """
 393     def __init__(self, tela, mapa):
 394         Labirinto.__init__(self, tela, mapa)
 395         # listas do algoritmo AStar
 396         mapa = mapa.split('\n')
 397         self.n = len(mapa)    #linhas
 398         self.m = len(mapa[0]) #colunas
 399 
 400         # procurar pela entrada e saída
 401         entrada = None
 402         saida = None
 403         print mapa
 404         for i, linha in enumerate(mapa):
 405             for j, char in enumerate(linha):
 406                 if char == 'E':
 407                     entrada = [i, j]
 408                 elif char == 'S':
 409                     saida = [i, j]
 410         self.entrada = entrada
 411         self.saida = saida
 412         
 413     # ajuda a calcular a distância
 414     def dist(self, orig, dest):
 415         return abs(orig[0] - dest[0]) + abs(orig[1] - dest[1])
 416 
 417     # retorna os vizinhos de um nó no mapa, caso possa caminhar por eles
 418     def vizinhos(self, no):
 419         mapa = self.mapa
 420         n, m = self.n, self.m
 421         pos = no.pos
 422         res = []
 423         listaPos = [(-1,0), (1,0), (0,-1), (0,1)]
 424         for p in listaPos:
 425             x, y = pos[0] + p[0], pos[1] + p[1]
 426             if 0 <= x < m and  0 <= y < n:
 427                 if type(mapa[x][y]) in (Caminho, CaminhoPercorrido, Saida):
 428                     novo = No([x, y], no, no.g+1, self.dist([x, y], self.saida))
 429                     res.append(novo)
 430         return res
 431 
 432 
 433     def resolve(self, callback):
 434         aberta = []
 435         fechada = [] 
 436 
 437         entrada = self.entrada
 438         saida = self.saida
 439         mapa = self.mapa
 440         
 441         at = No()
 442         at.h = self.dist(entrada, saida)
 443         at.pos = entrada[:]
 444         at.pai = None
 445         heappush(aberta, at)
 446         achou = False
 447         callback(0)
 448         qSaida = mapa[saida[0]][saida[1]]
 449         qEntrada = mapa[entrada[0]][entrada[1]]
 450         while len(aberta) > 0:
 451             at = heappop(aberta)
 452             fechada.append(at)
 453             if at.pos == saida: # achou
 454                 achou = True
 455                 break
 456             viz = self.vizinhos(at)
 457             for no in viz:
 458                 if not no in fechada:
 459                     if not no in aberta:
 460                         heappush(aberta, no)
 461                         topleft = mapa[no.pos[0]][no.pos[1]].rect.topleft
 462                         mapa[no.pos[0]][no.pos[1]] = CaminhoPercorrido(topleft)
 463                         callback(1)
 464         mapa[saida[0]][saida[1]] = qSaida
 465         # reconstrução do caminho
 466         if achou:
 467             caminho = [at.pos]
 468             while True:
 469                 at = at.pai
 470                 if at is None:
 471                     break
 472                 caminho.insert(0, at.pos)
 473                 topleft = mapa[at.pos[0]][at.pos[1]].rect.topleft
 474                 mapa[at.pos[0]][at.pos[1]] = CaminhoCerto(topleft)
 475                 callback(1)
 476 #            print caminho
 477             mapa[entrada[0]][entrada[1]] = qEntrada
 478             callback(2)
 479         else:
 480             print 'Caminho não encontrado'
 481 
 482 
 483 
 484 if __name__ == "__main__":
 485     def uso():
 486         print "Uso:\n\t%s [arquivo.mapa]\n\n" % sys.argv[ 0 ]
 487         print "Caracteres que compoe um mapa:"
 488         for k, v in globals().iteritems():
 489             if k.startswith( "CHR_" ):
 490                 legenda = k[ 4: ].replace( "_", " " ).capitalize()
 491                 print "   '%s'   %s" % ( v, legenda )
 492         print
 493     # uso()
 494 
 495     if len( sys.argv ) < 2:
 496         mapa = """\
 497 ############## ####################
 498 #E.#..#..#...###.....#.#..........#
 499 #................###.#............#
 500 #................###.#............#
 501 #................###.#............#
 502 #................###.#............#
 503 #................###.#............#
 504 #................###.#............#
 505 ##..S##...######## #...#..........# 
 506 ##############     ################
 507 """
 508     else:
 509         if sys.argv[ 1 ] in ( "-h", "-help", "--help" ):
 510             uso()
 511             raise SystemExit
 512         else:
 513             f = open( sys.argv[ 1 ] )
 514             mapa = f.read()
 515             f.close()
 516 
 517     pygame.init()
 518     jogo = Jogo( mapa )
 519     jogo.rode()

Atualizei o resolvedor para usar o AStar. Dá pra ver como o AStar é bom agora.... João Paulo Farias