Annotated A* for Multi-Size Agents in Godot

The direct answer

To pathfind for several square unit sizes in Godot without building a separate grid for each size, run A* over anchor cells and pass agent_size with each query. Expand a neighbor only when its clearance value is at least that size:

func anchor_is_traversable(anchor: Vector2i, agent_size: int) -> bool:
    if agent_size <= 0 or not region.has_point(anchor):
        return false
    return clearance_at(anchor) >= agent_size

One map, one anchor path per query

That is the core of low-level Annotated A*. A 1x1, 2x2, and 3x3 unit can search the same clearance map because each query supplies its own required clearance.

Each returned cell is the unit's top-left anchor, not its complete footprint. If an anchor has clearance 3, square agents of size 1, 2, or 3 fit there. Size 4 does not.

Choose the smallest architecture that fits

Annotated A* is useful, but it is not the only honest solution.

Why choose query-aware search?

Choose Annotated A* because it makes size explicit query data, not because custom code is automatically faster. Runtime and memory still need measurement on your map and query mix.

What annotated means

A blocked/open map stores one bit of passability. An annotated map stores more information about each anchor. Here the annotation is clearance: the largest open square whose top-left cell is that anchor.

A 2x2 body is represented during search by one point moving between valid top-left anchors. The clearance predicate proves that the complete 2x2 footprint fits at each returned anchor.

Daniel Harabor's clearance tutorial describes the fuller form with both agent size and terrain capability. This implementation fixes one walkability capability. If a game has distinct ground, swimming, and amphibious profiles, it needs one suitable clearance layer per capability it actually uses, or an equivalent on-demand cache. It does not need every mathematical subset of terrain.

This article assumes the clearance map already exists. The maximal-square build and anchor convention are covered in multi-size agent pathfinding with clearance maps. Use the same anchor convention in both layers. A top-left clearance map paired with center-based search anchors tests the wrong cells near every wall. That scalar annotation answers square profiles; rectangular and circular agent clearance needs orientation-specific masks or geometry fields.

# The query-time passability rule.
clearance[anchor] >= agent_size

Validate start and goal before searching

Apply the same predicate to the query endpoints before opening the frontier.

If the goal has clearance 1 and the query needs 2, that is not a generic connectivity failure. Reject it immediately. Otherwise A* explores the reachable map only to report an empty path whose real cause was already known.

var start_clearance := clearance_at(start)
if start_clearance < agent_size:
    return _failure(
        "START_CLEARANCE_INSUFFICIENT",
        start,
        agent_size,
        start_clearance
    )

var goal_clearance := clearance_at(goal)
if goal_clearance < agent_size:
    return _failure(
        "GOAL_CLEARANCE_INSUFFICIENT",
        goal,
        agent_size,
        goal_clearance
    )

Use a binary min-heap for the frontier

Sorting the full open list after every expansion makes a compact tutorial, but it is the wrong implementation to publish as a reference. The verified source uses a binary min-heap, so push() and pop() are O(log n).

The heap below is copied from the verified annotated_astar.gd in the download. Later snippets isolate smaller decisions from the same implementation or show a clearly labelled Godot alternative.

class MinHeap:
    var _items: Array[Dictionary] = []

    func is_empty() -> bool:
        return _items.is_empty()

    func push(cell: Vector2i, g_cost: int, f_cost: int) -> void:
        _items.append({"cell": cell, "g": g_cost, "f": f_cost})
        _sift_up(_items.size() - 1)

    func pop() -> Dictionary:
        if _items.is_empty():
            return {}

        var first: Dictionary = _items[0]
        var last: Dictionary = _items.pop_back()
        if not _items.is_empty():
            _items[0] = last
            _sift_down(0)
        return first

    func _sift_up(index: int) -> void:
        var current := index
        while current > 0:
            var parent := (current - 1) / 2
            if not _before(_items[current], _items[parent]):
                break
            _swap(current, parent)
            current = parent

    func _sift_down(index: int) -> void:
        var current := index
        while true:
            var left := current * 2 + 1
            var right := left + 1
            var best := current

            if left < _items.size() and _before(_items[left], _items[best]):
                best = left
            if right < _items.size() and _before(_items[right], _items[best]):
                best = right
            if best == current:
                return

            _swap(current, best)
            current = best

    func _before(a: Dictionary, b: Dictionary) -> bool:
        var a_f := int(a["f"])
        var b_f := int(b["f"])
        if a_f != b_f:
            return a_f < b_f

        var a_h := a_f - int(a["g"])
        var b_h := b_f - int(b["g"])
        if a_h != b_h:
            return a_h < b_h

        var a_cell: Vector2i = a["cell"]
        var b_cell: Vector2i = b["cell"]
        if a_cell.y != b_cell.y:
            return a_cell.y < b_cell.y
        return a_cell.x < b_cell.x

    func _swap(a: int, b: int) -> void:
        var item: Dictionary = _items[a]
        _items[a] = _items[b]
        _items[b] = item

