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...

We need women everywhere - even on Wall Street

A friend recently shared this rather unpleasant NYT article on social media, which sparked an interesting discussion about workplace sexism. One commenter said he couldn't feel bad for these women because - well, I'll let him use his own words:

The woman in the story leaves the bank after five years, ending what might have been a "brilliant career on Wall Street." What often constitutes a "brilliant" career on Wall Street seems to me to include the sorts of predatory, irresponsible, and morally bankrupt strategies that are often condemned by outside viewers. I don't mourn the fact that someone was prevented from participating in that business and culture.

It sounds like a valid viewpoint. Wall Street is bad; we should be focusing on dismantling it instead of trying to make the cadre of exploitative assholes who run our financial system more diverse. But I also strongly disagree for a couple of reasons.

BN-AA343_Deutsc_F_20131016143336
Wall street women; possibly also exploitative assholes? (source)

The mere presence of women changes business culture.

We know from empirical evidence that companies with women on their boards make more money. Women take fewer ill-advised risks than men and generally outperform men in investing, which you'd imagine wold be a useful thing on Wall Street!

Maybe the toxic, wasteful, and destructive culture on Wall Street is partly due to the fact that it's largely populated by entitled frat boys with nobody to tell them they're being assholes? I can't promise that more women (and PoC and other underrepresented folks) in high finance will fix all of the things that are wrong with it, but integrating the trading floor is a way easier way to start than burning the entire system down (however appealing that might be).

Having women at the levers of power matters.

This is the other big reason that integrating Wall Street is so  important. Wall Street holds a lot of the levers of power in the modern world. Women being largely excluded from Wall Street has a trickle-down effect in everything from who gets elected to national office to whose startup gets venture capital funding.

It's all well and good to say, "Screw Wall Street; women shouldn't even want to work there!" but the reality right now is that Wall Street being dominated by white men contributes to white men also dominating business, politics, the high-tech sector, and many other important and arguably more virtuous segments of our society.

The argument ultimately boils down to the tired old "boys will be boys".

We tend look at these kinds of stories, throw up our hands, and say, "Well, what did they expect?" It's the exact same dismissal we see when women complain about their treatment in everything from the military to competitive video gaming. And it's wrong.

esports-have-all-the-things-spor-640x360
eSports Guy prefers his gaming with a heaping side of testosterone

When we tell women not to bother working or playing in male-dominated arenas, not only are we complicit in limiting their career options but we also implicitly condone unacceptable behavior by men everywhere.  When Silicon Valley bigwigs hold important meetings at strip clubs; when women aren't invited on business trips because they'd "ruin the mood"; whenever a woman is subjected to behavior that's dismissed with "boys will be boys" or excluded because otherwise men would have to behave themselves like adults - these all damage our ability to succeed and advance in the workplace.

You can't just isolate the problem and hope it will go away. There is no place where sexism is acceptable, and we should not - cannot - allow men to carve out places where it is.

Even if that place is the hive of scum and villainy that is Wall Street.