AI Follies: Detection

By Shamus Posted Thursday Aug 13, 2009

Filed under: Programming 48 comments

Inasmuch as the bad guys are a part of the program you’re running, the bad guys always know where you are. The game knows where you are in the same way that a puppeteer knows where the puppet is. Your position in the game is just another variable it’s constantly tracking as part of running the show.

But unless you want every bad guy to begin homing in on the player the moment the loading screen vanishes, you need to pretend you don’t know where they are. Detection is the system of deciding when to stop pretending you can’t see them. By default the bad guys can draw a bead on the player and ding them between the eyes at an unlimited distance the instant a clear shot becomes available. AI is used here not to make the foes more potent in combat, but to make them less so.

This usually begins with line-of-sight checking. Calculate a line from the AI in question to the player. If that line hits (intersects) anything before it gets there, then something is in the way and obstructing the AI’s view of the player. A LOS check used to be kind of a big deal, but these days they’re generally considered to be an inexpensive operation. Still, there is a cost to doing the check and thus an upper limit on how many you’ll want to do a second.

Sounds easy, right?

That’s the state of detection as it existed around Wolfenstein, but once you’re dealing with complex 3D environments with varying light levels and trying to make believable enemies things get really hairy. The goal of your AI is to not make a fool of itself by being too perceptive or not perceptive enough. Nothing will distance a player from the game and break immersion like having a bad guy perfectly track them while they are completely hidden behind cover, or see them a half mile away. In the initial post in this series I mentioned AI bad guys that had “super-senses”. Counter-intuitively, super senses are the result of exceedingly stupid AI. In effect, it’s too dumb to know it shouldn’t be aware of you yet.

Complex occlusion:

That LOS calculation we talked about a second ago is fine for simple scenarios, but it falls apart quickly in anything less than a barren cube-shaped room. What part of the player is the bad guy trying to look at? Sure, you project the line from the bad guy’s eyes, but where does it go to? The player’s eyes? If so, then you end up with the hilarious “I can’t see you so you can’t see me” logic. If you’re standing in the open but you have something hiding your eyes, then you’ll be invisible to the bad guys. Picture Chris Farley hiding behind a lamp.

So, the AI needs to do several LOS checks to various parts of your body. It needs to be able to see the top of your head poking up from behind the couch, your legs sticking out from behind saloon doors, and your shoulder poking out from around a corner.

Field of View

Obviously AI should not have eyes in the back of their head, and there needs to be some limit on how far they’re allowed to see. Generally, you see quite far and in great detail directly ahead of you, but this high level of perception falls off quickly at the corners of your vision. (The edges of our vision see mostly motion and colors and changes in brightness, and aren’t very good at picking out shapes.) People are also generally very bad at looking up or down, and their vertical vision can often be even worse than their peripheral vision.

Now, most people intuit all of this, even if they don’t know it. We usually have a sense of when other people should be able to see us, and deviations from these expectations are jarring. AI that can detect an unmoving player out of the corner of his eye at fifty meters feels like a rotten cheater. An AI that only sees a 90 degree cone in front of him feels like a bumbling moron. (Although the latter is often forgiven for the sake of being sporting. Because they’re viewing the world through a monitor, the player can only see a ninety degree cone themselves.)

Light Changes

This has become more important since the introduction of HDR lighting in games. It’s now possible for the player to be blinded to areas with vastly different light levels. If you’re standing in the sun, you can’t see into the dark train tunnels. If you move to the tunnels, the area outside becomes too bright to make out. Players expect these restrictions to apply to AI.

But this one can get really tricky, and I don’t think a game has done it right yet. I first raan into the problem in Thief, when I’d crouch in a doorway. I’d be in darkness, but the room behind me would be well-lit. The guard in front of me should have spotted me instantly. In real life, it would be safer to stand in the lit room than to stand in the dark with the light directly behind me, forming a perfect back-lit silhouette. Eventually players learned to rely on the visibility gem instead of their common sense to judge how visible they were.

I suppose it would be sensible to extend any LOS check that succeeds. That is, if we draw a line from the bad guy’s eyes to (say) the player’s shoulder and it actually hits, we then continue to follow the line until it hits something. We can then compare the light level of the player to the light level of the thing stuck, and have any variance in those values count against the stealth rating of the player. This sounds reasonable, but I suspect that we’d see the failure modes move to somewhere else if we did this. Definitely one that requires more thought.

Camouflage

Just because the LOS check passes doesn’t mean the AI should truly “see” the player. If I’m wearing camo and crouching in the underbrush, it feels very unfair to be spotted by the AI. However, if I’m just behind some furniture it feels perfectly reasonable to be spotted.

So the LOS check needs to do more than just figure out if I’m visible. It needs to examine what sort of things are obscuring me, how much of me is visible, how much I should blend with those things, and if I’m moving. This is complex and it requires that your artists get involved with the AI system by tagging objects according to how camo-friendly they are. A fern? Very camouflaging. A beach umbrella? Not so much. I’ve never run into a game where I thought this was done well. In Crysis, the enemies sometimes had foliage-penetrating X-ray vision, and being spotted while sitting still in a thicket is no fun.

Subjective Perception

This is the most complex one, and the most annoying to players. Generally soldiers don’t immediately begin shooting to kill the moment they see someone milling about in the distance. There is nothing more tedious than the army of clairvoyant soldiers who can tell friend from foe at two hundred meters with enough certainty that they are willing to shoot to kill.

