A* Pathfinding Project

Local Avoidance For Specific Agents


#1

Hi! I was wondering if you could help me with the problem I’ve been having with my project. Let’s say I have 15 agents in the scene, each of those agents has a list of agents he is trying to avoid. What I want to do is to create a bigger invisible wall around those agents that will be avoided by agents that are on the list only and since the wall is attached to the agent, it will move as the agent moves. I tried using the local avoidance but I realized it’s not the one that I need because in local avoidance, the agent will stay on its original path while trying to avoid those agents. What I need is to treat the invisible wall as a moving obstacle so the agents will actually repath to its destination while avoiding the invisible wall instead of staying on the original path while avoiding. Hope you can help me with this. Thank you very much in advance!


#2

Hi

It’s hard to say without knowing the specifics of your game… but possibly you could do something with the ITraversalProvider (see https://arongranberg.com/astar/docs/turnbased.html#ITraversalProvider).

The idea I’m thinking of is to use the ITraversalProvider to add a large penalty for a unit to traverse a node close to a unit it is trying to avoid. That will make them try to navigate around them if it is at all possible. I would not recommend making nodes completely unwalkable if a unit gets too close as that will confuse it a lot and might make it try to move through (actual) walls or something like that (as it can then not distinguish between nodes too close to another unit and actual walls). Penalties usually work better for cases like this.


#3

Hello

I was also thinking of using penalties but my only worry is that since penalties are given to the node itself (not the agents), it would be costly for the performance to update the graph/nodes every frame since our agents are constantly moving. Is there a way for the penalties to be attached to the agents, much like the local avoidance, so that the penalty area will also move as the agent moves?

Thank you


#4

Hi

That’s the good thing about the ITraversalProvider. The penalties are never stored in the graph but are instead only calculated on demand by whatever code you use to implement that interface. This means that the graph will never have to be updated.


#5

Hello again

I tried using the ITraversalProvider, adding a high penalty to nodes that are inside the radius, but I’m having a problem with this. It’s not accurate. I mean, even if I put a high penalty to those nodes, the agent still makes a path through those nodes. Sometimes, it create paths correctly, but most of the time it doesn’t. Upon further testing, I noticed that it is very accurate when I set my Node Size of the Grid Graph to 1 (default), but we are currently using a Node Size of 0.2. Is there a reason why smaller node size is not accurate when adding penalties? Also, is there any way to log the total cost of the ABPath when I received the path? And also, is there a way to get the actual list of nodes that the agent will traverse upon receiving the path because I understand that there is a list of graph nodes in the ABPath but it’s not post processed? I need the actual list of nodes that the agent will traverse.

Thank you very much!


#6

By the way, our game is not turn-based, it’s real time. ITraversalProvider will still work though right? Because I just realized that it is under the “Utilities for turn-based games”.


#7

UPDATE: Upon testing further, it appears that the culprit for the inaccuracy is the Raycast Modifier, since it removes nodes significantly. I will still test further to confirm that this is really the cause.


#8

Sorry for the late answer.
Ah, yes the RaycastModifier does not take into account any tags or penalties for the nodes (I have some beta code that does that… but it’s tricky to get right for the more general case). If you do this you probably want to remove that. You could use the funnel modifier which also simplifies the path a bit, but not as much.

Yes, it will work perfectly well. The rest of the stuff on that page is intended more for turn based games though (even though they also work for real time games).


#9

FYI: I found that building a modified Raycast algorithm into the seeker was slightly faster than optimizing the whole paths when paths are long and when updates to paths are frequent.
We just use a simple incremental algorithm that periodically tests to see if the “next” graph point is visible from the AI’s current position, and if so, skips ahead. We snap the current position to the layered grid and use the fast grid linecast algorithm between the current node and the nodes in the path.
It also helps AI’s stay away from walls as we can include the tags when finding the current node and all nodes of the path are guaranteed to be a distance from walls.
Unfortunately the linecast algorithm ignores tags, so AI’s occasionally get too close to corners, but this is acceptable for us