Limit the amount of time / node distance when finding a path

Beginner Questions
#1

So I have some really basic code to generating a path manually that works, basically just doing:

_path = ABPath.Construct(transform.position, moveTo);
_seeker.StartPath(_path);
_path.BlockUntilCalculated();
OnPathComplete(_path);

Now the thing is that there are moving pieces and sometimes the path gets blocked by another piece moving somewhere. Now detecting this is not the problem (I have done it in both a manually way and using the blocker manager) however when I recalculate the path I want it to stop after a certain point.

The issues I am trying to prevent here are 2 fold, basically whenever an existing path becomes blocked, I want to make sure that:

  1. The newly generated path is is within X node distance compare to the old path (if the old path was 4 and the new one is like 50, in the context of my game I would rather them just wait where they are has most of the time, they will move in another direction just to move back to the original path as the path will most likely free up relatively soon.
  2. There is a chance there is not going to be a new path available and the grid can be large which can result is an extremely long search time and this being a turn based game, I need to be able to calculate the path in a blocked / non-async way I would want it to stop before it tries all the nodes.

Is there a way to limit the amount of time and/or the node count of the path a path is searched for and just have it is no path return if it can’t find it within that time / distance?

#2

Hi

If you are worried about frame rate drops I’d recommend not calculating the path synchronously. Do an asynchronous path calculation instead. See https://arongranberg.com/astar/docs/callingpathfinding.html

  1. I’d recommend that you compare the length of the old path with the new path. If they both have the same destination and the new one is really long, then stop the agent or do something different.
    It’s not possible to limit the number of nodes that are searched in the internal pathfinding algorithm (well, you can create a custom path type I suppose).
#3

I am doing async paths but I can still have issues with a path attempt take 1+ second to run when on a large map and there is no path available because it is blocked can take a while and during that time the unit just sits there for several turns while other units do stuff which is weird. I was playing around with making a custom ITraversalProvider which would allow me to limit the amount of nodes that are searched however that really is not what I am looking for after testing it out.

I was I also playing around with a custom A* system and I was able to basically say any node that would make the path X long read as unwalkable which gave me better results that I was looking for and was wondering if I would do that same with a custom ITraversalProvider? I noticed that a Path is passed into the CanTraverse() method however it seems like that path.path is always empty. Is there some piece of data on the Path passed into the CanTraverse() method that says what the current paths length is so that I can just have CanTraverse() return false if that node would make the path X long?

#4

Over 1 second!? That’s really really long. Either you have a huge map or your are using an ITraversalProvider which does pretty expensive stuff.

You could write an ITraversalProvider that just starts returning false after a while. It’s not perfectly accurate since the ITraveralProvider may be called multiple times for each node, but it’s pretty close.

Something like

class MyTraversalProvider : ITraversalProvider {
     int searchedNodes = 0;
     bool CanTraverse (Path path, GraphNode node) {
         searchedNodes += 1;
         if (searchedNodes > 10000) return false;
         DefaultITraversalProvider.CanTraverse(path, node);
    }
}