How to Pathfind in an Infinite World in Godot

The short answer

Your character wants to reach a place the game hasn't loaded yet. There's no tile layer there, no collision scene and perhaps no navigation region. Making the existing grid larger would mean generating terrain the player may never visit.

You can plan through unloaded terrain if its walkability and movement costs can be evaluated without instantiating that terrain. A custom A* can ask for neighbors as it explores them, with explicit limits on the search. It doesn't need a stored graph of the whole world.

That depends on your generator. A seed alone isn't enough. You need deterministic random access to the relevant terrain, plus any saved changes that affect it. If those changes aren't available, return a missing-data result or a clearly provisional route. Don't silently assume the original ground is still there.

For long journeys, a coarse route can guide smaller local searches. Keep rendering and physics near the player, and make navigation's knowledge of the world explicit. The runnable example below measures what this buys you and where it still gets expensive.

Evaluate the generator, not the scene

For a procedural grid, the useful interface is small:

query_terrain(global_cell)
    known       Have all terrain and saved-change inputs been resolved?
    walkable    Can this movement profile occupy the cell?
    cost        What does entering it cost?

The generator can answer this without adding nodes to the scene tree. In the fixture, it samples FastNoiseLite, applies a threshold and assigns a positive movement cost. It uses three fBm octaves with fixed seed, frequency, gain and lacunarity. Those settings are pinned in the source and receipt. Godot exposes these controls through FastNoiseLite.

Here's the terrain rule, before the saved-change overlay:

func base_sample(cell: Vector2i) -> Dictionary:
    var x := int(cell.x) - int(offset.x)
    var y := int(cell.y) - int(offset.y)
    var value := noise.get_noise_2d(float(x), float(y))
    return {
        "known": true,
        "walkable": value > -0.28,
        "cost": 1.0 + maxf(value, 0.0) * 3.0,
    }

offset is a control for the translation experiment. Subtracting it deliberately moves the terrain pattern. It isn't a general solution for generating noise with matching boundaries across arbitrarily distant chunks.

A fixed number of noise evaluations doesn't require building all the cells between the origin and the requested coordinate. But a route still pays for every state the search explores. Open and closed states, parent links, heap entries and cached samples occupy memory. This removes the prebuilt world graph, not the search's working data.

What moving the same query actually changed

Start with the 128-cell Manhattan span shown in the native scene, from (0, 0) to (128, 0). The second query shifts the endpoints, search bounds and terrain by (1_000_000, 1_000_000). Both searches see the same obstacles and costs, with the same neighbor order and a binary heap ordered by f, then h, then insertion sequence.

The first two rows repeat the visible route, with 128 steps, weighted cost 134.520, 805 expansions and 1,068 generator samples. The 400-cell example below them is retained to show a harder search. It returns 580 steps at cost 635.617. Obstacles and weighted costs favor detours, while A* explores alternatives beyond the final path. Its 72,813 expansions are search work, not route length. These are two particular terrain queries with different bounds, not a scaling law based on span alone.

The small query's roughly 26 ms median still exceeds a 16.7 ms frame at 60 FPS. The roughly 2.7 s scaling case makes the limit more obvious. This synchronous GDScript fixture is not a per-frame navigation budget. Reduce the search domain, improve guidance, schedule queries, or preserve search state across frames before putting a comparable workload on the main gameplay thread.

This run used AMD Ryzen 5 2600X Six-Core Processor, Windows build 10.0.26200, with Godot 4.7.2-stable (official), build ed1daf0bf, headless and single-threaded. Each location had three warmups and 30 timed queries. Query order alternated each round. The terrain cache started empty for each query, then memoized samples during that search. Timings include search, terrain sampling, heap work and path reconstruction. They exclude generator construction, cache reset and the separate legality check. The 128-cell run used the scene bounds Rect2i(-16, -32, 176, 160) and a 10,000-node cap. The 400-cell run used Rect2i(-64, -128, 576, 256) and a 100,000-node cap. Both had the time cap disabled. They were captured separately on the same machine with this protocol.

For each span, expanded-node counts, generator-sample counts and translated paths matched exactly. Timing equality wasn't an assertion. Hashing, allocation and ordinary system noise can affect wall time even when the algorithm does the same work. This is evidence for these queries and this implementation, not proof of constant runtime at every coordinate.

Inspect the 128-cell timing receipt and the separate 400-cell scaling and verification receipt. Both retain the raw samples and protocol.

The first 400-cell run used a 50,000-expansion cap. Both locations returned BUDGET_EXHAUSTED after 50,000 expansions and 51,107 generator samples. That partial result is retained in the exploratory 50,000-cap receipt. Raising the cap let us measure the complete route. A 400-cell span doesn't mean A* will inspect 400 cells, particularly on weighted terrain with detours.

