Blog

Postado em em 12 de dezembro de 2023

Como Criar Labirintos com Python – Otimização de Rotas

Aprenda como criar labirintos com Python e a compreender o processo de otimização de rotas.

Caso prefira esse conteúdo no formato de vídeo-aula, assista ao vídeo abaixo ou acesse o nosso canal do YouTube!

Para receber por e-mail o(s) arquivo(s) utilizados na aula, preencha:

Como criar labirintos com Python

Na aula de hoje, vou te mostrar como criar labirintos com Python! Isso mesmo, veremos como é possível desenvolver labirintos utilizando Python, e nas próximas aulas, você compreenderá o processo de otimização de rota, utilizado nos aplicativos de mapas atualmente.

Basicamente, iremos criar um labirinto com o objetivo de alcançar o seu final. A partir desse processo, determinaremos a rota mais curta para atingir esse objetivo. Esse procedimento é semelhante ao que ocorre nos aplicativos de mapas e gps quando você escolhe um destino.

Antes de chegarmos ao objetivo final desta sequência de aulas, onde exploraremos a otimização de rotas, é fundamental que você compreenda a construção de caminhos com Python, o funcionamento da biblioteca pyamaze, e a personalização do labirinto.

Por que Construir Labirintos?

Pense nos mecanismos de mapas e GPS que temos hoje em dia, como o Waze e o Google Maps. Eles nos permitem visualizar a melhor rota entre o ponto A e o ponto B dentro do mapa. Existem alguns algoritmos que permitem realizar eficientemente esse tipo de navegação.

Criar um labirinto e utilizá-lo para simular essa lógica e esses algoritmos permitirá que você desenvolva códigos e soluções eficientes, semelhantes às encontradas nesses serviços, utilizando Python.

Instalando a Biblioteca Pyamaze no Python

Para construir nosso labirinto com Python, vamos utilizar a biblioteca Pyamaze. Para instalá-la, basta executar o seguinte comando no terminal do seu editor de códigos:

pip install pyamaze

Ou, se estiver utilizando um Jupyter Notebook, execute na célula:

!pip install pyamaze

Como Criar Labirintos com Python – Pyamaze

Após a instalação, podemos importar a classe maze da biblioteca para o nosso código e criar uma instância dessa classe armazenada na variável labirinto.

Com isso, já podemos utilizar o método CreateMaze para efetivamente criar o labirinto, e labirinto.run() para executar e visualizar o labirinto.

from pyamaze import maze

labirinto = maze()

labirinto.CreateMaze()

Por padrão, não precisamos passar nenhum argumento para que ele crie esse labirinto padrão.

Labirinto padrão

O labirinto gerado é um “labirinto perfeito” ou “perfect maze“. Em um labirinto perfeito, não existem áreas isoladas ou fechadas por quatro paredes, garantindo que, a partir de qualquer ponto inicial, é possível alcançar o ponto final. Sempre haverá um caminho.

Além disso, o labirinto criado por padrão tem o tamanho de 10 por 10, ou seja, possui dez linhas e dez colunas, cada uma do tamanho de uma célula.

Informações do Labirinto

Por padrão, o final do labirinto será sempre a primeira célula (o quadrado verde), e o início do labirinto será sempre a última célula, a célula do canto inferior direito. Assim, a primeira célula será a linha 1, coluna 1, e o ponto final será, neste labirinto padrão, a linha 10, coluna 10.

Essas informações podem ser visualizadas imprimindo o labirinto.grid.

from pyamaze import maze

labirinto = maze()
labirinto.CreateMaze()

print(labirinto.grid)

labirinto.run()
Grid

O labirinto.grid é uma lista de tuplas, onde cada tupla indica as coordenadas das células do labirinto, no formato (linha, coluna). Por exemplo, (1, 1) representa a primeira célula na linha 1, coluna 1.

Por padrão, o método da classe maze cria um labirinto quadrado. No entanto, podemos definir o tamanho do labirinto, passando como argumentos o número de linhas seguido do número de colunas.

from pyamaze import maze

labirinto = maze(10, 5)

labirinto.CreateMaze()

print(labirinto.grid)

labirinto.run()

Labirinto:

labirinto personalizado

Grid:

Grid novo

O grid exibe todas as células presentes no labirinto, e podemos armazená-las na variável celulas.

from pyamaze import maze

labirinto = maze(10, 5)
labirinto.CreateMaze()

celulas = labirinto.grid

labirinto.run()

Mapa do Labirinto

Outra informação que podemos obter a respeito do nosso labirinto é o mapa correspondente a ele. Para isso, podemos armazenar o atributo maze_map na variável mapa e visualizá-lo com um print.

from pyamaze import maze

labirinto = maze(10, 5)
labirinto.CreateMaze()

mapa = labirinto.maze_map
print(mapa)

labirinto.run()

O resultado será um dicionário em que cada chave representa uma das células do labirinto, e o valor é outro dicionário com as direções norte (N), sul (S), leste (E) e oeste (W).

