I have tested several different methods for local obstacle avoidance over the past months. A little less recently, as I have been finishing a game, though. There is something that I really like about the Uncharted way of mixing and matching navmeshes for global search, and dynamic grid for more local path queries.
There is one potentially nasty thing about that combination and that is what to do when the local grid says that the path is blocked, but the global navmesh disagrees. I'm going to sidestep that question by making an assumption that all the stuff that is not in the global navmesh can be traversed some way. Let it be moving around, kicking or putting it on fire.
Even if the method has some problems, I thought it was worth the try. I limited my implementation to a small grid which follows the agent. The idea behind this is that the grid only tries to solve the pathfinding problem between two global navigation nodes. In case of navmeshes this area would be the area of current navigation polygon, if you use waypoints, it could be the area between the waypoints.
Simplifying the Grid
Grids are really simple on what it comes to creating obstacles. The horrible side effect of grids is that they create huge graphs and that shows in performance. Since we are using small grid, something between 20x20 to 64x64 probably suffices, this is not a huge problem, but 64x64 is still 4096 nodes to be searched with A*.
There is one simple trick we can do to reduce the node count drastically. After the grid has been build, we simplify our search representation by storing the grid as RLE spans (oh yeah, I'm big fan of RLE!). In practice this reduces the node count from N^2 to 2N. In our node grid range (N=20..64), that means at about an order of magnitude less nodes!
(I do remember reading some GDC slides which described the same trick used by some RTS, but I could not find the reference.)
The side effect is that the cost calculations become nasty and messy. But let's not care about that yet. Instead, let's dumb our search down even further by making more assumptions.
Simplifying the Search
If we were not using the local grid, the path through that area would be a straight line. Instead of building a full fledged A* pathfinder for the local grid we can use this information to create something that will do a good job if the straight line exists, and in any other case it will just get us out of the way of the obstacles and local minima.
I chose to use breath first search for this. Because of the search space representation, it is quite efficient. The open list never gets really big, in practice open list size is usually around 4, and hardly ever peeks past 8 items.
In order to get favor that straight path, the neighbour nodes which are about to be added to the open list are sorted so that the node that is closest to the straight line from start to end point is added first. This bias makes sure that the nodes close to the center line are visited first. The open list is never sorted, just the new nodes that are added to it. It's not pretty, but it works really well in practice.
Finding the Final Path
During the search an index to the parent node is stored and pathfind basically consists of finding the node where the end location lies and tracing back the nodes until we reach the start location. When finding the end node, I choose the closest one that was visited during the breath first search. This makes sure that I get path to follow towards the target, even if the way is temporarily blocked.
Finally, the Funnel Algorithm is used to find straight path through the regions. Funnel Algorithm just needs a series of segments which define left and right edge of constraints to move along the funnel. In our case the portals are the shared edge between two regions.
In my prototype the slowest part was updating the grid, which was stored 1 bit per cell. Updating the grid takes in average 0.026 ms, this includes about 6 segments and 6 agents. I'm sure you can squeeze that number down by vectorizing the rasterization phase. Path query, including string pulling, takes about 0.012 ms in average. All results on 2.8GHz Core Duo. One path query uses around than 1.5kB of memory to store the required search space representation and the final path.
[EDIT] Updated time measurements above, the originals were measured in debug build.
It was interesting to try to the local grid method. I think it has great potential, but the potential problems of syncing the failures from local grid to the global structure are a nasty side effect. I think it might be possible to create an "interface of assumptions", for example the one I explained on the opening sentence, to improve it.