A* no Godot com AStarGrid2D: Pathfinding para Jogos em Grid

Se o seu jogo se move em células (tático por turnos, roguelike, tower defense, qualquer coisa com tabuleiro), implementar A* no Godot não exige escrever o algoritmo na mão. O Godot 4 traz a classe AStarGrid2D pronta: você diz o tamanho da grade, marca o que é parede, e ela devolve o caminho célula por célula. Sem heap, sem lista aberta, sem reinventar nada.

Esse tutorial monta o fluxo completo que eu uso: criar a grade, conectar com um TileMapLayer, dar custo diferente pra cada terreno (lama custa mais que estrada), escolher como tratar diagonais e mover um personagem pelo caminho. Todo código é GDScript do Godot 4.x e roda como está.

Quando usar AStarGrid2D (e quando não)

O Godot tem três jeitos de fazer pathfinding, e escolher o errado gera retrabalho:

AStarGrid2D: pra movimento em grade. O mapa é uma matriz de células, o personagem anda de célula em célula. É o caso de jogo tático, puzzle, roguelike, tower defense. É a opção mais simples e mais rápida pra esse formato, porque a vizinhança entre células já é implícita: você não cadastra conexões, só marca o que é sólido.

AStar2D/AStar3D: pra grafos arbitrários. Você cadastra cada ponto e cada conexão na mão. Útil quando o mapa não é uma grade (waypoints espalhados, rotas de patrulha, mapa de mundo com estradas). Se o seu mapa é grade, usar AStar2D é trabalho extra pra chegar no mesmo lugar.

NavigationAgent + NavigationRegion: pra movimento livre e contínuo, sem células. Inimigo que persegue o player em qualquer direção, NPC desviando de obstáculo em tempo real. É outro problema, com outro custo.

Regra prática: o personagem ocupa uma célula e se move pra célula vizinha? AStarGrid2D. Move livre pelo espaço? Navegação. O resto é exceção.

Setup do A* no Godot: a grade mínima

O ciclo de vida da AStarGrid2D tem três passos: configurar, chamar update(), usar. O update() é obrigatório depois de mexer em region, cell_size ou offset; sem ele a grade não existe internamente e qualquer consulta falha.

var astar := AStarGrid2D.new()

func _ready():
    # A região da grade em células: começa em (0,0), 16 de largura, 9 de altura.
    astar.region = Rect2i(0, 0, 16, 9)
    # Tamanho de cada célula em pixels (usado pra converter célula -> posição).
    astar.cell_size = Vector2(64, 64)
    astar.update()

    # Marca uma parede.
    astar.set_point_solid(Vector2i(5, 3))

    # Caminho em coordenadas de célula:
    print(astar.get_id_path(Vector2i(0, 0), Vector2i(10, 5)))
    # Caminho em posições no mundo (multiplica pela cell_size):
    print(astar.get_point_path(Vector2i(0, 0), Vector2i(10, 5)))

Os dois métodos de consulta resolvem o mesmo caminho, mudando só a unidade da resposta. get_id_path() devolve um array de Vector2i com coordenadas de célula, que é o que você quer em jogo por turnos. get_point_path() devolve um PackedVector2Array com posições em pixels, prático quando o personagem vai deslizar pelo caminho.

Duas armadilhas que pegam todo mundo na primeira vez:

• Consultar célula fora da região quebra com erro. Antes de pedir caminho pra onde o jogador clicou, valide com astar.is_in_boundsv(celula).
• Origem ou destino sólido devolve caminho vazio. Clicou na parede? get_id_path() retorna array vazio. Trate esse caso em vez de assumir que sempre vem caminho.

Conectando a grade com um TileMapLayer

Mapa de verdade não é hardcoded: ele vem do TileMap. A ideia é gerar a grade a partir do que já está pintado no editor, usando uma camada de dados customizados do TileSet pra dizer o que é andável.

No TileSet, crie uma Custom Data Layer chamada andavel do tipo bool. Marque true nos tiles de chão e deixe false em parede, água, pedra. Com isso o level designer controla o pathfinding pintando tiles, sem tocar em código.

