Large Map Pathfinding in Godot

The short answer

A large world can run perfectly well with ordinary pathfinding. A much smaller one can stall every few seconds. If you've only looked at the dimensions of the level, that feels backwards.

The missing number is the search surface. Godot searches navigation polygons, edges, or grid cells. It doesn't care that your world happens to be 10,000 units wide if the useful graph is small. But give it thousands of tiny polygons, ask every agent for a new route in the same frame, then point one query at an unreachable island, and the search becomes expensive.

When I review a large-map hitch, I start with a less glamorous question: what work did this query actually make the engine do? That usually gets us further than reaching for a new algorithm on the first afternoon.

Start by shrinking the work around each query. Measure reachable and unreachable paths, count the polygons or cells that can be searched, and keep map synchronization separate from query time. If you're using NavigationServer, split the map into useful regions and filter out regions that can't belong to this route. Put a ceiling on pathological searches, and check whether a bounded result really reached the authored target.

If long routes are still too slow after that, HPA* is the next serious option. It searches a small graph of clusters and entrances first, then refines that coarse route through the low-level grid. You also have to measure its build and repair costs and prove that the refined path is still legal.

Here's the order I'd use. You may stop at step two if the measurements already explain the hitch.

1. Check how many path requests arrive in one physics tick.
2. Measure the searchable cells, polygons, and edges.
3. Time the query separately from NavigationServer synchronization.
4. Try a cleaner representation or a narrower region filter.
5. Add search limits and classify partial results.
6. Add hierarchy only if the remaining long-range search is still over budget.

What does large mean here?

Large isn't one metric. It can describe the graph, the crowd, the amount of streamed data, or just the coordinates. Those lead to different fixes.

It's tempting to put all five under “A* is slow.” That label doesn't tell you what to change. Maybe the query is fine and you're sending it 300 times. Maybe the path is fast but the map spent the frame reconnecting region edges. You need one more measurement before the story makes sense.

Measure the graph, then measure the frame

For a grid, record its dimensions, walkable-cell count, movement rules, terrain profile, and whether the target is reachable. On a NavigationServer map, record regions, polygons, total edges, vertex-merged edges, proximity edge connections, and free edges.

I use four authored query cases because one happy path can hide a lot. Warm the map first. Then collect a distribution, not the best stopwatch result you happened to get. Record median, p95, and maximum.

Where to look in the Godot debugger

Run a debug build and open Debugger → Monitors → Navigation Process. The Performance reference warns that some built-in monitors always return 0 in a release export, which is why the build type matters here. The navigation debug guide defines that monitor as the NavigationServer update step: map changes, regions, agents, and avoidance. It doesn't include independent path-query time, so time NavigationServer2D.query_path() or the worker job yourself.

The Navigation group also exposes polygon and edge composition. The labels below follow the exact Godot 4.7.1 monitor identifiers. Watch them together when you stream a chunk.

A jump in proximity edge connections or free edges, paired with a Navigation Process spike, points toward expensive region connection work. Vertex merging is the cheap pass; proximity edge connection checks the remaining free edges by distance and angle. I wouldn't call Edges Connected the bottleneck from the count alone, but it's the first ratio I'd inspect when loading chunks hurts.

Some built-in monitors update with a delay of up to one second. Treat the snapshot as composition evidence, not as a per-query timer.

• Navigation Process
• Under Navigation 2D, Regions and Polygons
• Under Navigation 2D, Edges Merged, Edges Connected, and Edges Free

func sample_navigation_2d() -> Dictionary:
    return {
        "navigation_step_ms":
            Performance.get_monitor(Performance.TIME_NAVIGATION_PROCESS) * 1000.0,
        "regions":
            int(Performance.get_monitor(Performance.NAVIGATION_2D_REGION_COUNT)),
        "polygons":
            int(Performance.get_monitor(Performance.NAVIGATION_2D_POLYGON_COUNT)),
        "edge_merges":
            int(Performance.get_monitor(Performance.NAVIGATION_2D_EDGE_MERGE_COUNT)),
        "edge_connections":
            int(Performance.get_monitor(
                Performance.NAVIGATION_2D_EDGE_CONNECTION_COUNT
            )),
        "free_edges":
            int(Performance.get_monitor(Performance.NAVIGATION_2D_EDGE_FREE_COUNT)),
    }

