RVO Avoidance

Development Programming & Scripting
1

I’m trying to use your RVO implementation.

Are the Weights actually used? In the code it looks like “VO” is used and RVO and weights are not actually used for me anyway.

What is OverrideWeightTime? how do I use that?

If I have a static object that can’t move itself should its weight be 1.0?

We are on 4.11 currently.

Thanks

1 Like
2

Hi, Jack. Let’s go through these questions:

  1. If weights are really not being used, there’s a bug, but as far as I know, they are. The idea behind weights is that that two objects trying to move around each other will act differently, where the lower-weight object will divert course more and the higher-weight object less. You can see this about halfway through UAvoidanceManager::GetAvoidanceVelocity_Internal(). When it calculates “EffectiveVelocityB” in that code, it becomes RVO because it is now avoiding against the anticipated reaction of the other object instead of the other object’s actual, current behavior. If you have a test level with two RVO characters walking straight at each other, they should each dodge about the same amount. Changing their relative weights should affect the amount each one dodges as described above.
  2. OverrideWeightTime is also used in UAvoidanceManager::GetAvoidanceVelocity_Internal(), right around the same place where weights are used. The point of that variable is to make that object ignore other objects temporarily, and let them know that this is the case. It was made for internal use, so that an RVO object that was avoiding another object would “lock in” to that avoidance maneuver for a short time, preventing jitter/rapid directional changes, as well as wasted computation. You could theoretically use it for something like a normally low-weight character who is executing some kind of lunge/dash/charge move and can’t (or won’t) adjust trajectory, although I have not tested this use case.
  3. Yes, if you have an object that isn’t going to reciprocate, it should be at max weight. Since the object isn’t moving, its expected course deviation would be nothing anyway. Since you mentioned it, you could even use OverrideWeightTime in this case, you’d just have to keep that timer from running out (setting it to max float would do it).

I hope this answers all of your questions. If it doesn’t, or if something doesn’t work as I described, please let me know. Thanks!

1 Like
3

OK thanks, yea that answered them.

I’ll keep playing with it. I’m not getting any RVO avoidance but instead VO.

Here: if ((OtherObject.OverrideWeightTime <= CurrentTime) && ((OtherObject.Velocity|PointBRelative) < 0.0f))

Possibly because I’m using vehicles and they are not usually going head on at each other. but one may stop in front of the other one.

I’ll debug it some more and get back to you if I cant figure it out.

One more question and this may be a side effect of RVO/VO anyway.

Sometimes they get confused on which way to go left/right and oscillate left and right and ultimately end up hitting the thing they are trying to avoid. I just read some RVO papers so this may be a normal problem with it?

I will try OverrideWeightTime, that may get them picking the first move and not oscillate.

Thank you.

4

OK, good to hear!

About the line of code you posted: Yes, if that branch is not met, then the other object is in override mode or is moving away from our object. In those cases, we know it will not reciprocate our avoidance attempts, so VO is used.

Is it possible that your vehicles have a combination of short sensing distance, narrow angle choices, and high movement speed such that they have no viable avoidance options and just elect to slow down/stop instead?

The left/right oscillation thing was what I was trying to avoid by adding the OverrideWeightTime concept. It may be that your time for overriding (assuming you have it in use) is too short. Basically, if you think that the characters just making a decision and sticking with it would help, then OverrideWeightTime should be useful.

About RVO, yes, it does inherently have some limitations. It’s basically a very short-range sidestepping system, and it’s not perfect. Some of the questions you have to answer as you code it are things best left to approximation, such as “what’s the best way to sidestep this person?”, which doesn’t have a single objectively-best answer. In our case, we try a set of angles and see which one grants us the most movement in our original direction, which seems reasonable, but isn’t provably the best answer in all cases. In short, there’s an element of heuristic behavior in RVO, but it usually works well and I haven’t seen it mess up in any reasonable situation, even including things like 200+ AIs looping around a four-way, bidirectional intersection.