Deterministic ties are part of the contract

The tie-break is deliberate: lowest f, then lowest remaining heuristic h, then row and column. It is not required for A* optimality, but it makes equal-cost queries deterministic and therefore easier to test, replay, and compare.

The A* loop changes in one important place

The rest of the search is ordinary A*: pop the lowest estimated total cost, discard stale entries, close the current cell, relax its legal neighbors, and store a parent whenever the cost improves.

The Annotated A* change is the clearance gate before relaxation. This fragment includes the score, parent, and closed-buffer initialization used by the loop; the download contains the endpoint validation and result helpers around it.

var open := MinHeap.new()
var cell_count := region.size.x * region.size.y
var g_score := PackedInt32Array()
var parent := PackedInt32Array()
var closed := PackedByteArray()
g_score.resize(cell_count)
parent.resize(cell_count)
closed.resize(cell_count)
g_score.fill(2147483647)
parent.fill(-1)
closed.fill(0)

var start_index := _cell_index(start)
var goal_index := _cell_index(goal)
var minimum_cost := _minimum_open_step_cost()
g_score[start_index] = 0
open.push(start, 0, _heuristic(start, goal, minimum_cost))

while not open.is_empty():
    var entry := open.pop()
    var current: Vector2i = entry["cell"]
    var current_index := _cell_index(current)

    if int(entry["g"]) != g_score[current_index]:
        continue  # stale heap entry
    if closed[current_index] != 0:
        continue

    closed[current_index] = 1
    if current == goal:
        return {
            "ok": true,
            "code": "OK",
            "path": _rebuild_path(parent, start_index, goal_index),
            "total_cost": g_score[goal_index],
        }

    for direction in DIRS:
        var neighbor := current + direction
        var neighbor_index := _cell_index(neighbor)
        if neighbor_index < 0 or closed[neighbor_index] != 0:
            continue
        if not anchor_is_traversable(neighbor, agent_size):
            continue

        var tentative_g := g_score[current_index] + step_cost_at(neighbor)
        if tentative_g >= g_score[neighbor_index]:
            continue

        g_score[neighbor_index] = tentative_g
        parent[neighbor_index] = current_index
        open.push(
            neighbor,
            tentative_g,
            tentative_g + _heuristic(neighbor, goal, minimum_cost)
        )

The path contains anchors, not occupied cells

Suppose a 2x2 query returns (2, 3) → (3, 3) → (4, 3). Those are three anchor positions. At each position the unit occupies four cells. Clearance proves the complete destination footprint fits, but the movement layer still owns sprite placement, transition geometry, and reservations.

That distinction prevents two separate bugs: drawing the sprite at the top-left cell center instead of the footprint center, and reserving only the anchor while another unit claims one of the covered cells.

The execution-side contract is in how to move multi-tile units on a grid in Godot. Planning returns legal anchors. Execution decides how the body moves between them.

Why not mutate AStarGrid2D for every size?

AStarGrid2D remains a good point-grid pathfinder. For one fixed body size, mark every anchor whose clearance is too small as solid and use the built-in path query. For two fixed sizes on a small static map, two prepared grids may still be the simplest design.

The awkward case is one shared instance answering interleaved 1x1, 2x2, and 3x3 queries. Rewriting set_point_solid() before each call makes passability global mutable state. You must update every affected anchor, prevent overlapping queries, and restore the previous profile correctly. Separate grids avoid that mutation but duplicate size-specific state.

The official AStarGrid2D API exposes cost and heuristic hooks, but not a query-specific neighbor-filter callback. That is why a short custom search fits many-profile grids cleanly. It is an API-driven tradeoff, not a verdict against the built-in class. The broader API and its normal use cases are covered in the AStarGrid2D complete reference.