The scene creates drawing output for inspection. The planner itself needs no terrain scene nodes. The new small-query verifier checks its results against both native-scene panels, in addition to translation and independent path legality.

Same span, different terrain

Moving only the query while leaving the generator fixed is a different test. You may land in water, behind a barrier, or in a region with different costs. The fixture also runs 12 fixed 160-cell routes near the origin and 12 near the distant coordinate, without subtracting an offset.

These are descriptive outcomes under a 10,000-expansion cap, not a test that the two locations have identical distributions. Invalid endpoints and budget failures remain in the record. Comparing only successful routes would hide part of the workload.

Bound the search and report why it stopped

An unreachable goal can keep an unbounded search exploring indefinitely. Give each request a finite domain and a work cap. The example accepts a Rect2i search window, an expansion limit, an optional cooperative deadline and a cancellation callback.

const Terrain := preload("res://scripts/articles/infinite_world_terrain.gd")
const Search := preload("res://scripts/articles/infinite_world_search.gd")

func request_route() -> Dictionary:
    var terrain := Terrain.new()
    terrain.begin_query()
    return Search.new().search(
        terrain.query,
        Vector2i(0, 0),
        Vector2i(400, 0),
        Rect2i(-64, -128, 576, 256),
        {
            "max_expanded": 100000,
            "max_usec": 4000,
            "revision": terrain.revision(),
        }
    )

The 4,000-microsecond setting is an example application policy, not a measured promise that this route will finish in four milliseconds. The planner checks the deadline between expansions. An individual sample, allocation or path reconstruction can overrun it. Use a resumable search or an appropriate worker design when your frame needs a stricter limit.

Partiality is a separate field. A failed search may still return a legal prefix ending at the expanded cell closest to the goal by Manhattan distance. That policy doesn't prove the prefix leads to an eventual solution. It can take an agent toward a dead end, so following it is an application decision.

The barrier tests distinguish a finite-window failure from global unreachability. They also verify an exact 128-expansion cutoff, cancellation, solid-goal rejection and legal partial paths. Godot's own AStarGrid2D documentation warns that requesting a partial path to a solid target can take unusually long. A partial-path option doesn't replace a budget.

Saved changes need an explicit unknown state

Suppose a player built a wall yesterday. Today its chunk is unloaded. Falling back to the seed because the local override dictionary is empty would route through the wall.

The fixture keeps an authoritative index of modified chunks. Their contents can be loaded or unloaded independently. An absent override is only evidence of unchanged terrain when the chunk's modification state is known.

cell query
  -> modified chunk, changes unloaded -> NEEDS_DATA
  -> loaded override exists          -> override value
  -> known unchanged cell            -> generator value

The search stops conservatively when it encounters unknown data. Another known detour might exist, but this implementation doesn't try to prove one while ignoring the unknown region. That behavior is explicit and testable.

The test primes the sample cache before editing, checks that the old path's revision becomes stale, unloads the modified chunk, then reloads it. The wall must still be present after reload. Edits to an unloaded modified chunk are rejected until its existing changes are available.

This is an in-memory simulation of a persistence lifecycle. It doesn't measure disk or network loading. Hash lookups have expected constant-time behavior in memory, but fetching missing data is additional work. Real save systems also need an authoritative index or an explicit unknown state for the index itself.

Generator reconfiguration, edits and load/unload operations invalidate the fixture's caches and revision. Before reusing a route, compare its revision with the current world revision. A larger system can track revisions per chunk and invalidate only affected routes. The example deliberately uses one conservative revision so stale data is easy to detect.

Use coarse guidance without trusting it as connectivity

For a long trip, a macro planner can suggest a corridor. The exact planner then checks the terrain inside it. In this fixture, the macro layer uses one noise octave and 32-cell spacing. The route is widened by one macro cell before refinement.

That is guidance. A point sample doesn't prove an entire macro cell is traversable, and dropping higher-frequency detail doesn't preserve every passage. The one-octave field also isn't an admissible estimate of the final weighted route cost.

The low-level A* keeps Manhattan distance as its heuristic because this fixture allows only cardinal movement and every step costs at least one. With these rules the heuristic is consistent, so its closed-state policy is valid. If you change the movement or cost model, revisit that argument.

These are single diagnostic queries, not repeated timing distributions. The counts include the coarse search, failed refinement and fallback work. The guided timer also includes its cache reset and phase orchestration. The detail-barrier fixture contains a gate outside the initial corridor. Refinement exhausts that corridor, then retries inside the full declared window using the remaining expansion budget.

The fallback makes that case recover, but it also costs work. And when a corridor succeeds, it can still exclude a cheaper route elsewhere. The guided method promises a legal route within its accepted domain. It has no general global-optimality or bounded-suboptimality guarantee.

