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

The short answer

AStarGrid2D can find a perfectly legal route that still looks like it was drawn on graph paper. That is not an A* failure. The search was asked to move between grid neighbors, so it returned a path made from grid moves.

Start with line-of-sight post-smoothing. Keep the first point of the legal grid path, connect it to the farthest later point it can see, keep that point, and repeat until the goal. This removes redundant bends without replacing the trusted AStarGrid2D search.

Move to Basic Theta* when the remaining problem is route selection rather than waypoint count. A smoothing pass cannot change which side of an obstacle A* already chose. Theta* lets visibility influence that choice during search by allowing a node to inherit a visible ancestor as its parent.

Godot 4.7.2 does not expose Theta* as an AStarGrid2D mode. jumping_enabled performs Jump Point Search-style pruning, but it does not add arbitrary-angle parent connections. Cost overrides change the score. They do not expose Theta*'s parent-rewiring step.

For the binary, uniform-cost baseline, use Euclidean distance for segment cost and the heuristic. Basic Theta* is complete under the paper's assumptions, but it is not guaranteed to return the globally shortest Euclidean path.

What any-angle means

Any-angle pathfinding does not ignore the grid. The grid still says which cells are blocked and which local neighbors the search may expand. “Any-angle” describes the reconstructed path. Two parent nodes may be connected by a clear straight segment even when they are not immediate grid neighbors.

A path with fewer points is not automatically an any-angle path. A long horizontal JPS jump may return only two endpoints, but it still follows a grid-direction ray.

Where Theta* fits in Godot

Use custom Theta* when a square grid must remain the source of walkability but the actor may cross visible cells in a straight line. For a continuous polygonal surface, Godot's navmesh search and corridor funnel are usually the simpler fit. AStar2D can search a visibility graph, but you still have to construct and validate every visible connection.

Polyanya is a separate research direction for online optimal search on convex navigation meshes. Godot does not expose it as an engine option.

The one change that makes Basic Theta* different

Ordinary A* reaches a neighbor through the current node. Basic Theta* also asks whether the current node's parent can see that neighbor. If the visible-ancestor route is cheaper, the neighbor inherits the ancestor directly.

This is the complete neighbor loop from the verified theta_star_grid.gd. The first LOS call keeps the ordinary local step consistent with the same corner and footprint policy. The second checks the ancestor shortcut. The full file uses a deterministic binary heap, rejects stale entries, and applies an explicit 1e-6 comparison tolerance.

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))

Use Euclidean distance for the path you now allow

For the uniform-cost point-agent baseline, use Euclidean distance for both segment cost and the heuristic. Manhattan and octile distance price routes restricted to grid edges. They can be strictly longer than a legal direct segment whose slope is neither axial nor 45 degrees, so they can overestimate the route Theta* is allowed to take.

This advice does not transfer unchanged to terrain weights. A long visible segment crosses cells whose costs must be accounted for. Pricing the shortcut only from its endpoints solves a different problem, so keep the first implementation binary and uniform-cost.

Line of sight is the correctness boundary

The parent update is the easy part. A false positive from line_of_sight() can send an actor through a wall. A false negative keeps the route legal but gives up a shortcut. The implementation therefore needs one written visibility contract shared by search and smoothing.

Choose where a node lives

The original Theta* paper places start and goal at grid-cell corners. A typical Godot tile implementation places path nodes at cell centers. Both models work, but they touch obstacles differently.

For a center-based grid, define a segment between cell centers and traverse every occupancy cell required by the chosen contact rule. A supercover-style traversal is a useful foundation because it can report more than the thin mathematical line, but tie and corner behavior still has to be explicit and tested.

Decide what happens at a blocked corner

The paper's model rejects a segment that enters a blocked cell or passes between blocked cells sharing an edge, while allowing a gap where blocked cells touch only at one corner. The authors also state that neither their corner-node placement nor that permissive gap assumption is required for Theta* to work.

A center-based grid with strict corner blocking is therefore a valid adaptation when that matches the game. Translate the existing diagonal policy into the long line-of-sight test. A segment must not regain a local corner cut that movement itself forbids. If the game permits corner squeezes, make that a named movement profile rather than a rounding accident.

Test every occupancy cell the segment requires

Sampling a few evenly spaced points is not enough. A thin obstacle can fall between samples. Advance from grid boundary to grid boundary, classify ties deterministically, reject out-of-bounds coverage, and return every occupancy cell required by the corner policy.

The result should also be symmetric. If reversing a segment changes the answer, a boundary tie is probably being resolved differently in the two directions.

line_of_sight(a, b) == line_of_sight(b, a)

A point can see through a gap an actor cannot use

A center-line test proves visibility for a point. It does not prove clearance for a circle, a 2x2 unit, or a rotating rectangle. Either inflate blocked space for each agent footprint and run the same point test on the derived grid, or make the segment traversal query a clearance representation that proves the full shape fits.

The downloadable proof is narrower. Its square_2x2 profile is an axis-aligned translated set of occupied-cell offsets. It does not prove clearance for a continuous disk, a rotated rectangle, or an arbitrary polygon sweep.

Collision avoidance after pathfinding cannot repair this contract. It may steer around moving actors, but it cannot legalize a route through a doorway that is too narrow.

Visibility and walkability need the same owner

