A* com Heap Binário

Este repositório contém uma explicação prática do Algoritmo A* (A-estrela) e de como combiná-lo com um heap binário para implementar de forma eficiente a fila de prioridade do conjunto aberto (open set).

Resumo

• O A* seleciona o próximo nó a expandir minimizando f(n) = g(n) + h(n), onde:
  • g(n) é o custo acumulado do início até n.
  • h(n) é a heurística (estimativa) do custo de n até o objetivo.
• Com heurística admissível e consistente, A* encontra o caminho ótimo.
• O heap binário oferece operações eficientes para a fila de prioridade:
  • Inserção: O(log N)
  • Extração do mínimo: O(log N)
• Na prática, usa-se lazy deletion para lidar com a ausência de decrease-key em heaps binários simples (como heapq do Python).

Conteúdo detalhado

Para uma explicação completa, incluindo código de exemplo em Python, boas práticas e alternativas ao heap binário, consulte o tutorial:

• TUTORIAL.md

Arquitetura do código (Python)

O aplicativo interativo está em main.py (Pygame). Principais componentes:

• compute_board_rect(...): calcula o retângulo centralizado do tabuleiro.
• create_grid(...): cria a matriz booleana de células (False = livre, True = obstáculo).
• pos_to_cell(...): converte posição em pixels para coordenadas de célula (row, col).
• nearest_free_cell(...): via BFS, encontra a célula livre mais próxima de uma origem.
• draw_board(...): desenha o tabuleiro, obstáculos e a grade.
• cell_center_px(...) e valid_cell(...): utilitários de coordenadas/validação.
• a_star_grid(...): implementação de A* sobre o grid 4-conexo usando heapq (heap binário).
• main(): loop do Pygame, trata eventos do mouse, replaneja caminho e anima o movimento do agente.

As funções agora possuem docstrings detalhadas em Português, facilitando o entendimento do fluxo.

Como o A* está implementado neste projeto

A função a_star_grid(grid, start, goal) utiliza:

• Heurística Manhattan: h(n) = |r_n - r_goal| + |c_n - c_goal|.
• Custo uniforme por passo (1 por movimento ortogonal).
• heapq como fila de prioridade (heap binário) com técnica de lazy deletion: quando um nó recebe um custo melhor, uma nova entrada é empilhada e as antigas são ignoradas no momento da extração se f estiver desatualizado.

No loop principal (main()), o agente:

• Converte sua posição atual para célula e, se bloqueada, usa nearest_free_cell(...).
• Planeja até a célula livre mais próxima do cursor do mouse.
• Replaneja quando o objetivo muda ou quando o grid é editado.
• Move-se suavemente entre os waypoints do caminho planejado em velocidade fixa.

Executando o tabuleiro (Python/Pygame)

Este projeto inclui um tabuleiro interativo feito em Python com Pygame. O tabuleiro ocupa 80% da janela, utiliza células de 32x32 pixels e permite desenhar/apagar passando o mouse com o botão esquerdo pressionado (toggle por célula).

Passos recomendados (Linux):

1. Crie e ative um ambiente virtual

python3 -m venv .venv
source .venv/bin/activate

2. Instale as dependências

pip install -r requirements.txt

3. Execute o aplicativo

python main.py

Controles:

• Botão esquerdo do mouse pressionado: alterna o estado das células ao passar por cima (marca/desmarca).
• Fechar janela para encerrar.

Referências rápidas

• Hart, Nilsson, Raphael (1968) — "A Formal Basis for the Heuristic Determination of Minimum Cost Paths".
• Russell & Norvig — "Artificial Intelligence: A Modern Approach".
• Implementações: heapq (Python), std::priority_queue (C++), PriorityQueue (Java).

Licença

Este trabalho está licenciado sob a licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional (CC BY-SA 4.0).

• Consulte o arquivo LICENSE.md para detalhes.
• Resumo (legível por humanos): https://creativecommons.org/licenses/by-sa/4.0/deed.pt_BR
• Texto legal completo: https://creativecommons.org/licenses/by-sa/4.0/legalcode

Ao reutilizar, por favor:

• Atribua crédito apropriado, incluindo link para este repositório e para a licença.
• Indique se foram feitas alterações.
• Distribua obras derivadas sob a mesma licença (CompartilhaIgual).