Monday, December 7, 2009
Improving Local Avoidance
Chris Paulson asked in the comments of another post how to improve steering based local avoidance. The reply grew quite large, so I thought I'd put it here as another post instead.
All kinds of local steering behaviors have the problem of getting stuck at local minima. That is what Chris is experiencing too, and that is what my recent research is trying to solve.
When splitting the system in reactive (local) and planning (path finding on static graph) navigation, the level of detail where the split happens is important. If the high level plan is too coarse, the local planning is not able to resolve. I think that is what Chris is experiencing.
I have noticed that agents usually do not resolve from local minimas, which are twice as large as their radius. For example two barrels next to each other are still ok to avoid locally, but if they are spaced more widely, so that the agent still cannot move through them, then they may be too big an obstacle. Add another barrel or wall to make it a a but more U-shaped and you get a case which is not easily solvable using reactive local navigation.
Local and Global Navigation
My reasoning has always been that as long as the results would be unpredictable anyways, use local navigation. Moving obstacles are always avoided locally, since at least in game environment we can assume that their movement is unpredictable.
Once they come to rest and touch other objects, they should be included in the planning level navigation graph. The Recast/Detour way is to update a tile once something has changed in it. As an example see Yakov's work.
The reasoning is to try to make it as simple as possible. Modifying the navigation mesh allows the rest of the system to always use the same format of navigation data. Obstacles that change the planning graph does not need to be special cased in the code.
Alternative to rebuilding a whole tile is the just cut holes into it. Cutting holes to polygons is not exactly very easy to get right. That cookie cutter method is limited to only obstruct movement, not allow it. For those reasons (and because Recast is pretty fast ;)), my preferred solution is to build small piece of the navigation mesh every time it is necessary. In contrast to Yakov's work, I probably would not update the mesh as often as he is doing.
If dynamic mesh updates shy you away, or you simply cannot do that. Local navigation can be enhanced to help out to avoid getting stuck at local minima. One way is to add additional representation for it, for example see . Another, maybe simpler idea would be to find islands touching obstacles, calculate their boundary, and steer towards the next "shadow boundary" of the obstacle island.
This proposed method has certain similarities with , which Google surfaced for me when I was searching about points of visibility graphs (there were a recent discussion about then at AIGameDev.com).
As an example take a look at the picture at the top of this post. There the orange agent is trying to avoid set of barrels. Most reactive local navigation methods would probably steer the character left into the local minima between the left most barrel and the wall.
To aid this situation, it is possible to calculate a graph of all the obstacles which are touching (check using obstacle radius plus agent radius). Then sort all the links per each obstacle based on their angle.
Using this data it is possible to locate the navigating agent by finding its' spot between two links at the nearest obstacle in the graph. Then you can follow the contour of the obstacle island by always choosing the next adjacent link left or right (that is, in the sorted per obstacle list if links) depending on which direction we want to traverse the object. This traversal will lead us to follow the contour of the obstacle because the links were sorted.
During the traversal, we can find the max steering angle left and right. Steering towards this angle will lead us out of any local minima. It is also possible to calculate the winding of the traversal and check if the agent is inside or outside a set of obstacles. If the traversal code hits a wall should make the steering and in that direction invalid. If both sides are blocked, we know that the link from current navigation node/polygon to the next one is blocked.
One way to resolve from this is to then temporarily disable the link and replan. The temporary disable could last a until certain time has passed, or until any of the objects move in the island have moved. It is really important to get this feedback part right. If you get stuck in local navigation, you should never replan unless you can fix that issue in global graph!
My favorite still is to adjust the navmesh even if it is a bit more complicated to implement.
 Automated static and dynamic obstacle avoidance in arbitrary 3D polygonal worlds
 Oriented Visibility Graphs: Low-Complexity Planning in Real-Time Environments