Godot Reachability Rules: Validate a World Change Before It Traps the Player

The short answer

Closing a door is easy. The ugly bug arrives two rooms later, when an NPC cannot reach its objective and the save file already contains the closed door. The game is still running, but a route required for progress no longer exists. Cooper and Bazzaz describe the broader distinction in their 2025 work on levels that remain playable without retaining a route to completion: a level can be completable from its start while still containing reachable states that trap the player. Read the FDG 2025 paper.

Store required Godot reachability as data, then audit the same rules before and after a runtime world change. Each rule names every phase in which it is active, the movement profile that will use the route, stable start and goal anchors, and whether any goal or all goals must remain reachable.

For AStarGrid2D, label connected components once per movement profile. Snapshot occupied-actor starts once at the beginning of the transaction and reuse that snapshot for both audits. Compare the candidate with the accepted baseline: reject a rule that newly fails or an old failure that gets worse, while allowing unrelated changes and partial repairs.

Run the audit again when loading a save. Prevention only covers changes that passed through the transaction boundary; old saves, mods, migrated anchors, and changed level data did not make that promise. This proof stays deliberately narrower than a complete quest-state softlock detector: it can prove that a worker lost its exit, not that a key is behind its own lock.

Write the invariant as data

The tower-defense path-validation guide shows the basic speculative blocker transaction. The reusable layer here is a rule that survives different mutations, phases, actors, and movement profiles. A door can close, a bridge can disappear, a quest phase can activate, or a loaded save can arrive already damaged; the invariant remains the same data.

ANY fits alternate exits and safe rooms. The ALL example below genuinely requires two destinations, so losing either garage fails the truck rule. phases is an Array[StringName], not one value: the worker's escape matters during explore and evacuation, while the truck rule applies during evacuation and lockdown.

Anchors have stable ids as well as cells. A raw coordinate is hard to migrate when repairing an old save; worker_17, west_exit, and north_garage give recovery code and failure reports durable names. If activation is more complex than phase membership, keep that policy above the rule set or replace it with a deliberately tested predicate.

rules.add_rule(
	&"occupied_worker_has_escape",
	[&"explore", &"evacuation"],
	&"worker",
	{&"worker_17": WORKER},
	{&"west_exit": SAFE_EXIT},
	RuleSet.GoalPolicy.ANY
)
rules.add_rule(
	&"truck_reaches_both_garages",
	[&"evacuation", &"lockdown"],
	&"truck",
	{&"truck_02": TRUCK},
	{
		&"north_garage": Vector2i(1, 1),
		&"south_garage": Vector2i(1, 4),
	},
	RuleSet.GoalPolicy.ALL
)

Snapshot occupied starts once per transaction

Some starts are authored markers. Others come from actors currently inside the affected room or island. The temporal rule is the important one: resolve dynamic starts once, before the baseline audit, then give that exact snapshot to the candidate audit.

An actor can move while a mutation is being evaluated. If the baseline uses its old cell and the candidate uses its new cell, regressions_from() compares different invariants. The result is noise in either direction: a legal change can look harmful, or an actually stranded actor can disappear from the candidate evidence.

The downloadable helper's try_commit() calls snapshot_dynamic_starts() once, stores start_snapshot, and passes the same dictionary to both audit() calls. The receipt counts provider calls and requires exactly one during the transaction. If the transaction spans asynchronous NavigationServer work, freeze or version the actor snapshot with the navigation mutation rather than quietly refreshing half the evidence while waiting.

Only ALWAYS changes whether a route exists

A* gives you a route and cost. A reachability invariant asks a smaller question: do these anchors belong to the same connected region? One component pass can answer that for every active anchor, but only when its neighbor relation is consistent with the pathfinder.

The precise result is narrower than the usual warning about diagonal movement. A cardinal-only flood fill is wrong for connectivity only under DIAGONAL_MODE_ALWAYS. That policy can cross a corner whose two side cells are solid, joining regions that cardinal movement keeps separate. Ignoring it can produce DISCONNECTED_REGION even though AStarGrid2D finds a legal route.

