IA Logo

IA Information

Dave Mark's books

Post-Play'em - Observations on Game AI

Posts Tagged ‘FSM’

Assassin’s Creed: First Look

Sunday, April 26th, 2009

In my latest episode of “finally got around to playing”, I have had a chance to mess with Assassin’s Creed (on X360). As with most people, I was immediately impressed by how visually attractive the game is. However, that has usually been a warning bell in the past. A lot of time “pretty game” has tended to also portend “stupid AI”. This doesn’t seem to be the case with AC.

While this isn’t normally my strong suit, I have to say that the animation model in the game is very well done. Even without the climbing and hoping and dodging, there is a lot of detail that made for convincing depth in the characters. Even just running forward and then rapidly changing to run the other direction prompts a foot plant and skid animation that is really kind of cool. I also like the fact that the transitions between animations are very smooth. Even just something as simple as changing from a walk to run and back to a walk (even on horseback) exposes a gradient of speed that does not have the hard-edged state change feel.

Look at me when I’m talkin’ to ya!

I also like how you can move around during the (long) dialog scenes. You don’t have to, but you can. In fact, I found myself wanting to pace during these conversations because it made it more realistic. Additionally, when your character says something while he is facing away from the listener, he will turn slightly towards him… not to directly face him, but to talk in his general direction. Think about it… don’t we all do this? How often do we actually look directly at the person we are talking to? It’s a nice touch with the animation that makes those plentiful dialog exchanges more livable.

Running, Jumping, and Climbing on Things

It goes without saying that the advanced animations are very well done. The climbing and running and jumping business is ridiculously well done. There are the occasional quirks but those are more of a problem with the control scheme (on the 360) than anything else. I especially like when I get too close to an edge and my dude has to fight to keep his balance.

Excuse me. Pardon me. Move, damnit!

There are ways that they incorporated this into the game design other than all of the building stuff, however. It was a very nice touch to have the character stagger or even fall when he runs into people. That makes the chase scenes through cities very realistic in that you do have to pay a little attention to where everyone is.

Of course, in order to utilize that mechanic, you have to pack the streets full of people going about their business. This was done very well. There are places where it is next to impossible to run through simply because of the press of people. Even walking through them can get annoying. I haven’t bothered to simply watch people to see where they are going, but you don’t get that initial impression of “random walk” that you get from a lot of other games. (One recent transgressor in this effort was when I was playing Oblivion where every person in the city just broadcasted “I am so lost!” I will write up my observations on Oblivion later.)

An even better touch is how the people react to your passing… not just physically, but verbally. If you bump into one of those jar-toting ladies and get them to drop their burden, they will give you a little lip. The same can be said for running into a dude when you are on a horse. I found myself being more careful moving through people just to avoid what should be relatively innocuous confrontations.

The agents in the game, be they friend or foe, do have a pretty obvious state-based behavior pattern. It works for this game, however. I also haven’t seen any situations where the FSM is stuck on stupid. The game mechanic has enough depth that the predictability of the guards is acceptable.

Now serving #43

I guess the only thing I can fault (although it still works well) is the “ninja fight” rules where the enemies tend to come at you one at a time. They do take turns, however, rather than waiting for the one fighting you to die before the next steps in. Again, this was matched well with the game mechanic of being able to grab people and throw them away. When you toss one dude away, his buddy will step right in. It does make the fight more manageable, however. On the other hand, there have been times when I have had more than one guy beating on me at the same time. I haven’t figured out what the difference is in those scenarios, however.

All in all, the game looks pretty good from an AI standpoint. I say that based on the fact that I haven’t noticed anything horrible about it. That’s usually a sign that things are working well. Figure that AI should be like umpires or referees in a sports game. They are necessary for the game to work smoothly, but you shouldn’t really notice that they are there.

I’m returning AC to GameFly tomorrow (although I will probably buy it because my kids are addicted to it) so it will be a bit before I follow up on this post. You can check to see if I have written anything else by clicking the Assassin’s Creed tag below.

Make sure you subscribe to the Post-Play’em feed to see more reviews and analysis.

