How do you handle obstacle avoidance locally for single characters, as well as local multi-agent coordination? Find out what works and what doesn’t…
Mikko Mononen, Kenio (Designer/Programmer specialising in AI, previously Lead AI on CRYSIS at Crytek)
AiGameDev.com summary, also the code – ie; the notes! Runs on Mac OSX AFAIK, I need to try it myself at some point 🙂
My Thoughts
Interesting talk about a nice-looking pathfinding method, although if it can’t be applied to vehicles or other interestingly sized objects it might need additional work to be more general.
Talk Content
Covering:
- Path following madness (following the path at any cost).
- Scope from A* to velocity – technical measures
- Navigation Loop – done to move the character through the world
Went back and researched all the mistakes done in pathfinding and finding the root of the problem. Was probably a big help in finding the problem – the whole scope of the problem, as in “Can’t see the forest for the trees”.
The Navigation Loop
Starting with graphs (from work at Crytek), firstly do A* to get the graph sections to walk through. Cut out this corridor, and find the corners.
To go around corners well use something like splines with a tangent not aimed at the corner itself but is in the right direction. When set going the steering do the movement and collision detection – in the demo it was sliding the character around the navigation mesh.
While the character moves you can contract the corridor (when moving off parts) but also add things from the original mesh if the movement (tangental lines) go outside it.
This allows extra styles of movement – such as direct linear or drunk movement if you alter the way the paths are calculated across the mesh.
Sources: David Miles, GCD06, “Crowds in A Polygon Soup Next-Gen Path Planning”, Thomas Young, GPG3, “Choosing a Relationship Between Path-Finding and Collision”.
Multi-Agent Navigation
How to move many agents in the same space. Need to take time into account; it’s an untraceable problem – throwing memory and processing time at it and it still might not be solved.
There are some global solutions – almost like moving pawns on a chess board, waiting while things pass, and reactive solutions – changing as the loop goes on.
Comparisons with Robotic navigation (with set input visuals and output movement – lots of reasoning about the world, then applying navigation at the end), Crowd Sim (good but doesn’t have exact answers for 25 characters in a room) and Medical science (which somewhat works on it).
Reactive Obstacle Avoidance
Need to do some kind of angle to get around – there is an area around a blocking character/item where you can’t enter. More interesting is moving objects to avoid – need to check the velocity of the moving object, and offset the cone of avoidance.
Why use Velocity Obstacle implementation? Sumo vs. ninja – bouncing off the world versus avoiding it in the first place. Easy to implement too (although not as easy as the first steering behaviours). Hard but possible to tune too – a steering behaviour is impossible to tune though so it is better then that!
Avoidance Velocity Selection has to be done before A gets too close to (moving object) B. A circle around A is formed of a grid of local space. These are scored to where it is desirable to move to – if B is moving close, areas in that bit are scored low for instance, while the direction of travel says where it is desirable to move to in the first place (these then overlap for the final score).
To make it faster for real time, do adaptive sampling so if one major area is “avoid” make it a huge area, but cut it up if you need more detail to check for where we want to move.
See references in photo.
Examples
In example 1; symmetrical case means you have to set in advance which of left or right is a preference since at one point both are valid. Examples 2 and 3 involve more complicated groups moving across each other or to the same point.
Example 4; One guy going into a flow of people is, because of no future planning, not as great but it still solves the problem even if it doesn’t look brilliant.
Conclusion
Using the navigation loop needs all the little pieces, and helps if you stat thinking about navigation in an entirely different way. Doing the smoothing on the way frame by frame saves so much work.
digestingduck.blockspot.com
memon@inside.org
google: mikka recast
Questions
Q. What about geometric methods?
Prefer sampling since when geometric sampling goes wrong, it goes badly wrong, but it is something to try and test in the future.
Q. What about caching?
Have not tired it. It changes a lot between different frames so don’t think caching will help.
Q. What about using other methods like Neural Networks?
You have to pick your fights really really carefully. It always appears to learn the wrong thing. Also hard to learn the network and redo it a lot. No encouraging examples either.
Q. If you cannot provide your agent with a simple state, can you still use this?
Short answer is: Yes. Longer answer is: It is quite complicated to do that. Instead of sampling in velocity space, it’d need to check different shapes of the agents too.
Q. What about silent communication about where the agents are going?
Medical science shows some of the social rules; helps define the behaviour. Gets very complicated as well.