What happens when I switch from Manhattan to Euclidean or Chebyshev distance?

Each heuristic changes how h(n) estimates distance to the goal, which reshapes the search frontier. Manhattan distance (horizontal plus vertical steps) is exact for 4-directional movement; Euclidean distance (straight-line hypotenuse) suits diagonal movement; Chebyshev distance (the larger of the horizontal and vertical differences) suits boards where diagonal steps cost the same as orthogonal ones. Picking a heuristic that undershoots the true distance keeps A-star optimal but can expand more nodes; overshooting speeds up the search but can produce a longer path.

Why does painting a Weight tile change the route instead of just slowing it down?

A Weight tile costs 5 to enter rather than 1, so it raises g(n) for any path that crosses it. Because A-star and Dijkstra always minimise total cost, they will happily take a longer route around a cluster of weighted cells if that route is cheaper overall. Greedy Best-First, which ignores g entirely, is the only mode that can walk straight through expensive terrain.

What does the frontier colouring actually track under the hood?

Blue cells are in the open set, discovered but not yet expanded, and are stored in a binary min-heap keyed on f, with ties broken by the lower h value. Dark blue cells are closed, meaning their neighbours have already been examined and their g score is final. Yellow marks the single node popped from the heap on the current step.

Why does Generate maze make Greedy Best-First perform so much worse?

The maze generator carves a perfect maze with exactly one route between any two cells using a randomised recursive backtracker, so there are no shortcuts for a heuristic to exploit. Greedy Best-First keeps rushing toward whichever open cell looks closest to the goal in a straight line, frequently charging down dead-end corridors, whereas A-star and Dijkstra methodically retreat and try the only other option.

Is the diagonal-move cost handled correctly?

Yes, when Allow diagonal moves is ticked, diagonal steps cost the square root of two instead of 1, matching their true Euclidean length, and the simulator blocks diagonal moves that would cut through the corner of two adjacent walls. The heuristic also switches to an octile-distance formula in this mode so it remains admissible for 8-directional movement.

Início▸Algoritmos e IA▸Busca A*

🗺️ Busca A*

Veja o A* encontrar o caminho mais curto em uma grade com f(n)=g(n)+h(n). Pinte paredes, arraste início e destino, troque a heurística e compare A*, Dijkstra e busca gulosa.

Algoritmos e IA3DModerado60 FPS

Sobre a Busca A*

O A* (pronunciado "A-estrela") é um algoritmo de busca em grafos do tipo "melhor primeiro" que encontra o caminho mais curto entre dois pontos combinando o custo-até-agora garantidamente ótimo de Dijkstra (g) com uma estimativa heurística da distância restante (h), dando a cada nó uma pontuação de prioridade f = g + h. Desenvolvido por Hart, Nilsson e Raphael em 1968, ele sustenta desde a navegação de personagens em videogames e o planejamento de movimento de robôs até o cálculo de rotas do Google Maps. Quando a heurística é admissível — ou seja, nunca superestima o custo real — o A* garante encontrar o caminho ótimo.

Esta simulação permite escolher entre A*, Dijkstra (h = 0) e Greedy Best-First (g = 0) em uma grade onde você pode pintar paredes e terrenos com peso (custo ×5), arrastar os nós de início e destino, selecionar uma heurística (Manhattan, Euclidiana ou Chebyshev), alternar movimentos diagonais e observar os nós se expandirem passo a passo. Estatísticas ao vivo mostram nós expandidos, comprimento do caminho e custo total.

Perguntas Frequentes

O que significa f = g + h?

No A*, cada nó no conjunto aberto recebe uma pontuação f(n) = g(n) + h(n), onde g(n) é o custo exato do caminho mais barato encontrado até agora do início ao nó n, e h(n) é a estimativa heurística do custo de n até o destino. O algoritmo sempre expande o nó com o menor f, garantindo que, se h for admissível, o caminho será ótimo na primeira vez que o destino for expandido.

O que é uma heurística admissível?

Uma heurística h é admissível se nunca superestimar o custo real para alcançar o destino — formalmente, h(n) ≤ h*(n) para todo n. A distância de Manhattan (soma dos passos horizontais e verticais) é admissível em uma grade conectada em 4 direções; a distância Euclidiana é admissível para qualquer grade. Uma heurística inadmissível pode tornar o A* mais rápido, mas pode retornar um caminho subótimo.

Como o A* difere do algoritmo de Dijkstra?