What the proof measured

I built a focused PathForge fixture instead of borrowing numbers from another project. It uses a 384×384 four-way grid with 131,572 walkable cells, 144 clusters of 32×32, 528 abstract nodes, and 1,976 directed abstract edges. The run used Godot 4.7.1 a13da4feb on a Ryzen 5 2600X under Windows. Each method had 12 warmup queries followed by 120 timed queries, 30 for each fixed route.

This isn't an open field with scattered obstacles. The fixture is a 12×12 layout of 144 room-like 32×32 clusters. Every internal cluster boundary is also an authored two-cell-thick wall, one cell on either side of the boundary, with exactly one single-cell gate. The hierarchy therefore gets an unusually clean model of the real topology: one entrance represents each legal crossing. Meanwhile, a Manhattan estimate can keep pointing a flat A* toward the goal while the legal route has to detour to a narrow gate.

The low-level fixture setup took 9.649 ms, then the hierarchy build took 39.799 ms; the full setup was 49.457 ms. Each build figure is one observation, not a distribution. Rebuilding one changed cluster took a 0.103 ms median and 0.125 ms p95 across 40 repairs, and the old edge revisions failed validation before the replacements were used.

These are local micro-benchmark results for this map and machine, not a general HPA* speedup. The scene, raw samples, source hashes, and exact protocol stay together in the JSON receipt; without that context we'd be comparing two anecdotes with decimal places.

Pick the representation before tuning it

Godot gives you several different search surfaces. A physically large navmesh can be cheap if a few polygons cover it. A high-resolution grid can be expensive even when it fits on one screen. And a navmesh made from one tiny polygon per tile may give you the density of a grid plus the synchronization work of regions.

AStarGrid2D.region is also a storage boundary, not a streaming system. Changing the region and calling update() clears solidity and weight data. You'll need a stable grid, several independently owned grids, or a higher-level graph that knows which local grid owns each chunk.

Partition the navigation map without making confetti

A NavigationRegion2D contributes local navigation data to a map. Regions that share one map still form one pathfinding world. Splitting a map into chunks only helps a query when you can leave irrelevant chunks out, or when unloaded chunks aren't on the map at all.

Godot 4.7's query parameters give you included_regions and excluded_regions. An empty include list means every region is eligible. A non-empty include list makes every non-included region ineligible. If the same region appears in both lists, exclusion wins.

That last rule is easy to miss when two systems build the filters. If a streaming policy includes a corridor while a door policy excludes one region in it, the door policy wins. Log both lists when a route mysteriously stops early.

Before and after: one map, narrower query

The corridor has to come from somewhere you own: a coarse route, an authored streaming lane, or an expanding ring policy. Including only the start chunk won't produce a complete cross-map path.

Reuse query objects, but give each owner its own pair

Godot recommends reusing a parameter/result pair because repeated allocation has a cost. That doesn't mean one global pair can serve several worker threads. The pair is mutable. Give the main thread or each worker its own context and don't use that context concurrently.

The example receives the map RID instead of calling get_world_2d() from a worker. Capture that RID and duplicate the chunk-to-RID mapping on the main-thread owner before dispatch. It also resets excluded_regions because the context is reused. The empty-list guard matters too: Godot interprets an empty include list as every region, so a failed chunk lookup shouldn't quietly turn into a full-map search.

A non-empty path still isn't proof that you reached the destination. Region filters and search limits can return a useful partial route. Pick the endpoint tolerance from your movement scale; one pixel may be generous in one game and nonsense in another.

class PathQueryContext:
    var parameters := NavigationPathQueryParameters2D.new()
    var result := NavigationPathQueryResult2D.new()