If a TileMap-derived occupancy grid owns walkability, use that same versioned data for line of sight. A physics ray can be correct when collision geometry is the canonical model, but a thin ray does not automatically match grid corner rules, non-point agents, or an occupancy update that has not reached the physics world.

Cache visibility only with the movement profile and topology revision that produced it. When a door, wall, or clearance map changes, an old true result is unsafe.

(start_cell, end_cell, movement_profile, topology_revision) -> visible

Start with line-of-sight post-smoothing

Post-smoothing runs after AStarGrid2D returns a legal route. It preserves the start and goal, then removes intermediate cells when a longer direct segment passes the same visibility contract that Theta* would use.

When the occupancy grid is authoritative, smooth the cell IDs from get_id_path() and convert only the retained IDs to world positions. That keeps the decision in grid space instead of reconstructing cell identity by rounding world coordinates.

Keep the farthest visible waypoint

The verified pass scans backward from the goal for the farthest later cell visible from the current anchor. The full function also handles empty and single-point inputs and rejects a topology revision change during the pass.

Searching backward matters because visibility is not necessarily monotonic along the waypoint list. One blocked candidate does not prove that every later endpoint is blocked. The straightforward implementation can make a quadratic number of LOS calls in the number of input waypoints, so measure it before adding cleverness.

This is broader than the original paper's forward A* post-smoothing pass. It examines more later endpoints, but it remains a deletion-only transformation of a route that A* already selected.

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

Where smoothing stops and Theta* begins

Post-smoothing has already committed to one grid path. It can remove bends from that route, but it has no search state and cannot introduce a new bend outside the returned waypoint sequence. Neither a forward pass nor the broader backward scan can move the route to the other side of an obstacle.

Theta* tests visible parents while the search is still open, so the shortcut can influence which route family wins. This structural limit, rather than one specific smoothing example from the paper, is the reason to escalate.

When Theta* is a good fit

Reach for Basic Theta* when the authoritative walkability is a square grid, actors move continuously, binary occupancy plus Euclidean distance is a useful first model, straight segments visibly improve the route, and every supported movement profile has a testable LOS contract.

Do not start there when movement is intentionally tile-to-tile, a navmesh already models the surface, terrain price matters more than geometric distance, exact Euclidean optimality is mandatory, large or rotating footprints lack a clearance model, or topology changes faster than cached visibility can be invalidated.

Variants worth knowing, not mixing into the baseline

Basic Theta* is a useful first implementation, not the end of the any-angle literature. These algorithms answer different measured needs and should not lend their paper results to a Godot implementation that has not been benchmarked.

• Lazy Theta* delays a line-of-sight check until expansion. Its paper motivates this when visibility is expensive, but whether it is faster in GDScript depends on the actual grid, queue, cache, and workload.
• Angle-Propagation Theta* carries angular visibility bounds to reduce repeated LOS work at the cost of a more complex implementation.
• Anya searches interval states and provides optimal Euclidean any-angle paths under its grid model without preprocessing. It is the relevant direction when exact optimality is non-negotiable.
• Zeta* and Zeta*-SIPP are newer optimal any-angle research for static grids and predictable moving obstacles. Their assumptions and results are research context, not a drop-in Godot recommendation or imported benchmark.

What the artifact proves

The downloadable five-file Godot 4.7.2 artifact compares ordinary AStarGrid2D, A* plus post-smoothing, and Basic Theta* on the same occupancy grid. Its verification receipt records 11 workspace logic checks plus a clean extracted-package rerun. The same-grid scene smoke also passes.

The receipt proves legality and reachability under its declared binary occupancy, corner, bounds, topology, and movement-profile rules. It does not prove global any-angle optimality.

Measurement-gap: this is a deterministic correctness artifact, not a benchmark. It contains no timing, memory, throughput, or comparative speed claim.

The route-family receipt

The escalation case is deliberately small. The AStarGrid2D route measures 19.314 cell units. Backward farthest-visible smoothing reduces it to 18.806 but remains on the upper side because it can retain only waypoints from that route. Basic Theta* takes the lower route at 18.601.

Those are fixture-specific correctness data, not a performance benchmark or a general path-quality percentage.

Operation counts tell the same story. The open-grid Theta* case expands 9 nodes and makes 120 LOS calls. The unreachable case expands 40 and makes 238. The seven-waypoint smoother needs one LOS call. These counts explain the extra kind of work without predicting elapsed time.

Keep two statements separate. Legal means every returned segment obeys the declared movement contract. Optimal means no legal route is shorter. Basic Theta* targets the first and does not guarantee the second.

A practical decision ladder

The first useful optimization is an unambiguous movement contract. Without it, a faster line-of-sight function only reaches the wrong answer sooner.

1. Draw the grid route and confirm the visual issue is grid-constrained geometry, not path following.
2. If removing redundant waypoints is enough, keep AStarGrid2D and add post-smoothing.
3. If the selected side of obstacles is still poor, prototype Basic Theta* on a binary uniform-cost grid.
4. Lock node placement, corner contact, bounds, and agent clearance before tuning performance.
5. Measure LOS calls and traversed cells as well as expanded nodes.
6. Consider Lazy Theta* only when measured visibility work justifies the extra algorithm.
7. Choose Anya or another optimal method only when you can state why near-optimal paths are unacceptable.