Esse código gera um labirinto aleatoriamente usando o método "busca em profundidade" e em seguida o desenha na tela usando ASCII art. Um exemplo de saída seria:
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | |
+ + +--+--+--+--+--+ + + + + + + + +--+
| | | | | | | | | | | |
+ + + + + + +--+ +--+ + + +--+--+--+ +
| | | | | | | | | |
+ +--+--+--+ +--+ +--+ +--+ +--+--+--+ + +
| | | | | | | | |
+ +--+ +--+ + + + +--+ + + +--+--+--+ +
| | | | | | | | | | |
+--+--+--+ + + +--+--+ + + + + + +--+--+
| | | | | | | | |
+ + +--+--+--+--+--+--+--+ + +--+ +--+--+ +
| | | | | | | | | |
+ +--+ + +--+ +--+ + + +--+--+--+ + + +
| | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Para entender o código, vamos dividi-lo em duas partes: a geração do labirinto e seu desenho na tela.
Desenho
Vou começar com o desenho. Aqui está o mesmo código, só que sem as funções de geração:
# Define a função para criar o labirinto. Parâmetros:
# w - largura do labirinto (i.e. número de colunas); padrão: 16
# h = altura do labirinto (i.e. número de linhas); padrão: 8
def make_maze(w = 16, h = 8):
Em primeiro lugar ele cria duas listas, hor
e ver
, uma para desenhar as linhas do labirinto (i.e. as paredes horizontais) e a outra para desenhar as colunas (as paredes verticais).
ver = [["| "] * w + ['|'] for _ in range(h)] + [[]]
Essa linha vai produzir algo como | | | | | | |
(na largura certa)
hor = [["+--"] * w + ['+'] for _ in range(h + 1)]
E essa linha vai produzir algo como +--+--+--+--+--+--+--+--+
(idem)
for (a, b) in zip(hor, ver):
print(''.join(a + ['\n'] + b))
Combinando as duas, o resultado é algo do tipo:
+--+--+--+-...-+---+
| | | | ... | |
O que, repetido várias vezes, vai produzir a saída final:
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Compreensões de lista
Ok, mas como as linhas são criadas? Para entender isso, vamos analisar a compreensão de lista que criou cada uma delas. Vou começar com o hor
que é mais simples:
hor = [["+--"] * w + ['+'] for _ in range(h + 1)]
Aqui uma lista está sendo criada, e atribuída à variável hor
:
hor = [ ]
Essa lista herá h+1
elementos:
for _ in range(h + 1)
E cada elemento será a string "+--"
repetida w
vezes:
["+--"] * w
Seguida da string +
:
+ ['+']
Ou seja, no fim das contas hor
é uma lista com esse formato:
hor = [
["+--","+--","+--","+--",...,"+--","+"],
["+--","+--","+--","+--",...,"+--","+"],
["+--","+--","+--","+--",...,"+--","+"],
...
["+--","+--","+--","+--",...,"+--","+"]
]
É fácil perceber que cada linha é um +--+--+--+--+
. E como existem h+1
linhas, a primeira estará "no topo" do labirinto, a última "embaixo", e as demais entre uma célula e outra.
A definição de ver
é semelhante:
ver = [["| "] * w + ['|'] for _ in range(h)] + [[]]
A primeira parte é uma compreensão de lista muito parecida com hor
:
[["| "] * w + ['|'] for _ in range(h)]
A diferença é que ela só tem h
linhas, e não h+1
como hor
. Para tornar ambas as listas do mesmo tamanho, um elemento adicional é concatenado a ela:
+ [[]]
No final, ver
será uma lista com esse formato:
ver = [
["| ","| ","| ","| ",...,"| ","|"],
["| ","| ","| ","| ",...,"| ","|"],
["| ","| ","| ","| ",...,"| ","|"],
...
["| ","| ","| ","| ",...,"| ","|"],
[]
]
zip
Agora que temos uma lista para imprimir as linhas e as colunas, precisamos intercalá-las para que o desenho se pareça com um grid. A ideia é imprimir uma linha de hor
, depois uma de ver
, uma de hor
, uma de ver
, etc, até que o grid inteiro tenha sido desenhado.
for (a, b) in zip(hor, ver):
O que a função zip
faz é parear cada elemento de hor
com um elemento de ver
; é como se você estivesse fazendo um for a in hor
e um for b in ver
ao mesmo tempo (atenção: isso é bem diferente de um for
dentro do outro). O número de vezes que esse for
vai executar é igual ao tamanho da menor lista. Como ambas têm o mesmo tamanho - h+1
- então esse é o número de vezes que o for
será executado.
print(''.join(a + ['\n'] + b))
Essa linha imprime um elemento de hor
, uma quebra de linha, e um elemento de ver
. Para entender isso, considere o seguinte:
a
é uma lista do tipo:
["+--","+--","+--","+--",...,"+--","+"]
a
+ ['\n']
vai simplesmente colocar uma quebra de linha no final de a
:
["+--","+--","+--","+--",...,"+--","+","\n"]
Isso + b
vai concatenar b
a essa lista. b
é um elemento de ver
, de modo que o resultado será:
["+--","+--",...,"+--","+","\n","| ","| ",...,"| ","|"]
''.join(lista)
vai criar uma string com cada elemento da lista, introduzindo um ''
entre um elemento e outro. O resultado nesse caso é equivalente a se concatenar cada uma das strings da lista:
"+--+--...+--+\n| | ...| |"
Ao imprimir essa string na tela usando o print
, o resultado será aquele padrão mencionado anteriormente:
+--+--+--+-...-+---+
| | | | ... | |
Que repetido uma vez para cada linha, resultará no grid completo (repare que na última linha não há | | | --- | |
sobrando; isso é porque o último elemento de ver
é vazio, como mostrado anteriormente).
Geração do labirinto
Se você executar somente as linhas explicadas acima (mais a chamada da função - make_maze()
- com ou sem parâmetros controlando a altura e largura) você verá um grid homogêneo. É como se você tivesse várias salinhas pequenas, sem ligação nenhuma entre elas. Como então transformar esse grid num labirinto?
O algoritmo de busca em profundidade funciona da seguinte forma: cada uma das salas começa marcada como "não visitada". Isso corresponde ao valor 0
atribuído a cada elemento da variável vis
:
vis = [[0] * w + [1] for _ in range(h)] + [[1] * (w + 1)]
Essa compreensão de lista é bastante semelhante àquelas já vistas anteriormente, de modo que não vou explicá-la com detalhes. Apenas perceba que o resultado final será da forma:
vis = [
[0,0,0,...,0,0,1],
[0,0,0,...,0,0,1],
[0,0,0,...,0,0,1],
...
[0,0,0,...,0,0,1],
[1,1,1,...,1,1,1]
]
Que é o mesmo que todas as células não visitadas, e as mesmas cercadas por uma linha e coluna onde tudo está visitado (os limites externos do labirinto). Normalmente se usaria uma linha inicial com tudo 1
e uma coluna inicial da mesma forma (para representar as paredes superior e esquerda), mas esse código está se aproveitando do fato que em Python:
lista[-1]
é equivalente a:
lista[len(lista)-1]
De modo que se você tentar acessar um elemento com índice -1
ele vai "dar a volta" e pegar o último elemento em vez disso. Ou seja, é como se o retângulo de zeros estivesse cercado por todos os lados com um retângulo de uns.
Em um labirinto ideal, só deve existir um único caminho entre quaisquer pares de células. Dessa forma, uma célula qualquer é escolhida como "origem" e se tenta chegar a todas as outras a partir dela:
# Serão usadas as funções "suffle" (embaralhar)
# e "randrange" (sortear número aleatório em um intervalo)
from random import shuffle, randrange
...
# Define uma função para visitar uma célula ainda não visitada
def walk(x, y):
...
# E usa-a para visitar uma célula aleatória em [0,0,w,h)
walk(randrange(w), randrange(h))
Recursão
A função walk
é uma função recursiva: após visitar uma célula ela tenta visitar todas as células adjacentes a ela, só retornando depois que elas também já tenham sido visitadas. Como isso é feito através de outras chamadas a walk
, basta chamá-la uma vez como mostrado anteriormente para garantir que o programa não pare até que o grid inteiro esteja visitado (i.e. a variável vis
contenha somente uns).
def walk(x, y):
Em primeiro lugar, a célula atual é marcada como "visitada" (pois nós estamos visitando ela nesse momento):
vis[y][x] = 1
Então são listadas todas as células adjacentes a ela. Isso corresponde às células de mesma coluna mas uma linha acima ou abaixo, ou mesma linha mas uma coluna à direita ou esquerda:
d = [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)]
Então essa lista é embaralhada, de modo que a ordem de visita seja aleatória:
shuffle(d)
Depois disso cada uma delas é visitada. Então se decide:
for (xx, yy) in d:
Se a célula já havia sido visitada antes, não faz mais nada:
if vis[yy][xx]: continue
Isso significa que ou essa célula está fora do labirinto (i.e. está além dos seus limites, aquela linha e coluna onde tudo é 1
) ou que já existe um caminho ligando ela à origem (mais sobre isso adiante).
Caso contrário, essa célula precisa ser adicionada ao labirinto. Isso é feito "quebrando a parede" que separa a célula atual (x,y
) da célula adjacente:
if xx == x: hor[max(y, yy)][x] = "+ "
Se ela está numa linha diferente, transforma o +--
em +
, abrindo um "buraco" na parede horizontal.
if yy == y: ver[y][max(x, xx)] = " "
Se ela está numa coluna diferente, transforma o |
em
, abrindo um buraco na parece vertical.
Em ambos os casos, o max
é usado para garantir que a célula afetada (seja ela hor
ou ver
) corresponda à fronteira entre uma célula e a outra:
- no caso de uma estar em cima e a outra embaixo, é a linha entre uma célula e a outra, que corresponde portanto à maior delas (já que a primeira linha é simplesmente o topo do labirinto);
- no caso das duas estarem lado a lado, é a maior coluna de sua linha, aquela que contém a parede divisória entre uma célula e outra (pois de novo, a primeira coluna é simplesmente a parede esquerda do labirinto).
Em seguida, visita essa célula que acabou de ser incorporada no labirinto:
walk(xx, yy)
O fato dela ser visitada antes de se visitar as outras células adjacentes é o que caracteriza uma "busca em profundidade" - em oposição a uma "busca em largura" (caso primeiro se visitasse todas as células adjacentes, depois fizesse a chamada recursiva em cada uma delas). A consequência disso é que o algoritmo vai "cavando um túnel" do ponto de origem até onde ele der conta, mas sempre se certificando que esse túnel não formará um ciclo (i.e. se a célula a ser escavada já faz parte do labirinto, não derrube a parede, deixe-a como está).
Código completo
O código completo, comentado de forma "sã" (nem demais e nem de menos) seria então:
from random import shuffle, randrange
def make_maze(w = 16, h = 8):
""" Cria um labirinto aleatório e o desenha na tela em ASCII Art
Parâmetros:
w - o número de colunas do labirinto (padrão: 16)
h - o número de linhas do labirinto (padrão: 8)
"""
# Matriz de células visitadas (0 = não visitada, 1 = visitada)
# Delimitada por uma linha/coluna com todos visitados (fronteira)
# Sofre overflow nos índices negativos
vis = [[0] * w + [1] for _ in range(h)] + [[1] * (w + 1)]
# Linhas contendo as células e linhas entre-células
# Inicia-se com todas as células disjuntas (paredes entre todas elas)
ver = [["| "] * w + ['|'] for _ in range(h)] + [[]]
hor = [["+--"] * w + ['+'] for _ in range(h + 1)]
def walk(x, y):
""" Visita uma célula e todas as suas células adjacentes,
em profundidade, unindo-as ao labirinto corrente.
"""
vis[y][x] = 1
d = [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)]
shuffle(d)
for (xx, yy) in d:
if vis[yy][xx]: continue
# Remove a parede entre células
if xx == x: hor[max(y, yy)][x] = "+ "
if yy == y: ver[y][max(x, xx)] = " "
walk(xx, yy)
# Visita a célula de origem
walk(randrange(w), randrange(h))
# Imprime o resultado na tela
for (a, b) in zip(hor, ver):
print(''.join(a + ['\n'] + b))
make_maze()