Correct way to implement "one-way" avoidance

Godot Version

4.2.1

Question

I’m currently working on a top-down scene where there a bunch of characters of the same type, each with a NavigationAgent2D. In that scene, there are also static objects that get incorporated into the NavigationRegion2D. These agents have destinations they’re bound for, which change over time, and sometimes they’re supposed to be standing still.

What I want to make happen is for agents that aren’t moving to stay put, and have other moving agents go around them. Think like a person standing on the street, someone walking would navigate around them.

What happens by default depends on my avoidance settings. In this case, I have a stander and a walker.

If I have avoidance enabled on both, the stander moves away from the oncoming walker as the walker approaches.

If I have avoidance disabled on the stander, the walker just attempts to walk straight through the stander, which fails in this case.

The solution that comes to mind is that perhaps I can convert my stander into a different state such that I turn off avoidance and rebake the navigation mesh perhaps? This feels really inefficient, but is the only way I’ve thought of as of yet. I also haven’t tried this, but conceptually seems like it should work.

So my question is, is that the intended way to do this kind of thing, or have I missed something in the documentation? If I understand what I’m reading, avoidance isn’t supposed to affect pathfinding, nor are obstacles.

Not to be prematurely optimizing anything, but if a rebake of my navigation region is required (which currently comes from a tilemap, if it’s relevant), I have concerns about performance. I eventually want a lot of these agents in a scene at once, and any arbitrary number of them standing and walking in possibly constrained areas.

Edit: After some more experimentation, is this what NavigationObstacle2D is for? It feels like it’s kind of acting roughly the way I want, kinda-sorta sometimes? I’m still messing with it, but it does seem to have an avoidance impact, but not necessarily on the path itself, and not consistently, which is odd to me.

Why don’t you use the avoidance_layers and avoidance_mask for this? That is basically their purpose, to define what should avoid what.

If you do not want to rely on avoidance and change the actual paths you need to change the navigation mesh. As long as there is a valid navigation mesh below your “standing” agent there is only so much the avoidance can do when the path still directs through that standing agent.

Yes NavigationObstacles only affect the avoidance velocities. They change nothing about the pathfinding.

One of the things I messed with was adjusting the avoidance layers and avoidance mask, and either I can’t achieve what I want or I wasn’t doing it right. The above scenarios were keeping avoidance mask and layers both to their defaults, i.e. 1 for both for the stander and walker.

I’ve tried turning off the avoidance mask for the stander, which theoretically should make the walker avoid it but it doesn’t avoid the walker. All that happens is that the walker gets close to it and then stops, presumably because it can’t get around it. My scene is wide open with a huge navigation layer, so it’s not that it doesn’t have room. My understanding was that this was by design. I’m not sure how else to affect it with avoidance layer and avoidance mask.

If you think that should work, then I can reduce my scene to even more bare bones and show what I’ve got.

Another piece of context I may not have provided is that when there are two walkers, I’d like them to both avoid each other. Not sure if I made that clear, because that wasn’t specifically what I was having issues with.

What is likely happening is that your movement code on the NavigationAgent forces the agent back on the path due to e.g. max path distances or path desired distance. So when the path point is blocked by something that is not part of the baked navigation mesh the agent can never get close enough to the path point to increase its path index and gets stuck.

1 Like

I also messed with those variables, but I haven’t tweaked the code yet. Thank you for validating what you expect to happen. I’m creating a new clean project with as little as possible to see if I can figure out what’s happening. It shouldn’t be relevant on its face that my agent is on a CharacterBody2D, right?

That your character is a physics node would only be relevant if the physics collision actively blocks the agent from reaching its target, e.g. a path point is blocked because the collision was not baked into the navmesh.

While avoidance works when one of the agents is not moving it has limited capabilities to make agents move around larger targets. The navigation path that the agent is following is not changing so the path points might still be blocked by the other avoidance object standing right on top of them.

