Navigation agent issues in a chunk-based Spherical World

[egod1537]

Environment

• Unity: 2022.3.62f2

• A* Pathfinding Project Pro: 5.4.5

• World type: Spherical World

---

Goal

I am implementing a navigation system for a Spherical World as described in the A* Pathfinding Project documentation,
where agents can walk on walls and ceilings, similar to Deep Rock Galactic.

The world is built using a procedural mesh with a chunk-based structure.

• Geometry is generated via Marching Cubes

• Each chunk owns its own Navmesh Graph

• Agents must be able to navigate seamlessly across chunk boundaries

---

Navmesh setup overview

• Procedurally generated meshes are injected directly into Navmesh Graphs

• Marching Cubes generation includes padding at chunk borders before baking

• Boundary triangles between adjacent chunks are topologically identical

• In theory, navmeshes across chunks should connect seamlessly
  

  

---

Attempt 1

Direct stitching using GraphNode.Connect

Approach

• Adjacent chunk Navmesh Graphs are stitched using GraphNode.Connect()

• At the graph search level, all chunks behave as a single navigation graph

Result

AIPathAlignedToSurface

• Path calculation and movement across chunks work correctly

• However, traversal over surfaces with bends greater than 90° is not possible

• I understand this limitation is intentional by design

FollowerEntity

• Wall and ceiling traversal itself works

• However, the agent stops at chunk boundaries

• The path is continuous, but runtime movement fails at the boundary

Analysis

• GraphNode.Connect() does not provide sufficient portal / surface transition data
  required by FollowerEntity

• As a result:

  • Pathfinding succeeds

  • Local movement logic treats the connection as incomplete

Code snippet

graphA.GetNodes(node =>
{
    Vector3 pos = (Vector3)node.position;
    if (!overlapBounds.Contains(pos)) return;

    NNInfo info = AstarPath.active.GetNearest(pos, constraint);
    if (info.node == null) return;

    float distSqr = (info.position - pos).sqrMagnitude;
    if (distSqr < SQR_STITCH_DIST_THRESHOLD)
    {
        GraphNode targetNode = info.node;

        if (targetNode.position == node.position &&
            !node.ContainsOutgoingConnection(targetNode))
        {
            uint cost = (uint)(targetNode.position - node.position).costMagnitude;
            GraphNode.Connect(
                node,
                targetNode,
                cost,
                OffMeshLinks.Directionality.TwoWay
            );
        }
    }
});

---

Attempt 2

Stitching using NodeLink2

Approach

• Instead of GraphNode.Connect(), NodeLink2 objects are created at chunk boundaries

• These act as explicit portals between navmesh surfaces

Result

FollowerEntity

• Successfully navigates across chunk boundaries

• Works correctly even across surface transitions exceeding 90°

Drawbacks

• Each NodeLink2 creates two GameObjects

• In a procedural, chunk-based Spherical World:

  • The number of GameObjects grows rapidly

  • This becomes impractical for performance and management

• In the worst case, this can result in up to ~60,000 NodeLinks
  (average is lower, but the upper bound is problematic)

Code snippet

graphA.GetNodes(node =>
{
    Vector3 pos = (Vector3)node.position;
    if (!overlapBounds.Contains(pos)) return;

    TriangleMeshNode triNode = node as TriangleMeshNode;

    NNInfo info = AstarPath.active.GetNearest(pos, constraint);
    if (info.node == null) return;

    float distSqr = (info.position - pos).sqrMagnitude;
    if (distSqr < SQR_STITCH_DIST_THRESHOLD)
    {
        info.node.GetConnections(adjNode =>
        {
            TriangleMeshNode triAdjNode = adjNode as TriangleMeshNode;

            if (ShareEdgeByPosition(triNode, triAdjNode))
            {
                if (!node.ContainsOutgoingConnection(adjNode))
                {
                    NavPortalFactory.CreatePortal(
                        (Vector3)triNode.position,
                        (Vector3)triAdjNode.position
                    );
                }
            }
        });
    }
});

---

Core questions

Under the following conditions:

• Spherical World navigation

• Chunk-based Navmesh Graphs

• Using FollowerEntity with A*PPP

1. Is there a recommended or intended approach to allow FollowerEntity
   to traverse chunk boundaries without creating large numbers of NodeLink2 GameObjects?

2. Alternatively:

   • Is there a way to provide the portal / surface transition data
     required by FollowerEntity directly at the GraphNode level?

   • Is there a non-GameObject-based connection mechanism
     that is functionally equivalent to NodeLink2?

