Questions about path finding between islands in an open world

General Grid graph
#1

Hi there.
I have a procedural and random map including one million tiles. Some tiles are island and some tiles are sea.
I use a grid graph with 2 kinds of tags such as “island” and “sea” so that different seekers can use different tags for path finding.
There are two questions.
1st. When a npc start to wander, it picks a node as an end point. Sometimes the start point is on one island and the end point is on another island. It seems that the system searches lots of nodes (more than 400 thousand) and the path is failed.
The question is can I set a max count of nodes for path finding? e.g If the max count is 10000 nodes , the path finding system will return failed after searched 10000 nodes and no path is found.
2nd. Sometimes a npc is chasing a player, the player go into a indoor space, maybe a house or an area enclosed by walls. At this time, the npc’s path is failed and standing still. But what I want is to make the npc go to some points near the house or the area.
I find that the unity navmesh always go to the nearest of end point. So I wanna know how can I make that happen with AStar Pro.
Any advice will be much appreciated.

#2

@aron_granberg

Hi Aron,
Could u please give some advices?

#3

Hi

  1. When using tags it is not possible for the system to know if a destination is unreachable unless it has searched every single node it can reach. However when using walkability, the system does some pre-processing to determine which nodes are reachable from which other nodes and can therefore mark the path as failed immediately. It might be beneficial for you to use 2 different graphs, one for island creatures and one for sea creatures so that you can use walkability to restrict movement for both of them. There is no way to set a max node limit from code, you could modify the ABPath.cs script I suppose, that should be easy enough.
  2. This is also due to using tags. When using walkability the agent can immediately find the closest node that it can reach, and try to find a path to that. With tags it is forced to search every single node it can reach before it can determine that it cannot reach the goal. When that happens it can return the path to the closest point it could reach, but that is not done by default to avoid having users rely on this case without knowing that it throws you off a really steep performance cliff. You can enable it by setting path.calculatePartial = true. It’s not the easiest workflow to enable this for the built-in movement scripts, but you can override the SearchPath method in a subclass of the AIPath script and it will work:
public class MyAIPath : AIPath {
	public override void SearchPath () {
		if (float.IsPositiveInfinity(destination.x)) return;
		if (onSearchPath != null) onSearchPath();

		lastRepath = Time.time;
		waitingForPathCalculation = true;

		seeker.CancelCurrentPathRequest();

		Vector3 start, end;
		CalculatePathRequestEndpoints(out start, out end);

		ABPath p = ABPath.Construct(start, end, null);
		p.calculatePartial = true;
		seeker.StartPath(p);
	}
}