Mapa

O número 1 indica a presença de um caminho aberto naquela direção, enquanto o número 0 indica a presença de uma parede. Por exemplo, em {‘E’: 1, ‘W’: 0, ‘N’: 0, ‘S’: 0}, temos um caminho livre na direção leste e paredes nas outras direções.

Caminho do Labirinto – Caminho Perfeito

Por fim, temos a funcionalidade do caminho perfeito (path). Essa funcionalidade revela o caminho ideal que deve ser percorrido para ir do ponto inicial (podendo ser qualquer célula) até o ponto final (célula (1, 1)).

from pyamaze import maze

labirinto = maze(10, 5)
labirinto.CreateMaze()

caminho = labirinto.path
print(caminho)

labirinto.run()
caminho perfeito

Como resposta temos um dicionário em que a chave representa a célula inicial, e o valor é a célula para a qual você deve se deslocar a partir dessa.

Nesse exemplo, se estiver na célula (2, 1), precisamos seguir para a célula (2, 2). Depois de (2, 2), vamos para (1, 2) e assim por diante.

Como vamos usar essas informações

Todas essas informações serão úteis para a construção do nosso algoritmo que determinará a melhor rota entre os pontos A e B dentro do labirinto.

Após o desenvolvimento do algoritmo, podemos sempre verificar se está correto por meio do caminho perfeito, que pode ser armazenado na variável caminho utilizando o labirinto.path.

Personalizações do Labirinto

Vimos como construir um labirinto padrão e determinar o número de linhas e colunas. No entanto, além disso, é possível fazer outras personalizações por meio do método CreateMaze.

Podemos passar para esse método a posição final do labirinto, ou seja, a célula que queremos alcançar.

from pyamaze import maze

labirinto = maze(10, 10)
labirinto.CreateMaze(5, 5)

labirinto.run()

Aqui, estamos criando um labirinto de 10 por 10, onde o ponto final deve ser a célula (5, 5).

Mudando a célula final

Outra personalização possível é utilizando o parâmetro loopPercent. O valor padrão desse parâmetro é 0, o que significa que existe uma única solução partindo de qualquer célula, e todas elas podem chegar ao destino.

Se aumentarmos o valor desse parâmetro (que varia de 0 a 100), mais caminhos possíveis serão abertos até a célula final.

from pyamaze import maze

labirinto = maze(10, 10)
labirinto.CreateMaze(loopPercent=50)

labirinto.run()
loopPercent=50

Observe como há menos paredes agora e mais possibilidades de caminhos a partir das células. Quanto maior o valor, mais caminhos possíveis até o destino existirão; quanto menor, menos caminhos existirão. Por padrão, ele inicia em 0.

Salvando e Carregando um Labirinto

Um dos parâmetros mais importantes a serem utilizados é o saveMaze=True. Isso não apenas gera o labirinto, mas também o salva em um arquivo CSV para que você possa carregá-lo posteriormente.

from pyamaze import maze

labirinto = maze(10, 10)
labirinto.CreateMaze(saveMaze=True)

labirinto.run()

Dentro desse arquivo CSV, teremos as posições das células e das paredes, criando o mapa do nosso labirinto.

CSV do labirinto

É possível até mesmo editar manualmente o labirinto dentro desse arquivo e salvá-lo novamente.

Com o labirinto salvo, para carregá-lo, basta passar o nome do arquivo para o parâmetro loadMaze.

from pyamaze import maze

labirinto = maze()
labirinto.CreateMaze(loadMaze="maze--2023-12-11--22-36-43.csv")

labirinto.run()

Caso o labirinto esteja em outra pasta, você precisará fornecer o caminho completo para o arquivo. No entanto, se estiver na mesma pasta que o seu código, basta passar o nome.

Como estamos carregando um labirinto que já foi criado, não precisamos mais definir o tamanho dele dentro de maze(), pois ele será carregado com o tamanho que foi salvo.

Agentes no Labirinto

Com nosso labirinto carregado, vamos agora explorar a lógica dos agentes no labirinto.

Os agentes são objetos que você cria dentro do seu labirinto para que possam percorrê-lo de um ponto inicial até o destino. Os agentes funcionam como “pessoas” andando pelo labirinto.

Para isso, vamos importar a classe agent e criar o nosso agente, passando para ele o labirinto criado.

from pyamaze import maze, agent

labirinto = maze()
labirinto.CreateMaze(loadMaze="maze--2023-12-11--22-36-43.csv")

agente = agent(labirinto)

labirinto.run()

Assim, teremos um quadrado azul sendo exibido na célula inicial do labirinto, representando o nosso agente.

Agente

Por padrão, o agente sempre começará na célula inicial do labirinto, mas é possível determinar o ponto de início passando as coordenadas da célula desejada.

from pyamaze import maze, agent

labirinto = maze()
labirinto.CreateMaze(loadMaze="maze--2023-12-11--22-36-43.csv")

agente = agent(labirinto, 7, 10)

