I’m using A* for a Tower Defense Game with a Recast Graph and RichAI on the agents.
I need to make sure the player leaves a path for the enemies to walk from their spawn points to my base. My idea was to simply check if there’s a path from each spawn location to my base that would allow an agent with a certain width to pass. (That width would be a good bit wider than my actual agents, so they can still pass each other)
However, I seem to be unable to see the forest for the trees. The only way I found to check if there’s (potentially) a path is via IsPathPossible (which I already use to set the agents target), but this doesn’t account for the agents width.
Can you please let me know how to check if something of a certain size/width can navigate from one point to another?
What you can do is to use the grid graph’s setting called ‘Erosion Uses Tags’. This will assign all nodes next to walls with a given tag, and nodes a distance of 2 from walls with the next tag, and so on. Then you can use IsPathPossible overload with a tag mask that excludes for example all nodes next to walls and see if a path is still possible.
I’m currently converting my game from recast to layered grid graph (and from RichAI to AIPath) to try your suggestion, but I’m facing some issues. One that I can’t figure out is how to work with static obstacles that have vertical walls. Gradual slopes seem to be no issue, but I can’t get vertical walls to work.
If I don’t set a collision layer, everything looks fine (e.g. look at the barn roof), but agents run straight through the vertical walls:
Actually, setting the offset for the collision test did the trick. I set it to 1.4 for the moment (1 = it’s actually just above ground, +0.4 for the step height). The default with the collider sticking through the ground is a bit strange (but there’s probably a reason for it).
So far it seems that GridGraph doesn’t work too well for me - I like the general idea of it, and it works with the fact that I have my own grid to handle the constructables the players can place, but it really doesn’t work with any world objects that don’t exactly fit into grid nodes.
Recast Graph works great for my scenario, is there really no way for me to find out if an agent of width X can go from one spot to the other?
One with 0.5 agent radius that my agents use for pathfinding
One with 1.5 agent radius that I use to check if the player has obstructed my path.
The seeker on my actual agents use the first graph.
I then place a seeker component on my spawn points which uses the second graph, and ask them to see if they can reach the target. The problem is that, even when the spawn point is completely framed by obstacles (navmeshcuts), this returns true:
private void OnPathCallback(Path p)
{
Debug.Log($"{gameObject.name}: CheckPathTo finished");
_pathfindingInProgress = false;
if (p == null) return;
if (p.error) return;
if (!p.IsDone()) return;
Debug.Log($"{gameObject.name}: Valid path");
_hasValidPath = true;
}
I then actually release an agent (= spawn an enemy) and they also say “yeah that’s great, I have a path to the target, I’ll be on my way” only to get predictibly stuck at a wall.
I did some more testing. My CanMoveTo() that uses PathUtilities.IsPathPossible actually works. Sorry for the confusion.
I noticed that StartPath correctly does not find a path all the way to the target - see the green debug line, it doesn’t actually go all the way to the target transform if the start point is completely encircled by obstacles with navmeshcuts.
But if I look at the path in OnPathCallback, there doesn’t seem to be anything distinguishing the invalid/unfinished path from a good path that leads all the way to the target.
Also, it doesn’t seem to matter what I set the “Character Radius” on my Recast Graph (the one that I have only for this specific purpose) to, there’s always a path (green debug line) even if the gap is tiny.
Paths will always go to the closest point on the navmesh that it can reach. It’s hard to distinguish those cases because the destination is rarely (if ever) precisely on the navmesh. Often it can be a few centimeters (or meters) above/below the navmesh, or it can be slightly outside it. Without having game-specific knowledge, it’s impossible if that should be detected as a partial path or a full path. What you can do is to compare path.endPoint with path.originalEndPoint on the calculated path and see if they are close enough for your game.
The navmesh is shrunk by the character radius. This means that every point on the navmesh is a valid point for the center of the agent to be (i.e. a circle with the given character radius). So even a tiny sliver of navmesh is completely valid for the agent to be in. Having a navmesh that is shrunk by the character radius allows many calculations to be much simpler. Note that in the current version navmesh cuts do not shrink the navmesh by the agent radius in the same way, however in the beta version they do. It might be useful for you.
I’m guessing you realized that you need to also make sure that the GetNearest calls know which graph to use? You should assign the NNConstraint.graphMask field to a mask that includes only the graph you are interested in, otherwise it might find a node on the wrong graph.
Thanks for your explanations. I’m now checking path.endPoint vs path.originalEndpoint and if the distance is greater than a certain value, I consider the path incomplete. Some further testing needed, but this should work well enough (my endpoint will be unobstructed in all scenarios, so if I can’t get reasonably close, that’s enough indication for me that the path has been obstructed).
I still haven’t figured out my issue with the navmeshcuts though. I’m on the latest version 4.3.47. I just noticed that on the navmeshcut there is a property RadiusExpansion that by default is set to DontExpand. I set it to ExpandByAgentRadius but it doesn’t do what I hoped for.
In the picture below, every square on my construction grid is 1.5x1.5m. The player can place barricades to form a maze, but I don’t want him to create gaps smaller than 3m. In other words, he needs to leave a tunnel of 2 squares open. For that, I created a separate “obstruction check” graph. I then check if I can find a path from the start point to the end point, before the player can place a barricade. The barricades are navmeshcuts.
My problem now is that if I ask the seeker, that is placed on the start point and set up to only traverse my “obstruction check” graph which has a character radius of 1.5, it will still squeeze through a gap that is only 1.5m wide.
Would the right thing to do be to have 2 NavmeshCut scripts? One with size X and only affecting graph 1, and one with size Y and only affecting graph 2?
My NavmeshCut was set to Shape “Rectangle (Legacy)”. This is probably because I started out working with the asset store version. Once I switched it to “Box”, the RadiusExpansion works exactly the way I’d expect (and want) it.
