Category Archives: Media

Goal-based AI in Red Faction: Guerrilla

I'll sometimes talk about the stretch of time between being in graduate school at Illinois and coming to Virginia. It was possibly the second most tumultuous segment of my life (after this past couple of years), when I dropped out of my PhD program, got married, and got a chance to work in electronic entertainment for the first (and probably the last) time.

I signed on with Volition, Inc. (now Deep Silver Volition) in fall of 2005, when the original Saints Row was deep into production and Red Faction: Guerrilla was struggling to make it out of its pre-production phase. I was one of two (and later, three) programmers assigned to create intelligent AI for the latter game - AI that would be able to function in an open-world, destructible environment! It wasn't an easy task!

The senior engineer on the team had already come to the conclusion that we should using goal-based, backward-chaining classical planning for AI, because FEAR had had so much success with it in the FPS genre already and we were doing a third-person shooter (albeit not on rails to the same degree as FEAR was). The precedent set by FEAR was simple: AIs had simple goals (find the player, kill the player) and sequences of actions that could achieve those goals (hide, step out of cover, snipe, ambush), each with its own animation or animation cycle. In the earlier parlance of game AI, each state became an action, and instead of having rules governing state transitions we had freeform action plans with the only requirement that they be the simplest way to achieve a goal.

But just having goals and actions available wasn't enough. We needed a more sophisticated system that modeled how people in a fight actually might behave.

The first piece: percepts

We realized early on that a lot of the goals a person might pursue in a combat situation are informational. What's going on? Is anyone over there? I hear gunfire, but where are my enemies? In order to choose whether to pursue an investigational goal or a combat goal, we needed AIs to have internal mental state about their beliefs. And the way AIs formed beliefs was through percepts.

Percepts were typically audio (hearing footsteps; hearing gunfire) or visual (seeing a civilian or enemy). Sounds were easy: we tagged every sound a PC or NPC could make with a radius; other NPCs would hear the sound if they were within that radius. Some sounds were obviously signs of combat (explosions, gunfire) while some weren't (footsteps). When an NPC heard a sound, it created one or more beliefs along the lines of "explosion over there!" "strange footsteps in my building" "somebody's hurt"- and these beliefs would decay over time.

