NavMesh.CalculatePath & NavMeshAgent.CalculatePath return not full path

I was performing several NavMesh performance tests and occasionally found out that in case of long paths both mentioned functions (NavMesh.CalculatePath & NavMeshAgent.CalculatePath) return only part of the path. Here is illustration with explanation:


this terrain is 2x2 kilometres
green sphere is start point of the path
orange sphere in top right corner is destination point
magenta cube is NavMeshAgent
green multi-line is the path which NavMesh.CalculatePath returned

I have tested how will NavMeshAgent behave in such cases:
When Agent riches the end of that “half path” it stops. To make it move to the destination point I have to call NavMeshAgent.ResetPath and then SetDestination again. After this Agent find the path to the destination and reach it.

When this happens - path parameters could be completely different (17 corners, 26 corners, 1180 meters, 1934 meters etc.)

So, is it intentional behaviour or a bug?
If it is intentional, then why it is not documented? (at least I didn’t find anything about such behaviour)

I also have a problem with that!!!

Hello,

Same problem here, all NavMeshPath returned by “NavMesh.CalculatePath” have 26 corners max…We (the team) are very stuck with this. Did you find a solution or an answer ?

Thanks :slight_smile:

Nouvel élément : En changeant les paramètres du Baking, la longueur change mais une erreur survient toujours, le “NavMesh.CalculatePath” retourne un “PathPartial” en status…Je continue mes recherches.

Hello, Eric

I din’t really search for solution, because it was not a critical problem for us in that moment and I still haven’t lost face in Unity answering my question.

As for your problem… When I contemplated what we can possibly do if we will require to calculate paths through whole location, I have several thoughts in mind:

  • check if your agent is (not moving && !NavMeshAgent.path.status.PathComplete && still not in the destination point)
    if all this is true then call NavMeshAgent.ResetPath and then SetDestination again.
  • another option is to use some kind of checkpoints, and search path between them. Instead of searching for the whole path at once
1 Like

Hi everybody,
Same problem here for me in 2019… The Navmesh.CalculatePath() Always return as partial with various number of corners and length … (35 corners max for me …)

I’m working with a NavmeshSurface component, not with the built-n NavMesh system.

Someone has an idea ? I need to precompute long navmeshpaths …

Thks

I had the same problem, checkout this workaround and let me know if you have any questions. You might need to change the constant values depending on the size of your navmesh. For performance reason you might also put this into a coroutine, depending on the size of your terrain.

private const int MAX_PATH_DISTANCE = 30;
private const int MAX_CORNERS = 512;
private const int MAX_TRIES = 3;
private static Vector3[] m_pathCorners = new Vector3[MAX_CORNERS];

public static int CalculatePath(Vector3 _start, Vector3 _target, NavMeshQueryFilter _filter, Vector3[] _path, int _startIndex = 0, int _numTries = 0)
{
    if (_numTries > MAX_TRIES || _startIndex >= m_pathCorners.Length)
        return -1;
 
    var startPosOk = GetNavMeshPosition(_start, _filter.areaMask, MAX_PATH_DISTANCE, out Vector3 startPos);
    var endPosOk = GetNavMeshPosition(_target, _filter.areaMask, MAX_PATH_DISTANCE, out Vector3 targetPos);

    // this can happen when the navmesh is still being backed or positions are outside the navmesh -> maybe increase MAX_PATH_DISTANCE
    if (!startPosOk || !endPosOk)
        return -1;

    NavMesh.CalculatePath(startPos, targetPos, _filter, m_navMeshPath);

    switch (m_navMeshPath.status)
    {
        case NavMeshPathStatus.PathPartial:
        {
            var numCorners = m_navMeshPath.GetCornersNonAlloc(m_pathCorners);
            Array.Copy(m_pathCorners, 0, _path, _startIndex, numCorners);
            var lastPos = m_navMeshPath.corners[m_navMeshPath.corners.Length - 1];
            if (Math.Abs(lastPos.x - targetPos.x) < 0.5f && Math.Abs(lastPos.z - targetPos.z) < 0.5f)
                return _startIndex + numCorners;

            return CalculatePath(lastPos, _target, _filter, _path, _startIndex + numCorners, ++_numTries);
        }
        case NavMeshPathStatus.PathComplete:
        {
            var numCorners = m_navMeshPath.GetCornersNonAlloc(m_pathCorners);
            Array.Copy(m_pathCorners, 0, _path, _startIndex, numCorners);
            return _startIndex + numCorners;
        }
        default:
            return -1;
    }
}
2 Likes

It would be nice if someone from Unity would take the time to look at where this maximum distance comes from. And explain to us what it is based on? I’ve been looking for a way to increase it for 2 days without success, because I don’t have access to the source code :confused:

1 Like