Left 4 Dead: Companion State Changes

Wednesday, February 25th, 2009

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!

Half Life 2: Oblivious to Death

Tuesday, February 10th, 2009

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

Mario Kart: Double Dash

Friday, November 9th, 2007

Over the past 4 years, my family has spent way too much time playing Mario Kart: Double Dash. Given that my kids are teenagers, we billed it as “driving lessons.” Only one of them has taken the wheel rather than the controller pad since that point and we have yet to see any ramifications (if you will pardon an obvious homonymic pun). However, there were times when my wife and I would feel an overwhelming need to swerve to avoid a non-existent red shell or banana peel. At that point, you begin to realize that you have played a game too much. Which had about the same effect as me realizing that I need to lose 20 pounds – it’s nice to acknowledge it, but changing the behavior is something else entirely. Which is why we continue to have family fests and beat the snot out of each other to the ultimate climatic moment of Rainbow Road.

Anyway, many years of playing the game have taken another toll on me – I have not been able to stop myself from making mental notes about the AI and the game design decisions that went into making it tantalizingly addictive. I even mentioned as much to Steve Rabin, Senior Software Engineer at Nintendo of America, while we were having a beer at one of the ubiquitous evening fests during GDC in 2003. If you have ever met Steve, you know that he would make for a fantastic poker player in his ability to not show a reaction. Therefore, I have little idea if the observations and conjecture I made about the DD AI at the time were even remotely close. I would like to think, however, that there was a twinkle and a smirk. Of course, I have no reason to believe that Steve was even involved in the development – perhaps he was just amused at my enthusiasm.

Anyway, here are some of the observations that I made over the past few years. (Has it been that long?) Forgive me if I get either too simplistic or too esoteric…

The State of Racing…

One of the obvious characteristics of the AI is its use of FSMs. This is something that is in use in most games today on some level or another. However, there were some distinct points where it was very noticeable that the AI was switching. For example, once you crossed the finish line, your team either went into “celebrate” mode or “whiny pout” mode. These were simply repeating animations that continued throughout the duration of the post-race promenade (for example, while you are waiting for your wife to finish because you left an ocean of banana peels for her to wade through causing her to look strikingly like Kristi Yamaguchi doing non-stop toe loops down the final stretch). However, if you are to get whacked in the behind by an errant shell, you will immediately transition into the crash state, then the “stunned recovery” state for a few cycles of the animation (about 2 seconds). Then, magically, you will begin to celebrate once again. It makes it very easy to see that there are very defined edges to the states (and likewise the animations).

The major states, then, seem to be as follows:

  • Pre-race
  • Driving (with occasional sub-animations)
  • Toting and throwing items
  • Crashing (various types)
  • Recovering (such as dragging along behind the car)
  • Post-race victory or bitching

There are some sub-states mixed in there for the more subtle animations, but they are usually very short-lived. The driving mode, especially, has extra states for turning, sliding, punching, taunting or even just looking around because there’s nothing going on.

One side effect of this is that the animation will get slightly muddled, for example, when you have multiple collisions in a row (especially in a tunnel). The way they get out of this is to give up trying to transition properly and simply reset the car on its wheels. It makes for an awkward flip

To Drive… the Invisible Path…

The AI racers don’t necessarily navigate freely along the track. They follow the technique of using invisible paths laid over (under?) the course. There are multiple lines on any given track and the AI will choose which one to follow at any one time.

The reason that this became apparent to me was the first time that I saw two opponents in front of me fighting for the exact same stretch of road. There was more than enough room for them to maneuver, but they insisted on being in the same spot for some reason. What’s more, that “spot” was meandering back and forth along the course… as one car drifted left, the other went right along with him. As they drifted back, they did so together like Ben Hur’s chariot trying to dice up his competitor’s wheels. Not only was the path dumb and the colliding dumb, they were being dumb in sync with each other. Solution? Put a repulsion vector on each other so that following the path is not as high a priority as keeping from scraping paint.