O algoritmo de Dijkstra define h = 0, então expande os nós em ordem de seu custo exato a partir do início, irradiando igualmente em todas as direções. O A* soma a heurística para guiar a busca em direção ao destino, tipicamente expandindo muito menos nós. Em uma grade aberta sem obstáculos, o A* com distância de Manhattan pode reduzir as expansões de nós em 50–90% em comparação com Dijkstra.

Por que a busca Greedy Best-First é mais rápida, mas não ótima?

O Greedy Best-First define g = 0 e usa apenas h para classificar os nós, correndo sempre em direção ao nó que parece mais próximo do destino. Isso é muito rápido em ambientes abertos, mas ignora o custo real do caminho, podendo ser atraído por terrenos caros ou desvios que resultam em uma rota mais longa. No pior caso, encontra um caminho arbitrariamente pior que o ótimo.

Quando devo usar distância de Manhattan, Euclidiana ou Chebyshev?

Use a distância de Manhattan quando o movimento estiver restrito a 4 direções (cima, baixo, esquerda, direita), pois ela conta exatamente o número mínimo de passos. A distância Euclidiana é apropriada quando movimentos diagonais são permitidos e o custo diagonal é igual a √2. A distância de Chebyshev (máximo entre |Δx| e |Δy|) é a escolha certa quando todas as 8 direções custam o mesmo, como é comum em muitos jogos de estratégia.

O que são células com peso e como afetam a busca de caminho?

Células com peso representam terrenos mais difíceis de atravessar — lama, água rasa ou uma estrada acidentada. Nesta simulação, uma célula com peso custa 5 em vez de 1 para ser cruzada, então o A* frequentemente desviará de várias células com peso em vez de atravessá-las. Dijkstra e A* tratam os pesos corretamente; o Greedy Best-First ignora custos e pode atravessar terrenos caros diretamente.

Qual é a complexidade de tempo do A*?

No pior caso, o A* tem complexidade de tempo e espaço O(b^d), onde b é o fator de ramificação e d é a profundidade da solução ótima. Com uma heurística consistente (que satisfaz a desigualdade triangular), cada nó é expandido no máximo uma vez, dando O(V log V) em um grafo finito com V vértices — o mesmo limite assintótico de Dijkstra usando um heap binário.

Como a geração de labirinto afeta a busca?

O gerador de labirintos cria um labirinto perfeito usando um algoritmo aleatorizado que talha passagens em uma grade, garantindo exatamente um caminho entre quaisquer duas células. Labirintos são particularmente exigentes para algoritmos de busca porque os corredores estreitos eliminam a vantagem heurística do A* — com apenas um caminho válido, todos os algoritmos precisam explorar aproximadamente os mesmos nós.

O que representam as cores na grade?

Verde marca o nó de início, vermelho o destino. Células azuis formam a fronteira atual (conjunto aberto), azul escuro marca nós visitados (fechados), e amarelo destaca o nó sendo expandido. Células com peso aparecem em marrom. Uma vez encontrado um caminho, ele é traçado em verde-limão do início ao destino, e você pode ler o custo exato no painel de estatísticas.

O A* pode ser usado em 3D ou em grafos que não são grades?

Sim — o A* funciona em qualquer grafo onde os custos das arestas são não negativos e você pode fornecer uma heurística admissível. Aplicações reais incluem planejamento de movimento de braços robóticos 3D (grafos de espaço de configuração), roteamento de rede (latência como custo) e análise de linguagem natural (treliças estilo Viterbi). A grade aqui é apenas a representação visualmente mais intuitiva do algoritmo geral.

Qual é o significado do contador "nós expandidos"?

Nós expandidos conta quantas vezes o algoritmo retirou um nó da fronteira e processou seus vizinhos — esta é a principal medida de eficiência do A*. Um valor menor significa que a heurística está guiando bem a busca. Em uma grade de 30×30 (900 células), uma boa heurística pode frequentemente encontrar o caminho ótimo expandindo menos de 100 nós, enquanto Dijkstra pode expandir cada célula alcançável.

Sobre esta simulação

Este simulador visualiza o algoritmo de busca A* encontrando o caminho mais curto em uma grade com pesos. Cada nó na fronteira carrega uma pontuação f(n) = g(n) + h(n), onde g é a distância exata percorrida desde o início e h é uma estimativa heurística da distância restante até o destino; o algoritmo sempre expande primeiro o nó de menor f. Alternar o menu do algoritmo para Dijkstra zera h, enquanto Greedy Best-First descarta g por completo, permitindo ver o mesmo labirinto resolvido de três formas diferentes, nó a nó.

