HI @aron_granberg!
I have stumbled upon a really weird issue and cannot move forward without your assistance. My case is very similar to the turn-based utilities example from the documentation.
I have units that can traverse the graph, the units are blocking the nodes that are on. Simple.
I am using the graph with 8 connections and my problem emerges when I try to move a unit when it is surrounded by units in a pattern like this:
☐ E ☐
E X E
☐ E ☐
X - unit that is being controlled
E - enemy that is blocking the node
The unit is using a traversal provider which excludes the nodes that are being occupied by enemies. When that happens the pathfinding fails, despite the graph being configured to use 8 connections and it is scanned properly (i.e. the connections are there, visible in scene view). When not using a custom traversal provider the path (using diagonals) is calculated without any issues).
The traversal provider code is super simple, only checks for the blocked nodes, but maybe I am missing something obvious there:
public class ExtendedTraversalProvider : ITraversalProvider
{
public List<GraphNode> excludedNodes = new List<GraphNode>();
public bool CanTraverse(Path path, GraphNode node)
{
if (excludedNodes.Contains(node))
{
return false;
}
else
{
return DefaultITraversalProvider.CanTraverse(path, node);
}
}
public bool CanTraverse(Path path, GraphNode from, GraphNode to)
{
return CanTraverse(path, to);
}
public uint GetTraversalCost(Path path, GraphNode node)
{
return DefaultITraversalProvider.GetTraversalCost(path, node);
}
}
I have prepared an isolated reproduction project ready to be shared. Please let me know how you would like to get it shared with you.
Sorry for the late reply.
This is the expected behavior. Grid graphs typically filter out these connections as well because they are typically undesirable (not doing it often leads to agents walking through corners of buildings and similar things).
Are you using the beta? I think you are, because this connection filtering is not done in the non-beta (iirc).
You can modify the code to get rid of this check. It’s done in the GridNode.cs script. Look for this block:
Thanks for the response.
Is it also expected when using 8 connections? I haven’t taken a look at the code yet, but I am somewhat confused by the part dir == 4 in the fragment you posted.
Thanks for the explanation! Despite I get the overall idea it seems that the result is quite radical. I mean the fact that the pathfinding fails, but there are connections, so looking at it strictly theoretically in my example why should it fail? There is a direct connection between two nodes that are next to each other, both of them are traversable, and yet the pathfinding fails.
I get that I can just comment out this filtering that you have pointed out, but what I am after is more of a discussion right now. In my project, when I want to prevent units to go through the corners of buildings I am just making sure that there are no diagonal connections between them. Shouldn’t it go that way? If there is a connection - the pathfinding should be able to use it, and if there is not - well
The reason it is done this way is because there are a lot of people who make their games with walls like:
and it’s not reasonable for an agent with a non-zero radius to squeeze through that infinitely thin opening.
That depends on the grid graph → cut corners setting.
See this image for an illustration of that setting.
So if it’s on, then it requires that diagonals have at least one adjacent non-diagonal connection enabled.
If it’s off, then both adjacent non-diagonal connections need to be enabled.
hmm, but that seems a bit like two sources of truth, am I right? The settings on the grid graphs affect the creation of the actual connections, but in my case, the connections are there, but because of that filtering, they cannot be used in some circumstances resulting in situation when it is a lot harder to predict a possible movement of a unit just by looking at the graph. Until now I’ve been assuming that if there’s a connection between nodes - a unit will be able to traverse between connected nodes.
I made it that way so that it’s consistent. Now you can use the ITraversalProvider to make thing unwalkable, and it will work exactly like if that node had been unwalkable when the graph was scanned. Previously, I had a lot of questions about why that was not the case.
Circling back to this issue after thinking about it for a while - I still feel that this isn’t consistent because of the automatic filtering inside the GridNode.
From my perspective, I see 2 areas where we can make changes that will influence how the agent will traverse through the graphs and this case could be potentially handled in both of them, and leaving it inside (somewhat hardcoded GridNode implementation) seems confusing for me.
We have a GridRules that could have simple remove that connections based on adjacent non-diagonals. That way we could have a graph in which we could predict how agents should move on just by looking at it. No connection = no possible movement.
We have ITraversalProvider for making things unwalkable, just as you said if for some reason it is needed to do it dynamically. If it would be done in the traversal provider the users could have it overridden if necessary.
Of course, if you don’t agree with that it is still your project, but then maybe you would at least consider adding some sort of toggle to disable that filtering? It will be pretty tough for me to keep updated if I have to modify your code at every version update.
I think @nevaleem is right on this. Current solution makes impossible to programm some unusual pathfinding. Imagine You want to make character who, like in this situation, jumps between other characters like gummybear in diagonal movement, and its a very important part of the rules (like bishop in chess). How am I able to find proper path for this gummybear? Your solution works only for walking (in a simple way) characters and I think this is not good if some hardcoded rules not allowed You for different scenario if there is a connection between nodes.
Hmm, it’s a good point.
I have made some changes and in the next beta update there will be this property exposed on the ITraversalProvider:
/** Filter diagonal connections using \reflink{GridGraph.cutCorners} for effects applied by this ITraversalProvider.
* This includes tags and other effects that this ITraversalProvider controls.
*
* This only has an effect if \reflink{GridGraph.cutCorners} is set to false and your grid has \reflink{GridGraph.neighbours} set to Eight.
*
* Take this example, the grid is completely walkable, but an ITraversalProvider is used to make the nodes marked with '#'
* as unwalkable. The agent 'S' is in the middle.
*
* \code
* ..........
* ....#.....
* ...#S#....
* ....#.....
* ..........
* \endcode
*
* If \a filterDiagonalGridConnections is false the agent will be free to use the diagonal connections to move away from that spot.
* However, if \a filterDiagonalGridConnections is true (the default) then the diagonal connections will be disabled and the agent will be stuck.
*
* Typically, there are a few common use cases:
* - If your ITraversalProvider makes walls and obstacles and you want it to behave identically to obstacles included in the original grid graph scan, then this should be true.
* - If your ITraversalProvider is used for agent to agent avoidance and you want them to be able to move around each other more freely, then this should be false.
*
* \see \reflink{GridNode.FilterDiagonalConnections}
*/
bool filterDiagonalGridConnections {
get {
return true;
}
}}
Hi, @aron_granberg, you missed my last hint (LayerGridGraphGenerator.cs line:1114) when making the last update. Unfortunately without modifying this file pathfinding will not work properly.
