Article
stopwatch

Thinking Beyond Single Frame Decisions

Dave Mark on March 18, 2008

This week’s developer discussion at AiGameDev.com is based on an article originally titled “Not Now… I’m Thinking! Using Human Reaction Times to Build Better AI Responses” written by Dave Mark from Intrinsic Algorithm. Be sure to let him know you can take fast action by posting a comment below!

20ms isn’t very long, is it?

As AI algorithms get more complicated they also get more resource-hungry, especially those relating to decision-making. Thanks to Moore’s Law, as time has marched on there has been a steady stream of relief in the form of more processing power. Also, as graphics processing exercises its pursuit of diminishing returns and edges toward the asymptote of reality, it grudgingly allows other computational areas such as physics and AI to use a greater percentage of that increased processing power. However, the players (and the game reviewers that are their unelected proxies) have expectations of better AI that always seem to outpace whatever gains we get in sheer horsepower alone.

The Single Frame Law

As AI programmers, we are forced (or force ourselves) up against the invisible wall of framerates. Our agents must live their lives in 20 millisecond slices — perceiving, pondering, planning and performing must all be arranged in little easily-digestible bites. What’s more, they share their cramped temporal quarters with dozens, scores, or even hundreds of other cohorts — all clamoring for the leftovers that the art department has discarded… and all working under the same 20ms edict. If you can’t decide what to do in 20ms, it isn’t worth doing. (Alternately, “You snooze, You lose!”)

We fuss over their progress like parents. We want so much from them — to give them the life that they so deserve… that we could give them! If only we could give them longer than those 20ms to act in, they could be so much more! But why not use more than 20ms? Who says that they should only be allowed a single frame to make up their minds? Why can’t it be different? Why not give them the freedom to think? To dream? To live their (often truncated) lives to the fullest? (Ok, this is getting a bit anthropomorphic here!)

Figure 1

Many AI routines, whether it be pathfinding, planning or complex strategic decisions are getting computationaly more expensive. Often, if we are to respect the unspoken Law of the Single Frame, we must choose a less accurate method of calculation… or simply cheat. The premise that these decisions must be made in a single frame may very well be flawed. The argument that I have heard numerous times is based on the reaction time of the agent. “The player wants to see immediate results from the units.” Does he, now? Or does he want to see “realistically immediate” results? And what does that mean?

The Reality of Human Reaction Times

Human reactions times vary depending on what type of reaction we are talking about. The reaction time to a simply sensory stimulus ranges from 150-300 ms (i.e. 7–15 frames). Note that this is simply for the reaction to a stimulus. ANY reaction. For example, an enemy wouldn’t react to a muzzle flash from a gun (“That’s a gun shot!”) for about a fifth to a quarter of a second. If you add in a simple deliberation factor (“Is he shooting at me?”), reaction times are significantly longer. Add in a complex decision that may be based on a number of factors (“Should I return fire or go to cover?”) and you may be closing in on a full second of reaction time. Even further, add the additional necessity to process the environment – perhaps even visually observing and calculating pros and cons (“Given the environment, where should I go for cover from the shooter?”) – and we now are to the point where there is a definite lag time that should be palpably apparent to the player. And yet, we insist that this decision needs to take place in the single frame between the gun being fired and the onset of the action of diving for cover.

(If you want to really get a grasp on how slow our reaction times are, here’s a graph based on this online twitch test. Seriously, try taking it yourself!)

I believe the gripe about “instant action” is not completely ill-founded. Certainly we want the agents to do something. We have all seen the situation where a stimulus is given, either by the game engine or by the player, and the agent stands there as if blissfully unaware for a moment until he decides, somewhat lackadaisically, that maybe he better get a move on. That sort of reaction is one that rightfully gets our AI labeled stupid, sluggish and unrealistic. But, if the moment that I pull the trigger the target immediately – i.e. the next frame – leaps for the best possible place in the room to take cover from me, it is going to look… well… unrealistic.

Delayed Reaction Gratification

Figure 2

So, what to do? To avoid the “instant reaction” problem, one person offered a solution up to me (much to my amazement). They suggested that, after the decision had been made, the agent play a decision animation for a specified period of time. At the conclusion of the enforced “wait time”, the real action would start. The decision itself, however, was still being made in that first frame. This seemed like a colossal waste of time. Although this did not happen, it would have been striking to hear that same AI programmer complain at a somewhat removed time that “we can’t do that complicated decision idea we had because it slowed down the frame rate.

Figure 3

