Problems with path finding a point outside of 2 graphs as opposed to a point outside of 1 graph

Feature Requests
1

Hello,
I noticed how if a destination point is outside of 1 existing graph, AIFollow will make the seeker go to the nearest node that is inside the graph before making the last path point array go directly to the destination, but if I use 2 graphs and the destination point is outside of both graphs, AIFollow will not do that unless the other graph is out of the way, so if the seeker is standing on graph 1, and the destination point is outside of both graphs but the seeker has to cross graph 2 in order to get to the destination point, nothing happens.

2

I believe I have a solution to this problem. When using 2 or more graphs, the pathfinder should scan each graph at a time (as if every OTHER graph is disabled, (non existing)).

Then, if the destination point is not on that graph but the seeker is standing on the graph (where the pathfinder will then pick the closest node ON that graph TO the destination point), if THAT node is not close to the destination point, it should then scan again from THAT point to the destination point from each separate graph at a time again, and the process should repeat itself UNTIL there are no more graphs left to scan from. Then, I believe it will work.

3

Do you remember how I added an extra array called ‘enabled’ for each graph, so that when enabled[index] is true, it is as if the graph exists, and when it is deselected (as false), it is as if the graph does not exist? In AstarPath.cs, I added…

if (enabled[i]) { ... }

inside every ‘for’ loop that has ‘i’ go from 0 up to graphs.Length. Somehow, if we were to do pathfinding per each individual one graph at a time using this example, the problem would be solved where we could do multi-graphed pathfinding without this problem occurring.

4

I belive the path finder should scan each graph one graph at a time separately in order to avoid the problem above from happening, while ignoring all the other graphs as if they are disabled or non-existing. There should be a lastPath variable that contains the last path that is found in the scanning of each individual graphs along with a priority.

If both the source and destination point is not found on each graph, then it should have the lowest priority. If the destination is on the graph and the source is not, it should have a priority of 1. If the destination is not found on the graph and the source is, it should have a priority of 2, and if both the source and the destination points are found on the same graph, then it should have a priority of 3. lastPath should contain the last path of the highest priority that is found while scanning each graph separately, and then have the seeker execute THAT path. I think that would solve the problem.

I was able to add a feature in the editor under where it says, “Show graphs” that says, “Enable graph x” where x is the graph index number depending on how many graphs there are created, and began to notice that as I started disabling the graphs that stood in the way of the seeker being able to go to a destination point that is outside of ALL graphs, I got results only when I disabled the graphs that were standing in the way between the seeker and the destination point. That’s why I believe this is the right direction to go in when doing pathfinding.

Then, game developers can do things like develop a graph for water, another graph for roads and another graph for sidewalks where only cars can travel on the road graph, boats can only travel on the water graph, and when the seeker is a person trying to get to another island, it can do the logic to go from the sidewalk to the car, from the car to the boat and to the other island from the boat. I have developed the .cs script that does this, but have ran into the problem above which is stopping me.

5

There is actually a feature for explicitly stating which graphs to search:
The graphMask variable on the NNConstraint is not much used (or mentioned), but in the cases where it is useful, it is really useful.
The graphMask enables you to set, for each path, what graphs it should be able to search (or actually, find start and endpoints on).
ABPath p = ABPath.Construct (transform.position, blah, null); p.nnConstraint.graphMask = 1 << 0; seeker.StartPath(p);
The above code will ensure that only the first graph is searched for close points (read up on bitmasks if you have no idea what “1 << 0” does).


However, there is another, much easier way to do what you want.
You can enable A* Inspector -> Settings -> Pathfinding -> Full Get Nearest Node Search.
That will make the get nearest node code search for the closest ‘valid’ node on all graphs instead of first choosing the graph by checking the closest node (even if it is not valid). It is disabled per default because it is slower having it enabled, and it is rarely needed (most people only use one graph anyway).
See http://arongranberg.com/astar/docs/class_astar_path.php#a10d5c41cd51043fb472da8692ffb1577

PS: If you do not want the last vertex in the path to be the exact requested point, adjust the Seeker -> StartEndModifier settings, for example setting End Point to ClosestOnNode.

6

I tried using

p.nnConstraint.graphMask = 1 << 0;

but it only works when I disable graph 1 and then re-enable it even though it is supposed to only focus on graph 0 and ignore graph 1.

Also, I was wondering where in StartPath does the function use GetNearest() for its start node and end node calculations? I also noticed that the Full Get Nearest Node Search didn’t solve the problem I was having.

7

GetNearest is called when the path is initialized so in Pathfinding.Path.Prepare I believe.
This is not called at the same time as StartPath, but often in the same frame (however during high load, maybe a few frames later).

Hm, interesting. In my tests it does exactly what you would want it to (as I have understood it).
You might want to set Min Area Size to 0 (in A* Inspector -> Settings -> Pathfinding), shouldn’t affect much, but might have some effect in worst case.

Ah, right. Sorry, have been misleading you a bit with the graphMask.
You see, I though graphMasks would be quite common to use, so I included it as an optional paramater to the StartPath function, this then of course means that that parameter has overridden the values set right before calling the function. It should look like this:

seeker.StartPath (start, end, OnPathComplete, 1 << 0);
Graph mask is the last parameter.

8

Could it have anything to do with when the graphs initialize themselves?

9

Don’t think so.
Can you send me a screenshot of your settings? Maybe there is something I have missed.

10

I figured it out and added some code to Start() and other functions. I wrote what I did. Does setting the graph mask to -1 clear it?

11

Ok, great!
Setting a bitmask to -1 is the same as setting all bits to true (since -1 in binary two-complement is …11111111, just ones). So yes, setting it to -1 clears it.