The AI Systems of "Left 4 Dead" [pdf]

http://www.valvesoftware.com/publications/2009/ai_systems_of_l4d_mike_booth.pdf

by StylifyYourBlog • 13 years ago

277 82 13 years ago

valvesoftware.com

TillE• 13 years ago

scribd is "unable to display this document", and the download button doesn't even work. Just link the original.

http://www.valvesoftware.com/publications/2009/ai_systems_of...

DanBC• 13 years ago

PDF submissions are automatically substituted for scribd links.

jfb6• 13 years ago

I had wondered why everybody else at HN seemed to love that garbage. What a terrible misfeature.

fafner2• 13 years ago

The link is to the original. The scribd link is to the side and is automatically added by HN.

(I never really liked scribd and with pdf.js it's clearly obsolete)

jfb6• 13 years ago

For PDFs at least, scribd seems purely parasitic.

lazyjones• 13 years ago

That's a very interesting read, even though in practice, the ingame AI still feels lackluster. Survivor bots often ignore nearby players attacked by special infected to move (slowly) towards some far away target (another attacked/incapacitated player) and special infected bots could really use some cooperation (as do many human players ...).

manmal• 13 years ago

I always wished that I could tell the bot teammates "stick together", "fan out" or "help me" via the chat. That would give them an actual sense of social intelligence, and bring them closer to real players (to be 100% realistic they would then have to ask "where r u??" :)).

Extigy• 13 years ago

Oh man that would be so cool. I suppose if text based adventure games can "understand" meaning within text, there's no reason it couldn't be remodelled into a chat setting.

Dove• 13 years ago

When Left 4 Dead first came out, one of the features they were proud of was a radial mouse menu of chat commands. You could make your character say "Heal me!" or "Tank!" or really any of about 27 things. I think it was intended so players could communicate without breaking character . . . which turned out not to be a high priority. I can't remember seeing anyone use it in a live game.

Anyway, I always thought the bots should respond to those commands, and was always surprised when they didn't.

Then again, the experience with the commandable AIs in Half Life was so profoundly miserable, I thought maybe they couldn't get it working reasonably. After all, when you give a command to a human, there are a lot of contextual clues involved in how to interpret it.

cateye• 13 years ago

This is exactly the reason why I don't like playing computer games. The games feel really scripted. Enemy character that wait until I cross a line before they attack me etc.

I wished that instead of investing in graphics, the AI got more attention.

ddorian43• 13 years ago

play multiplayer?

arethuza• 13 years ago

I only ever play multiplayer (mostly Halo 4 these days) - any time I try Campaign I find the AI rather boring and predictable. I don't know if the Halo series are bad for this or not.

arocks• 13 years ago

It is not fully scripted. The game has enough random elements that it might result in an unplayably hard scenario e.g. key portal blocked by dozens of mobs. Hence the AI must be smart enough to reduce the intensity of the generated content to a sufficiently playable level.

This is a challenge in every randomly generated game content and the AI Director solution seems to be a fair one.

vy8vWJlco2• 13 years ago

In light of the recent post on intelligence being analogous to the maximization of entropy available for future choices, I think things will get a lot more interesting in the future. Skynet may not be far off... (Even if computers can't feel, they might be able to put up a good fight.) That said, I don't know how I would feel about game characters stalking me on Twitter for a few days before showing up unannounced at my in-game job... Sometimes it's nice to know it's a game. (To say nothing of the autonomous military applications.)

vy8vWJlco2• 13 years ago

Google's PDF viewer works for reading in the browser (scribd isn't working on this one):

https://docs.google.com/viewer?embedded=true&url=http://...

fafner2• 13 years ago

pdf.js works as well.

adriancooney• 13 years ago