AStar2D can filter neighbors — mind the polarity

If the game already maintains an irregular AStar2D graph, enable its neighbor filter and apply the size predicate there.

The callback is documented but easy to reverse: returning true means reject this neighbor.

Read it as should_filter_out_neighbor(), not is_neighbor_allowed(). Returning allowed directly keeps the cells the query meant to exclude and removes the legal graph.

For a dense rectangular tile map, manually creating and connecting an AStar2D point for every cell may be more code than the custom grid loop. The router above is the decision; the callback is an option, not the default.

func _filter_neighbor(_from_id: int, neighbor_id: int) -> bool:
    var neighbor_anchor := id_to_cell(neighbor_id)
    var allowed := clearance_at(neighbor_anchor) >= current_agent_size
    return not allowed  # true means filter it out

Weighted terrain needs an admissible heuristic

The artifact treats the cost of entering the neighbor as the step cost. For four-way movement, Manhattan distance remains admissible when multiplied by the minimum possible positive step cost.

If the minimum is unknown, use zero and the search becomes Dijkstra's algorithm. A slower correct heuristic is preferable to one that overestimates and can return a non-optimal path.

Keep AStarGrid2D.jumping_enabled out of a weighted comparison. The Godot 4.7 docs state that jumping currently disables weight-scale consideration. HAA* is also not a drop-in optimization for this loop; it adds a separate hierarchical representation.

func estimate_cost(
    from: Vector2i,
    goal: Vector2i,
    minimum_step_cost: int
) -> int:
    var distance := abs(from.x - goal.x) + abs(from.y - goal.y)
    return distance * minimum_step_cost

Keep diagonals out until the movement contract exists

This implementation is four-way. A large body's diagonal is not made safe merely because the destination anchor has enough clearance.

Before adding diagonals, decide which intermediate cardinal anchors must be valid; whether either or both cardinal orders permit the move; what a diagonal step costs; which conservatively touched cells the body must avoid; and whether planning and execution use the same corner policy.

Do not copy a point-agent AStarGrid2D.diagonal_mode and assume it proves a 2x2 body can execute that step. Valid destination clearance does not validate the geometry between two anchors.

Return reasons, not only an empty path

The downloadable solver distinguishes invalid size, out-of-bounds start or goal, insufficient start or goal clearance, and a search that exhausts the connected region.

Return the empty path together with its failure code. The caller can then distinguish a goal that cannot hold a 2x2 footprint from two valid regions separated by a wall.

What the verifier checks

The downloadable Godot 4.7 project contains the exact solver, binary min-heap, demo scene, and headless verifier used for this article.

The machine-readable correctness receipt reports twelve named checks. It includes 120 generated size-2/3 comparisons against an independent Dijkstra solver that validates every footprint directly, plus 80 weighted optimality comparisons. The packaged ZIP was extracted into a clean project and reran the same checks.

Measurement-gap: this is a correctness receipt, not a benchmark. It makes no runtime, throughput, or memory claim.

The proof covers annotation correctness, search correctness, reference equivalence, and artifact integrity.

1. Annotation correctness: maximal-square clearance matches direct footprint expansion on the source occupancy grid.
2. Search correctness: a 1x1 unit uses a width-one opening, while a 2x2 unit rejects it and takes the wider route.
3. Reference equivalence: generated and weighted queries match independent full-footprint Dijkstra reachability and optimal cost.
4. Artifact integrity: the source parses in Godot 4.7, the scene runs headlessly, heap ordering is deterministic, and the extracted ZIP reruns all checks.

Why compare against direct footprints?

A clearance implementation can agree with itself while sharing the same anchor or boundary bug in both the map builder and the pathfinder. The independent reference returns to the original occupancy grid.

Annotated A* is not Hierarchical Annotated A*

AA* is the low-level search in this article. It evaluates anchor cells using size and capability annotations. HAA* builds and searches a smaller abstract graph, then refines the high-level plan with low-level searches.

The 2008 paper and Harabor's later tutorial report near-optimal paths and substantial search-effort reductions for HAA*. Those results do not describe this standalone AA* implementation. On a large map with many queries, the low-level search may still need a measured optimization such as hierarchy, sectors, caches, or another technique whose preconditions match the game.