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.
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.
> "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.
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.
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.
> 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.
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.
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)
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!)
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
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)?
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.
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)
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).
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.
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))
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 ...).
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??" :)).
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.
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.
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.
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.
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.
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.
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.)
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.
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.
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.
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).
[+] [-] danso|13 years ago|reply
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.
[+] [-] noelwelsh|13 years ago|reply
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.
[+] [-] lotharbot|13 years ago|reply
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.
[+] [-] corin_|13 years ago|reply
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.
[+] [-] chc|13 years ago|reply
[+] [-] afreak|13 years ago|reply
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.
[+] [-] TheMakeA|13 years ago|reply
[1] http://www.valvesoftware.com/publications.html
[+] [-] Brashman|13 years ago|reply
[+] [-] johnyzee|13 years ago|reply
[+] [-] solnyshok|13 years ago|reply
[+] [-] illicium|13 years ago|reply
[+] [-] lotharbot|13 years ago|reply
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|reply
[+] [-] adriancooney|13 years ago|reply
[+] [-] supar|13 years ago|reply
[+] [-] vy8vWJlco|13 years ago|reply
https://docs.google.com/viewer?embedded=true&url=http://...
[+] [-] fafner|13 years ago|reply
[+] [-] TillE|13 years ago|reply
http://www.valvesoftware.com/publications/2009/ai_systems_of...
[+] [-] fafner|13 years ago|reply
(I never really liked scribd and with pdf.js it's clearly obsolete)
[+] [-] DanBC|13 years ago|reply
[+] [-] kriro|13 years ago|reply
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)
[+] [-] winterismute|13 years ago|reply
Disclaimer: I am a MSc student working on the above method for my final thesis (involving GPGPU steps and a true multi-tiled approach).
[+] [-] gmaslov|13 years ago|reply
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.
[+] [-] akx|13 years ago|reply
[+] [-] NickPollard|13 years ago|reply
[+] [-] lazyjones|13 years ago|reply
[+] [-] manmal|13 years ago|reply
[+] [-] lucb1e|13 years ago|reply
[+] [-] krsunny|13 years ago|reply
[+] [-] mwctahoe|13 years ago|reply
[+] [-] iam|13 years ago|reply
[+] [-] hpcorona|13 years ago|reply
[+] [-] cateye|13 years ago|reply
I wished that instead of investing in graphics, the AI got more attention.
[+] [-] arocks|13 years ago|reply
This is a challenge in every randomly generated game content and the AI Director solution seems to be a fair one.
[+] [-] vy8vWJlco|13 years ago|reply
[+] [-] ddorian43|13 years ago|reply
[+] [-] jnazario|13 years ago|reply
no if only i could hire from that talent pool :)
[+] [-] kaoD|13 years ago|reply
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!]
[+] [-] ccozan|13 years ago|reply
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.
[+] [-] gmaslov|13 years ago|reply
[+] [-] setrofim_|13 years ago|reply
[+] [-] kriro|13 years ago|reply
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|reply