Navigating to the Closest Point on a NavMeshObstacle

Unity Engine
,
1

I have a carving NavMeshObstacle acting as a door to block passage through a wall:

If an agent is outside the wall - in this case to the right - and targets this block to come and attack it, we want it to navigate toward the obstacle. The transform.position of the latter is inside the complex, which causes the agent to find some alternate route all the way around the wall.

My tentative buggy solution is to derive the closest spot on the edge of the obstacle in a straight line to the agent, and navigate there. That only works if the agent is in direct line of sight; if not, there are times when it is best to navigate around the wall as it’s now doing.

What would be most handy is if you could set a NavMeshObstacle’s block-out area to be a certain walkability area at runtime, a feature I have yet to find.

2

I’ve run into the same issue and hadn’t come up with a quality solution yet ether.

I do have an idea that just occurred to me though…

I’m not sure what your projects tolerance for cpu is but I think that if you somehow identify that the point you want to get to is inside a blocking obstacle that you actually run NavMesh.CalculatePath ~4 times Once to each corner/side as you see fit. (maybe more is necessary depending on the size/shape of your Obstacles.

Then you pick the lowest cost path.

[I’m including my NavMeshPathExtention file that calculates cost of paths in a number of different ways. I don’t expect that it’ll be exactly what you need, but it’s pretty easy to understand the concepts.]

//#define DEBUG_COST_DRAG

using UnityEngine;
using UnityEngine.AI;
using System.Collections.Generic;
using Hemlock.WarEngines.Unit;

public static class NavMeshPathExtension
{
  
    static int IndexFromMask(int mask)
    {
        for (int i = 0; i < 32; ++i)
        {
            if ((1 << i) == mask)
                return i;
        }
        return 0;
    }

  

    public static void Cost(this NavMeshPath path, float maxMoveCost, ref DisplayPathData movementPath, ref DisplayPathData deniedPath, NavMeshQueryFilter navMeshFilter)
    {
        var corners = path.corners;
        if (corners.Length < 2)
            return ;

        movementPath.Clear();
        deniedPath.Clear();

        var hit = new NavMeshHit();
        NavMesh.SamplePosition(corners[0], out hit, 0.1f, NavMesh.AllAreas);
      
        var costMultiplier = navMeshFilter.GetAreaCost(IndexFromMask(hit.mask));
        int mask = hit.mask;
        var rayStart = corners[0];
        movementPath.PathList.Add(rayStart);

#if DEBUG_COST_DRAG
        string PathOutput = "first position " + rayStart;
#endif

        Vector3 lastCOllisionPos;
        float AddedDistanceCost = 0f;
        for (int i = 1; i < corners.Length; ++i)
        {

            if(movementPath.PathDistance < maxMoveCost)
            {
                lastCOllisionPos = new Vector3();
                while (movementPath.PathDistance < maxMoveCost && NavMesh.Raycast(rayStart, corners[i], out hit, hit.mask) && hit.position != lastCOllisionPos)
                {
                    lastCOllisionPos = hit.position;

                    AddedDistanceCost = costMultiplier * hit.distance;
#if DEBUG_COST_DRAG
                    PathOutput += "\n\t\tAddedDistanceCost collision [" + AddedDistanceCost + "] [" + costMultiplier + "] [" + hit.distance;
#endif

                    if (movementPath.PathDistance + AddedDistanceCost > maxMoveCost)
                    {
                        float Remainder = maxMoveCost - movementPath.PathDistance;
                        float PercentageOfThisLeg = Remainder / AddedDistanceCost;

                        Vector3 EndPosition = (hit.position - rayStart) * PercentageOfThisLeg + rayStart;
                        movementPath.PathDistance = maxMoveCost;
                        movementPath.PathList.Add(EndPosition);

                        deniedPath.PathList.Add(EndPosition);
                        deniedPath.PathList.Add(corners[i]);

#if DEBUG_COST_DRAG
                        PathOutput += "\n\tCollision Finishes MaxCost " + EndPosition + " " + hit.position;
#endif

                    }
                    else {
                        movementPath.PathDistance += AddedDistanceCost;
                        movementPath.PathList.Add(hit.position);

#if DEBUG_COST_DRAG
                       PathOutput += "\n\tCollision Inside MaxCost " + hit.position;
#endif
                    }

#if DEBUG_COST_DRAG
                    PathOutput += "\n\t\t\tHitMask " + IndexFromMask(hit.mask);
#endif
                    costMultiplier = navMeshFilter.GetAreaCost(IndexFromMask(hit.mask));
                
                    mask = hit.mask;
                    rayStart = hit.position;
                  
                }

                if (movementPath.PathDistance < maxMoveCost)
                {
                    AddedDistanceCost = costMultiplier * (corners[i] - rayStart).magnitude;
#if DEBUG_COST_DRAG
                    PathOutput += "\n\t\tAddedDistanceCost [" + AddedDistanceCost + "] [" + costMultiplier + "] [" + hit.distance;
#endif

                    // advance to next segment
                    if (movementPath.PathDistance + AddedDistanceCost > maxMoveCost)
                    {
                        float Remainder = maxMoveCost - movementPath.PathDistance;
                        float PercentageOfThisLeg = Remainder / AddedDistanceCost;

                        Vector3 EndPosition = (corners[i] - rayStart) * PercentageOfThisLeg + rayStart;
                        movementPath.PathDistance = maxMoveCost;
                        movementPath.PathList.Add(EndPosition);

                        deniedPath.PathList.Add(EndPosition);
                        deniedPath.PathList.Add(corners[i]);


#if DEBUG_COST_DRAG
                        PathOutput += "\n\tPositionFinishes MaxCost " + EndPosition + " " + hit.position;
#endif
                    }
                    else {
                        movementPath.PathDistance += AddedDistanceCost;
                        movementPath.PathList.Add(corners[i]);
#if DEBUG_COST_DRAG
                        PathOutput += "\n\tPositionInside MaxCost " + hit.position;
#endif
                    }

#if DEBUG_COST_DRAG
                    PathOutput += "\n\t\t\tHitMask " + IndexFromMask(hit.mask);
#endif
                    costMultiplier = navMeshFilter.GetAreaCost(IndexFromMask(hit.mask));
                    mask = hit.mask;
                    rayStart = corners[i];
                }

            } else
            {

                deniedPath.PathList.Add(corners[i]);
            }

          
        }

#if DEBUG_COST_DRAG
        Debug.Log(PathOutput);
#endif

    }

    public static Vector3 MaxCostPositionOnPath(this NavMeshPath path, float maxMoveCost, NavMeshQueryFilter navMeshFilter)
    {
        Vector3 maxCostMovePosition = new Vector3();

        var corners = path.corners;
        if (corners.Length < 2)
            return maxCostMovePosition;


        var hit = new NavMeshHit();
        NavMesh.SamplePosition(corners[0], out hit, 0.1f, NavMesh.AllAreas);

        var costMultiplier = navMeshFilter.GetAreaCost(IndexFromMask(hit.mask));
        int mask = hit.mask;
        var rayStart = corners[0];

        float TotalDistance = 0f;

#if DEBUG_COST_DRAG
        string PathOutput = "first position " + rayStart;
#endif

        Vector3 lastCOllisionPos;
        float AddedDistanceCost = 0f;
        for (int i = 1; i < corners.Length; ++i)
        {

            if (TotalDistance < maxMoveCost)
            {
                lastCOllisionPos = new Vector3();
                while (TotalDistance < maxMoveCost && NavMesh.Raycast(rayStart, corners[i], out hit, hit.mask) && hit.position != lastCOllisionPos)
                {
                    lastCOllisionPos = hit.position;

                    AddedDistanceCost = costMultiplier * hit.distance;
#if DEBUG_COST_DRAG
                    PathOutput += "\n\t\tAddedDistanceCost collision [" + AddedDistanceCost + "] [" + costMultiplier + "] [" + hit.distance;
#endif

                    if (TotalDistance + AddedDistanceCost > maxMoveCost)
                    {
                        float Remainder = maxMoveCost - TotalDistance;
                        float PercentageOfThisLeg = Remainder / AddedDistanceCost;
                        maxCostMovePosition = (corners[i] - rayStart) * PercentageOfThisLeg + rayStart;
                        TotalDistance = maxMoveCost;
                        break;

#if DEBUG_COST_DRAG
                        PathOutput += "\n\tCollision Finishes MaxCost " + EndPosition + " " + hit.position;
#endif

                    }
                    else {
                        TotalDistance += AddedDistanceCost;

#if DEBUG_COST_DRAG
                       PathOutput += "\n\tCollision Inside MaxCost " + hit.position;
#endif
                    }

#if DEBUG_COST_DRAG
                    PathOutput += "\n\t\t\tHitMask " + IndexFromMask(hit.mask);
#endif
                    costMultiplier = navMeshFilter.GetAreaCost(IndexFromMask(hit.mask));

                    mask = hit.mask;
                    rayStart = hit.position;

                }

                if (TotalDistance < maxMoveCost)
                {
                    AddedDistanceCost = costMultiplier * (corners[i] - rayStart).magnitude;
#if DEBUG_COST_DRAG
                    PathOutput += "\n\t\tAddedDistanceCost [" + AddedDistanceCost + "] [" + costMultiplier + "] [" + hit.distance;
#endif

                    // advance to next segment
                    if (TotalDistance + AddedDistanceCost > maxMoveCost)
                    {
                        float Remainder = maxMoveCost - TotalDistance;
                        float PercentageOfThisLeg = Remainder / AddedDistanceCost;
                        maxCostMovePosition = (corners[i] - rayStart) * PercentageOfThisLeg + rayStart;
                        TotalDistance = maxMoveCost;
                        break;


#if DEBUG_COST_DRAG
                        PathOutput += "\n\tPositionFinishes MaxCost " + EndPosition + " " + hit.position;
#endif
                    }
                    else {
                        TotalDistance += AddedDistanceCost;
#if DEBUG_COST_DRAG
                        //PathOutput += "\n\tPositionInside MaxCost " + hit.position;
#endif
                    }

#if DEBUG_COST_DRAG
                    PathOutput += "\n\t\t\tHitMask " + IndexFromMask(hit.mask);
#endif
                    costMultiplier = navMeshFilter.GetAreaCost(IndexFromMask(hit.mask));
                    mask = hit.mask;
                    rayStart = corners[i];
                }
            }
        }

#if DEBUG_COST_DRAG
        Debug.Log(PathOutput);
#endif

        if (TotalDistance < maxMoveCost)
        {
            maxCostMovePosition = corners[corners.Length - 1];
        }

        return maxCostMovePosition;
    }

    public static bool IsPathWithinCost(this NavMeshPath path, float maxMoveCost, NavMeshQueryFilter navMeshFilter)
    {
        Vector3 maxCostMovePosition = new Vector3();

        var corners = path.corners;
        if (corners.Length < 2)
            return false;


        var hit = new NavMeshHit();
        NavMesh.SamplePosition(corners[0], out hit, 0.1f, NavMesh.AllAreas);

        var costMultiplier = navMeshFilter.GetAreaCost(IndexFromMask(hit.mask));
        int mask = hit.mask;
        var rayStart = corners[0];

        float TotalDistance = 0f;

#if DEBUG_COST_DRAG
        string PathOutput = "first position " + rayStart;
#endif
        Vector3 lastCOllisionPos;
        float AddedDistanceCost = 0f;
        for (int i = 1; i < corners.Length; ++i)
        {

            if (TotalDistance < maxMoveCost)
            {
                lastCOllisionPos = new Vector3();
                while (TotalDistance < maxMoveCost && NavMesh.Raycast(rayStart, corners[i], out hit, hit.mask) && hit.position != lastCOllisionPos)
                {
                    lastCOllisionPos = hit.position;

                    AddedDistanceCost = costMultiplier * hit.distance;
                    TotalDistance += AddedDistanceCost;
                  
                    if (TotalDistance  > maxMoveCost)
                        return false;

                    costMultiplier = navMeshFilter.GetAreaCost(IndexFromMask(hit.mask));

                    mask = hit.mask;
                    rayStart = hit.position;

                }

                if (TotalDistance < maxMoveCost)
                {
                    AddedDistanceCost = costMultiplier * (corners[i] - rayStart).magnitude;
                    TotalDistance += AddedDistanceCost;

                    if (TotalDistance  > maxMoveCost)
                        return false;
                  
                    costMultiplier = navMeshFilter.GetAreaCost(IndexFromMask(hit.mask));
                    mask = hit.mask;
                    rayStart = corners[i];
                }
            }
        }
      
      
        return true;
    }

}
3

I’ve been debating between that approach, in my case comparing just the obstacle’s front and back - which still might get CPU-heavy with as many as a hundred units all converging on it in the same frame - with creating a whole system of zones in which you manually assign which end of each obstacle to approach from each zone. They would also need to have irregular trigger colliders and all the units track the one they’re in.

I’ll start with the former since it’s quicker to implement, and resort to the latter when and if the hiccup becomes too conspicuous.

Thanks for posting.

By the way, anything interesting in the DisplayPathData definition other than the following extrapolation?

    private class DisplayPathData{
        public float PathDistance=0;
        public List<Vector3> PathList=new List<Vector3>();
        public void Clear(){
            PathList.Clear();
        }
    }
4

Yeah, for tons of units this might not be a great solution…unless you check sides once and then use that point for all subsequent Navigation searches to that unit/location from the same user movement request. That seems like it could be a useful shortcut/approximation for your situation.

Yup, you nailed it except for one bit of bulletproofing.

    private class DisplayPathData{
        public float PathDistance=0;
        public List<Vector3> PathList=new List<Vector3>();
        public void Clear(){
            PathList.Clear();

            PathDistance = 0f;
        }
    }