Obstacle Avoidance Experiments

I had a little time today to do some more experiments with obstacle avoidance. It is starting to shape up nicely, I hope that in next update I can share some interactive examples too.

Today's experiment was to solve of unfortunate side effect of the sampling method I chose--namely initial collision. If two agents are overlapping, the sampling will always return blocked and the two agent will get stuck. I previously side stepped this problem by just ignoring the initial collision.

The collision happens most likely because of floating point inaccuracy or that the agent movement code did a bit different thing than what the local navigation told it to do. Some situations on games can make it that happen, so it is good to be able to handle that.

First I tried to adjust the time-of-impact values based on the initial collision, but that did not work out as well as I hoped. Eventually my solution was to calculate both the time-of-impact as well as time-of-exit values per sampling direction. The same code actually is able to return both the values easily (TOI is calculated using ray-circle intersection, TOI is the first hit and TOE is the second).

My final solution was to add yet another component to the sample scoring calculation (remember, the sample direction with smallest score is selected). Previously the score or penalty was calculated as follows:

score = Wa*da + Wt*1/toi

Where da is the angle difference between the desired direction and sample direction and toi is time of impact in that direction. Wa and Wt are weights, I have used values 2 and 1 for the weights respectively in my test.

If there is a collision, I'd like the agent to move to to the direction which resolves the collision as quickly as possible. The best direction is where the time-to-exit is the smallest. TOE is zero, if there is no initial collision. For each sample, the largest TOE among the all hits is selected. The modified score calculation looks as follows. I used We=100 in my tests.

score = Wa*da + Wt*1/toi + We*toe^2

The result is that the agent prefers to move away from the collision, but does not select overly stupid direction because of that unfortunate state.

Another thing is test was how the min and max time horizons affect the behavior of the agents. You may remember from the earlier blog posts that max time horizon specifies how early the agent starts to change the movement direction, and min time means how early the agent starts to change the movement speed.

Setting min time horizon close to max time horizon results much more varying and smoother movement, which smaller time horizon results faster and more aggressive movement. It is pretty much as simple as that. I just had not played around with it earlier.

As expected, more aggressive settings make the crowd to spread out much more in more congested situations, while less aggressive setting makes the crowd to make more swirl like solution.

I'm quite happy how few parameters there are to tune with this local navigation solution. I also like how readable their change is too. The overall behavior is mostly controlled how min and max time horizon is set. The weights allow further tuning how much the agent is supposed to favor moving towards the goal (Wa higher) versus moving fast (Wt higher).