It seems that in order to be able to process bigger and better decisions, especially large scale strategic processing, we will need to move beyond what can be accomplished in one frame. There are already ways to do this to some extent. For example, there are numerous resources on spreading pathfinding over multiple frames. GOAP techniques that use pathfinding architectures can be similarly arranged. Strategic decisions such as analysis of enemy force deployment or determining dynamic cover points in which to hide are more difficult to spread over multiple frames. An acceptable approach to this would be multi-threading where a worker thread queues and processes requests and returns the completed decision to the requestor when it is finished.

Figure 4

This method, as well, has had its detractors. “The world will get out of sync, though! The decision may not be valid anymore by the time it is returned.” My simple answer to this has been, and still is… “So? Isn’t that realistic as well?” Again, remember folks… we are talking about individual frames here. Life at 20ms at a time! The real world doesn’t work in 20ms slices. And people certainly don’t think 20ms at a time!

A Quick Example…

Mapping this objection into the example above, if my agent detects a shot, determines it is at him, decides he can’t fight and needs to hide, and then, after scanning the environment, decides that the nearby barrel is the best bet for cover, he may have taken a full second. Even less if he had already mentally tagged the barrel as being a convenient cover spot. Now what could possibly happen in that single second?

  • Someone could have killed the shooter. The threat is gone.

  • A second shooter could have appeared nearby invalidating the barrel as cover.

  • A grenade could have been thrown between him and the barrel.

  • The barrel could have been blown up. (Everyone knows barrels are for shooting!)

  • His allies could have come into the room making fighting a better choice than hiding.

Any number of things could have happened… in that single second! Whereas in computer time it was a full 50 frames, in a human’s eyes, it is only one second. If you take a moment to think about it (was it cheesy to say that?), he wouldn’t have even realized THOSE stimuli existed until after he reacted to the first. The point is, it isn’t terribly tragic if the decisions being made get slightly out of sync with the world. As humans with reaction times far longer than 20ms, OUR decisions get slightly out of sync with the world as well.

Figure 5

In the mean time, in order to avoid the “dumb agent” look, I do agree with the idea of playing a “deliberation” animation or two. After all, we are all well aware of the need for the player to have feedback on what our agents are “thinking”. So, have the agent do nothing for a few frames (i.e. base reaction time), look startled by the flash (“Was that a shot?”), look afraid or thoughtful for a moment (“Should I fight or flee?”) glance around for a moment (“Where should I go?”), and THEN start diving for cover. And if something changes while he is thinking or even acting, have him react to that as well… once he notices it. (“Man… there’s another dude over there, too? Guess this barrel wasn’t a great idea, was it? Now where should I hide? Whoa… my buds are here! Maybe I don’t have to worry about hiding after all!”)

So Is Our Realism Realistic?

So, the question of the week? Why are we sacrificing ourselves on the Altar of the Single Frame — and thereby limiting ourselves in our quest for Realistic Behavior when, in fact, realistic behavior doesn’t even limit itself that stringently? How about it folks? Pros and cons? Experiences? Horror stories?

You have 20ms to respond. Go!

Discussion 10 Comments

Jon S on March 19th, 2008

I think delaying a decision is a good idea in general, but it would need to be done with caution. People may not react instantly but they also react in different stages. If a situation is life threatening you react fast but may not have a specific goal in mind yet. Also I think people typically have a goal mind and continually put more thought into that goal as they go along. I think to do this properly you would need two stages of decision making. The first stage would be completely reactive and primitive probably message based. It would work with more specific stimuluses and a more limited data set to keep help keep it fast. It could even just be used to decide what type of reaction animation to play. The second part would be more robust use that could use the result of the first as a starting point for it's decision and start to look for better options. This could use a larger knowledge base and start to move with a purpose. For example it reacts to getting shot and starts running in a direction. Then it starts to look for good places to run to in the second part. I haven't thought of ways to accomplish this yet that I like however, I do like the idea in general.

jskoog on March 19th, 2008

Working as an animator I can only say that this is good stuff! I believe the best way of convincing a character on screen is thinking is to let him glance up to the corner of his eyes and do nothing for a while.. In a fast paced actiongame this doesnt really work though as "Im shoot at" needs to be responded to really fast. The trick here (and this is pure speculation) might be to let AI decisions stick and let our AI characters to be slightly out of sync with the world. I would like AI to have a "Im running for cover now and Im not changing my mind unless that barrel Im taking cover behind explodes" determination..

Frederico Nogueira on March 19th, 2008