DwinTeimlon post didn’t have the code for GetNavMeshPosition so I have added what I used. Also this part NavMesh.CalculatePath(startPos, targetPos, _filter, m_navMeshPath); should be _filter.areaMask or the path seems to not care about area cost.

 bool GetNavMeshPosition(Vector3 _position, int _areaMask, float _maxDistance, out Vector3 _navMeshPosition)
    {      
        NavMeshHit hit;

        // Sample points around the input position to find the nearest valid NavMesh point
        if (NavMesh.SamplePosition(_position, out hit, _maxDistance, _areaMask))
        {
            _navMeshPosition = hit.position;
            return true;
        }

        _navMeshPosition = Vector3.zero; // Or some default value
        return false;
    }
int CalculatePath(Vector3 _start, Vector3 _target, NavMeshQueryFilter _filter, Vector3[] _path, int _startIndex = 0, int _numTries = 0)
    {
        Vector3[] m_pathCorners = new Vector3[MAX_CORNERS];
        NavMeshPath m_navMeshPath = new NavMeshPath(); // You need to initialize this NavMeshPath

        if (_numTries > MAX_TRIES || _startIndex >= m_pathCorners.Length)
            return -1;

        var startPosOk = GetNavMeshPosition(_start, _filter.areaMask, MAX_PATH_DISTANCE, out Vector3 startPos);
        var endPosOk = GetNavMeshPosition(_target, _filter.areaMask, MAX_PATH_DISTANCE, out Vector3 targetPos);

        if (!startPosOk || !endPosOk)
            return -1;

        NavMesh.CalculatePath(startPos, targetPos, _filter.areaMask, m_navMeshPath);

        switch (m_navMeshPath.status)
        {
            case NavMeshPathStatus.PathPartial:
                {
                    var numCorners = m_navMeshPath.GetCornersNonAlloc(m_pathCorners);
                    Array.Copy(m_pathCorners, 0, _path, _startIndex, numCorners);
                    var lastPos = m_navMeshPath.corners[m_navMeshPath.corners.Length - 1];
                    if (Mathf.Abs(lastPos.x - targetPos.x) < 0.5f && Mathf.Abs(lastPos.z - targetPos.z) < 0.5f)
                        return _startIndex + numCorners;

                    return CalculatePath(lastPos, _target, _filter, _path, _startIndex + numCorners, ++_numTries);
                }
            case NavMeshPathStatus.PathComplete:
                {
                    var numCorners = m_navMeshPath.GetCornersNonAlloc(m_pathCorners);
                    Array.Copy(m_pathCorners, 0, _path, _startIndex, numCorners);
                    return _startIndex + numCorners;
                }
            default:
                return -1;
        }
    }

Then how I used it to draw a line render for a long distance.

 private IEnumerator DrawpathtoCheckpoint()
    {
        WaitForSeconds Wait = new WaitForSeconds(PathUpdateSpeed);     

        bool destinationReached = false;

        while (nearestOBJ != null && !destinationReached)
        {
            totalDistance = 0;
            NavMeshQueryFilter filter = new NavMeshQueryFilter();
            filter.areaMask = NavMesh.GetAreaFromName("Road") | NavMesh.GetAreaFromName("Terrain");

            Vector3[] pathCorners = new Vector3[MAX_CORNERS];

            //using the code from DwinTeimlon
            int pathCornerCount = CalculatePath(Player.position, nearestOBJ.transform.position, filter, pathCorners);

            if (pathCornerCount > 0)
            {
                Path.positionCount = pathCornerCount;

                for (int i = 0; i < pathCornerCount; i++)
                {
                    Path.SetPosition(i, pathCorners[i] + Vector3.up * PathHeightOffset);

                    if (i > 0)
                    {
                        totalDistance += Vector3.Distance(pathCorners[i - 1], pathCorners[i]);
                    }
                }

                if (Vector3.Distance(pathCorners[pathCornerCount - 1], nearestOBJ.transform.position) <= 0.1f)
                {
                    destinationReached = true;

                    // Set the destination to the last point on the calculated path
                    Vector3 lastPoint = pathCorners[pathCornerCount - 1];
                    nearestOBJ.transform.position = lastPoint;
                }

                // Display the total distance
                distanceToGoal.text = totalDistance.ToString("F1") + "M";
            }
            else
            {
                Debug.LogError($"Unable to calculate a path on the NavMesh between {Player.position} and {nearestOBJ.transform.position}.");
            }

            yield return Wait;
        }
    }
1 Like

I’ve recently looked into this topic, so I might have an explanation as to why the situation happens.

The problem with requesting paths over long distances is that Unity’s navigation system stops searching for any one path after going through a few thousands of navigation nodes (you can think of the nodes as “turns”). The algorithm always prefers a general direction towards the destination, but if the walkable space is rather sinuous in the game scene, or it spreads to long distances, then it takes more “effort” to go off the straight direction and search sideways, or farther. This can lead it to run out of the limited buffer memory assigned for this task, in which case it reports only the best partial path it had found that far.
Unfortunately you cannot change yourself the maximum amount of memory that the algorithm can use. Its size is currently hard-coded into the engine. If possible, you can try to help the search use this buffer more efficiently by adding walkable corridors through any large areas that are not walkable.

