Smooth Grid Paths in Godot: Post-Smoothing vs Theta*

AStarGrid2D` returns a perfectly legal route that still looks like it was drawn
on graph paper. East, 45 degrees, east again, repeat, across a room that could
have been crossed in one straight line.

That's not an A* failure. The search was asked to move between grid neighbors,
so it returned a path made of grid moves.

There are two standard fixes and they get treated as interchangeable. They
aren't.

Smoothing runs after the search

Keep the first cell, connect it to the farthest later cell it can see, keep that
one, repeat until the goal.

`gdscript
var output: Array[Vector2i] = [input[0]]
var anchor_index := 0

while anchor_index < input.size() - 1:
var candidate_index := input.size() - 1
while candidate_index > anchor_index:
calls += 1
if visibility.has_line_of_sight(
input[anchor_index], input[candidate_index], profile_id
):
break
candidate_index -= 1

if candidate_index == anchor_index:
    return _result(
        false, "MOVEMENT_VISIBILITY_MISMATCH", output,
        input.size(), calls, revision
    )

output.append(input[candidate_index])
anchor_index = candidate_index

`

Search backward from the goal, not forward. Visibility isn't monotonic along the
waypoint list, so one blocked candidate doesn't prove every later endpoint is
blocked. The straightforward pass costs a quadratic number of line-of-sight
calls in the number of waypoints, which is fine at waypoint counts and worth
measuring before optimizing.

Smooth over cell IDs from get_id_path(), not world positions. That keeps the
visibility test in grid space instead of rebuilding cell identity by rounding
floats.

Theta* runs inside it

Basic Theta* changes the relaxation step. When it reaches a neighbor it also
asks whether the current node's parent can see that neighbor, and reparents
when the visible shortcut is cheaper.

`gdscript
for direction in DIRECTIONS:
var neighbor := current + direction
if closed.has(neighbor) \
or not visibility.is_anchor_open(neighbor, profile_id):
continue

los_calls += 1
if not visibility.has_line_of_sight(current, neighbor, profile_id):
    continue

var best_parent := current
var best_cost := float(g_score[current]) + _distance(current, neighbor)
var ancestor := Vector2i(parent[current])
if ancestor != current:
    los_calls += 1
    if visibility.has_line_of_sight(ancestor, neighbor, profile_id):
        var ancestor_cost := float(g_score[ancestor]) \
            + _distance(ancestor, neighbor)
        if ancestor_cost < best_cost - EPSILON:
            best_cost = ancestor_cost
            best_parent = ancestor

if best_cost >= float(g_score.get(neighbor, INF_COST)) - EPSILON:
    continue
g_score[neighbor] = best_cost
parent[neighbor] = best_parent
frontier.push(neighbor, best_cost, _distance(neighbor, goal))

`

Note the first line-of-sight call. It tests the ordinary local step, not the
shortcut. Drop it and your diagonal moves start cutting blocked corners that the
search itself forbids, which is the whole bug this contract exists to prevent.

Use Euclidean distance for cost and heuristic. Octile prices a route along
eight-neighbor grid edges, so it overestimates any segment whose slope is
neither axial nor 45 degrees.

Where smoothing stops

Smoothing can only delete waypoints from the route A* already committed to. It
can't move the path to the other side of an obstacle, because the bend it would
need was never in the list.

One authored fixture in the verified project: the AStarGrid2D route measures
19.314 cell units. Smoothing gets it to 18.806 and stays on the upper side.
Basic Theta* takes the lower side at 18.601.

Operation counts tell the same story from the other direction. The open Theta*
case expands 9 nodes and makes 120 line-of-sight calls. Expansion counts alone
hide that work entirely.

What the line-of-sight contract has to say

This is the part that actually decides whether your implementation is correct,
and prose can't prove it:

• where a node lives (cell corners in the paper, cell centers in most Godot tile code)
• what happens at a blocked corner, and whether it matches the diagonal rule the search already uses
• which cells a segment touches, boundary to boundary, with deterministic ties
• whether line_of_sight(a, b) == line_of_sight(b, a)
• whether the agent footprint fits along the whole segment, not just the center line
• which topology revision a cached visibility result belongs to

Godot 4.7.2 has none of this built in. AStarGrid2D has no any-angle mode, and
jumping_enabled is Jump Point Search-style pruning, not arbitrary-angle
parents.

What's verified and what isn't

The standalone Godot 4.7.2 project is MIT licensed. Its receipt records 12
checks and zero failures, including line-of-sight symmetry across 5,995
unordered cell pairs, an 80-grid generated corpus where all 594 returned
segments pass the same contract, deterministic ties across 21 runs, and a clean
rerun after package extraction.

It records no timing, memory, or throughput data at all. Basic Theta* is
complete under its model and not optimal. The square_2x2 profile is a
translated occupied-cell offset set, not a disk or a rotating shape.

Full version with the corner rules, the FAQ, the sources, the source zip and the
raw receipt JSON:

Smooth Grid Paths in Godot: Post-Smoothing vs Theta*