func query_path_in_chunks(
        context: PathQueryContext,
        map: RID,
        regions_by_chunk: Dictionary[Vector2i, RID],
        start: Vector2,
        target: Vector2,
        allowed_chunks: Array[Vector2i]) -> PackedVector2Array:
    if NavigationServer2D.map_get_iteration_id(map) == 0:
        return PackedVector2Array()

    var included: Array[RID] = []
    for chunk_id in allowed_chunks:
        if regions_by_chunk.has(chunk_id):
            included.push_back(regions_by_chunk[chunk_id])

    # An empty include list means "all regions", not "no regions".
    if included.is_empty():
        return PackedVector2Array()

    var parameters := context.parameters
    parameters.map = map
    parameters.start_position = start
    parameters.target_position = target
    parameters.included_regions = included
    parameters.excluded_regions = []
    parameters.metadata_flags = (
        NavigationPathQueryParameters2D.PATH_METADATA_INCLUDE_NONE
    )

    NavigationServer2D.query_path(parameters, context.result)
    return context.result.get_path()


func reaches_authored_target(
        path: PackedVector2Array,
        target: Vector2,
        tolerance: float = 1.0) -> bool:
    if path.is_empty():
        return false
    return path[-1].distance_to(target) <= tolerance

Search limits are a result contract

NavigationPathQueryParameters2D has two search ceilings. In Godot 4.7.1, path_search_max_polygons defaults to 4096. path_search_max_distance defaults to zero.

The class reference says zero or below counts as unlimited for both properties. The 4.7.1 setter and query implementation agree with the effective behavior: polygon limits are enabled only above zero, while the distance setter clamps negative values to zero before the query runs.

When a ceiling stops the search, Godot rebuilds a path to the closest polygon it found so far. That may be exactly what you want for streamed movement. It may also send the actor toward an awkward first segment because the search stopped before finding the better corridor. Record endpoint error and first-segment direction too.

path_return_max_length and path_return_max_radius do something else. They clip the returned path after the search. You'll get a shorter movement plan, but you haven't made the underlying search cheaper.

Filters are cheaper than rebuilding policy into the map

Navigation layers let one query ignore regions that don't share its layer mask. They're a good fit for a small number of stable movement classes: ground, water, flight, or an access mode.

Use explicit region lists when the eligible chunks change per request. The 32-layer mask is intended for stable navigation categories, not per-chunk storage. Toggling regions to serve one query creates synchronization work for everyone sharing the map.

NavigationLink2D and NavigationLink3D are useful for ladders, jumps, teleports, ferries, and other authored crossings. They add edges to the normal navigation graph, but they don't build the abstract graph that HPA* needs.

Stream the resource and budget the map update separately

If your chunks live as PackedScene or navigation resources on disk, a plain load() blocks the calling thread. Godot's background-loading guide uses ResourceLoader.load_threaded_request(), a status check, and load_threaded_get() once the resource is ready. Calling load_threaded_get() too soon can still block.

The background request moves resource loading off the calling thread. It doesn't make scene-tree mutation or NavigationServer synchronization disappear. Instantiate and attach the scene from the main-thread owner, then expect the navigation map to synchronize after the region joins it. If the chunk bakes a navmesh at runtime, use the navigation baking APIs' background path as well.

You can remove the file-loading hitch and still see a later Navigation Process spike. That's the map connecting the new data. Capture both events instead of averaging them into one mysterious streaming time.

const CHUNK_PATH := "res://world/chunks/chunk_07_12.tscn"


func request_chunk() -> Error:
    return ResourceLoader.load_threaded_request(CHUNK_PATH)


func try_attach_chunk(parent: Node) -> bool:
    var status := ResourceLoader.load_threaded_get_status(CHUNK_PATH)
    if status != ResourceLoader.THREAD_LOAD_LOADED:
        return false

    var packed := ResourceLoader.load_threaded_get(CHUNK_PATH) as PackedScene
    if packed == null:
        return false

    var chunk := packed.instantiate()
    parent.add_child(chunk)
    return true

The map iteration ID is an observation, not your cache revision

NavigationServer2D.map_get_iteration_id() returns zero before the map has ever synchronized. It increases after synchronized map changes. And the 4.7.1 class source adds the awkward detail that proves why it isn't a permanent cache key: the value wraps back to 1 when it reaches its range limit.