🔬 O que mostra

A grade colorida acompanha a busca ao vivo: células azuis estão na fronteira aberta, células azul escuro foram totalmente expandidas (fechadas), e amarelo marca o nó sendo processado naquele instante. Ao alcançar o destino, a rota vencedora é traçada em verde-limão, e a barra lateral informa quantos nós foram expandidos e o custo total do caminho.

🎮 Como usar

Escolha o Algoritmo e a Heurística nos menus, depois use os botões da ferramenta de pintura para adicionar Paredes, terreno com Peso (custo ×5), ou arraste os marcadores Mover início/Mover destino pelo tabuleiro. Permitir movimentos diagonais alterna entre movimento de 4 e 8 direções, Mostrar valores g/h/f sobrepõe as pontuações brutas em cada célula, e Executar automaticamente, Passo, Gerar labirinto, Limpar paredes e Reiniciar controlam a reprodução e o layout do tabuleiro.

💡 Você sabia?

O A* foi publicado em 1968 por Peter Hart, Nils Nilsson e Bertram Raphael, e apesar de ter mais de meio século, ainda é a escolha padrão de busca de caminho na maioria dos videogames, pilhas de robótica e planejadores de rota, pois nunca explora mais nós do que o necessário quando recebe uma heurística admissível.

Perguntas frequentes

O que acontece quando mudo de distância de Manhattan para Euclidiana ou Chebyshev?

Cada heurística muda como h(n) estima a distância até o destino, remodelando a fronteira de busca. A distância de Manhattan (passos horizontais mais verticais) é exata para movimento de 4 direções; a distância Euclidiana (hipotenusa em linha reta) é adequada para movimento diagonal; a distância de Chebyshev (a maior entre as diferenças horizontal e vertical) é adequada para tabuleiros onde passos diagonais custam o mesmo que ortogonais. Escolher uma heurística que subestime a distância real mantém o A* ótimo, mas pode expandir mais nós; superestimar acelera a busca, mas pode produzir um caminho mais longo.

Por que pintar um bloco de Peso muda a rota em vez de apenas deixá-la mais lenta?

Um bloco de Peso custa 5 para entrar em vez de 1, então aumenta g(n) para qualquer caminho que o atravesse. Como A* e Dijkstra sempre minimizam o custo total, eles felizmente farão uma rota mais longa ao redor de um grupo de células com peso se essa rota for mais barata no total — o Greedy Best-First, que ignora g completamente, é o único modo que pode atravessar terrenos caros em linha reta.

O que a coloração da fronteira realmente rastreia por trás dos panos?

Células azuis estão no conjunto aberto — descobertas mas ainda não expandidas — e são armazenadas em um heap mínimo binário indexado por f, com empates desfeitos pelo menor valor de h. Células azul escuro estão fechadas, significando que seus vizinhos já foram examinados e seu gScore é final. Amarelo marca o único nó retirado do heap no passo atual.

Por que Gerar labirinto faz o Greedy Best-First ter um desempenho tão pior?

O gerador de labirintos talha um labirinto perfeito com exatamente uma rota entre quaisquer duas células usando um backtracker recursivo aleatorizado, então não há atalhos para uma heurística explorar. O Greedy Best-First continua correndo em linha reta em direção à célula aberta que parece mais próxima do destino, frequentemente entrando em corredores sem saída, enquanto A* e Dijkstra recuam metodicamente e tentam a única outra opção.

O custo do movimento diagonal é tratado corretamente?

Sim — quando Permitir movimentos diagonais está marcado, passos diagonais custam √2 em vez de 1, correspondendo ao seu verdadeiro comprimento Euclidiano, e o simulador bloqueia movimentos diagonais que cortariam o canto de duas paredes adjacentes. A heurística também muda para uma fórmula de distância octil neste modo para permanecer admissível no movimento de 8 direções.

⚙ Por trás dos panos

Veja o A* encontrar o caminho mais curto em uma grade usando f = g + h. Pinte paredes, arraste início/destino, troque heurísticas e compare A* vs Dijkstra vs Greedy para ver como a heurística muda os nós expandidos.

Canvas 2DPathfindingA*Heuristic SearchDijkstra

3D · Renderizador Three.js / WebGL · meta de 60 FPS · roda totalmente no navegador, sem instalação