Rectangular and Circular Agent Clearance in Godot

The direct answer

For an axis-aligned rectangular unit on a Godot grid, store its footprint as Vector2i(width, height) and test candidate anchors with either a summed-area blocked-cell table or a passability mask built for that footprint. For a circular unit, store a center and radius, then test candidate center cells against the actual blocked-cell geometry or a radius field derived from it.

The pathfinder can still search points. Those points represent legal poses: top-left anchors for rectangles and center cells for circles. Shape clearance decides which poses are available before A* expands them.

AStarGrid2D doesn't apply either body shape automatically. Its cell_size controls point placement, not agent dimensions. NavigationAgent2D.radius is an avoidance radius; Godot 4.7 documents that it doesn't affect normal pathfinding.

A project with two fixed shapes may be clearest with two masks or two AStarGrid2D instances. A shared structure is useful only when it makes the actual profile set or update pattern simpler.

This article proves whether a body can occupy a candidate pose. Moving between poses, rotating the body, and reserving runtime occupancy are separate contracts.

What square clearance can and can't encode

The square clearance guide stores the side length of the largest open square anchored at each cell. A value of 3 proves that 1x1, 2x2, and 3x3 square bodies fit there.

It doesn't answer whether 1x4 fits. Requiring square clearance 4 is safe but rejects narrow places where the rectangle fits without a 4x4 square. Requiring clearance 1 can let the other three cells overlap walls. A rectangle needs width and height, not one scalar size.

Circles need a different metric. Manhattan distance produces diamond contours; Chebyshev distance produces squares. A Euclidean collision rule needs Euclidean geometry.

Configuration-space planning supplies the common model: represent the entire body as a point, then mark every point-position that would collide as forbidden. The pathfinder searches the remaining point graph.

Rectangles need an anchor and orientation

This article uses the top-left occupied cell as the anchor. A 3x2 unit at (4, 5) occupies columns 4 through 6 and rows 5 through 6. That is the same convention used by the multi-tile movement guide.

Orientation belongs to the pose. A 1x3 north/south unit and a 3x1 east/west unit require different occupancy queries. If 90-degree turns are allowed, the search state is at least (cell, orientation).

Directly scanning all W * H occupied cells is a good baseline for small footprints. Precompute only when repeated queries justify it.

Query rectangles with a summed-area table

A summed-area table stores cumulative blocked-cell counts from the map origin. After it is built, the blocked count inside any axis-aligned rectangle comes from four lookups. The footprint fits when that count is zero.

This implementation assumes a zero-origin occupancy array. For a TileMapLayer region with a non-zero origin, subtract region.position before indexing.

A negative blocked_count() result means the query itself was invalid, not that the rectangle contains an empty count. rectangle_fits() therefore fails closed for invalid dimensions and out-of-bounds anchors.

The footprint test is a fixed four-corner query rather than an area scan. Updates are not free: one changed obstacle affects many prefix sums. The plain table is best for static maps or explicit rebuild phases.

For frequent dynamic blockers, keep static geometry in the table and test a small dynamic overlay separately, update dirty regions in a few prepared profile masks, or retain direct footprint checks for small rectangles. Use a more complex dynamic range-sum structure only after measurements justify it.

class_name RectangularClearance

var _grid_size := Vector2i.ZERO
var _stride := 0
var _sum := PackedInt32Array()

func rebuild(blocked: PackedByteArray, grid_size: Vector2i) -> void:
    assert(grid_size.x > 0 and grid_size.y > 0)
    assert(blocked.size() == grid_size.x * grid_size.y)

    _grid_size = grid_size
    _stride = grid_size.x + 1
    _sum.resize((grid_size.y + 1) * _stride)
    _sum.fill(0)

    for y in range(grid_size.y):
        var row_sum := 0
        for x in range(grid_size.x):
            var source_index := y * grid_size.x + x
            row_sum += 1 if blocked[source_index] != 0 else 0
            _sum[(y + 1) * _stride + (x + 1)] = (
                _sum[y * _stride + (x + 1)] + row_sum
            )