Use it to notice that the server caught up, or to trigger a conservative cache clear. For durable route ownership, keep revisions that mean something to your game.

A closed door and a changed terrain profile shouldn't have to look identical to the cache just because both advanced the engine's iteration counter. Existing paths also aren't rewritten for you when a region changes. Your movement code still decides which routes are stale and how quickly agents ask again.

cache key =
    topology_revision
    + movement_profile_revision
    + start_bucket
    + target_bucket
    + query_policy

About map_force_update()

There are two separate statements in the Godot 4.7.1 reference, and they shouldn't be blurred together.

The deprecation message and method description say different things. The deprecation message says map_force_update() is incompatible with asynchronous updates and can only be used in a single-threaded context at your own risk. Separately, the method description says an immediate update flushes the NavigationServer command queue, locks the server, and can severely affect performance.

That's enough reason to keep it out of the normal streaming path. Let the queued change synchronize, check the iteration, and query on a later frame. If you really need a forced single-threaded transition, treat it as an exceptional state change and measure the whole frame.

One map or several?

Regions on one navigation map can form one continuous route. Separate maps are isolated, and a built-in query won't cross from one to another.

Keep one map when loaded chunks need an ordinary end-to-end path and the combined polygon graph is still affordable. Use separate maps when hard isolation is the point: different floors, locomotion worlds, streaming instances, or game states that shouldn't connect.

Once you split maps, you own the hand-off. The high-level plan has to choose the next gateway and map before the local query can solve the current leg.

Large maps make request storms easier to notice

Even a healthy query can hitch when every unit asks for it together. If your group order writes 300 targets in one physics tick, shaving a little off each search may not save that frame.

Three ordinary mistakes can create the burst.

You can coalesce newer targets, spread requests over several frames, and inspect the returned endpoint instead of paying for a separate reachability call. The hundreds-of-units guide has the full scheduling policy. The 10,000-agent case study covers a different case where many agents share the same destination field.

• A moving target is assigned again every frame.
• Code runs a reachability query and then immediately runs the real query.
• Every invalidated agent repaths in the same tick.

Threading changes throughput, not search size

NavigationServer2D and NavigationServer3D queries are thread-safe and can run in parallel. The helper objects AStar2D, AStar3D, and AStarGrid2D aren't safe for simultaneous use by several threads. Give each helper one owner, or put a mutex around it and include that wait in your timing.

There's one source-level wrinkle around navigation/pathfinding/max_threads. Godot 4.7.1 registers a configured default of 4. That's not a promise of four simultaneous slots on every machine. NavMap2D and NavMap3D read the setting, use the processor count when the value is negative, cap a larger value to the processor count, and enforce a minimum of one.

The effective slot count is hardware-capped. Extra configured capacity also costs memory and synchronization because each slot needs prepared map data. Measure throughput on your target hardware; the number in ProjectSettings is only the starting point.

And keep the earlier ownership rule: each worker needs its own mutable PathQueryContext. Reusing objects means reusing them serially within that owner, not sharing one pair across the pool.

When the low-level search is still too large: HPA*

HPA* adds a coarse route above your grid. You split the low-level map into clusters, find legal crossings along their borders, and turn those crossings into abstract nodes. Long queries search that smaller entrance graph first. Then you run local searches only through the clusters selected by the coarse route.

A NavigationRegion2D chunk can line up with an HPA* cluster, but it doesn't become one automatically. The missing piece is the abstract graph and the cached local paths between entrances.

A small foundation in GDScript

This isn't the whole algorithm. It is the part that keeps an abstract edge tied to the low-level route and revisions that justify its cost.

The downloadable proof project fills in the missing pieces: entrance creation, cluster-local searches, an abstract A* heap, start and goal connections, witness concatenation, legality checks, and comparison against the exact low-level route. The smaller types below are the part you'll usually adapt first.

local_path is the refinement witness. It tells you which cells produced the cached cost instead of leaving a float with no explanation. An inter-cluster edge usually names both neighboring clusters as owners. An intra-cluster edge names the one cluster whose local search created it.

You'll still need entrance discovery, low-level A*, temporary start and goal connections, abstract A*, and path concatenation. But those pieces now have a place to store their receipts.