DIAGONAL_MODE_AT_LEAST_ONE_WALKABLE and DIAGONAL_MODE_ONLY_IF_NO_OBSTACLES never change the connectivity partition relative to cardinal movement. Whenever the first permits a diagonal, at least one side cell is walkable. That cell already joins both diagonal endpoints in two cardinal steps. The second policy is stricter, so the same argument applies. The useful rule is quotable: only ALWAYS changes whether a route exists—the other three policies can still change which route A* returns.

The helper still mirrors all four policies. That keeps its labels aligned with the engine, makes the corner assumptions explicit, and prevents an unknown future policy from falling through to a plausible-looking component map.

static func _walkable_neighbors(grid: AStarGrid2D, cell: Vector2i) -> Array[Vector2i]:
	var neighbors: Array[Vector2i] = []
	for direction in CARDINAL_DIRECTIONS:
		var neighbor := cell + direction
		if _is_walkable(grid, neighbor):
			neighbors.append(neighbor)

	if grid.diagonal_mode == AStarGrid2D.DIAGONAL_MODE_NEVER:
		return neighbors
	for direction in DIAGONAL_DIRECTIONS:
		var diagonal := cell + direction
		if not _is_walkable(grid, diagonal):
			continue
		var side_x := cell + Vector2i(direction.x, 0)
		var side_y := cell + Vector2i(0, direction.y)
		var side_x_walkable := _is_walkable(grid, side_x)
		var side_y_walkable := _is_walkable(grid, side_y)
		var allowed := false
		match grid.diagonal_mode:
			AStarGrid2D.DIAGONAL_MODE_ALWAYS:
				allowed = true
			AStarGrid2D.DIAGONAL_MODE_AT_LEAST_ONE_WALKABLE:
				allowed = side_x_walkable or side_y_walkable
			AStarGrid2D.DIAGONAL_MODE_ONLY_IF_NO_OBSTACLES:
				allowed = side_x_walkable and side_y_walkable
		if allowed:
			neighbors.append(diagonal)
	return neighbors

Guard cell shape, jumping, storage, and dirty state

The helper allowlists the three cell_shape values in Godot 4.7.1: square, isometric-right, and isometric-down. The receipt compares component labels with direct A* route existence for both isometric shapes under every diagonal policy. A future unknown shape returns a typed UNSUPPORTED_CELL_SHAPE failure rather than silently borrowing square-grid assumptions.

jumping_enabled is a search optimization rather than a new neighbor policy, so the component builder does not read it. The verifier tests the engine instead of comparing the helper with itself: across all four diagonal policies it compares direct A* route existence with jumping off and on for the same 1,600 ordered start/goal pairs, requiring zero mismatches and the expected reachable-pair counts. Godot's separate warning about jumping and weight scaling still matters when route cost, not mere existence, is the question.

Component labels live in a PackedInt32Array indexed by (y - region.position.y) * width + (x - region.position.x). A 256×256 region therefore uses 65,536 integer slots instead of 65,536 Vector2i dictionary keys. That is a storage-shape decision, not a performance result.

Dirty structural parameters are a hard boundary. is_dirty() means the grid needs update() before queries. Returning an empty component map would convert one setup error into many false anchor failures, so the helper calls push_error() and returns a typed INTERNAL_ERROR with GRID_PARAMETERS_DIRTY. Directed drops, one-way links, and irreversible abilities need directed forward/reverse reachability or strongly connected components; this undirected helper is not proof for them.

Keep a baseline, or one bad save freezes everything

Imagine loading a save where truck_reaches_both_garages is already broken. The player opens an unrelated door. A validator that demands a perfect candidate rejects that harmless action even though it did not damage the truck route.

Audit the loaded world first and keep that result as the accepted baseline. A rule that passed before cannot fail now. A failed rule cannot lose another reachable goal or invalidate an anchor that was valid before. A newly activated rule must pass before the phase change commits. An improvement may become the new baseline even if it does not repair every existing failure.

That last case lets recovery happen in steps and keeps old save damage out of an unrelated rejection receipt. The transaction stays generic because apply and rollback can change a door, bridge footprint, active phase, or server link.

