Question by Sungold · Dec 17, 2020 at 08:08 PM · performance navmesh navmeshagent distance distance check

Find closest "item" object by NavMesh navigation distance performantly

Hi all!

I'm making a FPS game with AI support.

When the AI controlled player does not have an item in their hand, I want them to find the closest item by Navigation Distance (not Vector3 distance because the level might have many floors, and this could select an item above or below them on a different floor).

All the answers to this have been just Calculate the Navmesh paths, and find the one with the least distance. So I implemented that but to get around having to calculate the path myself, I've just put a dummy NavMeshAgent on the Game Manager, moved it to the AI's position, and set the items in the level as targets and find the closest one with remaining distance.

My question is, is there a more performant way to do this? I thought about using a K-D tree and filtering out items that were too far away, but that would have to be iterative because what if there are no items in your initial spherical distance from the AI?

Here's the code I wrote:

     public GameObject FindClosestItem(Vector3 pos)
     {
         // find closest item by navigation distance using our dummy navmeshagent
         transform.position = pos;
 
         float minDistance = float.MaxValue;
         GameObject closestItem = null;
         foreach (GameObject item in items)
         {
             dummyAgent.destination = item.transform.position;
 
             if (dummyAgent.remainingDistance < minDistance)
             {
                 minDistance = dummyAgent.remainingDistance;
                 closestItem = item;
             }
         }
         
         // reset the game manager's position
         transform.position = Vector3.zero;
 
         return closestItem;
     }

Add comment