The climbing sequence is particularly impressive but maybe a tad excessive in my opinion but. I count six operations, two of which seem to computationally intensive due to their trial-and-error approach. I can see the reasoning behind it if the AI is climbing a physics props but surely map data could be retrieved relative to position and save all that ray tracing (if that's the correct term)?

supar• 13 years ago

Not sure what you mean by "map data". You can certainly have a list of props that are in the way and have them as a mesh. It's certainly easier if you have only one prop, but you have to account for that they may stack together in any way- and suddently the geometry configuration becomes non-trivial again.

kriro3• 13 years ago

Question about the navigation mesh.

I'm assuming that represents an entire open area (otherwise the path optimization makes no sense) and the dark stuff are the obstacles. In that case I'm wondering how the arrive at the actual grids and arrows (slide 12)

NickPollard• 13 years ago

Navigation meshes are commonly generated from actual collision geometry, i.e. as created by the art and design team.

gmaslov2• 13 years ago

This link explains fairly well how a navigation mesh may be automatically generated from the level geometry: http://udn.epicgames.com/Three/NavigationMeshReference.html . I believe it's also a good practice for the level designer to examine it manually and make any necessary corrections for sharp corners, narrow corridors, etc.

As for the path, A* search is usually the name of the game for any kind of 2D pathfinding. With the usual Euclidean distance heuristic it always returns the shortest path, but it's possible to use an "inadmissible" heuristic to make it run faster (and produce sub-optimal paths). The arrows shown on the slides are a little baffling; I can't imagine why those four vertically stacked boxes on the right-hand side would create a jagged path, for instance. It may just be exaggerated for effect.

kriro3• 13 years ago

Yeah I couldn't make sense of the arrows but I only know AI from 2d and have 0 clue about 3d game development.

Most toy examples I know use an even square grid so I was wondering if I might be missing something there.

Either way thanks for the answer (same goes for the other posters who provided links)

akx• 13 years ago

You might be interested in checking out https://code.google.com/p/recastnavigation/ (which, coincidentally, is what UDK/UE3 also uses nowadays (as a reference to the sibling comment))

winterismute• 13 years ago

Yes, navigation meshes can be created either automatically, by a designer, or through a mixture of the 2 (usually they are first computed and then adjusted by someone). Indeed, automatic and stable generation is essential in case of big, procedurally generated scenes, and it would be in general a nice achievement for the field. gmaslov provided links that explain some common ways of generating navigation meshes, that quickly looked to me like improved/refined application of the "flood filling" method. I just wanted to point out that there is a very interesting way (imho) of generating a 2D/multilayered navigation mesh, which is, by computing the Generalized Voronoi Diagram of the obstacles and then by annotating the vertices (and thus edges) of the graph with information about the closest obstacles' points. This way, we have both a "backbone graph" and a subdivision (a mesh). Here is a link to the related research of my Uni: http://www.staff.science.uu.nl/~gerae101/motion_planning/ecm... check it out if you are interested, there are also a couple of summarizing images and videos. The advantage is that such meshes are smoother, compact, yet they ensure very good coverage of the walkable space.

Disclaimer: I am a MSc student working on the above method for my final thesis (involving GPGPU steps and a true multi-tiled approach).

ccozan3• 13 years ago

That's hardly AI. It's just algorithms. Parametrized, using a probability distribution to randomize the environment, user programmed algorithms.

EDIT: Well, if this AI in game development, then so be it. But it's still not AI in the generic way, IMHO. To downvoters: I didn't contest the fact that they don't work. I do enjoy this games a lot and I praise the programmers that make such games work.

gmaslov2• 13 years ago

Ah, yes. The perennial curse of AI: as soon as it works, it's not called AI anymore ;-)

setrofim_4• 13 years ago

Reminds me of this passage from Douglas Hofstadter's GEB:

Loocas the Thinker comes across an unknown object--a woman. ... "Behold! I can look upon her face, which is something she cannot do--therefore women can never be like me!"

And thus he proves man's superiority over women, much to his relief ... The woman argues back: "Yes, you can see my face, which is something I can't do--but I can see your face, which is something you can't do! We're even."

"I'm sorry, you're deluded if you think you can see my face. What you women do is not the same as what we men do--it is, as I have already pointed out, of an inferior caliber, and does not deserve to be called by the same name. You may call it 'womanseeing'. Now the fact that you can womansee my face is of no import, because the situation is not symmetric. You see?"

"I woman-see," womanreplies the woman, and womanwalks away . . .

xhrpost• 13 years ago

If I remember correctly, people used to criticize IBM's Deep Blue for not being "real" AI because it just basically brute-forced a ton of possible play paths in the chess game. Someone then said: "Saying that Deep Blue doesn't really think is like saying an airplane doesn't really fly because it doesn't flap its wings."

setrofim_4• 13 years ago

That's what "AI" usually means in the context of game development.

ccozan3• 13 years ago

Thanks, I edited my comment. I am more in the field of general AI ( and the rest of pure definition of AI ). So normally what I saw is the intelligence of a programmer put into very clever algorithms. I don't see any learning effect , or persistence effect. In fact, once you shut down the game, it starts all over. I'd love a game that learns from the player ( like how to climb over an obstacle ). Or can anyone point me to such a game?

galaktor• 13 years ago

Exactly, AI in games solves a different problem than "traditional" AI. It's merely about creating the illusion of intelligence. Not unlike what happens in rigid body dynamics (approximated, not actual physics sim), graphics (plenty of tricks here, e.g. displacement maps vs actual geometry), animation (e.g. blending canned animations).

kriro3• 13 years ago

Search algorithms (especially ones using heuristics such as A*) are squarely in the AI category (planning a sequence of actions).

From a broader perspective the entire question of "should these bots seem humanlike or act rational" is a typical AI question (think the 4 squares of AI definitions in R&N). In this example it is specifically of interest to find a path that is not the most rational but rather the most humanlike (well technically I suppose you could find a performance measure to judge humanlike and optimize that and it would be rational after all).

opminion• 13 years ago

The intro of http://openlibrary.org/works/OL16095031W/Artificial_Intellig... discusses the variety of definitions.

johnyzee• 13 years ago

Adjusting enemy spawn and behavior by a calculated 'emotional intensity' of the player - very nice.

TheMakeA• 13 years ago

Valve is (was) very open with their publications. There are more available on their website[1]. I definitely recommend taking a little time to look through them.

[1] http://www.valvesoftware.com/publications.html

Brashman• 13 years ago

Any idea why there hasn't been anything since 2009? Have they stopped publishing/presenting or just not updated the site?

DerekAlia• 13 years ago

too busy making money off steam.

Caskman• 13 years ago

That's just an old page

http://www.valvesoftware.com/company/publications.html

solnyshok• 13 years ago

If a SurvivorBot ever gets far out of place for any reason, it is teleported near the team when no human is looking at it (AI cheating algoritm!!! Really enjoyed that)

illicium• 13 years ago

This works as long as the player doesn't notice. Counterexample: the Watson NPC in the Sherlock Holmes Nemesis game, http://youtu.be/13YlEPwOfmk

lotharbot2• 13 years ago

One of the reasons for this is SurvivorBots, despite their relatively solid behavior overall, can occasionally get stuck on an obstacle or trying to decide between divergent priorities (follow the others or grab a powerup? They can get stuck in a "dancing loop" where they shuffle a couple steps one way and then the other.)

It's important in L4D to require players to pay attention to their teammates, but it's also important to maintain the "fun" aspects of the game. It's one thing if the AI gets behind because they're being attacked and the player is doing a bad job of protecting them; it's entirely different if the AI gets behind because its algorithm sometimes gets hung up (and it's not fun for the player to have to try to solve pathing glitches!)

