Conteúdo
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
- Execute o aplicativo. Pode passar um arquivo de mapa como argumento (--help para mais info).
- Pressione F3 para resolver o labirinto
- 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
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