At the call site, assign multi-line lambdas to local Callable variables before invoking try_commit(). This is the parser-safe shape used by the packaged demo. The helper rejects STALE_PREVIEW and out-of-band signature drift before calling apply, then accepts only a non-regression. Every success and failure result contains both ok and code, so a consumer can inspect result["code"] without special-casing internal errors.

var previous_phase := rules.active_phase()
var enter_evacuation: Callable = func() -> bool:
	return rules.set_active_phase_unchecked(&"evacuation")
var restore_phase: Callable = func() -> bool:
	return rules.set_active_phase_unchecked(previous_phase)
var phase_result := rules.try_commit(
	rules.revision(),
	enter_evacuation,
	restore_phase
)

Rollback safety cannot depend on assert()

Godot's assert() documentation says assertion code runs only in debug builds or the editor. A shipped game therefore cannot use an assertion as its only rollback check, and side effects must never live inside the assertion expression.

The artifact validates rollback in ordinary control flow. A failed callback or mismatched canonical signature calls push_error() and returns an explicit INTERNAL_ERROR. The assertions come after those branches, so they provide extra developer feedback without carrying release correctness.

Two receipt checks exercise the explicit callback-failure and signature-mismatch paths. A separate rejected-mutation check requires blocker cells, active phase, revision, and the complete canonical state signature to match the pre-candidate state. Rollback is not 'we called the inverse'; it is 'the accepted state is observably back.'

func _restore_or_error(
	rollback: Callable,
	signature_before: String,
	context: String
) -> Dictionary:
	var restored := bool(rollback.call())
	if not restored:
		push_error("AntiSoftlockRuleSet: rollback callback failed (%s)." % context)
		return _internal_error("ROLLBACK_CALLBACK_FAILED", {"context": context})
	assert(restored, "Rollback callback must succeed.")

	var signature_after := state_signature()
	if signature_after != signature_before:
		push_error("AntiSoftlockRuleSet: rollback signature mismatch (%s)." % context)
		return _internal_error("ROLLBACK_SIGNATURE_MISMATCH", {
			"context": context,
			"expected_signature": signature_before,
			"actual_signature": signature_after,
		})
	assert(signature_after == signature_before, "Rollback must restore canonical state.")
	return _result(true, OK)

Validate the actor who needs the route

A one-cell player test can approve a corridor the real actor cannot use. Put the movement profile in the invariant and make it select the connectivity model built for that actor. On a grid, a profile can encode clearance and terrain permissions. On a navmesh, it can select a map baked for another agent radius or layer set.

A worker and a truck should not share labels when their passability differs. The proof registers one RuntimeAStarGrid2DState per profile and demonstrates that the worker remains connected while the truck is disconnected in the same logical world. The multi-size clearance guide owns how that passability data is built; this layer only requires each profile to provide an honest connectivity model.

This is also why occupied actors belong in the rule set. If a destructible bridge joins two islands, the player's objective can remain reachable while a worker on the far island loses its last safe exit. Snapshot that worker's anchor and audit its escape rule before applying the bridge mutation.

The public outcome remains REQUIRED_ROUTE_BROKEN, with evidence naming the rule, profile, start anchor, diagnostic, and mutation. ACTOR_STRANDED may be good UI copy, but it does not need to become another reason code.

Async navmesh rollback needs a second synchronization

The NavigationServer2D guide owns normal setup and synchronization. The additional concern here is transaction lifetime. Godot queues most server changes until synchronization, and map_get_iteration_id() advances when the changed map synchronizes. That applies once to the candidate and again to its inverse.

A server-backed transaction freezes competing navigation mutations and actor-snapshot changes, records the accepted signature and iteration, queues the candidate, and waits for a later iteration. It audits the candidate map only after that state is queryable. If the audit fails, it queues the inverse, waits for another later iteration, compares the restored canonical signature, and only then releases the mutation lock.

The async fixture creates two NavigationServer2D regions joined by a link. Disabling the link advances the iteration and makes the goal unreachable. Enabling it advances the iteration again and restores the original path signature. The fixture deliberately avoids map_force_update(). Publishing rollback after the inverse call but before that second synchronization would expose a state that gameplay cannot query consistently yet.

