Local avoidance issues on Recast graphs

[SeithCG]

Hi, I’m seeing some weird behaviours on my agents related to local avoidance. Basically they behave a little as if they ignored each-other presence, grinding against each-other instead of gracefully avoiding each-other.

In this picture the agent at the bottom is desperately trying to go right and up the slope but it’s just stuck against the other (static) agent:

They just don’t seem to realize that they can block each-other way and instead try to take the simplest path to their target. For example in this screenshot the agent on the right is supposed to go to the capsule agent to the left but instead of taking the available route at the top it just bunches up aimlessly against its colleague:

Here are some more info:

• I use RichAI and a RVO component
• I only have one RVO simulator
• The agents have a character controller component but no rigid bodies and they’re on a layer that doesn’t collide with itself.

The RVO simulator is in the main scene (different from the scene where the agents are) but I tried moving the component to the same scene as the agents (although it’s not Unity’s main/active scene) and it didn’t change anything.

Here are my settings for the RVO simulator:

And the agent components:

[aron_granberg]

Hi

You can try the 4.3 beta version (see https://www.arongranberg.com/astar/download). The beta has improved local avoidance when one of the agents is locked.
Note that if you are just setting the ai.canMove property to false then the movement calculations are completely disabled. The other agents will not know that the agent cannot move and they will assume it can at least partially move out of the way. Set the RVOController.locked property too to ensure that the local avoidance system knows that the agent cannot move.

[SeithCG]

Thanks Aron. Unfortunately at this point I cannot update to 2019.3b8 yet (I’m on 2019.1.5).

In any case I tried using the locked variable on the RVO component in the hope it would improve the situation (in the current non-beta A* version), alas it doesn’t.

[aron_granberg]

When are the cases then the agents are completely stopped?
If they are stopped for a longer time you may want to consider using a navmesh cut to change the navmesh under them to enable other agents to better route around them.

[SeithCG]

Agents get “frozen” (canMove, canSearch, enableRotation set to false + disabling of RichAI) when they attack or get hurt. Which is about 1s each time.

I also tried not disabling the RichAI (which if you remember was done to fix the issue of agents still going to their previous destination for a fraction of a second after getting “unfrozen”) but it didn’t improve anything either.

I’ll try the navmesh cut option and report here, but I’m afraid it might be opening a new can of worms (in terms of nearby agents being affected)…

[SeithCG]

Alright that was to be expected but using navmesh cuts in the middle of the action (ie. anything beside an agent being dead) results in a teleporting festival.

If an agent is close to other agents when its navmesh cut component gets activated (which is always the case in melee combat), then the other agents are of course teleported to the boundary of the new hole in the navmesh. Since they all in turn activate and deactivate their component it just looks like a huge mess with the agents progressively being displaced and trying to rejoin their target throughout the navmesh.

So, unfortunately, using an obstacle on the fly doesn’t seem to be a viable solution to reroute agents. And I’m not even talking about the fact that it downright changes the actual flow of the topography, which is definitely not a desirable side-effect.

Again, referring to the screenshots of my first post I’m just looking for a way for agents to realize their path is blocked by another agent and that if there’s an available route 2 meters away they should take it. Even if it is technically longer than the desired straight line.

[SeithCG]

Ok so I went ahead and upgraded the project to 2019.3.0b8 following the upgrade instructions but after I imported the package I get an error:

Assets\AstarPathfindingProject\PackageTools\Editor\EditorBase.cs(23,20): error CS0103: The name 'EditorResourceHelper' does not exist in the current context

Would you know how to fix this, please? I’m kinda stuck right now…

Update 1:
I ended up deleting the A* folder and reinstalling it from scratch. Got a few error messages on the way, had to restart the editor a couple of times. That worked (no more errors), but now, after I closed Unity I can no longer open it. It systematically crashes at the start.

Update 2:
After restarting my PC it doesn’t crash anymore. So that’s a good point.

However after exiting play mode I got 2 errors. I figured they might have been related to the graph which was not updated so I pressed Scan to recreate the cache but now I got a flood of errors saying:

ArgumentException: burst
Pathfinding.EditorBase.FindProperty (System.String name) (at Assets/AstarPathfindingProject/PackageTools/Editor/EditorBase.cs:126)
Pathfinding.EditorBase.PropertyField (System.String propertyPath, System.String label, System.String tooltip) (at Assets/AstarPathfindingProject/PackageTools/Editor/EditorBase.cs:141)
Pathfinding.RVOSimulatorEditor.Inspector () (at Assets/AstarPathfindingProject/Editor/RVOSimulatorEditor.cs:19)
Pathfinding.EditorBase.OnInspectorGUI () (at Assets/AstarPathfindingProject/PackageTools/Editor/EditorBase.cs:94)
UnityEngine.Debug:LogException(Exception, Object)
Pathfinding.EditorBase:OnInspectorGUI() (at Assets/AstarPathfindingProject/PackageTools/Editor/EditorBase.cs:96)
UnityEngine.GUIUtility:ProcessEvent(Int32, IntPtr)

They happen every time I have the A* game object selected.

Update 3:
The error messages still happen after exiting play mode:

InvalidOperationException: Not allowed to access vertex data on mesh '' (isReadable is false; Read/Write must be enabled in import settings)
UnityEngine.Mesh.SetVertexBufferData[T] (Unity.Collections.NativeArray`1[T] data, System.Int32 dataStart, System.Int32 meshBufferStart, System.Int32 count, System.Int32 stream, UnityEngine.Rendering.MeshUpdateFlags flags) (at <dfc62061cb3f4b1bb57c5179a5db6830>:0)
Pathfinding.Util.CommandBuilder.Build (Pathfinding.Util.RetainedGizmos gizmos, Pathfinding.Util.RetainedGizmos+Hasher hasher, Unity.Collections.NativeArray`1[T] buffers, UnityEngine.Camera camera, System.Boolean isGizmos) (at Assets/AstarPathfindingProject/Utilities/CommandBuilder.cs:391)
Pathfinding.Util.RetainedGizmos+BuilderData.SubmitPerCameraMeshes (Pathfinding.Util.RetainedGizmos gizmos, UnityEngine.Camera camera) (at Assets/AstarPathfindingProject/Utilities/RetainedGizmos.cs:185)
Pathfinding.Util.RetainedGizmos+BuilderDataContainer.SubmitPerCameraMeshes (Pathfinding.Util.RetainedGizmos gizmos, UnityEngine.Camera camera, System.Int32 versionThreshold) (at Assets/AstarPathfindingProject/Utilities/RetainedGizmos.cs:232)
Pathfinding.Util.RetainedGizmos.Render (System.Boolean allowGizmos) (at Assets/AstarPathfindingProject/Utilities/RetainedGizmos.cs:491)
Pathfinding.Util.RetainedGizmosWrapper.Submit () (at Assets/AstarPathfindingProject/Utilities/RetainedGizmosWrapper.cs:163)
Pathfinding.Util.RetainedGizmosWrapper.PostRender (UnityEngine.Camera cam) (at Assets/AstarPathfindingProject/Utilities/RetainedGizmosWrapper.cs:77)
UnityEngine.Camera.FireOnPostRender (UnityEngine.Camera cam) (at <dfc62061cb3f4b1bb57c5179a5db6830>:0)
UnityEngine.Camera:Render()
<RefreshOvertime>d__34:MoveNext() (at Assets/Enviro - Sky and Weather/Core/Scripts/EnviroReflectionProbe.cs:333)
UnityEngine.SetupCoroutine:InvokeMoveNext(IEnumerator, IntPtr)

And are followed by a series of other errors:

A Native Collection has not been disposed, resulting in a memory leak. Enable Full StackTraces to get more details.

And warnings:

Internal: JobTempAlloc has allocations that are more than 4 frames old - this is not allowed and likely a leak

Update 4:
Sigh. Well I feel I just jumped through all those hoops for nothing. The issue is still there, exactly as with the non-beta version. Agents don’t realize they block each-other way.

This is a major issue and a basic requirement. I genuinely hope that you can agree with that. A* is the best locomotion system I’ve tried so far. So much better than the Unity one.

Please let me know how I can be of help in sorting out this problem.

Update 5:
(I reverted to 4.2.8 since I had to keep working)

[Christougher]

What about temporarily assigning a large penalty to the nodes underneath the stationary AI? I believe there are several threads that discuss that

Like this?

Better way to penalty for stationary units

I am using grid graph and I am having dificult to change node penalty when a unit stop. After a lot of random programing I finished with something like the code below, not so beatiful, but functional. The problem is that some times, expecially when I create many units near of same node, I receive the warning log (see LogWarning below) and could not restore node penalty. Everything indicates that it was caused by nodes assyncronos update, I try to remove the penalty before it had been applied. …

Updating grid graph obstacle / penalties manually

I’ve been manually changing obstacles / penalties (without colliders) by overriding RecalculateCell like so: public override void RecalculateCell(int x, int z, bool resetPenalties = true, bool resetTags = true) { var node = nodes[z * width + x]; // Set the node's initial position with a y-offset of zero node.position = GraphPointToWorld(x, z, 0); float moveModifier = MySpecialIndependentGridClass[x, z].MoveModifier; bool walkable; uint …

I would be interested as well in the proper way to temporarily alter tags and/or penalties and then revert them.

[SeithCG]

Hi @Christougher. Thanks for your reply! The concept of making a very small area (basically just around an agent) a very high penalty sounds great because it doesn’t actually change the navmesh itself.

Now I have some questions regarding this:

• Does this work on Recast graphs?
• Is there a way to visualize the penalty areas on the navmesh?
• Can GraphUpdateScene be used for that purpose (ie. Are they made to be used on moving things like agents)?
• Does changing the penalty of an area at the position of an agent cause the agent to want to move away from it (in the case of agents melee-fighting that would be a problem of course)?

[ToastyStoemp]

Implementing a temporary block / penalty can be done unrelated from the graph type.

I wrote a little bit more about how I personally implemented such system for our game here: Avoidance, but not local

The ITraversableProvider is a great interface to modify the search based on some parameters.

Almost all the links are in the linked topic.

[SeithCG]

Thanks @ToastyStoemp. I will have to carefully look at your suggestion, although at first sight it looks a bit daunting to implement…

I did some more tests using a GraphUpdateScene component on the agents (the orange lines on the screenshot) with 10000 penalties, changing the tag value to Obstacles, modifying the walkability, etc. Nothing made any difference at all.

So it’s back to square one. I’m still not sure if this is a bug in the system or if agents were never supposed to be able to take another path if their current one was blocked by another agent.

To go back to your suggestion, Wolf, it sounds like A LOT of work to basically try and bend the system into working as it’s supposed to (you even recognize that “This solution is definitely not the best one”).

So I would really like to get @aron_granberg to weigh in on that situation and address it head on, as I perceive it to be a fundamental requirement.

[ToastyStoemp]

Using the ITraversableProvider is really not that much work to implement. maybe like 10 - 20 lines of code. And looking at your problem I think that would be plenty. I took it the extra step using the NNConstraints as I also wanted to make resample the destination. Also this isn’t really that difficult.

RVO or similar systems are indeed the ideal solution. We’re bending the system a bit with the ITraversable. I opted for the ITraversable solution as I want all my agents to use rootmotion for all their movement. And so far I haven’t gotten great results from RVO + Rootmotion ( though I should re investigate this now that my knowledge of these systems has grown).

[SeithCG]

Hey @ToastyStoemp so I’m following the tutorial on this page: https://www.arongranberg.com/astar/documentation/dev_4_3_0_993e267e/turnbased.html

My problem is with the BlockerPathTest.cs part. How does this work with RichAI? It looks like it’s micro-managing the path creation but I thought RichAI is supposed to take care of everything. In other words, how can I make RichAI work with the BlockManager?

Also, does this system replace the use of the RVO component on the agents?

[ToastyStoemp]

I wouldn’t say replace RVO.

Using the ITraversableProvider just customizes the search conditions for A*.
Default A* would say is this node walkable? yes -> Add it to the open list. No? Add it to the closed list.
The ITraversableProvider allows you to expand on that. So you can say something like:
If Node is walkable && is Node Not Part of the blocked list.

[SeithCG]

Ok that sounds really great, but from a practical point of view, how can I use it? How can I feed the information of the BlockManager into the RichAI script?

I found this post by @aron_granberg about a potential “solution”: https://arongranberg.com/2015/06/cooperative-pathfinding-experiments/ which suggest he’s aware of the problem. But it’s 4 years old and mentions a list of issues that makes it basically non-usable in a real-world production (which might be the reason why it never found its way into the official package)… sigh

[ToastyStoemp]

path = seeker.StartPath(start, end);
path.traversalProvider = traversalProvider;
//optional 
path.BlockUntilCalculated();

[SeithCG]

Thanks, I’ll try that!

So my questions were really about RichAI (which already works with Seeker and automatically takes care of path pooling). Are you saying that I should not use RichAI? I’m asking because @aron_granberg told me to not use StartPath on the seeker and instead simply set the destination on the RichAI script (plus do a SearchPath if the search needs to happen right away).

[ToastyStoemp]

That’s a valid point, I think the main reason Aron recommended using the seeker.destination is to aid the RVO. Making sure the agents are also brought back to their designated destinations after being pushed.

I don’t know what the correct answer is here to be honest.

The ITraversableProvider worked for me personally, though we don’t use RVO at all. I wouldn’t know what the best way (if any) to combine these 2

[SeithCG]

Alright I managed to get something that works. Thanks for pointing me in the right direction, Wolf!

As you can see on the screenshots below the second spider is capable of re-routing itself once its path becomes blocked and still manages to reach (and attack) its target.

The nice thing is it works with RichAI + Seeker. It’s also relatively simple in the end although it still feels a little too hacky for my taste and I still think something clear and simple should be available right out of the box.

I’ll keep testing the system in different situations and hopefully I won’t have to report any more issues (at least on that topic)!

[aron_granberg]

Hi

So there are basically 3 ways of dealing with things like this:

• Local avoidance. This is however only very local, which means it doesn’t do any higher order planning at all. It can move to the side of an agent in a way that works well in a crowd but that’s pretty much it in terms of avoidance. It cannot take a completely different route in the navmesh. One solution one can try is to give each agent a randomized priority (set on the RVOController). What this will do is that if two agents are stuck just pushing against each other in a narrow corridor having differing priorities will make sure that one of the agents can take precedence and push the other one away, thereby resolving the conflict.
• Updating the navmesh graph. E.g. using a navmesh cut as I suggested before. This makes sense if the blocking agent is stationary and will remain stationary for a longer period of time. This will allow the agent to route around it. I would suggest making the navmesh have the same radius as 2x the blocking agent’s radius. This will make any other agents stop at the same distance as they would when just using local avoidance and they will not be suddenly teleported away.
• Using the ITraversalProvider. This is the most flexible solution, but also the one with pretty much no pre-built anything. I’m glad you managed to get something to work. It’s quite tricky to get something working for generic games because different games differ so much.

@SeithCG

@aron_granberg told me to not use StartPath on the seeker and instead simply set the destination on the RichAI script (plus do a SearchPath if the search needs to happen right away).

Setting the destination is best if you are just using a normal ABPath and can let the RichAI script handle that itself. If you want to use a custom path type you should use ai.SetPath.

// Disable the built-in path recalculation
ai.canSearch = false;
var path = ABPath.Construct(start, end, null);
path.traversalProvider = traversalProvider;
ai.SetPath(path);

Using SetPath instead of seeker.StartPath will allow properties like ai.pathPending to work properly, but otherwise it is roughly equivalent.

See IAstarAI - A* Pathfinding Project

Is there a way to visualize the penalty areas on the navmesh?
You can set A* Inspector → Settings → Graph Coloring to Penalty and then you will get a color coded visualization of the penalties in the scene view.

Does changing the penalty of an area at the position of an agent cause the agent to want to move away from it (in the case of agents melee-fighting that would be a problem of course)?

TL;DR: no. If an agent is already standing at a node then it’s penalty doesn’t really affect the agent’s path at all. When the agent plans a path it will try to find the total cost of the path that is as small as possible. But if the start node has a penalty that will be go into the cost calculation for every possible path and thus it will not matter since it’s the same for every path.