func blocked_count(anchor: Vector2i, footprint: Vector2i) -> int:
    if footprint.x <= 0 or footprint.y <= 0:
        return -1

    var end := anchor + footprint
    if anchor.x < 0 or anchor.y < 0:
        return -1
    if end.x > _grid_size.x or end.y > _grid_size.y:
        return -1

    var top_left := _sum[anchor.y * _stride + anchor.x]
    var top_right := _sum[anchor.y * _stride + end.x]
    var bottom_left := _sum[end.y * _stride + anchor.x]
    var bottom_right := _sum[end.y * _stride + end.x]
    return bottom_right - top_right - bottom_left + top_left

func rectangle_fits(anchor: Vector2i, footprint: Vector2i) -> bool:
    return blocked_count(anchor, footprint) == 0

Rectangular rotation needs orientation states

For one obstacle/capability layer and 90-degree turns, prepare W x H and H x W masks. The pathfinder must include orientation in its state; otherwise a route can switch masks without validating the turn.

A rotation edge must check that the destination orientation fits at its declared pivot. A center-pivot turn may also change the top-left anchor. Continuous rotation near a wall needs swept-geometry validation because the rotating body can occupy more space than either endpoint rectangle.

The fit mask owns pose legality. The movement article owns pivots, touched transition cells, commit rules, and animation.

Circles need world units and blocked areas

Define the candidate position as the center of a grid cell, express radius in local units rather than a number of cells, treat each blocked tile as an axis-aligned rectangle, declare whether contact counts as collision, and decide whether the outside of the map is blocked.

The reference predicate below checks the circle against nearby blocked-cell AABBs. Contact is accepted within 0.000001 squared local units. The downloadable implementation precomputes the same minimum geometry distance into a reusable field.

This is a correctness reference, not the recommended inner loop for every A* expansion. The verifier compares the precomputed field with this direct geometry on 5,376 generated radius/cell cases, including non-square cells.

const CIRCLE_CONTACT_EPSILON_SQUARED := 0.000001

func circle_fits(
    center_cell: Vector2i,
    radius: float,
    blocked: PackedByteArray,
    grid_size: Vector2i,
    cell_size: Vector2
) -> bool:
    if radius <= 0.0 or cell_size.x <= 0.0 or cell_size.y <= 0.0:
        return false
    if grid_size.x <= 0 or grid_size.y <= 0:
        return false
    if blocked.size() != grid_size.x * grid_size.y:
        return false
    if center_cell.x < 0 or center_cell.y < 0             or center_cell.x >= grid_size.x or center_cell.y >= grid_size.y:
        return false

    var center := (Vector2(center_cell) + Vector2(0.5, 0.5)) * cell_size
    var world_size := Vector2(grid_size) * cell_size
    var boundary_distance := minf(
        minf(center.x, world_size.x - center.x),
        minf(center.y, world_size.y - center.y)
    )
    if boundary_distance * boundary_distance             + CIRCLE_CONTACT_EPSILON_SQUARED < radius * radius:
        return false

    var min_cell := Vector2i(
        floori((center.x - radius) / cell_size.x),
        floori((center.y - radius) / cell_size.y)
    )
    var max_cell := Vector2i(
        floori((center.x + radius) / cell_size.x),
        floori((center.y + radius) / cell_size.y)
    )
    min_cell = min_cell.clamp(Vector2i.ZERO, grid_size - Vector2i.ONE)
    max_cell = max_cell.clamp(Vector2i.ZERO, grid_size - Vector2i.ONE)

    for y in range(min_cell.y, max_cell.y + 1):
        for x in range(min_cell.x, max_cell.x + 1):
            if blocked[y * grid_size.x + x] == 0:
                continue

            var obstacle_min := Vector2(x, y) * cell_size
            var obstacle_max := obstacle_min + cell_size
            var closest := Vector2(
                clampf(center.x, obstacle_min.x, obstacle_max.x),
                clampf(center.y, obstacle_min.y, obstacle_max.y)
            )
            if center.distance_squared_to(closest)                     + CIRCLE_CONTACT_EPSILON_SQUARED < radius * radius:
                return false

    return true

