Another interesting observation in Left 4 Dead. In this case, it is about the state machine that the companion AIs are using. First, the observations:

The first clip in the video below shows me getting ready to leave the safe house at the beginning of the level. My companions did their usual "grab some stuff" behaviors and then lapsed into "random wander" idle behaviors (I couldn't hit the screen shot key fast enough to show Louis standing with his nose in the corner like a punished boy.) When I went down the stairs to the door, I was mildly perturbed that they didn't follow.

I then opened the door and shot the zombie standing outside. They still had not moved to join me. A zombie rushed me, I leveled him, and my sidekicks were still admiring the walls upstairs. Only when I stepped across the threshold did they move to join me (with Francis doing a completely unnecessary walk on the railing... but that's a future post). Something not shown in the video is something I have experienced before. Usually, when I step across the threshold of the safe house, they are in quite a hurry to leave the room, even to the point of pushing through me to do so. It probably would have happened in this case if we had not been under attack at the time.

In the second clip, we were at one of the intermediate buildings on a map. We had run inside, closed the door, stocked up on ammo and health packs, healed ourselves and whatnot. I opened the door and left the building. The video picks up as I look back inside realizing that my pals didn't seem to want to leave. This was different than the first clip in that the trigger was not leaving the room.

There was a Boomer behind the building that I could hear. Even when the Boomer came around the corner and started waddling toward me, they didn't move. Only when I fired my weapon did they decide it was time to rush out.

Now, for the explanation. It seems that Valve is using an HFSM (Hierarchical Finite State Machine) or another such tiered approach (a behavior tree can cause this as well). There is likely a high-level state that we will call "In Safe House". When in this state, other lower-level states are things like "random wander," and "random comment." The only thing that seems to override it is if they see a zombie outside a door (many of the safe house doors have those barred windows). They will actually engage and kill zombies outside the safe house from inside the door. Therefore, there is an "engage/kill" state that is contained under "In Safe House".

On the other hand, another high-level state is "In the World". It is in this state that the AI spends most of its time. Apparently, "stick with the player" and "defend the player" are only included in this high-level state. That is why they would not follow me down the stairs while I was still in the safe house or defend me when I got attacked. However, once I crossed the threshold, a message was sent to them to change states to "In the World" at which point, they were free to analyze their usual parameters such as distance (move to the player) and threats (defend the player).

Note that this would not have been a big deal if I had simply stepped out the door. Alternately, in other safe house situations, the random wander location is in sight of the door. Therefore, when I got attacked, they would have likely seen the zombies and fought back. This particular arrangement did not allow for that.

Now, I don't know what happened with the building in the second half of the clip. Because that isn't an "beginning/end of level" safe house, I would suspect the above rules don't apply. Why did they not leave, then? I have seen other behaviors where they don't seem to follow me like I would expect, but I have usually found other explanations for that (another post on that later). In this case, it would have made sense for them to leave along with me just like they tend to stick close in other circumstances. That leads me to believe that there was an artificial state in play that led them to believe that they were supposed to be there (or rather had yet to convince them it was time to leave).

Regardless, in this case, the obvious trigger was me firing my weapon. This was not the case in the safe house example.

Neither of these issues is dreadfully wrong in a gameplay sense. They are only noticeable in certain circumstances. And certainly the companion AI in L4D is better than some we have seen. However, when issues like these happen, they do make us pause and ask "what are you guys thinking?" Therefore, while the logistics of the game may not be affected too much, the perception of the game is. It breaks that coveted suspension of disbelief by making us ask (in typical gamer parlance) "WTF?!?"

A simple solution would have been to pay more attention to what was under the HFSM state of "In Safe House". Alternately, have more than one trigger to transition from "In Safe House" to "In the World" would have been better. For example, opening the door is an obvious trigger that it is time to go. Getting attacked certainly is urgent enough to warrant attention as well.

Additionally, abandoning the rigidity of a HFSM could be the answer as well. Much of the problem would be solved by using a system of free-floating priorities such as what I describe in my book, "Behavioral Mathematics for Game AI". In that arrangement, you can generally dispense with the state/transition model in favor of one that always has all possible actions in play through a system of calculated utilities and priorities. Something similar to this is probably already in effect in L4D for things like target selection, action selection (fight, heal, reload, etc.) and other actions. Therefore, extending it to cover the situations covered above would not be terribly difficult, in my opinion.

Anyway, all in all the companion AI seems to be fairly decent. As we AI programmers know, companion AI is a beast simply because of how involved the companion is with the player. There's more scrutiny, more options of what to do, and far more potential for the "WTF?" moment and the ensuing frustration. I think that companion AI is the next frontier of game AI that we are already in the middle of. L4D is in the vanguard of this movement and doing an admirable job of it.

Remember to click the tags below for more Post-Play'em observations on Left 4 Dead and other related subjects!

Also, if you liked this article, please take a moment to submit this link to StumbleUpon, Digg, or Reddit. I would appreciate it, as would many other game AI enthusiasts!

Labels: Companion AI, FPS, FSM, HFSM, Left 4 Dead

I saw an interesting error of logic (which is different than an error of execution) in Left 4 Dead earlier today. As I was holed up in a safe house, about to head out on the next stage of the map, Zoey neglected to grab a health kit. She was slightly injured at the time. The rest of us had health kits already so it wasn't that she was saving it for us or a semaphore was set saying "leave it for the player". Also, because we were in the safe house, there were no distractions requiring her attention. She simply was oblivious to the fact that there was a health kit there.

I thought that this was very odd. It would seem that the one thing that the AI sidekicks should do is stock up on stuff whenever they can. This is very much like how they take a moment between battles to do things like reload, pop some aspirin, or heal up. Those are the times that you are supposed to do things. Additionally, during those lulls between the frenetic nightmares, you should also make sure you are stocked up on "stuff". You never know when you are going to need it. However, while everyone else seemed to do so, she did not.

Because she was almost healed, I have to wonder if there was a fuzzy threshold that was not quite crossed at the time. I had half a mind to shoot her and see if she would change her mind. If I see it happen again, I will do so. Still, it doesn't make sense to ignore the purpose of what is an obvious pit-stop in the game.

Labels: Left 4 Dead, logical error

Ok... half price weekend on Steam finally got me into Left 4 Dead. After watching all my TF2 buddies drifting away to this mysterious "other game", I needed to jump in and take a look. Also, since it will likely be the buzz of GDC next month, I figured I had better have an idea of what it looked and felt like.

I have to admit that it's a pretty groovy game. All the stuff we have heard so far is correct. The online, team play is cool. It's so much better than most team shooters in that it seriously punishes you for separating from your cohorts too much. Also, because there is such a significantly different array of tactics that are necessary for playing as the infected, the versus mode is almost like having a second game. But that's not what this column is about...

The big AI pull on Left 4 Dead is the "AI Director" that we have all heard so much about. In an interview with Edge Online, Valve's Gabe Newell talks about all the nifty stuff they tried to take into account. Wikipedia even touches on the AI Director. It's no secret that this tech was a big deal.

When I finally got to playing it, I was very impressed with it myself. Having played through some of the levels more than once (like No Mercy, for example), I am well aware that I don't know where anything is going to be next. Compare that to other games where the 2nd time through you already have an idea of what is coming next... by the 3rd or 4th time, you have it down. I don't like that amount of rigid predictability. With L4D, I have been on my toes at all times.

It does seem like it does a decent job of balancing the flow of the game. There are plenty of times when I'm "on the edge". Compare this to the rubber banding I suspected in Doom 3 where it just seemed that the lower I got on health, the less damage the enemy did. The result was an (almost) asymptotic approach to 0 health. Exciting? A little. Contrived? Definitely. With L4D, this feeling is much more natural in that it is adjust the pacing of the enemies themselves rather than adjusting the abilities they present. Rather than the confusion of "why is this horrible monster doing very little damage now that I'm almost dead?", I find myself saying "thank God they aren't coming after us just now... I need to heal up a little!" It's a subtle difference, but it is there.

That's not to say that the game is always winnable in true rubber band fashion. On my first day of play, three friends and I played that last rooftop level of "No Mercy" about 8 times and kept coming up just short. It was exciting each time. Finally, we beat it by only barely dragging our asses into the chopper. Quite the getaway! As we reflected on what had happened (the game was new for all of us), I noted that every single time was different. Different monster placement, different ammo placement, different items, different pacing. We couldn't do the same thing each time because the computer wasn't doing the same thing. One time we used gas cans to light fires. The next time, I went looking for the gas cans... only to find that they weren't there (they were across the level). The next time, there were no gas cans at all... just more propane tanks -- which meant a different strategy entirely.

What I have found interesting is, while playing the infected (which I am having trouble getting the hang of), I can watch the other zombies "pop in" as they spawn. It's kinda fun to see them do that. Oddly, I feel a strange kinship with them at that point. ("Yeah, right here buddy! We're gonna get 'em from this closet, right dude? Right? Hey... pay attention to me!")

The other thing I get to watch as the infected is how their "idle" behaviors work. There are quite a few of them and they blend well. Admittedly, by their nature, zombies don't have to be terribly engaging, but it is a nice touch to come around a corner or see a group far off actually doing stuff. Sometimes, I feel that the sensory distance is a little short, however. If a little beepy grenade gets every zombie in the same zip code to freak out, why doesn't my shotgun wake them all out of their staggering stupor as well? Again, people just don't model the sense of hearing well in games. *sigh*

The AI of your counterparts is pretty decent, for the most part. I've seen a couple of odd glitches, however. Therefore, I think I'm going to make that a separate post so I can possibly post some FRAPS-caps of them in action.

(As always, make sure you check the tags below to see what else I may have written about this game.)

Labels: Doom 3, FPS, Left 4 Dead

When I posted my first observation on Half Life 2, "Movement on Rails" the other day my colleague, William van der Sterren commented that one of the cool things that they did in HL2 was making the NPCs acknowledge the player's position during conversations. While I certainly agreed at the time, I thought this was limited to eye contact and head position. That was just the beginning. I had not experienced the full depth of what they had done in the game.

Last night as I was playing some more, I had some of the extended conversations at Black Mesa East. As Dr. Mossman was walking me through the lab, I was surprised to not only see her turning her head, but even walking backwards (convincingly well) at times so that she could continue to face me. I'm tempted to go through that section again just to mess with her. If I keep moving, does she keep changing?


Anyone who has coached kids playing baseball has probably taught the drill of how to watch the ball as you are running backwards. Part of that drill is to change sides without turning your head. That is, looking over your left shoulder, then turning your lower body to run with the other shoulder leading so that you are now looking over your right shoulder. I think it would be interesting to watch the NPCs in HL2 react to that sort of situation.

All in all, I agree with William that it was a new point of immersion for a game NPC. More specifically, it worked to not break the suspension of disbelief simply because it looked natural.

Monlogue Breaks

On the other hand, there were awkward pauses in the monologues of the various characters. Sometimes, I figured that they were waiting for me to cross an invisible trigger threshold. That is, as they entered a room, they waited for me to cross through the doorway that they were then going to close behind me. However, the next line of monologue was put into the same queue as the actions such as closing the door. Therefore, they could not proceed with their spiel until such time as I allowed them to close the door. If I had not moved, they would never have continued.

A solution for this would be to have a separate queue for the speaking and the actions. However, the speaking could be superseded by ad hoc lines such as, "Come on through the door so I can close it behind us." and then continuing on with the monologue. This shouldn't be too difficult to do with a priority-based system. The insertion of the vocal line "Come on through..." would be a higher priority than the other lines. As each normal line finishes, it triggers the insertion of the subsequent line into the queue with the appropriate priority. If there is nothing else more pressing, it would chain right on the end as per usual.

One of the effects you can pull off with this method is reaction-based stuff. For example, I was dying to fire my pistol into the ceiling during some of the speeches and conversations. Would they have reacted? I don't know about HL2, but in other games, probably not. However, a priority-based system would override whatever sequence is being dictated with "What the hell are you doing?", a few follow-ups about shooting weapons in the house ("You'll put your eye out, kid!"), and the revert back to the regularly scheduled monologue.

Another effect would be acknowledging random people walking by. For example, during the hallway monologue, Dr. Judy could have received an event that a colleague was approaching coming the opposite direction. She could have inserted a slightly higher priority event to say "Hi" to the person in between lines of her monologue. She would say "Hi" at a break between lines and then go back to what she was talking about. Sure, there are caveats that you have to look for, but the inclusion of simple mechanisms like this work in a similar fashion to the head-turning one. They look natural and therefore feel natural to us.

(Remember to check the other Post-Play'em observations on Half Life 2.)

Labels: dialogue, Half Life 2

One thing was kind of startling to me just now (I actually quit playing so I could write this). When I got killed, there were 2 bad guys right in front of me. I had only just hit the floor when they both immediately turned and began their "random patrol" state. I laid there and watched through my red-tinted death goggles as they paced back and forth in front of me. Despite being bombarded with radio traffic about my existence, and just enduring a firefight with me, neither of them was at all affected by my demise. Even a non-AI-savvy person would be jolted by this obvious lack of attention to my body. It just screams "state change". Kind of a reverse aggro, I suppose.

In Halo 3, on the other hand, it was a very effective touch that, when I died, I could hear the Brutes and Grunts celebrating and taunting me. It was a reminder to me that I had let down my people. Also, it was a touch of "humanity" (loosely used) for the enemy AI. The one simple inclusion of an "enemy down" state would made a lot of difference.

Think about all the ends of firefights you see in the movies. There's the "is he dead?" phase, there's caution, relief, reporting in, etc. When I died in Half Life 2, I was wanting them to come over and prod my body or something. Really an extra couple of voice lines and a couple extra states to transition into and the extra immersion would have been very welcome. After all, dying (in a game) is an emotional moment for the player. Make him remember it.

(Remember to click on the tags below to see more about my observations of Half Life 2.)

Labels: FSM, Half Life 2, Halo 3

OK, I admit that I had not gotten around to playing Half Life 2 until now. (It's part of my post-book writing, pre-GDC ramp up.) I am not terribly far into it. I am alternating between riding my airboat (kinda fun!) and having to stop and do the various side-tasks.

So far the enemy AI is decent, although bland. (I'm playing on Normal, if that matters.) I've noticed a little ADD in the soldiers, however. They can sometimes forget where I am (or just was). If they are supposed to be looking for me, it isn't working.

Another annoyance was the rails that the background people are walking on. During some of the opening scenes, when I was in the middle of a large room, people would walk straight through me. At one point, I didn't notice what had happened right away other than that I was jostled out of the way. However, only about 15 seconds later, while I was standing in the same spot in the middle of the room, another person walked down that exact same line. I looked around a little to see if there was an obvious path that I was on but I didn't see one. It looked like they were simply going from one point of interest to another and didn't care that I was in the way.

Possible solutions involve the addition of a steering behavior on top of the standard pathfind. Even just the addition of a vocal cue of "excuse me" or "look out" would have softened the blow somewhat. Instead, the citizens came off as completely mindless.

On a positive note. The manhacks are convincing in their movements, though. They remind me of how difficult it is to control those little remote-control helicopters... which I suspect is the effect they were after.

(Remember to click on the tags below to see more about my observations of Half Life 2.)

Labels: Half Life 2, pathfinding, steering

I just made another interesting observation on Company of Heroes. In the campaign scenario that comes with free download (the town of Carentan), two enemy tanks came barrelling over the bridges, busted through my defenses, and took up positions on the intersections just SE and SW (screen-relative) of my Town Hall. They then turned toward the building and started whacking on me. I dispatched those tanks right where they had turned. So far so good--great tactic.

However, a minute or so later, another tank came down the left side through about the same path as the first. He stopped exactly on the place where I had destroyed the first tank (never mind parking directly ON the smoking hulk of steel) and turned in the same manner to face the Town Hall. Wow. Serious Deja Vu, folks. It immediately jumped out at me that this tactic was exactly scripted--right down to the exact location to stop and turn.

An easy solution to this would have been to randomize the point somewhat. Use the original point as an anchor, but throw in a random displacement within a radius. Check to see if it is valid to not only sit, but to have the desired sightline, and then move to it. Rather than a single, repeated waypoint, you now have something that resembles "over there someplace."

The unfortunately side-effect of this is that I now know that I can defend specifically against that particular point (mines? an AT weapon?) and be in business. Moreover, I know that I may have to defend against it more than once. That's not what I play RTS games for. I want to react dynamically to the AI and have it react dynamically to me. Now this may simply be a part of the campaign mentality (which I have not always been fond of in RTS games). Just like how the Town Hall gets leveled every time at about the same time forcing me to fall back to the church. OK fine, I get it... I get it. Still, it was alarming to see them use the exact same point twice in succession.

Otherwise, it's still a good game so far (I may have to ditch the free demo and pick this one up for real!)

Labels: Company of Heroes, RTS, scripting

Well, now that I'm finished writing my book, I am grabbing a few demos of games that I really need to take a look at. I pulled down the free demo of Company of Heroes off of Steam the other day and have had a chance to putz with it a bit.

One of the reasons that I wanted to see CoH was the articles by Chris Jurney in AI Game Programming Wisdom 4. He wrote up a pair of articles on the pathfinding algorithms that they used--one for constructing realistic turns for vehicles and one for the 'leapfrogging' of squads. Both are good reading.

Anyway, I haven't touched an RTS since Empire Earth (which chewed up way too much of my time in its day). It took me a bit to get back in the RTS groove. I was immediately impressed by the way the squads moved, but perhaps that is because I was looking for it. Also, they seem to react well to the unexpected. One concern that I had was how they didn't seem to always go for cover when I would have expected them to. Despite having plenty available, sometimes they would hang out in the open. This is more alarming when 4 of the 6 squad members are in cover nearby but the other 2 don't go. It makes me briefly wonder if the value being tracked is the amount of cover per squad rather than per soldier. I will have to investigate further on that (or just ask Chris when I see him next month).

The vehicles, as well, move admirably. Calculating vehicle movement on the fly (in a destructible environment!) is, indeed, a pain. Again, I will observe more, but they seem to do fairly well. The tanks have the advantage of being able to turn in place. However, the jeeps and trucks do not have this luxury and need to plan ahead lest they find themselves unable to make a turn.

On the 2nd campaign map (with the 3 bridges), I noticed some serious influence map work going on. As I got my bridge defenses shelled (and failed to rebuild quickly), the offensive seemed to shift to that bridge. As I reinforced it at the expense of another bridge, they seemed to shift to the one I had borrowed from. Now, with the fog of war in place, I don't know for certain that is what happened. They may have been hanging out over there and just were able to push forward when I moved away. I will have to see if there is a replay mode that shows the enemy.

Sometimes I wish that the squads were a little more autonomous. There are times when I wish that they would take some more initiative with their orders. When I give them orders, everything is cool. I can tell a squad to attack/move all the way across the map and they will engage and move repeatedly until they get there. However, if I only give a unit partial orders, they will wait patiently until I get back to them... even if that means standing in the middle of the street.

One example of this is when I had an anti-tank artillery unit pointing one direction with no target and a tank started firing at them from behind, they didn't turn around. While sticking to my orders is cool and all, some intelligent reactive behavior would have been warranted there. I'm not sure if this aspect is more of a design decision than a failing of the AI, however.

Again, I need to play with the game a bit more to get a feel for it. Right now I am spending more time noticing what I am doing rather than what the AI is doing.

(If you jumped into this article, you may want to click the "Company of Heroes" tag below to see if there are more observations on it.)

Labels: Chris Jurney, Company of Heroes, pathfinding, RTS, squad, vehicle