A* Pathfinding Project

Point graph distance threshold


#1

nodes in my point graph are not evenly spaced apart. some nodes are close together, others are far apart.

i would like, when searching for a path, for the seeker to consider the distance between nodes. That is, certain characters can only travel to nodes that are close together, while others can traverse the nodes that are spread far apart (as well as the nodes that are close together)

It seems to me that the best way to accomplish this is some sort of distance threshold when requesting the path. if the distance from one node to another is higher than the seeker’s threshold, that connection is not considered traversable.

any idea how I could accomplish this? perhaps it’s something already supported by the API?


#2

Hi

This is not possible out of the box I’m afraid. The easiest, if you only have one or two of these thresholds, is to create multiple graphs (see https://arongranberg.com/astar/docs/multipleagenttypes.html).
Otherwise you could modify the PointNode.Open to add a check for if a connection is valid or not according to your distance threshold.


#3

hey, thanks for the tips.

i could use multiple agents/graphs, but that sounds like a huge chore. I can’t rely on auto-scan to be the end result of my graph. It requires a ton of tweaking post-scan (e.g. if i set the scan distance too high, i’ve got dozens of nodes that are linked that shouldn’t be) and that will add up to a ton of work if i have to manually set up a graph for each character type in each level

I see PointNode.Open, but I’m unsure on the best way to proceed. is there a recommended way to get my distance threshold float into that method? perhaps passing it to PathHandler or something when starting to seek the path? some other means of shuttling arbitrary data through the system? or some Func callback i can inject into there to add custom rules?


#4

Hi

Yeah so in the Open method you could add something like

if (!path.connectionFilter(this, other)) continue;

right after the CanTraverse call.

Then in the Path class you would add a new field

System.Func<GraphNode, GraphNode, bool> connectionFilter;

Also in the Path.Reset method you would have to add the line

connectionFilter = null;

(otherwise path pooling will break)

When you are starting to calculate the path you could then set the connection filter. Something like

 path.connectionFilter = (a, b) => ((Vector3)(a.position - b.position)).magnitude < 2.5f;

Also note that an easier way to disable connections that you don’t want could be to add invisible colliders there and let the point graph’s raycast check take care of it.


#5

Ah got it, I’m all set up now on this front, thanks 8)