A* Pathfinding Project

Testing multiple points to shoot on a target


#1

I would like to find a way to shoot a target from potential points around the target.

What I do is:

  • First, I check on the navmesh if there points I’m looking for are walkable.
  • If they are walkable, I calculate a path to the point.
  • If the path can be completed and walked on (no holes, walls blocking the way): I save the point as a valid option.

Finally, I create a path from the starting point to the end point and make the NavMeshAgent use that path.

This is what I did using the navmesh system. It seems quite brute force so if anyone has a better idea I’m all ears, because I plan on using this sort of movement for almost any shooter.

What I like about this algorithm, is that I can pick the distance I want from the target.

With Unity’s NavMesh system I used 2 functions and everything was calculated during one frame:

               // 1) find a valid point on the navmesh
               NavMesh.SamplePosition(testPosition, out var navMeshHit, maxDistance, NavMeshConstants.WalkableArea);

                // 2) can we reach that point of the navmesh
                if (found)
                {
                    var navMeshPoint = navMeshHit.position;
                    Agent.CalculatePath(navMeshPoint, path);
                    if (path.status == NavMeshPathStatus.PathComplete)
                            {
                            }
                }

My question is two-fold:

  1. Is there a smarter/more optimized way to achieve something similar?
  2. How do I do this the Astar way? (which functions do I use?.. How can I calculate this in one frame?)

#2

Hi

Note that you do not need to explicitly find a path to the node to figure out if it is reachable. You can use the PathUtilities.IsPathPossible method instead.

If you need a path request calculated immediately then you can use the BlockUntilCalculated method on the path object.


#3

Amazing ! That’s surely going to be a big performance boost :slight_smile: Thank you


#4

I notice that IsPathPossible supports a tag list, but that it doesn’t support a GraphMask. Is there any way to use IsPathPossible while excluding specific graphs?

For example, I have a feature where one of my AIs can break down walls. I’ve implemented this as a NodeLink. Upon begining traversal, the AI will break the wall, at which point the path through the wall becomes walkable:

Before:
image

After:
image

This works great. However, there are time when I want my agent to walk around (random patrol) without trying to use these off-mesh links. In trying to evaluate whether a given random position is a suitable destination, I was hoping to use IsPathPossible, with a GraphMask override to instruct it not to use these kinds of node links. (All of those node links are on their own PointGraph).

Does that seem possible? I think the only way I can get this working currently is to actually use seeker.StartPath(), and then ignore the path if it contains any of these kinds of links.


#5

Another method of finding this type of point is by using something like the RandomPath. and calculate a random point from the player towards the agent.
https://arongranberg.com/astar/docs/wander.html scroll down to Method 3 The RandomPath type
You can add an ‘aim’ direction on the RandomPath to get points closer to the agents original position:
https://arongranberg.com/astar/docs/randompath.html#aim


#6

Wouldn’t 2 graphs that are connected have the same graph layer anyways?
So path from one graph layer to another is never possible


#7

Maybe I’m misunderstanding how to use GraphMasks, but say I have something like this, a Recast graph with two other Point graphs, each containing different kinds of NodeLink2 links:

image

My goal, for random patrol, would be to set the GraphMask such that only the first two graphs, but not the “Fragile Breaks” graph, would be included. This isn’t possible with IsPathPossible, as there is no graph mask option. But it seems to be an option for Seeker.StartPath, which allows a graph mask to be provided. I was just trying to determine if there was a more efficient way to answer the question “Is it possible to get from A to B, but without using the one of the graphs”.


#8

Hi

Using the IsPathPossible method with a tag mask is (as the documentation mentions) pretty slow. In fact if you want to use a tag mask (or graph mask) calculating the path can often be faster. The IsPathPossible method is very convenient, but it can only be highly performant if you just have two nodes and no other constraints.

Btw. You can use an ITraversalProvider when you are calculating the path to prevent the agent from using any node links (by e.g. making it treat all PointNode’s as unwalkable).

See https://arongranberg.com/astar/docs/turnbased.html#ITraversalProvider

The graph mask as used by e.g. the StartPath method is only used when searching for the closest nodes to the start and end points. The path may pass through any graph regardless of the graph mask.


#9

Another odd thing is that IsPathPossible appears to return true in cases where two regions are completely isolated from each other. For example, in this image, the two navigable regions are isolated by a navmesh cut, and the blue walkable regions are clearly not connected. However, IsPathPossible returns true when trying to go from one side to the other.

And if I try to request a path from one side to another, it provides me with a valid path, whose status is Complete, which contains various triangle nodes going from A to B.

Is there something special I need to do such that gaps like this aren’t considered connected?


#10

Well… that sounds like there is a valid path between those two points?


#11

I bet I know why I’m getting unexpected results. It’s because the gap between the two areas is due to a NavmeshCut. IsPathPossible probably doesn’t look at navmesh cuts, for performance reasons. Those areas are connected, sometimes, just not at the time I was calling IsPathPossible

Here’s some visual debugging, where my agent thinks he has a valid path from the left-most grey box to the green target circle. The other grey boxes are the nodes returned by the path provided by seeker.StartPath:

IsPathPossible thinks there’s a path to the green circle, and then the path claims to be Complete, even though the nodes don’t get very close to the green circle. Overall, I’m just trying to verify whether the agent can get from A to B.

At first I tried testing whether the desired destination and the last nodes in the path were close together. But since they’re navmesh nodes, they tend not to be, and I got a lot of false positives where I’d get nodes on the other side of relatively thin walls. So I’m still trying to find a good way to know that an agent can reach a position.


#12

Hi

The path may succeed because the system by default only tries to find a path to the closest point to the target that it can reach. In this case it is right up to that navmesh cut.

I’d advice you to compare the end point of the path with the destination you actually want to reach and see if they are close enough. You can also set the cutoff threshold for how far away from the query points the system will search using the A* Inspector -> Settings -> Max Nearest Node Distance setting.

The IsPathPossible method definitely considers navmesh cuts. If you change A* Inspector -> Settings -> Graph Coloring Mode to “Areas” then the nodes will be colored accoring to their connected component (see https://en.wikipedia.org/wiki/Component_(graph_theory)). The IsPathPossible method will return true for nodes that have the same color and false for nodes with different colors.

See also https://arongranberg.com/astar/docs/pathfinding.html#GraphDebugMode


#13

Thanks. I’ll take a look at that, and I’ll keep digging.

Interestingly, the two areas appear to be distinct. Here’s the graph with area coloring enabled. But IsPathPossible was still telling me the path was possible. I’ll just do some more debugging to make sure I wasn’t misinterpretting things.

image


#14

Make sure your nodes are what you think they are. E.g. by drawing a line between them

Debug.DrawLine((Vector3)nodeA.position, (Vector3)nodeB.position, Color.red);

#15

Yeah, I’m surely doing something wrong in my code. Using the following to test for connections between the two areas, I get all consistent “false” results from IsPathPossible.

            if (Input.GetKeyDown(KeyCode.J))
            {
                var nodeA = AstarPath.active.GetNearest(A.position).node;
                var nodeB = AstarPath.active.GetNearest(B.position).node;
                var possible = PathUtilities.IsPathPossible(nodeA, nodeB);
                Debug.DrawLine((Vector3)nodeA.position, (Vector3)nodeB.position, possible ? Color.green : Color.red, 1);
            }

So I’ll look for my error.