I think the idea very interesting, and there is an algorithm technique which goes in this direction. It’s called anytime algorithms. Usually an algorithm when executed goes through its completion and if it is interrupt before the needed time to complete the task, it can’t return no useful answer, but anytime algorithms can be interrupt at anytime, that the reason for its name, and it returns some useful information. After it can resumes and continues the process exactly from where it was interrupt. Thus the quality of this information will increase as the time for the reasoning process increases. As Jon S has said, the first stage should be almost reactive, so an anytime planner should give a plan without much elaboration just using one or two frames, it’ll just try to get the agent away from the danger perceived. But during the runaway plan execution (its frames), a more elaborate plan could be developed. This second process can represent the second stage. So at some level we could give for each agent goal a specific value representing the rate reasoning/execution. However all this ideas to the increment the reasoning realism (comparing to human one) process should be done carefully focusing in the benefit of the player’s entertainment. http://en.wikipedia.org/wiki/Anytime_algorithm

RyanP on March 19th, 2008

I do agree with Jon S and Dave M. The decision structure for AI should be based off of a "tree" type architecture where each action can branch but also be interrupted for the sake of new inputs and information being delivered as stimulus. one of the ways an animator such as Jesper S can account for it in a game situation that was described above is to when a shot is heard play an animation where the head snaps in the direction of the sound as a normal person would react and then the slight delay as the head moves around to look where to go, so you get the added benefit of at least a second or two while the enemy snaps his head and then looks around. Using the split tree decision above you have at least two possible times for delay and using multi-threading you can almost do all of them simultaneously being that you could have the enemy thinking for almost two full seconds while 2 animations were playing (head snap and head look) and if you needed to a third thread after the head snap possibly doing a default movement based on previously known factors (any allies here, any previously discovered cover, etc). Just my two cents.

Dave Mark on March 19th, 2008

I didn't go into detail about what I envisioned on screen during that 1 second (or whatever period of time). That could very well spin into an entire discussion on the forums or a chapter in a book. However, this is some suggestions about my example above. Each of these would be an animation that could be started with a simple series of delayed messages. 150ms: Flinch 250ms: Snap head around towards shot 400ms: Look alarmed, begin to raise gun as if to fight 550ms: Look panicked, step back slightly 700ms: Glance around room as if looking for cover, prepare to move 1000ms: Begin to move/dive towards selected cover Note that this gives us a full 1000ms (1 sec) to be able to process the thoroughly process the environment as it was at the beginning of the process in order to find a good cover location. At 50fps, this is a heckuva lot better than insisting on getting that information back in one frame. Remember folks, 50 frames seems like a long time - 1 second doesn't. Addressing the idea of having a goal in mind all along, this can be relevant, I agree. Much of it would have to do with the level of awareness that the agent had prior to the beginning of the process. If the agent was expecting a fight, he could be mentally tagging places all along. This can be handled in two ways. Actually keep a list of well-processed cover points as the agent is moving or, simply cut down the time allowed for processing the world AFTER the process begins. (e.g. instead of 50 frames, only use 30). Even being alert, however, doesn't negate that 200 seconds before even turning the head. (Did you try the reaction time link I included? You are actually waiting for the frame to turn from red to green... and you still can't "pull the trigger" quickly, can you?)

Ian Morrison on March 19th, 2008

To expand on the "thinking animation" thing a bit, who says that the AI can't make a split second decision or play for time to make the larger decision? While the AI in your example is trying to figure out if he should flee, where he should flee to, and how he could get there, he could still be making reactionary decisions on the fly. Instead of looking around wildly when a shot is fired, he could immediately move to make himself a smaller target by hitting the dirt or ducking down and putting his hands over his head. In a pathfinder, the frames leading up to the pathing decision could be filled with a reactive steering technique so that the AI isn't sitting in one spot mulling things over. In either case, you're letting a low cost decision making apparatus (FSM, etc) make general, "better than nothing" decisions while the AI figures out a more optimal course of action. Thanks for bringing up the topic, though, Dave! I just realized that the AI in my current project is actually quite bad about this... at the moment, 10 or so agents in a reasonably busy environment ends up bloating the AI runtime to 20ms, which starts cutting into the smooth 60 frames per second I'm shooting for (it's a 2D game, no excuse really). I've actually already implemented basic reaction times... all the AI's outputs are put into a buffer, while new decisions are being made each frame. It's just never occured to me that I could be using that time to spread my decisions out!

JonBWalsh on March 19th, 2008

I think this is a great way to get a ton more realism out of your AI and sounds like something that would be really exciting to see play out in game. As for the discussion of what to do in those initial frames where the AI is determining the best course of action I think that there's plenty you could do depending on the situation. One great solution is have an immediate 1 frame calculation of a quick reaction. It could be something as simple as a reactionary animation, a dive to the ground to be less of a target, or a panicked scramble away without any real determined destination (think scambling back down an alley/around a corner or towards a cluster of boxes without actually knowing which one is the actual destination. Even better any initial reaction could be put on a similar system as the longer one. So when the shot is fired the AI will first go to make an initial reaction which might take a short 300-400ms and cause one of the simple behaviors like I mentioned above (or those that others have mentioned in the discussion). Once that decision has been made the AI can then move on to making the longer termed decision. Either way I think this brings up some great points. I'd love to see AI minded people take reaction time more into account. Even AI that are bound to the same rules of the world as the player (such as in fighting games and RTS games) tend to feel like they are either cheating because of their instant reactions or handicapped because of their forced delays. One last thing to note is that such a system, if implemented, sounds like it could grow very complex to make it realistic. I say this because under different circumstances the reaction time of an AI is going to be different. For example if the AI watches an enemy go around a corner and decides to follow the enemy could do one of two things. The enemy could keep running or have taken cover/turned around and is ready to confront the AI. In this situation as the AI turns the corner they are going to be aware of the situation and ready to react to whatever choices the enemy has made. On the other hand if the AI is unaware of any enemies and walks around a corner and is fired at they're reaction to this unexpected situation should be much slower (as they have to go through who's shooting at me, where are they, what should I do, etc.). I could easily see many different situations having to be accounted for to both give the AI the proper reaction time to situations which they have to think and quick reactions to situation they should already be expected.

