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