I’m not entirely sure what causes the AI to switch paths. Obviously an event like a spin or crash would cause the AI to pick up a new line. However, it is difficult to tell of the AI changes lines when nothing else is happening – like a cross-country skier stepping into a new pair of tracks. This does, happen, however. I’m just curious as to when and why. Certainly not when they are bumping and grinding down the straightaway, however.

There is another factor, it seems, behind why the paths are the way they are. Not all paths are created for all cars. If the AI is in one of the big heavy cars, for example, they will tend to pick a path that wanders back and forth across the track. This is very noticeable with Wario’s purple beast. He drives like he has imbibed heavily. This is an interesting balancing mechanism – Wario’s car, like other larger cars, is fast once it gets up to speed. If that were left unchecked, once he passed you, he would be a bitch to catch up with. However, if that speed were spent meandering all over non-optimum lines, it slows down his progress and makes for a neat stylistic appearance as to what we get out of ol’ Wario’s character. It is difficult to know what exactly is happening behind you in the race except on such short tracks as Baby Park. Does Wario drive like a drunk moron when he’s 3 places back or only when he’s in front of you?

That brings me to another point… rubber banding.

The Search For Equality…

Rubber banding is one of the most misunderstood aspects of Double Dash – and probably many other games that utilize this technique. Really, it is also a point that blurs the lines between AI, simulation modeling and the basic game design decisions. There is a staggering amount of this going on in DD.

First there is the speed of the cars. In general, when you start a new “Cup” (group of races) and the game “picks teams”, the AI will also assign a general skill level for each car. Throughout that cup, the running order will generally be the same give or take a couple of places. The same 2 cars will generally be in the top 3 and the same two cars will generally be in the back of the pack. This is obvious after having finished a 16-race cup and having one car have a single-digit score – which is only possible if you are continually finishing either last or 7th. Also, if you are a trained professional like I am (I have to look into some form of Mario Kart accreditation or certificate), you will realize by about the 2nd lap of Luigi circuit which of the cars you will have to put up with for all 16 races. [misc. editorial rant: Damn big, fat Peety-head!]

There seems to be three ways they go about stringing out the pack like this:

1) By simply using the published speed of the cars. The fast cars will tend to be toward the front, whereas the putt-putt-mobiles will be in the rear. That means that those first two cars you have to contend with as a good driver will be the big, fast cars.
2) By varying the published speed of the cars. Just because two cars are 3-star speed, doesn’t mean they will always go 3-star speed. This is good in that there are more speeds in practice than the 5 possible stars that the cars are rated at.
3) By varying the time they have their “foot on the gas and brake”. Again, this is visible on Baby Park when you lap someone. If you watch, you will see them move forward in fits and starts as if they are only “hitting the button” intermittently. It’s a nice effect that makes them seem unsure of themselves.

However, the above isn’t rubber banding – it’s just spreading out the pack. As you improve in your skills throughout the game, you will notice that you will usually have a fair amount of company… within reason. If you stop dead in the middle of the track for a minute, don’t expect the AI racers to be sitting around having coffee waiting for you to catch up. However, there will be some noticeable slow-down of the entire pack. Likewise, if you are good, the whole pack will be slightly better than normal. One way of noticing this is if you have two human players of differing ability. You will see such things as the pack stringing out more than usual to accommodate the different players, the lead player running away with the race as the pack holds back or the poor player getting completely skunked as the lead player pulls the pack along with him. I’ve spent too much time racing and not enough time testing this phenomenon, however.

Another method of rubber banding is one that people refer to as “cheating.” (This is likely because it is frustrating… imagine that.) If you are in the back of the pack, you can plan on getting better “stuff” from the boxes. If you are in last, you will be fed a steady diet of mushrooms, stars, lightning bolts and blue shells. If you are in front, however, expect to get green shells, fake blocks and the occasional potassium fix from bananas. It should come as no surprise, therefore, that the AI racers in the back of the pack are the ones getting the lightning bolts and the blue shells. (One note, it IS possible to have a blue shell by accident when you are in front… which means you get to hit yourself with your own blue shell!) If you watch on Baby Park, or keep your eyes on who is the one not getting zapped by the lightning bolt, you will see that the AI is getting much the same load of goodies that you are. I concede that it is possible that they are getting more aggressive stuff, but it is not outright “cheating” in the AI sense.

