Bug with one way links, floodfill, areas, and ABPath

General
#1

I’ve been setting up one way links between graphs that allow our enemies to leave their spawn areas to attack the player, but not navigate back into them once they are within the main area. Depending on exactly how things are set up sometime the enemies will refuse to find a path across the link.

I’ve managed to build a test case and isolate what is causing the bug (spoiler, it is in floodfill), but I’m not sure what the correct fix is.

If I set up three graphs (I used recast graphs but the bug should show up regardless of graph type) as shown below:

Graph 0,1 and 2 are in that order in the inspector, and each has that number as its graphIndex at runtime.

Graph 0 is the main play area graph, graphs 1 and 2 are the spawn areas.

There are a pair of one directional NodeLinks, one connects graph 1 to graph 0, the other connects graph 2 to graph 0.

There is a seeker that tries to create an ABPath from the green sphere (representing the spawn point) to the red sphere (representing the player)

If I drag the spheres around the scene to try different paths what I observe is:

  • Pathfinding entirely within any one graph works.
  • Pathfinding from graph 0 to either of the other graphs correctly fails to find a path
    (since the links are one way)
  • Pathfinding from graph 2 to graph 0 correctly finds a path via the link
  • Pathfinding from graph 1 to graph 0 INCORRECTLY fails to find a path via the link.

In the last case stepping through the seeker code reveals that it bails out early because the nearest node to the start point (in graph 1) and the nearest node to the end point (in graph 0) have different area IDs. The ABPath uses this as a heuristic to tell it that there isn’t going to be a valid path between the nodes.

Stepping through the Floodfill code reveals why the graphs end up as different areas. The following sequence of events occurs:

  1. FloodFill() steps through the three graphs in order
  2. graph 0 is flood filled, and all nodes are assigned to area 1
  3. Graph 1 is flood filled, assigning all nodes to area 2
  4. The link from 1 to 0 is followed, all of the nodes in graph 0 are re-flood filled and changed to area 2 (The link between graph 0 and graph 2 isn’t followed because it is one way)
  5. Graph 2 is flood filled assigning all nodes to area 3
  6. The link from 2 to 0 is followed, all of the nodes in graph 0 are re-flood filled and changed to area 3 (The link between graph 0 and graph 1 isn’t followed because it is one way)

Graph 1 ends up with all of its nodes coloured as area 2, and graphs 0 and 2 end up with nodes coloured as area 3.

Thus when one-way links are used to connect areas whichever is the last area to be flood filled will end up ‘winning’ and all of the other areas will end up with unique area ids, and will be early rejected when trying to path-find between them via the links.

I’m not sure what the correct long term fix is. I can probably work around it in my specific case by creating links that are bi-directional, but have a VERY high cost to traverse in the return direction.

#2

One possible solution would be to have one-way links still add connections in both directions, but have the return connection have a cost of uint.MaxValue. Floodfill ignores the cost on connections and would thus connect up the areas, but the pathfinding should avoid using it.

To make it really robust we could modify the code in node.Open() so that when it is enumerating the outgoing connections it treats a cost of uint.MaxValue as special and skips connections which cost that much.

#3

Yeah, that is one long standing bug.
There is a way to solve it by detecting strongly connected components using e.g Tarjan’s algorithm, but that requires a lot of code for things that 99% of all users will never need and then it will just slow the system down for them. Flood filling is already pretty slow.

#4

Would it be worthwhile having an easy way to disable the Floodfill and associated heuristic check? If I’m dealing with graphs that I know have one way links and where flood fill is going to fail why would I bother paying the cost of calculating it?

How bad is the cost of trying to calculate a path between non-connected areas? (presumably high because it will devolve into an exhaustive search?)

#5

Sure, I think it will work if you just add a “return;” at the top of the AstarPath.FloodFill method.
Yeah, it’s essentially the cost of searching all the nodes that it can reach, which can be high or low depending on how large your world is.