1. Freeze competing mutations and the dynamic-start snapshot.
2. Record accepted state signature and map iteration.
3. Queue the candidate and wait for a later iteration.
4. Audit the synchronized candidate.
5. On rejection, queue the inverse and wait for another later iteration.
6. Compare the restored signature before releasing the lock.

Audit every loaded save, then declare the repair policy

Pre-commit checks cannot protect a save written by an older build. They also cannot protect against changed geometry, removed mods, migrated anchor ids, or a route rule that did not exist when the save was created.

After restoring authored and runtime navigation layers, activate the saved phase and run the same audit. Do not start AI movement or accept another world mutation until that result exists. The loaded audit becomes the baseline, allowing unrelated changes while preventing new or worsened failures.

Recovery is a game rule, not something the pathfinder should invent. A last runtime blocker may be removed, a designated emergency link may open, an occupied actor may move to its recorded safe anchor, or a missing objective id may migrate. An old failure that is safe to defer can enter repair mode with further regression blocked.

Silent teleportation is not always harmless. If position affects combat, stealth, replay, or deterministic simulation, tell the player that the save needed repair and record what moved. A failed load with specific evidence can be safer than inventing a world the rest of the save does not recognize.

Return evidence using the vocabulary you already have

REQUIRED_ROUTE_BROKEN says which invariant rejected the world change. The evidence should reuse the existing endpoint, grid, synchronization, and stale-preview vocabulary rather than creating one reason for every story the UI might tell.

Keep the rule id, phase, movement profile, stable start and goal ids, mutation id, baseline and candidate revisions, and reachable-goal sets on both sides. That is enough to reproduce the rejection and distinguish new damage from a pre-existing save problem.

PATH_ENDED_SHORT remains a page-level NavigationServer verdict here. It is not yet part of the shared PathFailureReport.Reason enum, so this artifact does not emit it. The async fixture checks endpoint reachability in its receipt without pretending that the shared enum has already been extended.

Three failures worth checking here

Treating a baseline failure as candidate damage. This freezes harmless actions in an already-invalid save. Compare the two audits, reject regressions, and route the old failure into the declared recovery policy.

Refreshing occupied starts between audits. The candidate is no longer being judged against the same rule. Snapshot dynamic anchors once even if an actor moves while an asynchronous mutation is waiting.

Publishing rollback before a restored navmesh synchronizes. The inverse change has only been queued. Keep competing mutations frozen until the second synchronization and canonical-signature check complete.

These checks do not replace the focused owners elsewhere in the corpus. Use the runtime AStarGrid2D update contract for point edits versus structural rebuilds, the avoidance boundary for local steering, and the no-path report guide for the shared diagnostic envelope.

What the verified artifact proves

The standalone Godot 4.7.1 source package contains RuntimeAStarGrid2DState, AntiSoftlockRuleSet, the visible worker/truck scene, headless verifier, project file, README, and MIT license. The machine-readable receipt records 27/27 named logic checks plus scene smoke, then a 28th check for the clean extracted-package rerun.

The exhaustive diagonal sweep covers all 65,536 solid-cell layouts on a 4×4 grid. Cardinal versus AT_LEAST_ONE_WALKABLE differs in zero layouts. Cardinal versus ONLY_IF_NO_OBSTACLES also differs in zero. Cardinal versus ALWAYS differs in 39,978. A separate A* fixture proves that policies can preserve reachability while returning different two- or three-point routes.

The receipt also covers square and isometric cell shapes, direct A* jumping equivalence, dirty and unsupported typed failures, packed labels, ANY, two-goal ALL, multi-phase activation, profile-specific connectivity, one-call dynamic-start snapshots, baseline-invalid unrelated changes, worsening, partial repair, load recovery, stale preview, signature drift, consistent result shapes, explicit rollback failures, exact restoration, and two-iteration NavigationServer rollback.

The final ZIP is 20,391 bytes with SHA-256 c1e32bdcef8df7406e0b6bdc7bafa13a61ac8b318d61de8e72b13fd4181abbc0. Measurement-gap: this is deterministic correctness evidence, not a timing, allocation, throughput, asymptotic, production-scale memory, or released-product benchmark.