For chunk portals and an explicit abstraction of local connectivity, use the existing large-map pathfinding guide. The original HPA* paper describes a hierarchy with precomputed local crossing information. A few low-frequency noise samples don't provide that same information.

Where Godot's built-in navigation fits

AStarGrid2D searches a finite region. You can use bounded grids per chunk or per active planning window. If you change the region and rebuild with update(), replay the terrain's solidity and weights. The API documents that reset.

The fixture measures the cost of constructing and populating progressively larger grids separately from the implicit query:

Each row is one setup measurement, with one terrain evaluation per cell during population. It shows the work of representing the selected region eagerly. It isn't a fair head-to-head query speed comparison, and it doesn't measure memory bytes. A reused grid amortizes that setup across later requests.

NavigationServer2D and NavigationServer3D work with navigation regions and maps. They don't infer missing navigation surfaces from your noise seed. Keep a bounded active representation, account for synchronization when regions change, and revalidate routes as needed. The NavigationMaps guide explains the map/region and synchronization model. This fixture doesn't benchmark navmesh streaming against the grid planners.

Coordinates still have limits

Integer keys avoid floating-point rounding within their range. They don't make that range infinite. Each Vector2i component is signed 32-bit, even in a double-precision engine build. For a larger logical address space, use 64-bit chunk components and bounded local cell coordinates, with checked arithmetic. See the Vector2i reference.

The search performs neighbor arithmetic in scalar integers, checks the 32-bit range, then constructs the next Vector2i. Its boundary test searches near the positive limit. Your Rect2i bounds and their end coordinates must also remain representable.

Sampling has a separate precision boundary. The verifier converts consecutive integers through PackedFloat32Array explicitly. 16_777_216 and 16_777_217 round to the same float32 value, while GDScript's scalar float distinguishes them. On the tested build, the two direct noise calls also returned the same sample, -0.072942890227. Equal noise outputs alone don't establish the width of every API argument or internal operation.

For chunk-local generation, define how neighboring chunks share boundary samples and how chunk identity enters the generator. Resetting coordinates at each chunk without that contract can repeat terrain or introduce seams. The translation fixture doesn't implement that generator.

Rendering and physics are another concern. Keep local scene coordinates near the active area, or evaluate the tradeoffs of a double-precision build for a large 3D world. Godot's large-world coordinates guide discusses precision and origin shifting. A pathfinding key doesn't fix scene precision on its own.

What about SDF, RRT and travel-time fields?

If your terrain already supplies a true signed distance field or a conservative distance bound, you can use it for clearance and local segment validation. For a finite-radius agent, evaluate clearance in the appropriate configuration space. A point-agent route through free cells doesn't establish that a larger body will fit.

Sphere-tracing-style steps can check a segment against a distance bound without uniformly sampling every small interval. They still don't choose which side of a mountain leads to the goal. An arbitrary scalar noise value isn't a safe step length, either. The distance-bound requirement comes from the original sphere tracing work.

Potential fields can help steer away from nearby obstacles, but local minima and narrow passages still need handling. Keep global route selection and local movement separate. None of these controllers is implemented or timed in the downloaded grid fixture.

RRT and PRM are worth considering when configurations are continuous or include motion constraints that don't fit a simple tile graph. Lazy PRM delays collision checks on proposed edges until they matter to a query. RRT* adds rewiring to improve solutions as sampling continues under its theoretical assumptions. Those asymptotic results don't promise a small node count or a frame-time bound for a particular game. See Karaman and Frazzoli.

Fast Marching can construct arrival-time fields on a selected domain, which can be useful when many agents share a destination. It still requires a domain and numerical work. A procedural world doesn't make solving the field free. The original Fast Marching paper is the relevant starting point if that matches your movement model.

Run the proof on your terrain

Download the standalone source and inspect the full verification receipt. Open project.godot for the two-panel scene. Press Space to switch cases. Run the small-query benchmark first, then the full checks:

godot47 --headless --path . --script res://tools/verify_infinite_world_small.gd
godot47 --headless --path . --script res://tools/verify_infinite_world.gd

godot47 is the local command used for the recorded Godot 4.7.2 executable. Use your engine executable's path if you don't have that alias.

The verifier checks 25 assertions, including weighted-cost agreement with native AStarGrid2D over 12 small seeded maps, independent path legality, translation, overlay invalidation, failure statuses and a scene smoke check. The source package is also rerun after extraction into a clean project. The small-query script separately checks translation, path legality and agreement with the native scene.

Keep the heap, generator and result contract visible when adapting the code. Sorting the whole frontier before each pop adds work that a binary heap avoids, but heap choice alone doesn't determine runtime. Record expanded nodes, generator samples, result status and path cost beside timing. You'll need all of them to tell a faster implementation from a query that stopped early or solved an easier problem.