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:
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.
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.
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 pyamazeOu, se estiver utilizando um Jupyter Notebook, execute na célula:
!pip install pyamazeApó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.
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.
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()
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:
Grid:
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()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).
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.
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()
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.
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.
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).
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()
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.
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.
É 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.
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.
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()
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()
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.
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()
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.
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()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()
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.
Para acessar outras publicações de Python, clique aqui!
Expert em conteúdos da Hashtag Treinamentos. Auxilia na criação de conteúdos de variados temas voltados para aqueles que acompanham nossos canais.
Quer sair do zero no Python e virar uma referência na sua empresa? Inscreva-se agora mesmo no Python Impressionador