How to teach an AI parkour

When all you expected to be able to do in a third person action game was press a button to jump over a gap, 'traversal' in level design wasn't that hard. Adding the odd bit of scenery you can vault over isn't much harder: level designers place markers that tell your character they can vault, and what animation to play to make it look right.

But full free-running over complex terrain has become an expected feature, and the job of manually marking which bits of a level you can climb, vault or scramble over has become dauntingly huge. At GDC in San Francisco last week, Ben Sunshine-Hill of Havok explained a solution they're offering to developers as middleware: AI.

Havok's AI middleware is essentially doing the painstaking job of a level designer intuitively deciding how characters should vault or jump over each bit of terrain, but automatically, and for every possible spot in the level.

Those calculations are difficult: checking every pixel of the space between you and your destination would take an impractically long time. So Ben's invention is a set of clever maths tricks to that make these calculations much quicker.

How? Well, this bit gets tricky, and I'm not as smart as Ben, so I'll butcher his deeply technical talk in layman's terms as best I can.

Each one of these checks comes down to: “How do I get from here to there, if there's an obstacle in the way?” That involves checking for collisions along an arc that represents the trajectory of a jumping animation - imagine firing a jet of water to land where you want to go, and seeing if the jet hits anything. If it does, that doesn't mean you definitely can't vault the obstacle - other animations might be able to clear it, so you need to fire different jets to check those too.

Ben's system tests a whole row of starting positions at a time, and checks the possible trajectory arcs from them all in the same direction. Picture a lawn sprinkler firing all its jets at once in parallel arcs. The system makes a note of where each jet first hits something, and stores all that information in a graph.

The benefit of this is that most of the really tricky calculations about which animations will fit can then be applied to this simple, 2D graph. It's a little cheat sheet of all the possible things you might hit and where they are. It's much easier to look at that graph and see, 'this whole set of positions on the left are all totally clear, so our vaulting animation will work fine in all those positions.'

It's called segment casting, and it's the magic bullet that makes Havok's system efficient enough to be feasible. With it, something that used to take human intelligence - and a huge amount of time — can be automated.

The same system can be used to handle even trickier stuff, like irregularly shaped low walls. Yes, it's low enough to vault over, but where should your character put their hand? If it's a craggy, irregular ridge, you need to find a spot that's close to where you are, but isn't too low, and isn't too sloped that your hand would slip off. So again Havok's system fires its sprinkler array of arcs downwards, maps out where each part of it hit something, and manipulates that much simpler data to find the natural place to put your hand.

What's the benefit of this to the gamer? Changing this from a huge, time-consuming human task to something you can solve automatically with middleware makes it much more viable for developers to let you clamber on stuff. In short, it means more free-running in games, which feels nice and is cool.

It may also lead to better free-running: humans aren't perfect, and if you've ever played a free-running game and found yourself stopped by a piece of the level you 'should' be able to vault over, you know things get missed. If and when it's perfected, this technology could solve that reliably.

But for me, the most interesting thing about this system is that it's needed at all. Listening to the technical challenges involved in creating it is a startling glimpse into the insane amount of complexity and work that goes into free-and-easy movement in a game. Ease is hard.