A* Pathfinding Project

StartMultiTargetPath returns path with different end point


#1

Hello,

My Graph is Layered Grid and my game is voxel based. When I call StartMultiTargetPath and pass x number of end points, sometimes I get as a result a path with end point that is not passed but close to that passed point.
e.g. Lets say i want to find path to position (20,5,15) and my agent is on (10,4,5), StartMultiTargetPath will return path (20,4,15), a layer below if that position is free.
What would I like for result is paths with exact same end points as i passed to method. How can I do that, have I missed something in settings?


#2

Help please, I really need this.


#3

Hi

Sorry for the late answer.
Is there a node at (20,5,15) that it can actually reach?

Do you think you could send a screenshot of this?


#4

I thought it was occurring in both cases when path can or can not be reached, but while doing some debugging I realised it only happens for paths that can’t be reached.
I don’t have actual screenshot of that happening since I made a workaround for that problem some time ago, but here are some drawings.
So basically I would pass blue points to StartMultiTargetPath and as a result I would get red point as closest path event tho I haven’t passed that point to a method. That said i’m forced to use StartMultiTargetPath to calculate all paths not only closest, then check if end points of those paths match with points I passed to a method earlier and get closest.

So once again lets get through some example.
I want to find closest path from position {20,5,15(can be reached) ;21,5,15(can’t be reached)} and my agent is on {10,4,5}.
StartMultiTargetPath in this case will return two paths with end points {20,5,15 ;21,4,15}.
{21,4,15} was not passed to a method but I got it as a result for closest path to point {21,5,15} that can not be reached.
What I would like for a result is only closest path with end point that I passed to a method.



#5

Hi

Ah, I see.
Normally the system will try to find the path to the closest point that can be reached. You can set the upper limit for how far away it will look for those points in the inspector. Reduce A* Inspector -> Settings -> Max Nearest Node Limit to something appropriate (e.g. 1 node width).


#6

Thank you, for now it seems it is working properly, I will get rid of my workaround and let you know if I get into some problem caused by some side effect if any.


#7

Hello, after using new settings with Max Nearest Node Limit set to 1 and getting rid of my workaround I got huge performance boost but I have found a problem when GridNode under agent is carved out and no longer accessible, agent would get stuck since he is no longer able to find other closest node.
Is there a way to fix this or should I implement my own solution to a problem?


#8

Hi

Sorry for the late answer. I have been traveling and have not been able to answer support requests for some time.

Hmm… That is a bit tricky.
I suppose the easiest fix is to increase Max Nearest Node Distance a bit but then do a check like this:

MultiTargetPath path = ...;
for (int i = 0; i < path.targetPoints.Length; i++) {
     // Check if the closest node (not necessarily walkable) is the same as the path end node (which is the closest node that *is* walkable)
     if (path.targetsFound[i] && AstarPath.GetNearest(path.targetPoints[i], NNConstraint.None) != path.targetNodes[i]) {
        // Path is actually not valid
        path.targetsFound[i] = false;
    }
}

#9

First of all thank you for your time, second I’m sorry, I forgot to post that I have found a solution. To make a problem as understandable as possible I will run you through my process of finding closest object. First I will pass dictionary with positions as key and object as value so when I find closest position I know what object that position belongs to, btw because it’s a grid based graph so I never want to search for center of object but surrounding positions, some times positions above or under, depending of object type, so for one object I have minimum 4 positions. Then if I pass those positions to pathfinder it would return a path to closest position, then I would use endPoint of that path to get its object from dictionary. With Max Nearest Node Distance different from 1 sometimes I would get endPoint that it was not passed as searchPoint and as a result I would not be able to find in dictionary object for that position, then I realized that multi path also has chosenTarget property and that solved all my problems, now my Max Nearest Node Distance is 2 and it’s high enough to get agents out of carved node and low enough for them not to chose some node that its not passed and I’m ok with some little offsets for slopes or stairs.

Here is a code that I use for closest object search.

private ClosestWorldObject<T> FindClosestObject<T>(
      IPathfindingAgent agent,
      Dictionary<Vector3, T> locationItemDictionary) where T : WorldObject
{
      if (locationItemDictionary.Count == 0)
      {
            return default(ClosestWorldObject<T>);
      }

      bool pathExists = false;
      Vector3[] searchArray = locationItemDictionary.Keys.ToArray();

      MultiTargetPath multiPath = this.seeker[agent].StartMultiTargetPath(
            agent.GetPosition(),
            searchArray,
            false,
            (Path pathCandidate) =>
            {
                  if (!pathCandidate.error)
                  {
                        pathExists = true;
                  }
            });

      multiPath.BlockUntilCalculated();

      if (!pathExists)
      {
          return default(ClosestWorldObject<T>);
      }

      int pathIndex = multiPath.chosenTarget;

      return new ClosestWorldObject<T>(
          locationItemDictionary[locationItemDictionary.Keys.ElementAt(pathIndex)],
          searchArray[pathIndex]);
}

ClosestWorldObject is just a struct with two fields object and calculated reachable position.
WorldObject is a class that contains fields : center position of object, list of positions that I would like to be reachable for that position and cached GraphNodes for those positions so I don’t have to call GetNearest every time I want to check IsPathPossible for agent and some position.

I have just one question, do I even have a benefit of filtering positions with IsPathPossible before passing then to pathfinder?

Sorry for long post but I like to be as understandable as possible and once again thank you for your time and effort.

Cheers


#10

Not a significant benefit. However you would get rid of the overhead of the pathfinder doing a GetNearest call I suppose.