However, if I’ve already gunned down half the guys in their base then I do expect this level of paranoia from the AI. Uh, unless there is no way for this particular bad guy to have heard about the attack, in which case he should go back to be more curious than trigger happy. Unless he’s heard shooting. Or he’s spotted me in a forbidden area where only an enemy would go. (I think it’s fair to assume that anyone coming out of the sewers or air ducts is a troublemaker. (Unless there are civilians around.))

Aren’t you done with the AI yet? We’re going gold in a few weeks.

Having these systems fail is often worse than not having them.

In one of the Cat in the Hat books, the story features a red mess that the kids keep trying to clean up. Each attempt to do so just ends up moving the mess from one place to another. I’m sure this was an environmental message of some sort, but it’s a nice metaphor for the problems that AI programmers are up against. Every time you try to fix a hole in the AI you just move the failure mode to a new situation. Adding better complex occlusion just makes the field of view problems stand out. Fixing those reveals the problems with camo. Fixing that (if you can) will expose the shortcomings in subjective perception. And so on.

 


From The Archives:
 

48 thoughts on “AI Follies: Detection

  1. David V.S. says:

    How about alertness? A guard patrolling or half-asleep has a fairly slow-moving field of view. A guard who is panicked after hearing gunfire is actively looking back and forth, and perhaps up and down.

    Or the AI’s current task? Someone engaged in conversation, or with his head under the hood of the truck he is repairing, won’t be as perceptive to the player’s sneaking by.

    This post makes me wonder if anyone ever made an “Daleks” mod for Unreal Tournament in which the computer bots have perfect homing but only moved when a player moves.

    1. Gilfareth says:

      For the record, Mark of the Ninja did this wonderfully. Spooking guards or having them catch you before poofing off and coming back when they stopped actively hunting you made them more suspicious, which meant more sweeping up and down to check the vents and ceilings as well as them moving at quicker paces once sufficiently freaked out. I absolutely loved spending way too long on a mission taking out individual guards just to pile them up in various easy-to-see points to freak out other guards, eventually leaving one last man surrounded with the corpses of his late coworkers and finishing the level to let him stew in his fear and permanent psychological damage.

      P.S. oooold post, so hello Shamus! Figure you’re the only one ever going to see this. :P

  2. Jericho says:

    For camoflage, I suppose you could go with a simple numeric system, based on colour/pattern. Red is a (on a scale of one to ten) 2, green is 10. If you are wearing a red shirt, your shirt is rank at 2 as well, so it blends. However, patterns/noise would require a similar system, as a striped shirt would not blend as well on a solid wall. Foliage is inherently noisy, so a solid green shirt would not help.

  3. Ingvar says:

    Hm, I wonder how much of the “Can the AI see the player” you can offload on the GPU? Of course, taht’d essentially just swap one bottle-neck for another.

    I was thinking something along the lines of “render the view from the AI character’s POV in low-resolution screen. make sure to NOT run any shaders and just paint the environment in one (or more, if you’re looking at light levels too) colour and the player avatar in another; if there’s enough high-contrast player-pixels in the view, the player is visible”.

    Thinking closer about it, you’d probably kill the rendering pipeline kinda bad, doing that, though.

  4. gremlin says:

    Thief actually used different fields of view for different alert states. Every enemy had multiple field-of-view cones that applied at different alert states and adjusted differently to darkness.

    Actually, I just came across an article about the Thief AI:
    http://aigamedev.com/open/highlights/thief-ai/

  5. Rob Hale says:

    One of my pet peeves is when the Field of View doesn’t relate to the characters head. An AI may be standing still looking left to right but their Field of View stays perfectly still based on their world rotation.

  6. Picador says:

    Many of these problems — with Subjective Perception topping the list — may in fact be impossible to “solve” in any objective sense. Different games may be simulating different worlds — in Thief, you’re supernaturally gifted and can nearly turn invisible in the shadows, while most games have no such conceit. What is a “realistic” way for a cyborg guard at a mad scientist’s lair to react to a noise he hears in the air ducts, after he heard a scream from the hallway ten minutes ago? Who the hell knows?

    I think that AI detection problems are never going to satisfy everyone’s expectations of “realism”. Instead, I think that at this point “realism” is just another word for “intuitive gameplay mechanics”. In other words, players need to know the parameters of the game with regard to detection, so they can play the “sneak around” minigame without getting frustrated. Thief obviously does a good job of this, since it’s the central gameplay mode: the tutorial at the beginning gives the player a very clear sense of when the AI will detect them and when it won’t. Perhaps game designers need to focus more on communicating the parameters of the detection AI early on in the game, rather than just simulating more and more “realistic” detection behavior that may or may not jibe with a given player’s intuitions about what constitutes “realism”.

    1. WJS says:

      What is a “realistic” way for a cyborg guard at a mad scientist's lair to react to a noise he hears in the air ducts, after he heard a scream from the hallway ten minutes ago? Who the hell knows?

      I’m gonna go with… “The writers who created the characters”. So games aren’t always simulating perfectly realistic scenarios. So what? Seriously, is “there’s no point in bothering” all this post has to say?

      Creating a good AI model is the first step, the second being to tweak the parameters of the model (you know what those are, right?) so that it fits the game you’re shooting for. I’m honestly surprised that there doesn’t seem to be any decent middleware for AI. It seems like the kind of thing that some people are very interested in (Shamus having to restrain himself from playing around with AI last post, for example (I’d really like to see that, by the way)), and as it’s been noted, it’s obviously not something that a lot of game developers want to spend a lot of time on, so there should be a market for it.

  7. Factoid says:

    @David V.S.: I think most games do a pretty good job of that one actually. It’s probably a relatively straightforward trigger. As the AI perceives sounds, sights, etc…it becomes progressively more aggressive in searching out the source.

    Some games only have two states: Alerted and not alerted. Others have shades of gray in between. It’s fairly simple to model, actually…as the alert level goes higher the field of view widens, detection distance increases, etc…

    Stealth games tend to have the most shades of gray in that area. FPS games tend to operate on a two-state system.

    Modelling that isn’t terribly difficult, but the checks to determine what triggers a certain alert level is where the challenge comes in. Some games do that better than others.

  8. Deoxy says:

    Some of those problems can be helped along a good bit with map-specific coding.

    That is, I know that a bot in room A can’t see anything in room B. Even though the foliage between clearing F and clearing G is fairly thin, there’s enough of it that visibility is impossible, so don’t check. That sort of thing.

    Camouflage and lighting can receive similar “cheats”, based on what’s in the game (if the character is wearing THIS it makes it THIS much harder see him when he’s in THIS part of the map).

    The point here is to give the appearance of having done all the hard stuff you mentioned. Actually doing them is one way to do that, but there are probably easier ways.

    For example, one thing to remember is that the player doesn’t see the world from the eyes of the foe, so it doesn’t matter if the enemy can actually see them or not**. If you give a reasonable chance to see based on whether the player is moving, some kind of terrain and/or range modifier, and possibly some stealth game-stat, players will generally be satisfied. If a guard should probably see someone doing the thing in question, and they usually do, and if a guard should probably miss someone doing this other thing in question, and they usually do, players will be happy.

    Basically, as I said in the last post to someone else, that’s all great stuff, but it’s WAY overkill. Approximate it well enough with shortcuts, and people will be happy.

    **Until players have a way to individually control the limbs of their avatars, checking to see if the bot can actually see the player is a bit of a crap shoot, and almost guaranteed to be annoying in a significant number of situations. This is currently abstracted, so whether the bot can see the player needs a similar level of abstraction.

  9. Lazlo says:

    I’ve always felt like Splinter Cell did most of these fairly well, although I can certainly see some of the flaws you mention here show up. Of course, AI detection was really about 90% of what that game was all about, so I’d hope they put some effort into it.

    The interesting thing to think about here is the very expensive and simplistic way to go about it: for each NPC, build out the “screen” that they would see if they were a player. Then it’s just a matter of building an AI smart enough to pick out a person and distinguish friend or foe from what is effectively a video feed. If you can nail *that* problem, then lots of people (who probably aren’t game developers) will want to have a talk with you.

    1. DL says:

      Actually, what you proposed isn’t as unfeasible as you might think. Sure, doing that check for *every* AI enemy each cycle would be prohibitively expensive, but we don’t need that.

      Most of the time, if the agent is already aware of the player, we only need to check for direct visibility (once you focus on something, it’s pretty easy to keep track, barring something blocks your line-of-sight). The line-of-sight check can be implemented through rayshooting, and since most of the objects in the level are stationary, you can build a nice accellerating structure around them and then you can afford to shoot up to 50 milion rays per second (I actually have an implementation right here that can do that. Plus, the time complexity increases with a logarithm of the number of objects, so you can cram as many obstacles as you like into it without any noticeable decrease in performance).

      The most difficult case you would have to solve is the one of an agent that does not yet know the precise location of the player, but may have a reason to look for him (either just because he’s a guard on duty looking for intruders, or his level of alertness is higher for some reason, such as having heard gunshots).

      You can first shoot a couple of rays from his eyes to different parts of the player’s avatar, to decide whether there is any chance at all of him seeing the player. In this test you may ignore partially transparent objects (tree branches might be a single polygon that’s transparent in places determined by a texture) and still be able to quickly eliminate the impossibilities in most situations.

      When you have determined that there is a line of sight, you could render the scene from the agent’s viewpoint. You could use a simplified shader for this, because you only need the approximate colors of the avatar and the surroundings. What is important is this – you have to keep track (in a stencil buffer of an RBO perhaps) which of the pixels rendered are player and which are the environment, ideally rendering the avatar into a separate buffer. This information will allow you to calculate the contrast of the avatar and the obscuring objects, using photometric weighting over a matrix or whatever. The bonus of this is, that it can all be done on the GPU in a single pass.

      Aggregating the contrast values (on the CPU again) would yield a number that you could call the “visibility” of a player, that you could then modify based on how quickly the player is moving, the distance between the agent and the player, alertness level, and so on and so forth.

      The hidden perk of this is, that it takes into account such things as differences in lighting (as mentioned in the article), and camoflage (ie. the player is harder to detect if he has similar colors to his surroundings) and so is almost perfectly realistic.

      Almost. In fact, those who develop military camouflage have found that the most important factors in detecting the human form (if there’s not a very clear difference in color) are its characteristic silhouette and the discrepancy in color patterns between foreground and the camouflaged person. Emulating the detection of these is the focus of computer vision, but since one of my flatmates is a researcher in that area, I happen to have some insight into that as well:)

      The thing is, there is some research going into using markov chains constructed from a picture to realistically fill in blanked out portions of it. These chains then containt the information about patterns in the image in question, so constructing a chain of a rendition of the scene without the player’s avatar and with it and comparing them may give you some insight into how different the patterns are.

      However, to be entirely honest, I have no idea how long a construction of this chain would take or how exactly to compare them. I’ll have to ask him, I guess.

      Matching the silhouette might be a more complicated calculation, but I do believe that just the pattern test would be good enough.

  10. Deoxy says:

    Lazlo:

    Actually, the ability to recognize people in a real video feed is already disturbingly well developed. The debate now is not about whether to create such capability but where it is right and reasonable to use it. Very off-topic and VERY disturbing political/can-I-trust-the-government sorts of things….

  11. Neil says:

    First of all, I think these sorts of posts are the most interesting on the site. Kudoes, keep it up.
    Secondly, P&P RPGs and games based on their mechanics (Neverwinter Nights, Knights of the Old Republic) usually use a random factor to cover all of the complexities. Would it be possible to use a hybrid system for this sort of thing? Yes, check LOS, noise generation, camo color matching, light situation, smell, and possibly threat evaluation; but when you get to levels of failure mode possibilities that would take unacceptable levels processing power to resolve, could you not simply use a randomization factor to cover those situations? Sometimes the guard had his coffee this morning and spots you, sometimes he didn’t. Sometimes the player accidentally steps on a twig or trips a little and makes some noise.
    Of course, you would have to control the magnitude of the random factor to reasonable levels. Just because the guard rolled a 1, you shouldn’t be then able to tapdance on the corpse of the other guard you just shot 5 feet away.
    Get to the point of “good enough” with the described behavior, and use a dice roll to cover the rest.

  12. Ryan says:

    I have played a game like that. Metal Gear Solid 4 seems to fit that description pretty well. You are given a camo rating based on your camouflage, how fast you’re moving, and the lighting of the area you are in. The higher the rating the better your camo. In the top left corner of the screen is a radar type HUD telling you where you are and where everyone else is. A little circle grows around you showing how visible you are, if anyone else gets within that circle(and is looking in that direction) then they will spot you. Seems to work well as far as I can see.

  13. Rattus says:

    Lazlo :
    Problem with that would be that you would have to render the game for each AI character so you’d have to have one GPU for each couple of characters… probably not good idea as you mentioned.

    Deoxy :
    Local university guys have made a search engine that can find a person face in other photos. So you insert one photo of a guy’s face and get all the indexed pictures that has the guy inside. And it’s really working quite well.

    More to the point – I think the AI in games just need to appear smart enough. Article about FEAR AI was great in showing this, how much for example helps when enemy soldiers shout what they’re about to do.
    If they flank you and you don’t notice – you can see that as a cheating – they teleported behind you. If you hear “We’re flanking him” or “Calling reinforcement” then you know what’s happening. They actually don’t need to perform the actions, they just need to make you believe they are doing them and such you consider them smart.
    Usually it’s about the immersion breaking. When I see enemy popping out of thin air, no matter how good the AI is, I know it’s cheating.

  14. MelTorefas says:

    A game whose AI I like is Halo/Halo2. I am actually *just* playing these games for the first time (FPS has not previously been a big draw to me), and on the PC. Now, this AI is not always smart. Especially in the case of allied marines and their tendency to run directly in front of your moving vehicle. But, the AI detection has never once broken the game for me. Enemies spot me when I feel they should and fail to see me when I would expect them not to. And the AI is smart ENOUGH to use cover decently well and to use different AIs for different creatures, which provides some good variety. I know Halo/2 isn’t that complex compared to modern stuff, and I haven’t played Halo3 yet to see how the AI is in it (no PC port yet). But yeah, I do like the 1 and 2 AI.

    As always your articles are a great read.

  15. Jennifer says:

    I think more important than “can they see me?” should be “can they hear me?” unless they’re an “alert NPC” who is doing something like guarding and scanning the surroundings constantly for potential threats. Most people don’t spend their time constantly staring off into the distance so real stealth is based more around being quiet than being invisible.

    People also see movement a lot better than they see someone who is sitting still, so you might be able to construct a better (and cheaper) AI by focusing on movement rather than vision.

    You can also out-clever situations like trying to stare into a tunnel from a lit area by placing your mobs appropriately. No one is going to guard a dark tunnel by standing outside in a well-lit area. They’ll be INSIDE the tunnel where they can see out but anyone approaching won’t have an easy time trying to see them. If they are outside for some reason they probably won’t even try to see inside the tunnel, so they should only go on alert if they hear something suspicious.

    You could also mitigate a lot of this problem by having the AI do sensible things when they are alerted instead of relying on them pinpointing the player. Hear a suspicious noise coming from an empty tunnel? Take cover and see if it happens again. A second suspicious noise? Lob a grenade in there. The “take cover” as an initial action would fix the “friend or foe?” identification aspect (it would appear to the player that the AI paused before they began blasting away, they don’t need to know WHY the AI paused). It’s a sensible action, too, because the player is almost always *assaulting* a position instead of *defending* one.

    I think intelligent level design can compensate a LOT for the inevitable AI flaws. If you want people to use stealth or tactics, put in alternate routes that let them come up behind fortified positions. The detection won’t seem so dreadfully out of whack if “sneaking” doesn’t consist of slowly creeping through a wide-open area to get to the front door and picking off the idiot guards who are standing right out in the open.

    Get rid of the stupid “wandering guards”. You don’t guard by wandering, you guard by taking up a good position and then sitting still so people might not spot you right away. Anyone walking around should be non-alert, someone’s relief, or a sergeant type checking on sentries.

  16. JPLC says:

    @Ryan
    I was going to mention the Metal Gear Solid series as well. MGS4 is the ultimate culmination (so far) of the AI of the series, so it is a good example. I was, however, going to mention MGS3 for the fact that your Camo Index was more related to your own actions in that game. In MGS4, your camo will blend in to the environment automatically if you are still and stealthy, but in MGS3, you had to set the Camo yourself. It certainly slowed things down in MGS3, but it was a more interactive approach.

  17. Kdansky says:

    Have you ever wondered why the Marines and Combine in Half Life 1 and 2 always announce their next action over the radio which Gordon hears too? It makes their actions more credible, that’s all.
    Neil: One of the problems with such rolls is their frequency. If you roll every three seconds, that may or may not be too often or too rare. Possibly you can sprint past them after a failed roll before they get a second chance. Or on the other hand, they have a 1% chance to find you (hidden behind an armoire in the dark, shrouded in a silence spell), but since they roll ten times a second, they will usually find you in less than 10 seconds anyway. A real GM can roll “once per scene”, but an AI will be incredibly hard pressed to figure out how long such a time frame is.

    You covered this first (small) topic pretty well I think. I have also written some AI a long while ago, and it’s damn hard to do even decently right. I’ve gone from Stupid As A Brick to Ninja Senses On Rocket Chainsaws and back a couple times, but after quite a bit of tuning it offered a fun game. It also made up an estimated 30% of all codebase for that small project, showing how complex it got compared to anything else.

    If I look at current games, I think most games have ludicrously simple models for their enemies. No camouflage, no memory, no emotions, no cooperation. They blow their AI budget on pathfinding (difficult in a 3D environment) and other things.

  18. MadTinkerer says:

    I was actually pretty impressed with the AI in Dark Messiah of Might & Magic.

    In the game’s opening chapters you fight a LOT of the same enemy. What’s impressive is that unlike, say, fighting a hundred Combine soldiers in a row in the HL2 mod Coastline To Atmosphere, fighting the Blackguards doesn’t become tedious. This is done in several clever ways:

    1) Like the Ultima Underworld, System Shock and Bioshock (sorry, Shamus) games, your character is taught/given a bunch of different several different tactical options which slowly expands through self-improvement. (It’s most like the Underworld games, really.)

    In addition to the explicit “skills”, every area has one or more “environmental” options. Objects to pick up and toss at enemies, fire and spikes to kick enemies into, chains to climb, doors to shut, traps to spring, and so on. Grabbing and tossing large heavy objects, in particular, is slightly less effective than the Gravity Gun, but still a good addition to your arsenal. Regardless of your play style there will usually be a few good opportunities to simply grab a shovel (or whatever) and toss it at the bad guys before switching to your main tactic. In other words, the sheer variety of encounter-setups prevents the fighting from getting dull, and the fact that you are essentially fighting the same guys prevents you from worrying about whether a given tactic will suddenly not work.

    (Note that it’s not all Blackguards through the whole game, just one looong section where they make it very entertaining to fight the same enemy over and over again. Kind of like in Super Mario Brothers where you stomp on a lot of the same enemies in different rooms.)

    2) The skills are well thought out and designed to support different play styles. There are three skill “tabs” with two branches each: Melee Combat & Ranged Combat, Offensive Magic & Support Magic, and Passive Skills (more health, more mana, poison resistance, etc.) & Stealth/Assassin Skills.

    After a bit of experimentation, I’ve noticed that the AI is programmed to react predictably on an individual level to each of the options presented. Where it seems clever is when two or more Blackguards are in the same area (which is the usual case) and how their buddies react to their reactions(“I thought I heard something!” “I didn’t hear anything!” “Hey! An intruder over there!”).

    Stealth is nice and simple: You can hide anywhere it’s dark without the skill, but with the skill it also makes you quieter and you can move around more easily. It’s worth waaaay more than it’s cost, because it can be combined with environmental stuff (see above), melee rushes, ranged attacks, or just used to sneak past. There’s also a couple extra skills in the Stealth tree (backstab, for example), but the main skill just goes so well with everything else, it’s totally worth investing in, unless you’re a total berserker tank and don’t want to wait for them to hear you.

    Blackguards are also clever enough to flee and call for help, but stubborn enough that they won’t do so unless severely wounded. This adds a very entertaining tactical element where you’ll be spotted by Blackguards A, B, and C, and if you’ve wounded A badly enough and he’s crawling off to warn D, E, and F, it becomes very important to finish A off even if B and C are right in your face.

  19. MadTinkerer says:

    Gah, noticed a copy/paste error in the third paragraph. 15 minutes to edit is too short!

  20. MintSkittle says:

    I actually ran into a rare opposite in FO3:Operation Anchorage. In certain areas are stealth-suit commandos hiding in corners, but are instantly identified by the VATS system. Even though VATS gives 0% chance to hit, exiting VATS leaves you pointing directly at them, so you could just chuck a grenade at them while they just sat there.

  21. B.J. says:

    I still remember the worst AI detection system in a game ever: Hitman 2. It’s particularly egregious because it’s supposed to be a stealth/disguise game.

    The idea was even if you were wearing a disguise you still needed to act like your disguise. Reasonable enough, but the implemenation was way off. Apparently all soldiers were supposed to walk slowly, if you ran that gave away your disguise. It didn’t just make guards suspicious, it caused them to OPEN FIRE.

    Guard 1: “Hey is that Bob over there? I wonder why he’s jogging like that?”
    Guard 2: “INTRUDER! KILL HIM!”
    Guard 1: “…or maybe he needs to take a leak?”

    The worst was the Japanese level. You could disguise yourself as an enemy ninja (which included a full face mask) but the enemies would still spot you and shoot. From a mile away. Outside. At night. In a blizzard.

    I’m still not sure exactly how I finished that game.

  22. Zukhramm says:

    Let me complain about how the player detection in MMOs disturb me. Why are they not attacking me, when I’m slughtering their allies right in front of them? I’m out of their aggro range, wow, that makes sense…

  23. Aergoth says:

    I’ve always thought the bad guys in Nightfire (various assorted Bondmooks) did this rather well. You could sneak up underneath the window and they wouldn’t see you, but if you shot the guy in front of the frozen pond and he fell backwards, it would set the guys behind the window off and you’d get shot.

    Factoid’s example works pretty well there. They’ve got four/five states that I could determine:

    Attack (Bond is right there, I can see him) Response: Shoot at him.

    Alert (Bond is around somewhere. I saw him, but he moved to somewhere I can’t see him.) Responses: Look very carefully at the area I last saw him in.

    Warning (The guy standing next to me was just shot. I can’t/didn’t see where it came from) Response: Look around very carefully.

    Caution (That was a noise wasn’t it?) Response: Go investigate

    At Ease (nothing going on, sitting here chatting with my buddy, waiting to get shot.)

    They’ll move from At Ease to any other state easily. They will go from Caution to At Ease and Caution to Warning, but not from Alert downwards, and they’ll only move from Warning to At Ease given a good long time to feel safe.

  24. drew says:

    @Zukhramm: I both agree and disagree. Yes, on one level it is absurd that I can make eye contact with three other (human!) solders while killing the fourth without them doing anything to help their ally.

    On the other hand, realistic AI would absolutely ruin the strategy of most MMORPGs. Take WoW, for example. Right now, when fighting one enemy while others are around I have to consider my options carefully. I cannot retreat/kite them without paying enough attention to ensure that I don’t run into another enemy. If the first enemy gets low on health, they will start to flee and I am faced with the decision of perusing them and risking drawing in an “add” or letting them go. I have to consider what options I have for killing them quickly or slowing their escape along with what the consistences of picking up an add would be (which, in turn depends on my own current health.)

    Conversely, if the AI was “better” all the enemies is a given room would converge on me at once — after all, I am in plane sight and clearly attacking an ally of theirs. I don’t know if I really have a point here, but it’s interesting (to me) to see an AI behavior that is clearly unrealistic yet also clearly contributes to the strategy/enjoyability of the game — usually it goes the other way.

    I guess this comes back to what Picador said: if you communicate clearly to your players what the rules are (and those rules make for a fun game) that can go a long way toward earning forgiveness for rules that are not objectively realistic.

  25. Daemian Lucifer says:

    Actually its not true that every enemy knows where you are the minute the level loads.Sure,the game has all the variables of your location,but those values arent sent to all of its procedures.So AI doesnt immideatly know where you are,but finds out when he receives such input from some other part of the game.

    Also,a nice solution would be if LOS would go from you to the enemies.For example,your colours could be compared to the surrounding colours,then those that dont blend well would send trace beams in some arc in front of them.Then if some of those beams come into enemies eyes,youd be spotted.Advantage of this is that you dont have to do loads of calculations for each enemy every second,but just for one object,which is you.Of course,in stealth games youd need to extend this to all the objects that youve disturbed(like a body,or open hatch,or similar).

  26. Mark says:

    The article gremlin (#4) shared is incredibly insightful. Someone did this series for you, Shamus! :) One thing that the article mentions early on is that most game AI uses hearing and vision almost exclusively, and that got me thinking about the design of such a program.

    The hearing system is basically a literal implementation of an Event/Listener design pattern. Since it’s linked closely to the game’s sound engine, knowing what sound effects play and when is easy. The tough part is modeling the sound’s behavior based on geometry. Each Listener will know how to respond to different sounds based on what the sound is and his current mental state (which is itself an aggregation of all sensory data up to that point. I’m sure you’ll get to that eventually, and I really hope you mention empiricism and behaviorism, because that’s basically what it is).

    Vision, by contrast, is implemented as a method to poll the world, and polling is a naturally inefficient model. Rather than just receiving an event with all the relevant data, you have to get some kind of limited snapshot of the world state and then analyze it. When you take into account all of the geometry/texture/lighting, you’re all but rendering the scene from the POV of each avatar. (Side note: One thing that became painfully obvious in my run through Thief 3 is that my shadow was invisible to everyone else.)

    Motion detected in the visual periphery does seem more like an event that would trigger closer scrutiny from the observer (which may take their attention off of something else (subjective perception)). It would also mean that vision’s slow polling mechanism isn’t activated until the observer has a reason to start looking at a particular area more closely.

    Anyway, fascinating series so far, Shamus. I look forward to reading the rest of it.

  27. Ergonomic Cat says:

    I hesr the solution is to make everything [i]procedural[/i].

    I don’t want a 100% perfect AI. The thing players have going for us is our hue-mon brain. If the AI knows what we know, we’re just outnumbered.

    Also, perfect AI == Skynet.

  28. Tacoma says:

    An option I’m keen on seeing on any game with advanced AI is a choice of AI methods. Considering that you’ll probably use one of a dozen stock AI methods once they’re written, the programmer can stick in the most efficient three which have varying levels of effectiveness.

    EDIT: I’m not worried about storage space. They need to get better at space optimization anyway.

    That way the player can choose to have kind of dumb AI that runs very smoothly, good AI that takes a solid chunk of processing, or awesome AI that takes probably more processing power than he has available.

    Of course, having better AI makes the game easier, because as Shamus said AI is all about providing opportunities for the enemy to miss you.

  29. Zukhramm says:

    @drew: While the way it usually works in MMOs does indeed force the player to use strategy I do not belive a more realistic AI would ruin any form of strategy. It would just ruin that particular strategy.

    If they had a more realistic AI they would obvisouly not place the mobs the same way and expect players to make it through.

    While a game certainly can give up realism to be fun, I prefer, and especially in an RPG (even if it’s an MMORPG), the world to make at least some sense.

  30. A Reader says:

    raan? Under light changes.

  31. Rutskarn says:

    The most egregious fudging of stealh mechanics I’ve ever seen was in Dark Messiah. Let’s say I want to stab some orc in the back — a noble pursuit. So I get into a small patch of shadow and wait for him to come around.

    Of course, since I am:

    1.) Standing in a corner that was barely dark enough to conceal a good-sized spider

    2.) A foot away from a wall mounted torch

    3.) Wearing metal gear

    4.) Holding a pair of daggers that crackle with lightning

    5.) Standing up

    …he walks right past me, completely unsuspecting until I jam a dagger into his throat.

    At which point, I step briskly back into the shadow and wait for his buddy to walk over, bend over his body, and then proceed as normal.

    I really didn’t care for that game.

  32. Greg says:

    Can’t we just dial the games graphics back five years and stuff a pattern recogniser into each enemy? If we could get one going on a crappy processor in interactive C (motion and colour detection no less) for our lab robot then surely you could manage it in the sort of specs required for a modern game. Even if you only did the check every few seconds you could pass it off as reaction time.

  33. Zaxares says:

    On Subjective Perception:

    Ah, I remember this well from my days in Hitman 2. You could be perfectly disguised as a Russian soldier in head to toe fur coats and hat, running along the side of an airplane hangar.

    At the far end of the airfield, an enemy soldier sees you running, is alarmed, and starts shooting.

    The first time it happened to me, I went “Whaaaat? I can’t even see HIM from that distance away. And what happened to my disguise? I’m suspicious just because I’m running??” To quote from a walkthrough I once read on Hitman 2, “I don’t know about you, but I was a Russian soldier, and I saw another Russian soldier running along, my first instinct would not be to open fire!”

    This got even more ridiculous in a later level, where I was running, in white snow-camouflage uniform, through a FREAKING BLIZZARD and a sniper half the map away saw me, was alarmed, and shot me in the head.

    Fortunately later Hitman games vastly improved on the AI, but Hitman 2 always stands out to me as the game where you “must not run, unless you’ve already been spotted doing the dirty deed. Running is a cardinal sin in the world of Hitman 2.”

    1. WJS says:

      Right.
      Acting properly in disguise? -> Great idea.
      Soldier who sees you running gets alerted? -> Sure.
      Expected reaction? -> Run over to ask what’s the emergency. (Or ignore you, based on reasons)
      Actual reaction? -> Open fire on fellow soldier.
      WTF???

  34. Benny Pendentes says:

    In the ‘extra’ DVDs for LOTR, they showed how they’d designed the AI for interactions at the Battle of Helm’s Deep. When they first set it up the orcs were omniscient, so they created a couple of oriented horizons to limit the range over which an orc could hear and see. An orc who couldn’t see the enemy but could see another orc who *could* see the enemy gained some useful information – head in the direction that other orc is looking. Piling enough little rules like this together created pretty believable interaction.

  35. The Guardian says:

    There WAS a game that actually did camouflage fairly well. Operation: Flashpoint.

    One time I was infiltrating a guarded house and I was seen so I made a beeline around a corner… HELLOOOO, Soviet Tank! So I ran some more, around another corner and hid in a bush. The tank came zooming around the corner, and actually flattened the other four bushes next to me but not mine, and then stopped about 15 feet away. I don’t actually remember how I got out of THAT situation!

    It brings up a related point to your Subjective Perception too. That would be FALSE perceptions! That tank, for example, in reality should have either kept pursuing to where they thought I ran, turned around and flattened my bush for good measure, or headed back to its post. The guys hunting for me in the woods should shoot at random things like animals or branches swaying in the breeze. Not all the time, but if their tension level gets high enough they should become more trigger happy.

  36. BritishDan says:

    @Daemian: I have to disagree with you. When the level loads the program knows the exact state of everything on the level. If the AI programmer is horrible and this code says “run to, then shoot, the player”, everything on the level will come right at you. Only by introducing complexity, such as a specific state for every enemy on the level, can you start to hide the fact that you are really at the program’s mercy.

    There are really two elements to AI, reactive and predictive. Detection, as Shamus describes above, is reactive. The challenge there is trying to restrict the program from reacting to something that the player doesn’t think the program should be aware of. This problem, hiding what you already know, should be simple but as Shamus points out it’s a minefield.

    The second bit that I suspect he will get into is predictive behaviour. Think of a game like chess or Madden. In Madden you can run the same play 20 time in a row successfully because the AI doesn’t include things that we take for granted like “memory” and “learning”. These concepts are extremely difficult to include in an AI, and as some people have already pointed out, good AI is less about actually solving problems and more about adding in enough fakes to try to convince you that our code actually behaves intellegently (when, in fact, it often behaves randomly instead).

    1. Shamus says:

      Speaking of Madden:

      My brother is a huge football fan, and loves his madden games. In the 2004(?) edition, he discovered that the AI was basically helpless in the face of a single play, called “renegade”. He’d play an entire quarter of renegade, taunting the computer in the process.

      “Now, you KNOW what play I’m gonna run, right?”

      It was sort of pointlessly hilarious. It was also frustrating for him, since it meant he had to deliberately hamstring himself (by not running a play he know would work) in order to get any sort of interesting gameplay out of the AI. You could turn the difficulty up, but that didn’t make the AI any smarter, it just make its cheating more brazen. Turn it up enough and you’ll be playing a game of “1978 Pittsburgh Steelers vs. the Bumpkin Lake High Junior-varsity dumbasses”.

      Madden is the most egregiously awful franchise ever, bar none. It’s been running for over a decade and still has obvious and entirely fixable core gameplay issues, even while they tack on ever more stupid cruft…

      Arg!

      I have to stop this rant before it gets started.

    2. WJS says:

      He’s right, though; what you’re talking about is the game telling the bots about the player. Even though they’re part of the game, they don’t know where the player is unless the game passes a reference to them.

  37. Decius says:

    For sight, just check for LOS from the enemy to five points on the player: Two feet, two shoulders, and head. While that does leave the potential for confusion with odd geometry, it should work in ordiary play.

    Once we’ve figured out that the enemy has LOS, figure out if he notices. Factor in distance to the player, arc length from center of vision, and player movement speed, as well as enemy percerption skill and alertness level.

    For sound, everytime a sound plays (Include virtual events, like player_breathing, if there are enemies good enough to notice.), decide if it is heard, factoring in distance and obstructions. If so, determine if it is noticed. The sleeping gaurd would wake up if his superior approaches, only to fall asleep again after a few minutes. For that reason, when the player approaches, he should wake up, but be expecting an ally. If none show up, he should look around and become more alert.

    Making that happen, without scripting every possible case, is what makes a good AI. A great AI would also include reasonable combat options for unseen opponents, and different responses to alerts (“There’s an intruder” vs. “It’s only another drill”)

  38. Deoxy says:

    For sight, just check for LOS from the enemy to five points on the player: Two feet, two shoulders, and head.

    So, if there’s a slight rise in between us, obscuring my feet, and I’m standing with my head and shoulders blocked by a tree, but the rest of me is visible?

    At the very least, there should be some kind of “center of mass” check (say, hips instead of shoulders) to bar such relatively rare but VERY broken instances.

    But really, as I said, until the player can directly control the movement of said feet, checking the exact location of the feet (for just one example) is going to be screwy in at least significant number of situations.

    MANY things are still abstracted in video games (walking, for one very simple example). Real world detection depends on several such things (walking again comes to mind – how loudly do you drop your feet, where EXACTLY do you step, etc). Detection should thus be abstracted at a similar level as the stuff it depends on.

    For LOS, for instance: use the algorithm that determines hits with ranged weapons. That’s a decent level of abstraction. Now, whether or not you notice what you see (in camo, being still, for instance) is a different matter.

  39. Carra says:

    I just finished Hitman: Blood Money and the AI was quite good. There’s a lot of infiltration missions. An example would be to assasinate an actor in an opera. You can freely walk in your regular clothes between the tourists. If you draw a gun, you’ll be shot of course. If you try to go backstage, you’ll be shot. But not immediately. They give you a warning and if you do not move back in a few seconds, then they shoot. Change your costume to that of for example a painter and you can walk backstage. You can even walk around with your weapon if you dress as a police officer. At one point I dressed up as an actor to walk on stage and shoot the other actor. I however drawed my regular gun and they started shooting at me. Changing it to a WW1 replica and suddenly I could walk around :)

    It’s not perfect AI either. If I just shot someone with no witnesses and three guys walk in then it’s a good guess that I shot him. I’d expect all entrances to be sealed in a few minutes and everyone held for interrogagion. And if you find me trying to sneak into your house for the fifth time then I’m probably not doing much good.

    But overall, it was realistic enough for me not to really notice the AI.

  40. Andrew says:

    Considering the only way to make a fully human AI would be to simulate an actual person (which I’ve been told would take unheard-of processing power), AI seems to boil down to a game of predicting as many scenarios as possible. Even biological intelligence acts stupidly when exposed to a situation it has no experience with. This is why less ambitious games can have very simple AI that manage to leave the immersion intact (as there’s only a handful of possible player actions for them to react to), while the AI for open-ended games (any Bethesda title, really) will react wrongly more often than not. The player’s expectations of the AI’s competence also tend to be important. If your enemy is a robot that tends to act comically clueless in the cutscenes, the player will consider it perfectly reasonable when said robot fails at something a normal person would easily be able to do. If, however, your enemy is a top-secret special ops soldier trained from the age of six in modern combat, and they can’t seem to hit the broadside of a barn from a few meters away, the player will obviously call you out on it.

    Now that I think about it, having robots as enemies is actually a pretty clever workaround, since it means you can just hang a lamp on the whole thing- after all, those robots were programmed too, and when picking between turbo-charged transistors for their death ray and mildly competent AI for their robot mooks, your typical short-sighted evil genius will naturally sink their entire budget into their precious doomsday device.

  41. Shoku says:

    How expensive is actually placing a low rez camera in the head of AI units? It seems like you could have very close fog on most units (admittedly this would probably end up being another little thing for level designers to configure,) but that moment where something explodes could instead set the nearby units to scan the distance to see what they could find.

    Actually comparing some color-pattern score on the player against the environment next to them could shortcut any actual contrast comparison though that itself might not be all that expensive.

Thanks for joining the discussion. Be nice, don't post angry, and enjoy yourself. This is supposed to be fun. Your email address will not be published. Required fields are marked*

You can enclose spoilers in <strike> tags like so:
<strike>Darth Vader is Luke's father!</strike>

You can make things italics like this:
Can you imagine having Darth Vader as your <i>father</i>?

You can make things bold like this:
I'm <b>very</b> glad Darth Vader isn't my father.

You can make links like this:
I'm reading about <a href="http://en.wikipedia.org/wiki/Darth_Vader">Darth Vader</a> on Wikipedia!

You can quote someone like this:
Darth Vader said <blockquote>Luke, I am your father.</blockquote>

Leave a Reply

Your email address will not be published. Required fields are marked *