Any guidance would be greatly appreciated.

[aron_granberg]

Hi

Simplest solution, if possible, is to generate all chunks up front and put them in the same Navmesh Graph. Then things will work automatically.

If not. Are all chunks the same size? If so, you could use a recast graph together with the graph.ReplaceTile method ( ReplaceTile - A* Pathfinding Project ). If you set up a recast graph with the exact tile size as your chunks, and then call ReplaceTile with a mesh that fit the tile bounds exactly (even a millimeter off will make it not work), then the chunks will connect to each other automatically.

See also GetTileBounds - A* Pathfinding Project , which can be useful for debugging.

You may also be interested in ReplaceTiles - A* Pathfinding Project , which is a slightly higher level abstraction. It is likely nicer to work with, though, as it will even resize the graph automatically for you.

[egod1537]

Hi, thanks for the detailed reply.

To clarify my situation a bit more and make sure I understand the intended usage correctly, I would like to provide some additional context and ask a follow-up question.

1. The world is very large, so I am using a chunk streaming system where only chunks within a certain radius around the player are active.
   Because of this, putting all chunks into a single navmesh upfront is not ideal, since changing or streaming a single chunk would require rebuilding a very large mesh.

2. All chunks are the same size.
   The logical chunk size is 16³, and during marching cubes generation I use padding (18³) to ensure seamless boundaries.
   If needed, I can adjust padding/culling so the final generated mesh fits the chunk bounds exactly.

3. Agents must be able to walk on walls and ceilings (using AIPathAlignedToSurface / FollowerEntity).
   Because of this, using a RecastGraph (which assumes a fixed up direction) does not seem viable.
   Currently, I inject the generated meshes directly into NavMeshGraph instances.

4. Regarding ReplaceTile / ReplaceTiles:
   From the documentation and examples, these APIs appear to be primarily described in the context of RecastGraph.
   I would like to confirm:

   • Is ReplaceTile(s) considered an intended and supported approach for NavMeshGraph as well, and is its behavior reliable in production?

   • If ReplaceTile(s) is not recommended for NavMeshGraph, is there a recommended pattern for streaming or stitching chunk-based navmeshes so that FollowerEntity can traverse chunk boundaries correctly, without creating a large number of NodeLink2 GameObjects?

Any guidance on the intended design or recommended approach for this kind of setup would be greatly appreciated.

[aron_granberg]

Hi

1. Ok. But what is very large? There are people using this package with navmeshes on the order of 10x10km. If you can have the meshes upfront, it’s usually better. But if you are regularly changing chunks, this would not work.
2. Oki
3. You’ll not be able to use the recast graph to generate the navmesh itself, but you could use the tile-based nature of it, together with ReplaceTiles. I remembered that there is one place in the code that you’d need to change, though. You’ll have to change the implementation of RecastGraph.RecalculateNormals so that it returns false instead of true. Otherwise walking on walls will not work.
4. A RecastGraph inherits from a NavmeshGraph under the hood, but they have some differences in how they handle tiling (the recast graph does, but the navmesh graph doesn’t). You can use the tiling feature of the recast graph, but replace the contents of each tile with whatever you want. One limitation is that the tiling is only along the X and Z axes of the graph. If you have multiple chunks that are above/below each other, then you’ll need to combine them into a single mesh. You’ll not be able to use ReplaceTile on a navmesh graph, since it considers the whole graph to always be a single “tile”.

The code for the NavmeshPrefab component may be interesting for you as reference code when implementing this.

[egod1537]

The project I am working on targets a near-infinite world where terrain can be dynamically destroyed and modified, so pre-baking the entire navmesh upfront is not a realistic option in my case.

Through your response, I learned for the first time that it is possible to keep the RecastGraph’s tiling structure while replacing the contents of each tile with a custom mesh. This approach seems like it could be a viable alternative for my current situation. To support this, I believe that moving away from an XYZ-based chunk streaming model and transitioning to an XZ-based tile streaming structure is a reasonable choice, even if it involves some structural trade-offs.

I also understand the limitation that tiling is only supported along the XZ axes, and that chunks stacked vertically need to be merged into a single mesh. When applying this approach, I will also take into account the need to modify RecastGraph.RecalculateNormals so that it returns false.

I will try applying the suggested solution and follow up with results or any additional issues I encounter. Thank you for the valuable insights.