O script lê tudo no _ready():

@export var tile_map: TileMapLayer

var astar := AStarGrid2D.new()

func _ready():
    # A região e o tamanho de célula vêm do próprio TileMap.
    astar.region = tile_map.get_used_rect()
    astar.cell_size = Vector2(tile_map.tile_set.tile_size)
    astar.update()

    for celula in tile_map.get_used_cells():
        var dados := tile_map.get_cell_tile_data(celula)
        if dados == null or not dados.get_custom_data("andavel"):
            astar.set_point_solid(celula)

Repare que get_used_rect() pode não começar em (0,0). Se o mapa foi pintado a partir da célula (-8, -4), a região acompanha, e as consultas usam as mesmas coordenadas de célula do TileMap. É por isso que vale sempre converter posição de mundo pra célula com local_to_map() em vez de dividir por tamanho de tile na mão.

Pra fechar quadrados grandes de parede de uma vez (a borda do mapa, por exemplo), existe o atalho fill_solid_region():

astar.fill_solid_region(Rect2i(0, 0, 16, 1))  # linha inteira do topo

E quando o mapa muda em runtime (porta que abre, ponte que cai), basta atualizar o ponto:

astar.set_point_solid(celula_da_porta, false)  # abriu, virou andável

Não precisa chamar update() de novo pra isso. O update() só é necessário quando região, tamanho de célula ou offset mudam.

Custo de terreno: lama, estrada e weight scale

Aqui está o recurso que separa pathfinding básico de pathfinding de jogo tático. Nem toda célula andável custa igual: atravessar lama é mais lento que andar na estrada, e o caminho "mais curto" em células nem sempre é o melhor. O A* resolve isso com peso por célula.

# Custo padrão de cada célula é 1.0.
# Lama: custa o triplo. O A* só passa por ela se compensar muito.
astar.set_point_weight_scale(Vector2i(4, 3), 3.0)

Com peso 3.0, entrar naquela célula equivale a andar três células normais. O algoritmo continua achando o caminho de menor custo total, então ele contorna a lama quando o desvio é barato e atravessa quando o desvio sai mais caro. Você não programa essa decisão: ela emerge do custo.

O jeito limpo de alimentar isso é a mesma técnica do andavel: uma Custom Data Layer custo do tipo float no TileSet, com 1.0 no chão comum, 3.0 na lama, 0.5 na estrada. O loop de setup fica assim:

for celula in tile_map.get_used_cells():
    var dados := tile_map.get_cell_tile_data(celula)
    if dados == null or not dados.get_custom_data("andavel"):
        astar.set_point_solid(celula)
    else:
        astar.set_point_weight_scale(celula, dados.get_custom_data("custo"))

Um detalhe de design que aprendi testando: diferenças pequenas de peso (1.0 contra 1.2) quase não mudam os caminhos e o jogador não percebe. Pra terreno "sentir" diferente, use contrastes francos, tipo 1.0 contra 3.0. E estrada com custo abaixo de 1.0 é um truque ótimo pra fazer unidades preferirem rotas naturais sem nenhum script de comportamento.

Diagonais e heurísticas

Por padrão a AStarGrid2D permite movimento diagonal, e isso nem sempre é o que o jogo pede. A propriedade diagonal_mode tem quatro opções:

# Jogo tático clássico, só 4 direções:
astar.diagonal_mode = AStarGrid2D.DIAGONAL_MODE_NEVER

# Diagonal liberada sempre (padrão):
astar.diagonal_mode = AStarGrid2D.DIAGONAL_MODE_ALWAYS

# Diagonal só se não cortar quina de parede:
astar.diagonal_mode = AStarGrid2D.DIAGONAL_MODE_ONLY_IF_NO_OBSTACLES

O modo ONLY_IF_NO_OBSTACLES merece destaque: ele impede aquele visual estranho de personagem atravessando a quina de uma parede na diagonal. Em quase todo jogo com diagonal eu uso esse em vez do ALWAYS. Existe ainda o DIAGONAL_MODE_AT_LEAST_ONE_WALKABLE, um meio-termo que exige só um dos lados livre.

