Wednesday, October 28, 2009

Choosing the Right Velocity

I browsed through the RVO library code while checking the differences that HRVO added to it and I noticed that they smooth out the velocity quite a lot. I have to comb through the literature again to see if someone has mentioned anything about it. I remember seeing a mention in some paper that they assume that the velocities are valid at least a certain amount of time.

HRVO velocity selection is pretty nice and simple. Looks a lot like the ST (strategy) from Fiorinis paper. Basically it generates potential sample points at:
  1. all intersection points of the velocity obstacles
  2. all the intersection points of the velocity obstacle edges and the circle which has radius of max speed
  3. plus the desired velocity projected pass apex of a VO (if I understood that bit of the code correctly).
Next all the points are validated, so that they lie out side the multiple velocity obstacle. And the sample point that is closest to the preferred velocity is chosen.

The above image shows a scenario of sample points. The valid sample points are blue and invalid red-ish.

A critical point is what happens after that. Instead of applying the whole velocity to steer the agent, they clamp the delta from current velocity to the new velocity by max acceleration. Sounds like the likely thing to do, but I did not expect it to be such dominating factor of making velocity obstacles to work. Games often fiddle with the velocity directly. It could be that I was making false assumptions.

I have to give the RVO library another spin and see how much the smoothing actually affects the results.


  1. Looking at the example picture, it looks like there is no consideration to avoid an obstacle by steering to pass behind it while it moves forward, which is usually the easiest way to avoid bumping into someone in real life.
    But I suppose you're only talking about velocities now.

  2. That's a good question, and while writing this answer it clarified my understanding of VOs a bit too :)

    I should have put some labels into the pic to make it easier to explain :) Lets define that the larger agent at top is agent A and the other at right is agent B. The more vertical VO is for agent A (VOA) and the more horizontal is for agent B (VOB).

    Any velocity we choose that is on left side of VOA is going to steer to pass behind agent A and any velocity we choose at the bottom side of VOB is going to do the same for agent B.

    For example the point closest to the desired velocity (the arrow point from the point at lower left corner), is going to steer to pass behind both agents. (I hope I got that right, I'm still in desperate need for another cup of coffee this morning ;)

    I think the samples which are tangent to apex of the VOs (at the tip of the blue lines) should have similar property too (see figure 10 in below paper).

    For more details you could take a look at part "3.2 Structure of Avoidance Maneuvers" in Fiorini's paper:

    It is quite trivial to calculate such steering adjustment as you suggested for a single "enemy", but combining them is usually the hard part. I think this is the really interesting property of VOs. They allow you to geometrically figure out how to combine such constraints.