Please do let me know if you find anything interesting in your debugging, or what solution you come up with. And of course, reply here if you have further trouble or have reason to believe there’s a bug. Thanks!

5

Slowing down/stopping is not actually working for me yet. I haven’t hooked that up yet. Our vehicle code is quite a lot different from the vanilla unreal vehicle stuff, so that will take me a bit to get working right.

They do avoid each other using steering changes only pretty well as they follow their spline path. I can drive and stop in front of a group of them and they get around me ok.

What i’m basically trying to do is prevent them from choosing paths that take them off of the road they are on. I may just have to customize the AvoidanceManager to do just what I need. I tried creating dummy IRVOAvoidanceInterface objects along the edge which sort of works.

6

I think I see what is going on in WheeledMovementComponent…

		FVector NewVelocity = AvoidanceManager->GetAvoidanceVelocityForComponent(this);
		if (!NewVelocity.Equals(AvoidanceVelocity))		//Really want to branch hint that this will probably not pass
		{
			//Had to divert course, lock this avoidance move in for a short time. This will make us a VO, so unlocked others will know to avoid us.
			AvoidanceVelocity = NewVelocity;
			SetAvoidanceVelocityLock(AvoidanceManager, AvoidanceManager->LockTimeAfterAvoid);

Basically does the OverrideToMax weight, which means vehicles never do RVO essentially so their weights don’t do anything., they always do regular VO?

Note: I had to fix a seperate bug here to get this working originally.
https://udn.unrealengine.com/questions/311171/rvo-vehicle-avoidance-bugs.html

7

I see what you’re saying there, but I believe that this is still RVO. The first object to be processed will calculate AvoidanceVelocity in a reciprocal manner. It accounts for its weight and the weight of the other object, and it diverts course based on the relative weights. Thus, the first object is using RVO and is doing its fair (weighted) share. At that point, the first object commits to that plan and is temporarily acting as a VO. The second object then has two choices: Either do a weighted avoidance against the previous state of the first object (RVO), or do an unweighted (VO) avoidance against its new state. In this code, we choose the VO way because it doesn’t require caching the other object’s state, and because avoiding the new state effectively factors in the dodge weighting anyway. This makes it ultimately work the same as RVO, because the bigger dodge the first object did, the smaller dodge the second object will need to do. Furthermore, if the first object had to deal with multiple objects to avoid, the second object will now, at no additional cost, factor that in and avoid against its actual intended velocity.

Thanks for fixing that bug you linked with the wheeled movement component. You’re right that the lock time after a clean move should be really small, preferably shorter than one frame. I don’t know what to say about the Z issues - this system ran in 2D when I worked on it, so I can’t comment on that as well as Lukasz. But it looks like those were good changes, so thank you for that.

I hope that this explanation of how we combine RVO and VO to create the effect of RVO with only one weighted calculation and no cached object state. If this isn’t clear, or if you believe it to be incorrect or buggy, please let us know!

8

Ok thanks

Last question what is the NavEdges stuff and AvoidsNavEdges() for in the avoidance manager? I couldn’t find it used anywhere.

Could this be used to define “walls” along the edge of my road for vehicles?

Or should I be using RVO2 or the DetourCrowd stuff instead? ( I do not use the nav mesh for vehicles on roads, they follow unreals SplineComponent/SplineSegments

9

Yes, this is a hookup for adding information about nearby walls to consider for avoidance.

UAvoidanceManager::SetNavEdgeProvider() registeres an object with INavEdgeProviderInterface. Once set, every agent will query for walls (usually: border edges of navmesh) using INavEdgeProviderInterface::GetEdges() function and include them in velocity calculations.

There’s no default implementation in Engine, won’t be added anytime soon, but is used internally by our projects and works.

You can’t DetourCrowd without a navmesh. DetourCrowd simulation depends on doing internal repaths (and is much slower than RVO).

1 Like
10

Great thank you, I just tried that and it does work ( mostly ) thanks!