A heurística (a estimativa de distância que guia a busca) também é configurável via default_compute_heuristic e default_estimate_heuristic. A regra é casar com o movimento: HEURISTIC_MANHATTAN pra grade sem diagonal, HEURISTIC_OCTILE pra grade com diagonal (é o padrão e funciona bem), HEURISTIC_EUCLIDEAN quando o resultado vai virar movimento contínuo. Se você não tem motivo pra mexer, o padrão serve.

Última propriedade dessa família: jumping_enabled = true ativa uma otimização (Jump Point Search) que acelera bastante a busca em mapas grandes e abertos. O porém é direto: ela ignora os pesos de célula. Se o seu jogo usa custo de terreno, deixe desligada. É um ou outro.

Movendo o personagem pelo caminho

Caminho calculado é só um array. O movimento de tabuleiro clássico (anda uma célula, para, anda a próxima) fica limpo com tween:

extends Node2D

@export var tile_map: TileMapLayer

var astar := AStarGrid2D.new()
var caminho: Array[Vector2i] = []
var movendo := false

func _unhandled_input(event):
    if event is InputEventMouseButton and event.pressed \
            and event.button_index == MOUSE_BUTTON_LEFT:
        var clique := tile_map.to_local(get_global_mouse_position())
        var destino := tile_map.local_to_map(clique)
        var origem := tile_map.local_to_map(tile_map.to_local(global_position))

        if not astar.is_in_boundsv(destino) or astar.is_point_solid(destino):
            return

        caminho = astar.get_id_path(origem, destino)
        if not caminho.is_empty():
            caminho.pop_front()  # a primeira célula é onde já estamos

func _process(_delta):
    if movendo or caminho.is_empty():
        return
    movendo = true
    var proxima: Vector2i = caminho.pop_front()
    # map_to_local devolve o centro da célula, em coordenadas do TileMap.
    var alvo := tile_map.to_global(tile_map.map_to_local(proxima))
    var tween := create_tween()
    tween.tween_property(self, "global_position", alvo, 0.15)
    tween.finished.connect(func(): movendo = false)

Dois pontos valem atenção. Primeiro, o caminho inclui a célula de origem, por isso o pop_front() logo depois de calcular. Segundo, map_to_local() devolve o centro do tile, então o personagem para alinhado sem nenhuma conta extra de offset.

Pra movimento deslizante em vez de passo a passo, troque a fila de células por get_point_path() e siga os pontos com velocidade constante num CharacterBody2D. A estrutura é a mesma, muda só a interpolação.

Performance e recálculo

A boa notícia: pra mapa de jogo típico (algumas dezenas por algumas dezenas de células), o custo de um get_id_path() é desprezível e você pode recalcular sempre que o destino muda sem pensar duas vezes.

O que evitar é recalcular sem motivo. Recalcular caminho de vinte inimigos todo frame é desperdício clássico: o caminho só muda quando o mapa muda ou o alvo muda de célula. Guarde a célula do alvo no último cálculo e só refaça quando ela for outra. Em jogo por turnos, então, o recálculo acontece uma vez por ação e performance simplesmente não é assunto.

Pra mapa gigante e aberto sem custo de terreno, jumping_enabled resolve. Pra mapa gigante com custo de terreno, o caminho costuma ser reduzir a frequência de recálculo e espalhar os pedidos entre frames, não otimizar o A* em si.

Fechando

O fluxo inteiro cabe numa frase: região e célula vêm do TileMap, andavel e custo vêm de Custom Data do TileSet, set_point_solid() e set_point_weight_scale() montam a grade, get_id_path() devolve o caminho e um tween anda por ele. Nenhuma etapa exige entender a matemática do A*, mas todas ficam melhores quando você entende o que peso e heurística significam.

Se quiser fixar, monte um tabuleiro pequeno com três terrenos (chão, lama, estrada) e clique pra mover. Depois mude os pesos e veja o caminho se redesenhar sozinho. Ver o algoritmo trocar de rota porque a lama ficou cara é o momento em que isso deixa de ser API decorada e vira ferramenta sua.