Most efficient way to check validity of path without ai

General Recast graph
#1

Hey there,

I would need your help please.

Every x seconds we check if there are new available jobs in the factory, if so we find the closest worker and give to they the task to complete the job. To make sure the worker is not stuck somewhere we check if the path is valid, if not we look for the next worker. I am a bit worried about the performance impact of such activity but we find it necessary since it happens players stuck the worker and without this check the whole factory fails.

So we do the following check:

public static bool IsPathValid(Vector3 startingPosition, Vector3 destination, float horStopDistance, float vertStopDistance)
{
    var node1 = AstarPath.active.GetNearest(startingPosition);
    var node2 = AstarPath.active.GetNearest(destination);
    if (ReferenceEquals(node1.node, null) || ReferenceEquals(node2.node, null)) return false;
    if (!AreTwoPositionsWithinRange(destination, node2.position, horStopDistance, vertStopDistance)) return false;
    return PathUtilities.IsPathPossible(node1.node, node2.node);
}

public static bool AreTwoPositionsWithinRange(Vector3 positionOne, Vector3 positionTwo, float horizontalDistance, float verticalDistance)
{
    var isHorizontalDistanceInRange = (new Vector2(positionOne.x, positionOne.z) - new Vector2(positionTwo.x, positionTwo.z)).sqrMagnitude <
                                      (horizontalDistance * horizontalDistance);

    var isVerticalDistanceInRange = Mathf.Abs(positionOne.y - positionTwo.y) < verticalDistance;
    
    return isHorizontalDistanceInRange && isVerticalDistanceInRange;
}

Do you think this is the most performance efficient approach? We are suffering from some performance issues related to this so we need to limit the number of workers the player can have.

Ps we are on version: 4.3.61

Thanks!!
Paolo

#2

Hi

The IsPathPossible call is basically instant. However the GetNearest calls may be slower. So if you are doing this for many pairs of startingPositions/destinations. Try to see if you can cache the GetNearest calls, or make sure you only run them once for a given position each frame.

1 Like
#3

Hey,

thanks for the feedback!

Actually that make sense, after all once a structure is placed then it won’t be moving around and the nearest node is always available since we prevent building on top of it. So technically we cache it once and leave it there until the structure is destroyed. Only few will need to be checked.

Thanks again, this help out a lot!

#4

Hey @aron_granberg ,

first of all happy new year!

I implemented the solution you suggested but then one question came up.

What happens if someone remove a corridor that connect a worker from the working area? Does the cached node update the area or it requires a new get nearest node call?

Thanks,
Paolo

#5

If you use a recast graph, the node may become destroyed if you update the graph. Check the node.Destroyed property. If that is true, then you’ll need to run GetNearest again.

#6

It works wonderfully, thanks!

Sorry to bother you with all these questions, I tried to find the answer in the forum but I couldn’t.
I was thinking to add a security check in case the worker get stuck by checking if is still (sqrMagnitude < x) and if agent has reached the destination, but it also seems it get triggered when very close to the destination. Do you have any suggestion on how I could effectively check this?

Thanks,
Paolo

#7

I’m not quite sure what you are asking. Would you mind elaborating?

#8

Hey there,

of course, I am sorry I didn’t explain myself properly!

So I mean:
To make sure the workers don’t get stuck and the player experience is not damaged I would like to add a check that is done while the worker is moving to make sure that he is stuck then cancel the action. And for stuck I mean that he has not reached his destination but he is not able to move further. I used to do this check on the Unity NavMesh API by checking the distance and the velocity and was still then would unstuck him.

Is there something similar I could implement in your library?

Thanks!

#9

If that approach worked, you could use the exact same approach here. Check ai.velocity as well as the distance to the destination.

#10

Yeah I tried it but it also get triggered when it’s starting to stop so it would be a false positive. No worries, if there isn’t something already in the API I’ll think of something myself :smiley:

Thanks again for the help!