Now, there does seem to be a change in that algorithm as the race progresses. If you are in last on the first lap, there isn’t as much of a sense of urgency. If you are in first on the first lap, you won’t be getting assaulted non-stop. However, in both of those positions, things seem to change as the race wears on. If it has been smooth sailing for the first two laps, you can expect to have attracted a bit of attention on the third one. Perhaps it is this phenomenon (and the resultant indignation that ensues) that causes people to cry foul. However, once you have been in the position of playing catch-up on the final lap, you will realize that the game is more than happy to dispense one killer weapon after another in order to help facilitate retribution upon the AI. This is even in play on a multi-player race without the AI even being present. So again, this is a game design decision in order to further exciting races.

In the Pursuit of High Drama…

A couple of notes on artificially generated excitement… I can’t tell you how many times (probably because it is now into 4 digits) I have been on the final lap, in 2nd place and within striking distance of the 1st place car, but seemingly without hope… and it has driven straight into the only banana on the entire planet. It is almost as if the AI has gone out of its way to encounter the treacherous fruit leavings! Sometimes that is enough for me to make that last pass to win. Other times it is only enough to make the ending that much more exciting. Is the AI hitting that banana on purpose? Is it simply that the object was dropped onto one of the invisible paths? Does the AI drop objects onto the paths on purpose? This I can’t tell you.

Another observation I have made in this vein is that things that green shells don’t seem to have studied for their Physics 101 final. I swear that green shells, upon hitting walls or other obstacles, will uncannily bounce so as to cross in front of you. It happens too often to be coincidental. Similarly, I have seen green shells bounce off of objects at unlikely angles to strike the AI car in front of me a la the “lone banana” phenomenon above. I know that this is not a hard computation to make… just a little quick vector math based on the path of your car. Therefore, it is my estimation that this is a subtle trick to make the game environment a little busier in the right way. Make it look like things were really dangerous – especially when my back-seat sister forgets what she’s doing and throws green shells forwards instead of backwards.

Things That Work…

In general, Double Dash is a very well done game from the point of AI. I remember way back when we started, I never felt hopeless (until I hit Rainbow Road for the first time and fell off so many times I started laughing until I cried). On the other hand, now that I can’t even beat my own best times any more and have therefore maxed out my own (rather capable) abilities, I still run the risk of not finishing first on some of the races. I prefer winning games only about half the time, and, even after all these years, Double Dash hasn’t slumped back into the role of being a pillow for me to beat on mercilessly. While I tend to finish first on most of the races (80%?), getting a perfect 160 is still a goal rather than a given. I attribute this to the excellent rubber banding in the AI and design decisions.

The characters use their weapons well and intelligently for the most part. The driving makes sense, even when it wanders around the track. The character animations are engaging and amusing at times. (Being a Yoshi player, I am always tickled when he stands on the back of the kart looking “vigilant” glancing left and right to see what’s up.)

Things That Could Improve…

Sometimes, I wish that the AI states were just a little more obscure. It isn’t distracting or annoying, but I want there to be a little more subtlety to them. This is not that big of a deal, however, especially since we aren’t dealing with life-like, human characters. The effect goes quite well with the cartoony feel that is a trademark of the Mario games.

All in all, for the style of game that Double Dash is, the AI worked very well. Otherwise it wouldn’t be one of the top Game Cube games in the history of ever… still. And I wouldn’t still be playing it!

So… is there anything that you have experienced that I may have missed? Is there anything I said in here that is completely out of whack? Drop in a comment! One thing I would be very amused to find out is that I have chalked some effect up to the AI when it wasn’t really there in the first place. Now THAT is the sign of a good design (or an AI programmer who wants to believe in things waaayyy too badly!).

Add to Google Reader or Homepage

Content 2002-2015 by Intrinsic Algorithm L.L.C.