Percepts - especially those linked to line-of-sight - could be very expensive to calculate, and so we put all requests to perform eye raycasts (how we had to determine line-of-sight, since our geometry was destructible and we couldn't have pre-baked LOS calculations) on a queue. The delay between any particular NPC requesting a raycast to the player (or anyone else) and actually getting it tended to only be a few frames, but along with the planning delay it tended to nicely simulate the time it would take a normal person to react to something new in their field of vision; AI did not have that weird property of reacting immediately to being able to see you.

The second piece: orders

For military units, orders were a second big part of the puzzle. Orders consisted of things like "guard this building", "guard that person", "patrol this route", "kill the enemy". These didn't normally affect which goals were available (though they could, for things like guarding and patrolling, which were also goals) but tended to limit what actions were available to NPCs.

For example, until a building was destroyed, NPCs assigned to guard it would almost never consider an action plan that required them to leave. This prevented the problem in older games of monsters hearing the player and then all streaming out the door so the player could pick them off one-by-one. Instead, guarding NPCs would pick actions like "go to sniper point" or "go to a window that provides cover" or "search the building".

The third piece: goals

Goals tended to be simple, and fell into a few categories. Examples were things like "guard this building", "patrol this route", "get to safety" (for civilians), "investigate a disturbance", "dodge enemy fire", "find the enemy", and "kill the enemy". AIs would attempt to form a plan to achieve their highest-ranked goal, then if that failed, they'd drop down to their next-highest priority.

Since only a limited number of planning passes were allowed each frame, sometimes AIs would spend a small amount of time idling before they could generate a new plan. To smooth this over, we baked in some reaction animations so that it looked like they were thinking/looking around before they started running off to the next objective.

The ability to fall back to a lower-priority goal also meant that if we were actively preventing AIs from achieving their goals, they still did something sensible. For example, we limited the number of enemy NPCs who could engage the player at once on all but the highest alert levels; more distant NPCs would fall back to goals of observing the enemy or guarding. Also, it was possible that it might not be possible to fulfill an investigation or attack goal without violating the NPC's orders, in which case being able to fall back to "guard" or "escort" was important.

The final (and most fun) piece: actions

Once a goal has been chosen, an AI will try to string together a sequence of actions that takes the NPC from their current condition to the goal state. For example: if an NPC wants to kill the player, an available action might be to shoot the player from a vehicle turret. If the NPC is not on a vehicle turret, however, the NPC must first man the turret. In order to man a vehicle turret, the NPC must be in the vehicle; if they are not, they must enter the vehicle. And they cannot enter the vehicle unless they are adjacent to a door, which might require going to the vehicle. (You'll also notice that each of these is only a single animation sequence or cycle; that was by design as it gave us both a good action granularity and obvious points to blend between animation states.)

Of course, a much simpler plan of action is just "shoot the player from where you're standing". Each action has a "cost" associated with it, which may be variable (traveling further costs more). The plan the NPC can find with the lowest cost is the one they try to perform. For example, an NPC standing out in the open may dive out of the way, do a dodge roll, or duck into cover in order to avoid incoming fire; ducking into cover is the least expensive so if the NPC is already in cover they will almost always do it - unless the incoming projectile is explosive and they'll be caught in the blast, in which case they'll pick one of the more expensive options (typically diving, since it gets them out of the way the best). Likewise, an NPC in the open can run to cover, but it's usually cheaper to just dodge.

Evaluating whether an action is possible may require some computation in itself; for example, in order to perform a melee action, the NPC must be able to pathfind to a location adjacent to their target, within 2-3 feet of the same height, and have a clear line-of-action to the target from that location. That's a pathfind and a short raycast, which is non-trivial in cost. For these actions, we may delay planning a frame if our AI budget has been used up, and if it turns out that the action is untenable, we may prevent evaluating it again for a period of time (usually at least several seconds). That way we don't waste compute cycles evaluating actions we know aren't going to apply to the current situation.

Multiple action plans = emergent behavior

That kind of heuristic logic actually led to one of my favorite bugs during development. There are wild people living out in the Martian desert in RF:G called "Marauders" - kinda like the sand people on Tatooine in Star Wars - who use a lot of melee weapons and have Mad Max-like vehicles. I had a test level set up with a crowd of Marauders, one of their vehicles, and a couple of structures including a ramp. I ran my PC over a ridge at the top of the ramp, expecting a mob of Marauders to swarm me with their melee weapons, but instead, a couple of guys jumped in the vehicle, drove up the ramp, and ran me down!

The reason was that there was a bug in the melee heuristic that was comparing the difference in height not at the endpoint of the move-to-melee action, but at the start, and since the Marauders were all at the bottom of the ramp, they immediately discounted melee as a possibility and fell back to the much more complex plan of "go to car, get in car, drive to  enemy, run over enemy" to satisfy their "kill the bad guy" goal. That's exactly the kind of emergent behavior we wanted from AI in the game, and despite the fact that it only showed up in that case due to a bug, it was still an amazing proof of concept.

Anyway, it's hard to explain how the thing worked in any more depth without actually experiencing the game, so why don't you go do that? I'm sure it's cheap on Steam...

Powerful prose passages

We're all familiar with the feeling we get when we're swept away by an incredible piece of music. Often it's a particular passage that hits us in just the right way; it's one of the few ways you can reliably make me emotional. Not surprisingly, that's also the reason I've done my music plugs bit - to share some of those experiences with you.

But it's not just music that can touch a person - every once and a while, I'll go back to one of my favorite books and read a passage that moves me, or just makes my spine tingle. Here's a short list (which should also be taken as recommendations):

Ian McDonald

If there's a better magical realist sci-fi author than Ian McDonald, I haven't found her. McDonald's prose style is unique, punchy, powerful. There's a passage in Desolation Road, the first of his two Mars novels (novels? is that even the right word?) where rain falls on the Viking probe for the first time. Note - and this can be said for nearly all of the passages listed here - that some of its impact comes from the lead-up throughout the book and it doesn't hit at full strength without that background, but it's still enough that Jo Walton over at used it as a reading at her wedding. That's enough of an endorsement for me.

Following up Desolation Road is Ares Express, the story of a young girl going on an adventure that crosses the face of Mars. The introduction to the book is also our introduction to her, and there's no better way to introduce both a character and a world than the first five pages of that book. Do yourself a favor - go to Barnes and Noble, find Ares Express, and read the prologue. If you are not immediately moved to buy the thing, I fear for your soul.

Terry Pratchett

Yeah, yeah, we know - Pratchett is almost cliche: prolific, goofy, a geek's geek's favorite writer. But when he's on, he's on. And seldom is he more on than in his characterization of his, well... characters, who are always simultaneously relatable and larger-than-life. Death's introduction to Mort in Mort is one of those beautiful little pieces of prose that sends tingles down your spine. And the parable of Granny Weatherwax and the farmer's wife in Carpe Jugulum... well, that's some pretty intense stuff there, too.

Guy Gavriel Kay

Certainly, there are some holy crap moments in Kay's largely low-fantasy, alternate-historical fiction, but there's a passage in Sailing to Sarantium that literally forced me to put down the book because I couldn't read through the tears that were streaming down my face. It's not a sad passage - I just found it that powerful, like when you hear the opening of the last movement of Beethoven's 5th Symphony for the first time. Kay's description of the small chapel in Sauradia - and Crispin's reaction to it, punctuated by Kasia's response - is so amazing that if it were any shorter I'd include an excerpt right here.

Anyway, those are my top picks - if you've got any of your own to suggest, please do!

Nerd Rage

There's been a lot of whining lately about whether or not Ben Affleck should play Batman, or what role Black Widow (or any female hero) should have in franchises like The Avengers or the upcoming DC Comics movies.  The loudest whining comes from the hardcore fanbase who have strong notions about how these franchises should work.  And it does seem like studios worry about these people when they make creative decisions - there has been talk about walking back "Batfleck".  Wonder Woman movies have been canceled because studios don't feel they can modernize the franchise without losing comic fans.

Mike Lawrence - Sadamantium
Mike Lawrence embodies nerd rage, but at least he's funny when he does it.

But I say, so what if the "hardcore fans" hate a creative decision?  Just ignore them!  Old-guard nerddom makes up a tiny fraction of the current geek and geek-friendly fanbase.  They're also a much narrower demographic, being mostly straight white men in their 30s, 40s, and 50s.  The actual audience for these movies - the ones whose butts are going to be in the seats - is much larger and far more diverse.

You have to weigh the effect of listening to the old guard against the benefit of moving in a new direction.  Listening might prevent some short-term blowback, but it also means perpetuating some of the worst parts of geek culture and geek media, including the marginalization and objectification of women, the tokenization and exclusion of minorities, etc.  When hardcore fans argue that any deviation from their established canon is bad, they're really arguing that narratives created in the 1950s and '60s - with all of the cultural baggage that implies - should be continued into the twenty-teens.

The current geek fanbase contains the trend-setters and taste-makers of the next generation.  We had a saying in college: "A tradition is anything that started before your freshman year."  If we take the time to change our stories to be more modern and inclusive now, those changes will be reflected in both the media and the perception of "canon" in five, ten, or twenty years.  We'll look back on the sexism of comics today the same way we look back on the camp of the Superman and Batman stories of the 1960s - as a curious, outdated artifact and nothing more.

So let us reject the calls for sameness, for established understanding of characters and their roles.  We can create new stories - not to cash in on a particular short-lived facet of the zeitgeist, but to be lasting additions that move our beloved franchises in completely new directions.  Let's remember that the best way to avoid negative press is to make a good movie.  And if a bunch of whiny, entitled man-children decide they're going to boycott then let them.  The old-guard nerds can't live without geek culture, but geek culture can certainly live without them.


I geek out about linguistics. I love when people remix language to do creative things. They get bonus points if use more than one language (two of my favorite Christmas carols are "In Dulci Jubilo" and "Nowell Sing We"). I saw another example today that really amused me.

Monet from One Piece, a woman with the wings and legs of a bird, wearing a green tank top that reads "happy".
Monet, who is several puns.

The writer of the Japanese comic/cartoon One Piece, Eiichiro Oda, loves to put random English words on his characters' clothing.  In the most recent storyline, there is a woman named Monet who has the wings and legs of a bird.  She also wears a tank top with the word "HAPPY" on it.

Oda is fond of wordplay and puns, and this is a great example.  The obvious joke is that HAPPY is only one stroke away from HARPY, the half-woman-half-bird creature from Greek myth. In Japanese, there's a second bit: the transliteration of English "happy" is ハッピ (literally "happi"), while "harpy" is rendered ハーピ (literally "haapi"). The pronunciations are nearly identical; the only distinction is whether the vowel or the subsequent consonant is long.

But here's the thing: the wordplay doesn't work at all for Oda's monolingual Japanese fans.  Harpies aren't native to Japanese folklore.  Japanese doesn't borrow its official word for the mythological creature from English either.  In Japanese, it's ハルピュイア ("harupyuia"), from the Ancient Greek ἅρπυια, so you have to be familiar with the English spelling and pronunciation to be in on the joke.

So I'm all about the idea of In a World...

...but the execution seems a just little bit flat.  Judging from the trailer, writer/director/lead actor Lake Bell does well, but it would have been nice if they'd cast someone with actual announcer credits (there are women who do that job, you know).  Likewise, Fred Melamed is no Don LaFontaine, and while I like Demetri Martin's comedy, his screen performance is just north of meh.

Even if it's just a solid B, though, this is a good thing.  More films by women means fewer films by the likes of Michael Bay and M. Night Shyamalan - a win for everyone.

(And lest you think I'm picking on In a World..., I'm actually going to see it, which is kind of a big deal as I've probably only seen two or three movies so far this year.)