Robadob• 13 years ago

There is a similar exploit people have used in survival maps. If you were are able to get your player physically stuck (usually by moving up and down an angled area which goes below your player height, e.g. stair rail with ceiling above) you would teleport to the nearest teammate. http://www.youtube.com/watch?v=m_TzVMFRO-c

danso• 13 years ago

I love this game, one of the last FPSes I still play other than Team Fortress 2...unfortunately, like TF2, it's not very playable unless everyone in the round is amenable to being a team player. The multiplayer deathmatch allows one team to take the role of monsters, who have the backing of the zombie horde to make up for lack of guns. Playing it really provides some interesting insights to how the AI effectively functions, by slowly getting the human players to come unglued, either by targeting stragglers or letting the best players get too overconfident and move ahead of the team. Of course, all deathmatch games have this dynamic but it's very explicit in L4D, mostly because it's impossible for one human or monster player to singlehandedly own the opposing team in the way that an ace player can miraculously wipe out a team in Counter-Strike.

edit: The AI controlled human players is extremely competent, maybe the best bot players yet created. But they do show their limitations in multiplayer...among their weaknesses: they're too willing to sacrifice their healthpacks for an injured teammate, and will almost always try to help an incapacitated player no matter how hopeless his/her cause. Real humans can be total assholes, but in some situations its best for the team to leave a straggler behind, especially if the enemy has set up an ambush for the rescuers.