1 Like

Я тоже решаю эту задачу, пока я не приступил к выполнению, но уже есть 2 идеи.
Первая для двигающихся персонажей. По скольку у меня нет Navigation Agent, а пути я вычисляю вручную, получая путь из Navigation Server, я закреплю Raycast к каждому НПС. Когда Raycast обнаружит на пути другого НПС, то перестроит маршрут исключив следующие точки с учетом радиуса НПС, то есть сместить путь на радиус НПС.
Смотри этот пример https://www.reddit.com/r/godot/comments/igcnn7/dynamic_obstacle_avoidance/

Второй способ управление геометрией Navigation Regions. Нужен для создания непроходимых или дорогих поверхностей в игре (к примеру Лужи).
Для этого нужно определить точки принадлежащие NavRegion, затем с помощью геометрических вычислений вырезать из текущей области новую и создать для него новый Region с иной стоимостью. Когда Region уже не нужен вернуть все обратно. https://docs.godotengine.org/en/stable/classes/class_geometry2d.html
Я пока не приступал к воплощению, поэтому детальней ничего написать не могу.

1 Like

@smix8 So the behavior I was seeing in my first test scene was with code I had from a project I’ve been working on. I made a very bare-bones project with just the essentials, with mostly code from examples: GitHub - dfego/one-way-avoidance-test

I think everything is in order, but it’s still not doing something. I’ve seen agents do avoidance in my own game, so I’m not sure what I may be missing here, but this will hopefully be a learning experience.

@comrade_suli I translated your response (thanks, Google!) and appreciate the ideas! The first idea is something I’ve considered having to do later, even if avoidance works now, because of some complex behaviors I’m hoping to create. The second one seems expensive performance-wise, unless I manage to split up the map into a lot of different regions (which feels expensive itself).

Okay, so I tried messing with more variables in my basic scene, and the one that seems to have an impact is Time Horizon Agents. The default is 1 second, but raising it even to 2 seconds gets my walker around my stander. It still bumps into the stander, which implies I need to tweak another setting, but I guess my question is why is this happening? Are there constraints on how abruptly the avoidance system will suggest changing an agent’s velocity? In my case, I wouldn’t mind getting pretty close and then just scooting around. It seems kind of like if the time horizon is only 1 second in my case that it doesn’t have the ability to move fast enough to get around it, but there’s always an option for getting around it.

So I guess I’m confused. Do I already need to lean less on the built-in navigation, or am I just not using it right?

These test line scenes do not work where both agents move on a perfect line against each other.

RVO avoidance works with passing sides and expects that those exist. In a “natural” movement no agent will keep the perfect line velocity so there will always be a situation which triggers the assignment of the passing side.

In an unrealistic tech demo where both agents are moving only on a line against each other or one agent is not moving at all from the start this will never happen so the avoidance will not work at all.

If you increase the path desired distance and path max distance to a high enough value that an agent can move around an avoidance object without constantly reseting its navigation path it can work. But it works a lot better when both agents are at least using their velocity, even if one agent is nearly not moving, because that allows the internal orca planes to be contructed correctly used by the RVO avoidance to determine which directions are still free and usable.

Time horizon is a tricky one, it is the time in second that a velocity need to be kept without collision. If the agent can not keep this velocity for this time it will slow down its velocity. It should be kept between 0.1-1.0 sec in most cases, too high and your agents will crawl half the time, too low and your agents will be frantic changing the directions all the time.

1 Like

Thank you for the detailed information. I think what this confirms for me is that for my desired behavior, representing people navigating and milling around an area, with some standing still, that I’ll probably want to turn off the built-in avoidance and code up something on my own. It might be helpful for the documentation to a little more clearly spell out the limits of this system, because without that, it’s easy to think it’s a bit more powerful and versatile than it is.

I suppose one could argue the system could be augmented too. :thinking: All that code is in the engine, right? In C++?