labirinto.run()
Mudando a posição do agente

Outras configurações que podemos passar para o agente incluem o parâmetro filled=True, que exibirá o agente não como um quadrado azul no centro da célula, mas como um quadrado do tamanho da célula toda.

E o parâmetro footprints=True, interessante porque quando o agente se movimentar pelo labirinto, ele deixará “pegadas”, ou seja, será possível visualizar o caminho percorrido.

Por exemplo, todo agente tem sua posição determinada pelo atributo position, sendo uma tupla com as coordenadas da célula. Podemos alterar a posição desse agente atribuindo novos valores.

from pyamaze import maze, agent

labirinto = maze()
labirinto.CreateMaze(loadMaze="maze--2023-12-11--22-36-43.csv")

agente = agent(labirinto, footprints=True)
agente.position = (10, 9)
posicao = agente.position
print(posicao)

labirinto.run()
footprint

Repare que nosso agente está na célula (10, 9), e na célula (10, 10) onde ele iniciou seu caminho, ficou uma marquinha em azul mais vibrante. Essa é a “footprint” (pegada) que ele deixou.

Caminho do Agente no Labirinto

Observe que, se fossemos determinar linha a linha a posição do nosso agente para que ele pudesse “andar” pelo nosso labirinto, o código ficaria com muitas linhas e mal otimizado.

Outro ponto importante é que, ao definir o caminho de um agente pelo labirinto, ele ignorará as paredes. Portanto, precisamos verificar no gabarito se o caminho desejado é possível, ou então ele passará pela parede.

Uma forma de determinar o caminho que o agente irá percorrer é criar um dicionário em que a chave é a posição inicial e o valor é a posição para a qual você deseja que ele vá. Esse caminho deve ser feito célula a célula.

Com o caminho definido, você pode traçá-lo com o método tracePath(), que recebe um dicionário contendo seu agente como chave e o caminho que ele irá percorrer como valor.

from pyamaze import maze, agent

labirinto = maze()
labirinto.CreateMaze(loadMaze="maze--2023-12-11--22-36-43.csv")

agente = agent(labirinto, footprints=True)
caminho = {(10, 10): (9, 10), (9, 10): (8, 10), (8, 10): (8, 9)}
labirinto.tracePath({agente: caminho})

labirinto.run()
Agente andando 1

Se você quiser visualizar a animação do agente se movendo pelo seu labirinto, pode passar um parâmetro adicional para o tracePath(), que é o delay.

Por padrão, o delay é 300, e quanto maior você passar, mais tempo o agente levará para se mover. Por exemplo, se passarmos o delay=600, ele levará o dobro do tempo para se mover e será possível acompanhar a animação.

labirinto.tracePath({agente: caminho}, delay=600)

Podemos passar para o tracePath() o caminho perfeito que havíamos visto anteriormente com o labirinto.path. Dessa forma, o agente irá do ponto inicial até o final, seguindo o caminho perfeito.

Agente percorrendo o caminho perfeito

Por fim, uma última forma de determinarmos o caminho que esse agente deve percorrer é através de uma sequência de texto, em que informamos as direções que ele deve percorrer a partir da célula em que se encontra.

Essa direção deve ser passada com as siglas em inglês N (norte), S (sul), E (leste), W (oeste).

from pyamaze import maze, agent

labirinto = maze()
labirinto.CreateMaze(loadMaze="maze--2023-12-11--22-36-43.csv")

agente = agent(labirinto, footprints=True)
caminho = "NNWSWW"
labirinto.tracePath({agente: caminho})

labirinto.run()

Textos no Labirinto

Uma última modificação que podemos fazer no nosso labirinto é adicionar textos a ele.

Podemos importar a classe textLabel e adicionar um rótulo de texto ao labirinto que irá exibir o número de passos do caminho que definimos anteriormente. O valor exibido será equivalente ao comprimento da sequência que nosso agente percorreu.

from pyamaze import maze, agent, textLabel

labirinto = maze()
labirinto.CreateMaze(loadMaze="maze--2023-12-11--22-36-43.csv")

agente = agent(labirinto, footprints=True)
caminho = "NNWSWW"
labirinto.tracePath({agente: caminho})
texto = textLabel(labirinto, title="Nº passos", value=len(caminho))

labirinto.run()
Rótulo

Conclusão – Como Criar Labirintos com Python

Nessa aula, você aprendeu como criar labirintos com Python utilizando a biblioteca pyamaze. Exploramos a personalização, salvamento e carregamento dos labirintos, além de como definir um agente para interagir, percorrendo-o e registrando os passos dados.

Com esse conhecimento, na próxima aula, iremos aprender a desenvolver um algoritmo em Python que determinará a melhor rota possível. Essa funcionalidade é comumente encontrada nos aplicativos de mapas e GPS hoje em dia.

Hashtag Treinamentos

Para acessar outras publicações de Python, clique aqui!


Quer aprender mais sobre Python com um minicurso básico gratuito?