One geometry field can serve several radii

Store the minimum Euclidean distance from every candidate center to blocked geometry and the map boundary. A profile fits when that value satisfies its radius under the same contact-tolerance convention.

Several radii can share one field. The raster convention remains important: a standard Euclidean distance transform on a binary grid measures distance to obstacle samples, while a blocked tile occupies an area. Treating the tile center as the entire obstacle can let a circle clip an edge or corner.

Three defensible choices are exact point-to-blocked-AABB distance, a finer geometry raster with a documented approximation, or center-sample distance plus a conservative margin such as the tile half-diagonal. The last option deliberately rejects some valid space.

Don't describe a center-sample field as exact tile geometry unless the conversion has been proved.

Apply the shape predicate to pathfinding

After preprocessing, neighbour acceptance is small: a rectangle reads an orientation-specific mask, while a circle compares the stored squared distance plus the declared tolerance with its squared radius.

For a few fixed shapes, prepare one AStarGrid2D per rectangle orientation or circle radius and mark invalid points solid. For many profiles, use a custom search whose neighbour expansion calls the profile predicate. The Annotated A* guide shows that integration point; its own artifact intentionally remains square-only.

Direct checks may be easier to maintain for small, frequently changing footprints.

For continuous circular actors, navmesh baking is a different architecture. NavigationPolygon.agent_radius shrinks the baked walkable surface, and Godot's actor-type workflow uses separate navigation maps for different radii. Complex shapes aren't represented by that radius model. Use the grid-vs-navmesh guide for that system choice.

rectangle: rectangle_mask[orientation][cell] == PASSABLE
circle:    radius_field_squared[cell] + epsilon >= radius_squared

A shape-safe cell is not automatically a shape-safe edge

Rectangle or circle clearance proves that the body can occupy an endpoint pose. It doesn't prove the transition.

A rectangular diagonal may touch cells outside both endpoint footprints. A circle moving along a segment sweeps a capsule that can hit a corner. A rotating rectangle can occupy more space than its two endpoint orientations.

For discrete one-cell tactics, define a conservative transition rule and use it in both planning and execution. For continuous movement, use an appropriate geometry or physics sweep and account for its numerical contract. Runtime ownership remains separate; the reservation-table guide handles units competing for otherwise legal cells.

Choose the smallest sufficient representation

No representation wins every workload. Use the smallest one that matches the body shapes, obstacle updates, and movement rules the game actually ships.

Common mistakes

Most failures come from mixing pose, metric, and transition contracts. Keep each one visible in code and tests.

1. Using AStarGrid2D.cell_size as agent size. It controls point placement.
2. Changing NavigationAgent2D.radius to alter wall paths. It affects avoidance, not normal pathfinding.
3. Approximating 2x5 with square clearance 2. Three rows may overlap walls.
4. Using an inscribed circle for a rectangle. The rectangle's corners can clip; a circumscribed circle is safe for translation but conservative.
5. Calling Manhattan distance a radius field. Its contour is a diamond.
6. Measuring only to blocked tile centers. A blocked tile occupies an area.
7. Ignoring the map boundary. The center may be inside while the body is not.
8. Rotating without orientation in the search state. The route gains an unvalidated free turn.
9. Checking only endpoint poses. Fit, transition safety, and runtime ownership remain different contracts.

What the verifier checks

The machine-readable correctness receipt reports twelve named checks on Godot 4.7 stable. They include 9,216 rectangle comparisons, 5,376 circle comparisons, 1,600 radius-monotonicity comparisons, 80 generated profile-path cases, non-square cell geometry, map boundaries, orientation masks, the declared contact tolerance, a diagonal endpoint counterexample, and scene smoke.

The source ZIP was extracted into a clean directory and passed the same parser and verifier again.

Measurement-gap: this is a correctness receipt, not a speed or memory benchmark. The circle field is checked against a direct blocked-AABB reference; it is not described as an independent geometry implementation.

PathForge V1 currently uses a maximal-square clearance map for square N x N profiles. The rectangle and circle code here is a standalone article artifact, not an undocumented PathForge launch feature.