afreak• 13 years ago

> like TF2, it's not very playable unless everyone in the round is amenable to being a team player

Amen. TF2 and L4D are two games that I consistently play years after the fact which is unlike other games I have.

Unless you're playing with people you know, both games are equally frustrating. Specifically in TF2, it's those who go and play support classes when there are already enough of those in play on the map on your team that makes it frustrating.

ahelwer• 13 years ago

That only matters if you care about winning.

TF2 also has a huge accessibility problem which contributes to an overabundance of support class players, but also makes it a brilliant game. As opposed to the Battlefield series, where seeing the enemy first is most of the battle, it's actually difficult to inflict any damage at all in TF2. For instance, I'm at about the 200 hour mark and when I play demo I can only hit ground-based targets with pipes maybe 20-30% of the time - and that's quite good! For beginners, the only playable frontline classes are pyro and heavy. Spy and sniper are also popular because it's easier to survive when playing them, and maybe sneak a few insta-kills. Medic is easy to play, but can be very boring.

tl;dr: Don't hate the player, hate the game. And don't hate the game, because you'd be hating what makes TF2 such a wonderful game to play. Even at professional levels getting an airshot is a remarkable feat.

corin_2• 13 years ago

I haven't touched L4D since before L4D2 came out, and I hardly played L4D2, but what I found was that the further we got from the original launch, the less people there were on the servers, and the more dedicated those remaining were. It felt like you had to stay very active or get left behind, such was the tactical/practice element.

So while I liked the team-based nature, I found it actually didn't help longevity - for me, at least. Well, more relevantly, this is also the case for my friends - individually I'm a poor data point as L4D was the last game I took any real interest in at all.

lotharbot2• 13 years ago

> "The AI controlled human players is extremely competent... But they do show their limitations"

I have often wished that Valve would make the player-bots more explicitly customizable (particularly because I only play team vs environment modes, and occasional really bad bot decisions make the game harder in a not-fun way.)

There are several settings available through the console, but they can only be tweaked if the server has SV_CHEATS on. At one point I had a list of 4 or 5 minor changes that made the bots substantially more competent, the main one being reducing their following distance to about a third of what it previously was. My most wished for change, which I have not been able to find a setting to control, is the threshold at which AIs will use their healthpacks on themselves or actual humans.

noelwelsh• 13 years ago

I too have played a lot of L4D. What I find interesting about L4D is the way the game changes dramatically as go up the difficulty levels. On normal difficulty you can just run'n'gun. On expert you'll be knocked down in five hits, so you need to be much more cautious (unless you have amazing reflexes). Manipulating your environment becomes much more important, particularly the use of throwable items redirect the zombies or stop them attacking from all directions.