Since the number of polygons (i.e. nodes) in the NavMesh is an important factor that leads to long paths not being completely resolved, you can try instead to simplify the NavMesh a bit. You have some leverage to do that through two parameters used when building the NavMesh:

  • Voxel Size - you’ll want to increase it in order for the NavMesh to hopefully get larger polygons, thus fewer of them. In that case the NavMesh will lose accuracy at the edges (near the walls) and when approximating the elevation;
  • Tile Size - you’ll want to increase it so that the NavMesh is less fragmented and the polygons can be larger. In that case you trade off the speed at which a change in the scene propagates as a change to the NavMesh (e.g. obstacles enable carving). A local modification in the scene will affect an entire NavMesh tile at once.
    The documentation for these parameters is here: NavMesh Surface component reference | AI Navigation | 2.0.4 .

NavMesh Obstacles that carve the NavMesh are easy to use, and rather fast, but they generally fragment the NavMesh tiles into more polygons than before (example). The more obstacles there are in an area, carving close to each other, the bigger the chance for sections of the NavMesh being broken into more NavMesh polygons. I’d recommend “Carving” only for temporary obstacles in the game. For long-term modifications of the NavMesh I’d recommend placing “Not Walkable” NavMeshModifiers in the scene, as obstacles, and updating the NavMesh at runtime.

Another factor to consider is the balance of area costs. It might help if you keep the costs within similar orders of magnitude (e.g. the highest cost could be 10-20 times higher than the lowest cost). For example, if an area is on the straight path from the start to the destination but it has a cost much higher than the surrounding areas (e.g. 200 vs 1) then the path search might go even far away into the sides in the hope that it will find a route with a cost lower than the one of the straight path. In intricate maps, extensive searches like these can exhaust the space in the buffer before even getting close to the destination that’s seemingly not very far away.

Once you’ve found the right balance between NavMesh complexity, accuracy and speed of update, suitable for your game, you could try to avoid the problem with the partial path by setting the agent’s destination to be some estimated intermediate position, within the space between the start point and the wanted destination.
Another approach could be to let the agent move on the partial path for a while, and request a new path to the destination once it is closer to the wanted target (let’s say 10-20% closer than initially), or when it has moved a certain distance away from the previous start point.

I hope this info helps.

In the situation when you let the agent move towards the end of the partial path you can try to prepare the next section of the path in advance, to have it ready, and then assign it to the agent at the right time.
Unfortunately the navigation system does not have an async version of the CalculatePath() method but you can maybe use an Agent’s SetDestination() method as a replacement, because that pathfinding operation is executed asynchronously. It does only a fraction of the work each frame.
What you need to do:

  1. Add a NavMesh Agent component on a dummy game object and set isStopped = true or speed = 0 in order for that agent to not move on the (upcoming) path each frame. Set .obstacleAvoidanceType = NoObstacleAvoidance so that it is “invisible” to other agents and does not interfere with their movement. Set .agentTypeID to the agent type that you need. (Start from NavMesh.GetSettingsByIndex() if you need a way to find agent type IDs that you cannot get through other means.)
  2. Use the Warp() method to move it into the start position of the path. The agent will be momentarily disabled, moved to the new position, and then immediately enabled again. The property .isOnNavMesh then becomes true if the agent is attached correctly to a NavMesh for its own type, at the wanted position. (You can also use the function NavMesh.SamplePosition() to find precise positions on NavMeshes.)
  3. Call dummyAgent.SetDestination( target ). The search will run on the main thread but will be split over the course of multiple frames. It will inspect only a number of nodes equal to NavMesh.pathfindingIterationsPerFrame each frame. You can change that value at any time.
  4. Later in your game code check each frame until dummyAgent.pathPending is false and dummyAgent.hasPath is true
  5. Once the path is ready, store it and assign it at the right time to the wanted agent: npcAgent.path = dummyAgent.path. This copies the path from one agent to the other. The npcAgent needs to be somewhere close to the path’s start point, otherwise the agent will not receive the pre-calculated path, and in that case npcAgent.pathStatus will report PathInvalid.
  6. Repeat from 2. whenever there is a need of another path search.

To cancel the pathfinding request of an agent (the dummy, in this case) you can either disable the NavMeshAgent component, change its .agentTypeID property, or call Warp() to move it somewhere. These operations also delete any path that the agent has stored internally.

You can set up multiple agents like this one for the purpose of queuing up multiple requests for paths, which will be processed in sequence over many frames. Feel free to disable a dummy agent when not in use, but keep the agent enabled when you need its path to be computed.