Busca de caminhos em um labirinto – BFS, DFS e A*

O que mostra

Um labirinto é modelado como uma grade de células; cada movimento leva a uma célula vizinha acima, abaixo, à esquerda ou à direita, e todos custam o mesmo. A busca em largura guarda as células em espera em uma fila: explora primeiro todas as células a um passo, depois a dois passos, e na primeira vez que chega à chegada já tem um caminho mais curto. A busca em profundidade usa uma pilha e segue uma direção até ficar presa, por isso seu caminho costuma ser mais longo. A* ordena as células por f = g + h, em que h é a distância Manhattan até a chegada.

Como usar

Escolha BFS, DFS ou A* e clique em Passo a passo para acompanhar as células numeradas em espera, ou em Executar para ver uma animação. Compare a tabela de resultados após cada execução. Use Desenhar paredes, Apagar paredes, Definir partida e Definir chegada para mudar a grade, ou escolha um Tipo de grade e clique em Nova grade.

Parâmetros que você pode mudar

• Algoritmo BFS – busca em largura, DFS – busca em profundidade, A* – guiada por uma estimativa de distância
• Tipo de grade Labirinto com ciclos, Obstáculos aleatórios, Grade vazia
• Número de colunas 11–41 células
• Paredes extras removidas (labirinto) 0–60 %
• Densidade de obstáculos 0–45 %
• Velocidade 1–100 passos/s

Perguntas para explorar

1. Por que o caminho encontrado pela BFS é sempre um dos mais curtos, enquanto o da DFS muitas vezes não é?
2. Em uma grade vazia, qual algoritmo explora menos células, e por quê?
3. Você consegue montar um labirinto em que a DFS chega ao destino explorando menos células que a BFS?