Conteúdo
Versão Educativa usando Recursão
Este código utiliza recursão para resolver um labirinto.
O mapa deve ser dado em formato texto, vide exemplo no fim do código.
A versão mais atual encontra-se em: http://www.gustavobarbieri.com.br/labirinto.py
Contribuição de GustavoBarbieri
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
Resolvendo com busca A*
Esta versão utiliza o algoritmo de busca A* (A-star_algorithm) e consegue obter um caminho mínimo no menor tempo possível.
Contribuição de João Paulo Farias:
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 '############## ################'])
Versão Recursiva (2)
Esta versão utiliza o mesmo princípio da versão educativa, a recursão, porém o código utiliza mais elementos Pythônicos e é muito mais enxuto.
A recursão se dá entre duas funções: step() e find_path().
Contribuição de RodrigoSenra
1 base_maze = """
2 #############
3 # # #
4 # ##### ### #
5 # # #
6 # ### # #####
7 # # ##
8 ### ###### ##
9 ### ## ##
10 # ### #### ##
11 # ### #### ##
12 # # # #
13 ### # # #####
14 # # S
15 #############"
16 """
17
18 NORTH = 0
19 EAST = 1
20 SOUTH = 2
21 WEST = 3
22 NO_WAY_OUT = 4
23
24 move = {
25 NORTH: lambda (x, y): (x, y-1),
26 EAST: lambda (x, y): (x+1, y),
27 SOUTH: lambda (x, y): (x, y+1),
28 WEST: lambda (x, y): (x-1, y)
29 }
30
31 def step(maze, pos):
32 """ Take a single (recursive) step"""
33 #show(curr_maze) # uncomment this to see step-by-step
34 px, py = pos
35 found = False
36 dir = NORTH
37 turn = 1
38 maze[px][py] = '.' # take a step
39 while not found and dir!=NO_WAY_OUT:
40 found = find_path(maze, pos = move[dir](pos))
41 dir += turn
42 if not found:
43 maze[px][py]=' '
44 return found
45
46 decide = {
47 'S': lambda m, p: True,
48 '#': lambda m, p: False,
49 '.': lambda m, p: False,
50 ' ': step
51 }
52
53 def find_path(maze, pos=(1,1)):
54 """ Decide where to go or to give it up."""
55 px, py = pos
56 if px<0 or px>len(maze[0]) or py<0 or py>len(maze):
57 print px, py, maze[0]
58 return 0
59 here = maze[px][py]
60 return decide[here](maze, pos)
61
62 def convert_maze(txt_maze):
63 """Convert multi-line text maze into list-of-list maze"""
64 list_maze = []
65 for line in txt_maze.split('\n')[1:-1]:
66 list_maze.append([i for i in line])
67 return list_maze
68
69 def show(maze):
70 """Pretty-print maze"""
71 print
72 for line in maze:
73 print ''.join(line)
74
75 if __name__=="__main__":
76 curr_maze = convert_maze(base_maze)
77 if find_path(curr_maze,pos=(8,1)):
78 show(curr_maze)
79 else:
80 print "Amazing, I'm lost!"
Versão Recursiva Enxuta (ou Mais Educativa!)
Gustavo Niemeyer utiliza o mesmo princípio da versão educativa, a recursão, e também da otimização que se A or B, B só será avaliado se A for falso para criar uma versão super enxuta, porém clara:
Contribuição de GustavoNiemeyer
1 maze = """\
2 #############
3 # # #
4 # ##### ### #
5 # # #
6 # ### # #####
7 # # ##
8 ### ###### ##
9 ### ## ##
10 # ### #### ##
11 # ### #### ##
12 # # # #
13 ### # # #####
14 # # S
15 #############
16 """
17
18 NONE, WALL, FNSH, SEEN, GOOD = " ", "#", "S", ".", "+"
19
20 def solve(maze, x, y):
21 found = False
22 if 0 <= x < len(maze[0]) and 0 <= y < len(maze):
23 if maze[y][x] == NONE:
24 maze[y][x] = SEEN
25 if (solve(maze, x+1, y) or solve(maze, x-1, y) or
26 solve(maze, x, y+1) or solve(maze, x, y-1)):
27 maze[y][x] = GOOD
28 found = True
29 elif maze[y][x] == FNSH:
30 found = True
31 return found
32
33 if __name__ == "__main__":
34 maze = [list(line) for line in maze.splitlines()]
35 solve(maze, 1, 8)
36 for line in maze:
37 print "".join(line)
Versão Gráfica
Visite ResolvedorLabirintoGrafico para uma versão em Python + PyGame que mostra passo a passo em modo gráfico o método recursivo de solução.