class_name HpaGraph2D
extends RefCounted


class AbstractNode:
    var id: int
    var cluster_id: Vector2i
    var entrance_id: int
    var cell: Vector2i

    func _init(
            p_id: int,
            p_cluster_id: Vector2i,
            p_entrance_id: int,
            p_cell: Vector2i) -> void:
        id = p_id
        cluster_id = p_cluster_id
        entrance_id = p_entrance_id
        cell = p_cell


class AbstractEdge:
    var to_node_id: int
    var cost: float
    var local_path: Array[Vector2i]
    var movement_profile: StringName
    var owner_clusters: Array[Vector2i]
    var owner_revisions: Array[int]

    func is_valid(current_revisions: Dictionary) -> bool:
        if owner_clusters.size() != owner_revisions.size():
            return false

        for index in owner_clusters.size():
            var cluster_id := owner_clusters[index]
            if int(current_revisions.get(cluster_id, -1)) != owner_revisions[index]:
                return false
        return true


var nodes: Dictionary[int, AbstractNode] = {}
var edges_from: Dictionary[int, Array] = {}
var cluster_revisions: Dictionary[Vector2i, int] = {}

Invalidate changed clusters before you trust the cache

A door near a boundary can affect both sides. Pass every affected cluster into one invalidation call, advance its revision, remove owned edges, and queue the clusters for rebuild.

The code deliberately removes both inter- and intra-cluster edges by ownership. The rebuild step has to rescan boundary entrances and recreate local witnesses before a query may use the changed clusters again. If your graph searches while a repair is pending, either exclude those clusters or fall back to the low-level reference.

signal clusters_need_rebuild(cluster_ids: Array[Vector2i])


func invalidate_clusters(changed: Array[Vector2i]) -> void:
    if changed.is_empty():
        return

    var changed_set: Dictionary[Vector2i, bool] = {}
    for cluster_id in changed:
        changed_set[cluster_id] = true
        cluster_revisions[cluster_id] = (
            int(cluster_revisions.get(cluster_id, 0)) + 1
        )

    for from_node_id in edges_from.keys():
        var kept: Array[AbstractEdge] = []
        for edge: AbstractEdge in edges_from[from_node_id]:
            var touches_change := false
            for owner_cluster in edge.owner_clusters:
                if changed_set.has(owner_cluster):
                    touches_change = true
                    break
            if not touches_change:
                kept.push_back(edge)
        edges_from[from_node_id] = kept

    clusters_need_rebuild.emit(changed.duplicate())

Build, query, refine

The full path request follows six phases. If start and goal are in the same cluster, try the direct low-level route too. That avoids an unnecessary trip through the entrance graph.

The original HPA* paper reported substantial search savings with near-optimal paths on its benchmark maps. Those results explain why the technique exists; they aren't our benchmark. Dynamic variants make another trade: more stored work can reduce query time, while frequent topology repairs move the break-even point in the other direction.

Measure build time, repair time, abstract search, refinement, memory, and end-to-end latency separately.

1. Find the start and goal clusters.
2. Run local searches from the start and goal to every reachable entrance in their own clusters. These become temporary abstract edges.
3. Search the abstract graph.
4. Concatenate the cached local witnesses selected by that abstract route.
5. Remove duplicate join cells and verify every low-level step.
6. Compare the final endpoint and, in the proof scene, compare cost with a low-level reference search.

Failure cases worth keeping in the demo

The receipt should record completion, endpoint error, legality, and reference cost alongside query time.

A practical pre-ship check

Before you call the large-map work done, I would want answers to these questions. If one answer is “not yet,” keep that limitation visible in the result.

• Did you measure a long unreachable route as well as a reachable one?
• Can you separate query time from Navigation Process?
• Do filtered and bounded paths report whether they reached the real target?
• Can you explain every cache revision in game terms?
• Does each worker own its query objects?
• Does an HPA* edge carry the low-level path and revisions behind its cost?
• Does the refined route pass a low-level legality and cost check?
• Have you measured build and repair often enough to find the break-even point?
• Did you test coordinate precision separately from pathfinding time?