William on March 19th, 2008

"But, if the moment that I pull the trigger the target immediately – i.e. the next frame – leaps for the best possible place in the room to take cover from me, it is going to look… well… unrealistic." I understand this is not the main message of the well-written article, but nevertheless: I don't think an 'instant reaction' will be perceived by the player as being 'instant', let alone as a problem, for several reasons: - animation blending consumes a few frames to display movement that will be recognized by the player as a leap - shooting animations (muzzle flash, smoke, tracers, impacts) typically hide part of the AI's response (notably in first-person shooters) - a lot of TV sets already add 1 or 2 frames of lag because of upscaling (100Hz/120Hz, etc), hence the calibration function in Guitar Hero 2 and later. You can use GH2 to measure this on your TV. Furthermore, there are many situations (soccer, football, Counter-Strike) where we expect the AI to anticipate events and thus respond instantaneously, because that's what humans do. I can see why we don't want to be restricted to a single frame for our AI processing. On the other hand, I don't think the single frame response will be perceived as unrealistic behavior. And I appreciate the simplicity of a single frame response design. William

alexjc on March 19th, 2008

I'm going to take a different perspective on this problem, maybe a little more technical one. [B]1. Multi-Threading[/B] Solving this problem of coping with delayed decisions is probably [I]the[/I] biggest obstacle to the adoption of true multi-threaded paradigms for game AI. Writing a thread safe parallel algorithm is almost purely mechanical, and much easier in comparison... It's the process of dealing with a result that could arrive much later, or possibly never arrive, that causes developers to either not try or give up on multi-frame decisions. [B]2. Real-Time Systems [/B]Switching from a mostly linear program that are common these days (using threads as helpers within a frame) to a fully threaded "real-time system" is a huge risk and requires a very different approach to the engineering of the system. As I mentioned, it's incredibly hard to make any kinds of guarantees that you will get the result in time as soon as you've opened your door to computation that can take multiple frames and compete for processor time. There are many books on this subject... [B]3. Behaviors [/B]Don't forget that it still costs the game computation power to just "do nothing" or "quickly react" the way humans do! In theory it's easy to get the behaviors right. You can try to play a placeholder animation until you get the computation result. But doing that often will increase your reaction times to unacceptably slow by the time you've blended in and out again. So, if you try to predict what should happen, e.g. setting off in a certain direction using reactive movement, then trying to correct the motion once the full path arrives, then you end up with a potentially messy looking animaition. [B]4. Any-Time vs. Incremental Algorithms[/B] I worked on one of these for my thesis. I don't like them. The problem is they are just not stable. You can let them run and depending on how long they run they'll give you something very different. It's a nightmare to debug. You're far better off calculating the perfect result with an incremental algorithm, but that will find the rest of the path later (for example). This means you get responsiveness within a frame, and there's no loss of predictability. Well, I think that's it for now. What a fascinating topic! Alex

William on March 23rd, 2008

Suggestion: the merits of this approach are better illustrated using a 'stealth' game such as Thief or Splinter Cell. In these games, players spend a lot of time watching their opponents (typically security guards), and when detected by a guard still should have an opportunity to take out said guard.

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!