Tying this back to the article, the L4D bot AI, in my opinion, is intended to just be good enough to get you enough experience to play online reasonably competently. Multiplayer is the real game, and perhaps PvP is the real real game (I haven't played it much.) Bots are pretty poor at tactics, just bunching up by the player. They also don't use throwables at all.

chc• 13 years ago

The most inexplicable problem with the AI humans is that they absolutely guzzle adrenaline shots. Is there a needle anywhere around? Your adrenaline junkie teammate will grab it and shoot up immediately regardless of the situation. It's a huge waste of a great item. I initially thought it was just a bug, but as it was never fixed, I guess that's what they're meant to do. It's bizarre.

jnazario2• 13 years ago

in the past few months i started to learn a little bit about AI, including algorithms in planning (like PDDL) and logic engines. the more i learned the more i saw what the gaming companies, and that entire community, are doing and how they are some of the biggest consumers of these technologies. i have to say that it's impressed me, and it seems like the gaming companies are on the forefront of multiple areas of technologies, not just graphics and specialized CPUs.

no if only i could hire from that talent pool :)

kaoD• 13 years ago

Woah, I've been doing the same thing for the past few months because I took an AI branch for my last year in college. Unfortunately I feel they've been teaching us mostly outdated and useless algorithms (with all due respect).

I wish I was taught more about neural networks, machine learning, data mining techniques... and less about classic (and failed) AI algorithms. The most I learnt about these techniques was from teaching myself, even for the last year.

Perhaps we attend the same classes?

[sorry for the OT guys, no PMs in Hacker News!]

jnazario2• 13 years ago

no, i'm not a student.

presentations and papers like this are what i'm referring to:

https://skatgame.net/mburo/icaps2010-pg/ICAPS-PG.2010.1.bart...

http://www.plg.inf.uc3m.es/icaps-pg2007/papers/Symbolic%20Ex...

http://www.slideshare.net/StavrosVassos/the-simplefps-planni...

http://abotea.rsise.anu.edu.au/data/offline-htn-planning.pdf

http://www.guerrilla-games.com/presentations/VUA07_Verweij_H...

etc etc etc. turns out a lot of these ideas people thought were failures are getting a new lease on life in games, and they're working pretty well.

curious what classic AI algorithms you think are failing. from where i sit i'm seeing them get a new lease on life. maybe it's just the natural cycle of things: they get hot and invested in, they then fail to live up to their assumed potential, they fall out of favor for a while, and when everyone who was familiar with them - and their shortcomings - is gone a new generation finds it again and starts the cycle over.

lucb1e2• 13 years ago

I never felt like playing this game until now. The AI sounds very interesting to try for myself! Game producers should release such documents upon launching the game, it makes it that much more interesting.

mwctahoe• 13 years ago

but then some people will look through the docs, find the exploits and become the top players. Wouldnt really be fair from a game play standpoint but I agree this was one of the most interesting things i have read in weeks.

lucb1e2• 13 years ago

I don't think it's all that hard for many students (or others with no life) to play the game enough to find flaws in the AI without releasing technical documentation. You're right though, this is a concern... Perhaps if they release the docs a few weeks delayed?

krsunny• 13 years ago

Its hard to find a good match these days, people will either kill you or themselves at the beginning of a PVP match.

iam2• 13 years ago

Great stuff, have to disagree on the "replayability" section though. There were only 2-3 tier 2 weapon spawns on the entire map, the crescendos were pretty much always in the same spot (this was a bit better in L4D2), and so on. After the first 10 times every map felt the exact same.

hpcorona• 13 years ago

As a 3+ years of playing every night, i will have to disagree. The weapon spots are not important... The replayability comes with everything it provides. I have over 1 tb of dem files because i record every single match since start, and i still enjoy it.

iam2• 13 years ago

Oh, I don't think the game is not replayable, I had a lot of fun playing it and L4D2. I just don't think it was at all obvious accomplished their goals with the director AI that they set out to. Hence "replayability section" (directly referring to the PDF)

The AI Systems of "Left 4 Dead" [pdf]

Related Stories