Ultimate Presentation
Killzone2_Revive.medium

The AI in KILLZONE 2’s Bots: Architecture and HTN Planning

Remco Straatman on August 23, 2009

TRANSCRIPT

Overview

Introduction and Motivation

Alex This next talk is split up into 2 parts, because well, many people worked on it, and lots of interesting technology came together. The first part is going to be by Remco Straatman. You saw Remco this morning, he's the lead AI on KILLZONE 2 and subsequent projects, and in charge of AI at Guerrilla. Remco, do you want to take it away?

Remco The title of this talk is "KILLZONE 2 multiplayer bots" and the talk will describe various aspects of how we implemented the, let's say, player imitating bots in the multiplayer modes. The work that we present here is done by, like Alex said, a lot of people in the team at Guerilla, but mainly the work has been done by Alex, the host here, and Tim [Verweij], who is sitting over there, who is also working at Guerilla, and myself.

Remco First I will start with a short introduction to the whole thing, like "why do we have bots?" or "what is the scope of the whole thing?" before we continue to explain to you guys how we implemented it. The first is, that after we finished KILLZONE 1, we checked which things worked and which things didn't work, and one of the things that worked actually better than what we thought, were the bots that were available in off-line multiplayer. We hacked these things together in the last two weeks of the project, and we got a lot of good feedback on it, so we thought it would be a good idea to do that again... not the hacking part, but the feature itself!

Remco Another thing was that, from a game design perspective, it was clear that multiplayer should have a bigger focus in the next version of KILLZONE. At that time multiplayer for shooters in console wasn't that big, it was clear that it was getting bigger, and that it would be a bigger part of the game and also the expected features of such event.

Remco And then finally, one of the decisions that was made initially is that the role of the bots would mainly be to teach players how to play all the new game modes and all the various choices available to the player. The initial role was not so much to make competitive bots like the ones that'll snipe you from the other side of the level, but to make something for people to ease into multiplayer game, testing out stuff, without getting shot all the time or being called out names through microphones. That was the initial goal, and then later on I will explain to you that we also started to use the things in action multiplayer games, this is how we set out.

Project Scope

Remco Just some scope on what the multiplayer part of KILLZONE 2 actually turned out to be in terms of design choices. KILLZONE 2, for those who don't know, is a PS3 exclusive title; you can have a maximum of 32 players online at the same time. There are a number of game modes, each of them are team-based, every online game is a battle between the two teams the Helghast and the ISA in the game. Most of these game modes are slightly technical in nature. You play multiple game modes on one map, so during one round, there will be one map, you will play one game mode for a set number of times, or a set number of points, when this finished, you switch to the other game mode, you play that and at the end of the host of game modes, the final score is determined by which team won most game modes. Another new feature was that, there's sort of a class-based structured for players, so there's a number of main classes that the players can chose from once they've unlocked them, and each class has a number of specific abilities which they can use, and also they can mix and match them between unlocked classes.

Class-based Gameplay

Remco The goal was to have, at least in the beginning, an offline mode where bots could help people play the different game modes, and test all the classes, and then, once the project started running, game design actually decided that they also wanted the bots to be available in online games where multiple human players could be in the game and bots and extra players could join, and bots drop out, or drop in again if people leave.

Game Modes

Remco The game modes, just to give you a short idea of what kind of thing they are, there's a "Capture & Hold" where there's a number of areas on the map that need to be taken into control; the teams get points for how long they have control over the areas. There's "Bodycount" which is simply just team death match, and there's "Search & Retrieve" which is a bit like capture the flag, there's one flag and both teams need to bring it back to their home base, and after a number of them, the one who has brought most of them to their base has won. There's "Search and Destroy" where there's one defending team which has to prevent the other team from blowing up a certain structure. And there's "Assassination" where the defending team, one of the players gets assigned the role of the assassination target, the others have to defend them for a certain amount of time, the other side has to try and eliminate the targets. If they don't succeed within a certain amount of time, then the defenders win.

Badge Abilities

Remco The other side is the badges: the class-based system. Basically there are a number of them. There's the "Scout", which has Sniper-rifle, he can "cloak" which means he's invisible when not moving or shooting, slightly visible while moving, and has a "Spot & Mark" ability which allows him to show all targets in the area on the mini map of the other players. There's a "Tactician", who can control spawn areas for team mates to spawn from after dying. There's calling "Air Support" that means you point on the map and a flying robot will come in and shoot at all nearby enemies for some time. There's an "Assault", which is basically a heavy class, this can run faster extending the amount of time. And just to complete this, there's an "Engineer" that can place Sentry Turrets and repair stuff, a "Medic" that can heal friendlies, and a "Saboteur" that can disguise as a member of the other team and place explosives on the map.

Remco The point of showing this is so you could see that for bots to actually play the game, in a way that makes sense, they need first of all to know how to use all these abilities, and second of all, they need to know how to do it in combination with the game modes and overall strategies. That's the kind of thing that we set out as a goal for us, when designing how to do the AI. I'll just briefly show a movie of the combined results, what it looks like when you combine all these things into the actual game, before continuing to explain the architecture of the whole thing.

Gameplay Teaser (Video)

Remco As you can see, that's quite hectic. There are quite a lot of things going on, so you can imagine why this would be quite intimidating for starting players, and why you would want to make a starter mode for them to get into it. And also you can see that there's quite a lot of cooperation and tactical choices, and use of badges that would require some specific AI. The first thing we did when we started this whole project, was to look at the current architecture that we had for the previous version, which basically was a set of Lua scripts on top of the squad and individual AI that we already had. And Tim, as part of his thesis, started looking at how we could generalize that and transform it into something that would work for the new system.

Architecture

Three-layer Architecture

Remco The thing that we came up with is a three layer AI system. At the top level there's a strategy AI, that is an abstract AI component, it doesn't have an actual entity in the world, it's just something that is running for both sides. There's one instance of this for the ISA team, and one instance for the Helghast team, you can think of it as the general of the two teams. And the strategies are different for each of the various game modes. So the part of the decoder decides what to do: when you do a "capture and hold" it's different from the part that you need to do when you're in "team death match."

Remco Below that, there's a squad AI, once again that's abstract AI as well, it doesn't directly relate to one of the members of one of the teams. And the squads, they work together to achieve a common goal or objective. And the strategy may decide to add more or less squads, and reassign people between squads, or bots in this case.

Individual Low-Level AI

Remco At the lowest level, there's individual AI. This individual AI, they are actually coupled to specific player entities in the game, and these player entities also need common combat behavior, so they need to be able to stand their own, and they need to be able to make all decisions to sensibly fight and to do their standard things, but it's the higher levels that would take care of the more longer term tactical and strategic decisions.

Inter-layer Communication

Remco If we look at this into a bit more detail, then you will see that there, of course, needs to be some kind of communication and coordination between all these layers, and at the highest level, the strategic AI talks to the squads, in a sense that it gives them orders, so it tells the squad "you need to attack this area", or "you need to defend this guy" or "advance to this regroup point". And then "back from squads to strategy" is form feedback on how well they are doing. So, for instance, if a squad is trying to Capture & Hold an area, and it's finding out that "I've lost almost all my men and I'm still haven't got control of the capture and hold area", it will already send back a message, like "this objective is not going to work this time". And at the squad level, there's again a control part, so the squad part sends out specific orders to the individuals to tell them what their role is in the overall goal the squad trying to achieve. "Individuals back to squads" is information about what they've observed, so individuals will share information about threats, and whether they're being attack with the rest of the squad, and with the squad itself.

Remco Then there are some cases where we side-step a couple of the squad layers, basically there's some specific game modes, where one player has a special role, like in assassination, and in this case we directly control that specific player from the strategy. And in a similar way, there are some cases where bot players, with specific badges, send back messages to the strategy, so in the case of the Engineer that can place a Turret, once it's placed, there's a turret to help defend one area, his role in defending isn't as big anymore, so in that case he can request reassignment, in case there's other places that need defending. The strategy can then decide to pick that request up and then reassign that specific bot to another place where he could place more of those defensive systems.

Remco So that's the overall picture. For the rest of the presentation, I'm going to discuss the individual AI, and the squad AI a little bit, and then Alex in the second part of the talk is going to discuss what we did in the strategic part of the whole thing.

Individual AI

Overview & Data Flow

Remco The individual AI, like I said before, is a specific AI that controls one of the player entities, it needs to be able to do a lot of things itself. It's not the case that we're micro-managing each individual on "who" to attack or "when" to attack, or to use this weapon, or this weapon to attack somebody. These are all things that AI needs to be able to do by itself. A lot of the individual AI is shared with the single player AI, and the architecture for it is pretty much in place for the last couple of projects already, with some changes that I will discuss.

Remco The overall flow is similar to what you see in a lot of similar systems. Below, what you'll see is that the AI will get stimuli which is a representation of sounds and things that are visible in the world, through perception, so calculating if you can actually see sometimes, if the sound is close enough to hear it etc… this will lead to a knowledge about threats, this knowledge is incomplete, you could be mistaken or maybe you don't know everything. On the other hand, information comes in from higher layers in the form of orders, "we want you to do this", and messages from other individuals close by to it, so like, "I spotted this guy" which is a different way of building up the threats compared to perception, similar to what the Crysis guys just mentioned.

Remco Then there's a number of daemons, which are basically routines that are run after every updated extract information from the world or the agent itself "how many bullets do I have left in my gun" stuff like that. And this all together leads to a role states which is sort of a data-base that represents how the individual things, the world is, at this moment. But once again, some of these things are not directly copied from the actual game state, so there could be mistakes in there, or it could be incomplete.

Remco Based on this, the planner will generate a plan which is a sequence of tasks, and it will start executing it. And then, at a task execution level, there's actually still some more layers that divide task into smaller animation actions. And once it's done, the final result will be the input to the virtual controller that is given from game codes. So we do a strict separation between AI and game code, we don't directly control animations or guns or whatever. We just have to do with something that mimics the joystick controller.

Hierarchical Task Netwonk (HTN) Planning

Remco If we look at the planning part in a bit more detail, because that's what I'm going to be talking about for a couple of slides, is in the previous KILLZONE, we had a different system for coming up with plans. For this one, after reviewing the pros and cons of what we did before, we decided to go with the HTN planner. HTN planning is not something we came up ourselves, HTN stand for Hierarchical Task Networks, it's something that originated in academic AI community, and you can look up the links if you want. What we did ourselves is take the formulas and implement our own planner, and adjusted it by adding stuff for plan monitoring or replanning, which I'll discuss on some of the next slides.

<

Remco Just to give a brief overview of what HTN planning is, each individual has a domain, which describes its behavior. The domain has a number of methods. Each method has a number of branches which describe how you can achieve a specific method, and each branch itself has preconditions, which describe when the specific branches are applicable for that method, and it has a list of tasks. So within the method, the branches are evaluated in order that they are described. So the first one that has its preconditions set to 2, will try to instantiate its task list. The task list can have 2 types of tasks, there's primitive tasks, which are things that an agent could actually perform, so these are atomic things like shoot your weapon, reload, walk a little bit, these type of things. And then there are compound tasks which correspond to the methods. So in that way you have some kind of recursion. The first branch that finally completely decomposes into a task list with only executable primitive tasks is the one that ends up being the plan that you execute.

Example Domain for Turrets

Remco This is a very short, brief summary of how it works; I'll give you a simple example even though the syntax itself is a bit lispy, so not too simple. Basically what you see here, is the rules for choosing which weapon to use so if you're at somewhere in the point of the whole branch strategy, the placeable Sentry Turret has to decide whether it'll shoot with its missile or with its gun. There's a method that's called "select weapon" and it takes a turret, which takes us to input the threat that it has decided to attack. It is two branches: the game designers decided turrets will only use bullets against humanoids, and other turrets, and it'll only use rockets against the flying stuff, and these are all the classes that we have in the game.

Remco The top, the white part is the pre-condition and it checks its database to see if the threat fact describes the selected threat, and its humanoid or if it's a Turret, and it close enough, in that case then it can continue to decompose, attacking using that specific weapon. The second branch actually does the same thing for rockets, and if during planning you manage to turn the complete task list into our primitive task, then you're done, you've got a plan. So that is one side of it. If you don't have a plan this way, you can generate a plan so you will end up with a list of actions to perform.

Plan Monitoring

Remco Of course, once you start running the plan, the world changes, and this means that you have to keep track of what you want to do, if you still want to do the same plan, typically the plan will fail and you will replan when the current task fails, so you're trying to shoot, and, I don't know, you lose your gun or something like that, and that is the easy one to detect. But a more difficult one so typically, where you want to stop a current plan before it has become impossible to continue it. One of the things is that a better plan becomes available: so you're moving from A to B and all of a sudden a grenade lands next to you then it might be a better idea to jump to somewhere else. Another thing that could happen is that even though the specific task that you're still doing, the walking for instance, is still possible, the overall context of the plan no longer makes sense. For instance you're running towards a mounted gun to mount it and start shooting, but while you are still walking, which is going fine, the mounted gun gets blown up, so it's a better idea to stop that. That suggests that you probably want to generate plans all the time, if you start doing that.

Remco The problem becomes that you will get very twitchy behaviors: for instance, a simple rule could be "I select the threat closest to me, I walk to go shoot it and then I'll start attacking" if you keep planning, then the moment you start moving maybe another threat will become closer to you, and you'll generate a new plan, and run the other direction, so that's not what you want. And the other thing is that, if you continuously keep doing that, reevaluating you're whole tree with all the methods, branches, preconditions, etc… it will all just become very expensive.

Replanning and Continue Branches

Remco We fixed that by, during replanning, we also check to see if you should still continue the plan that you're actually doing. So the people who make the whole domain for an individual, (in our guys these sort of AI programmers) they will add extra branches to describe if you should still keep on going the same plan when you had that part of the decomposition. The special branches have only the action in the task list, the key word would continue, when during replanning you hit that one, then you just keep the plan that you were still doing at that moment. And if you place those carefully in the domain, you can get all the advantages of stopping to achieve behavior and optimizations.

Remco To give another example, which is admittedly very simple, is that turret again, in this case the turret will continue attacking the same threat once it has decided to pick one, as long as it can do it. In this case the continue branch just says, "if I was attacking as a turret, then I end up here in the decomposition, then keep on doing it, "if you are not attacking as a turret yet, then in that case, you forget what your previous active plan was", maybe you had another plan before, that was of lower priority, "you will remember that you are now attacking as a turret", and then it tries to decompose the compound select threat and attack as Turret, which will finally somewhere down the line probably end up at the example I gave before. And once you've actually performed that attacking, you'll forget once again, what you were specifically attacking.

HTN Planning for Individual Bots

Remco So this HTN technology, how do we use this with individuals? Which type of behaviors do we actually see? Does the general combat behavior show the stuff that you also see in single player? Shoots at enemies', hides, "go into cover, run away from grenades, throw grenades, use machine guns, mounted gun" these type of things. Then in the multi player, you've got badge behavior, so the ones that you can do without specific consideration for the game mode or technical concerns. There's stuff like: if you're a medic, you should just heal, comrades that are mortally wounded, if you're an engineer you're near something that needs repairing, just repair it. Then there's a behavior that arrives from orders, guys get orders from either the squad or the strategy, and they will listen to that, and in the case of orders from squad then, specific badges can interpret an order in a different way. So if you are given an "attack to area" order from your squad and you're a Tactician, then you'll probably end up with a plan that says "ok, walk up close to the area you want to attack, call in flying sentry bot, and then continue to attack to that area", whereas when you're an Assault, you will not add that badge specific behavior to your plans. And then finally, there's some mission specific behaviors, so in the case of "Search & Retrieve", you'll be given specific order to pick up and return the search and retrieve targets. So these are the kind of behaviors that you can expect in the whole domain.

Example Domain for Medics

Remco I'm going to give another example of how this actually translates into methods and branches and all other things. This actually happens in the bots domains. This is sort of readable, so what you're looking at here is actually a debug view that is in game, for the Medic on the left trying to heal his friend over there. In game, we have some debug views that show the state of the various bots, and one of the views that you can see, is how did it get to the plan it currently has. Unfortunately the screen shots of the debug view are too difficult to read, so we just transcribe them into normal text which you now see into the slide. What you can see here is the whole decomposition from the top level behave method, which is what typically triggers all planning, and what you see here in the first decomposition, is that there are numerous branches, there's a "behave on foot, behave in a vehicle, behave in mountain gun" etc. I picked the on foot one because it's walking around. Then, one of the highest level individual behaviors for when you're a Medic is to do reviving of your friends. So that's the one it picks, well it wasn't already reviving somebody, so the two top branches which have to do either with continuing, or early aborting the reviving behavior, they were not chosen and the one that is chosen is to actually revive, try to revive your friend. Then, there's a number of orange primitive tasks, that are part of the medic revive branches task list, these don't need to be decomposed, they will just be placed in the plan if you actually manage to make a complete plan. There's a part that says "walk to position that is close enough to the guy to heal him, position probably will be selected based on the fact whether you expose yourself, if it's in range, etc.

Task List Debug View

Remco The debug view hasn't completely folded out here, so we continue to next one. Try to switch to the revive gun, and then there's a couple of different variants for that, based on whether you're already holding the thing or not. And finally, the last of two orange ones, is "use the thing on the guy and then forget the fact that states that you are reviving the guy". So this is how the whole system of branches, continue branches methods etc.. all comes together to lead to an actual plan for the guy. This is another debug view translated into PowerPoint slide, the task list is the thing that's interesting. This is the final resulting plan from the decomposition that you saw before, so here you can see in a shorter completely instantiated way the things I just discussed, you can see further instantiated the walk part, and you can see that at the moment it's actually in the phase of selecting its weapon, and after that it'll use it on the wounded soldier.

Development Statistics

Remco This is the way the planner works towards the behaviors that we see for individual guys. Now in order to give some insights on how complex our domains are, or how often all this is performed, we pulled out some random numbers from our debug views, and if you check out the individual multiplayer domain which is shared amongst all bots of different classes, this is the complete description of all the behaviors that they can do. There are 360 methods, which combined, contain like 1050 branches, and if you group these methods together into behaviors, so something like healing your friend would be one behavior, it can still consist of a number of branches or a number of methods. Then there's like around 140 of them, and you can also see that there's quite a lot of control in order to get the whole re-planning working in situ.

Remco In terms of performance, how often do we do it? Well we generate approximately 500 plans/ second, and this is for 14 bots and 10 turrets which also use the same off-role individual AI, and 6 of these squads. The squads also use the same planner; I will come back to that later. So 500 plans, we don't generate plans every update for everybody. Each of these plans actually tries out quite a lot of different ways, there's 8000 decompositions, so that means that you can see,that not all branches actually consist of task lists with only primitive task, where there's a lot of them, that actually requires some further specification. And on average, we do 15 decompositions per planning, so each time we generate a plan we go into more detail 15 times, and number of branches evaluated is about a factor 48 bigger than the number of plans we generate, which means that we actually try out quite a lot of different plans before we end up with the one that individuals or squads will actually perform.

Squad AI

Overview & Data Flow

Remco OK, so the individual can fight and do their badge things and everything, and then the next thing becomes to have groups of them work together in a sort of sensible way, and to take some slightly higher level decisions. Well, squad is simply a collection of a number of bots that work together, and the whole architecture for the squad AI is not that much different from the individuals. And the main difference is being in what type of decisions are being made and what inputs are and the type of actions it takes. So what you can see is that, instead of relying on perception, to come to its world state, it actually takes all its information from messages from its members. It still also gets orders, and only this time they come from the strategy layer, one layer higher. There is still the same planner, of course the domain looks different, and there's also the same task execution, only, the actual type of tasks are different. Almost all the tasks apart from some debugging or logging stuff are handing out orders to the squad members.

World State Debug View

Remco Just to give you an idea of the difference between the kind of things that squad reasons about compared to the individual reasons about, here's a part of the world state of a squad, so you see that it knows what game mode there is, it knows what the status of the capture and hold game mode is, it knows that it doesn't order from the strategy, it knows that it has 3 members and what they are doing at the moment. So these are the type of inputs that help the squad to generate its plans.

Example Domain for Defending

Remco To give another example to show you the difference, is a snippet from (one of) the squad domain: what you can see here is, this is a part that actually tries to make its squad members advance to another area, and the primitive tasks, they're here, well you still have "forget" which removes data base fact from the world states. You've got to remember which is the same as individuals can do. Then here it starts to become different, there's a start command sequence primitive tasks, which means I am now going to send a whole load of commands to the same individual, and they will all end up in the command queue, similar to command queues for RTS units, same in the command queue in this specific unit. And then the whole part is slightly indented, is basically all giving orders to that specific members. So there is an order for cleaning your area restriction, so it's free to move, setting the new area restriction, so it know which area it can move into to go from A to B, it orders it to move to defense, to a specific part, so this ties in with the example that I gave before where, once the individual receives this "move to defense" it can actually, in its own plan, decompose this either into "move there and just scan around" or "move there, place a turret" or "move there, place a spawn point" or "move there, call in a Sentry zone and then continue your things". And then there's after the move, there's a new area restriction handed out as an order to the individual to say, like, "ok, you can do your thing now, but you have to do it within this area" finally it closes off this command sequence, that is just to let it know that there will be no more commands edit to the commands queue.

Remco This shows the lowest two layers, and after the break, Alex will take on the highest part of the AI thing which is the strategy layer.

INTRODUCTION

KILLZONE 2 was one of the most anticipated titles of early 2009. While the quality of the graphics is immediately obvious, the game also received acclaim for its dynamic and adaptive AI. This is most obvious in multiplayer mode, featuring both online and offline bots that battle in a mission-based game environment.

In this presentation from the Paris Game AI Conference 2009, you'll learn about the architecture behind the AI for the Killzone series that has evolved over the years. You'll also discover exclusive details about the hierarchical task network (HTN) planner that was entirely written for the next-gen experience in KILLZONE 2.

About the Team

Remco Straatman (main presenter) is the Lead AI Programmer at Guerrilla Games, and was in charge of both the single player and multiplayer AI on KILLZONE 2. Remco's also responsible for the development of the AI technology over the years. He presents the last few slides in the recording below.

Tim Verweij (off screen) established the overall architecture of the multiplayer bots as part of his Masters Thesis. Tim also implemented the Capture and Hold strategy, and worked on the HTN domain for the bot's behavior.

Alex J. Champandard (presenting the next part) was contracted in the production phase on the KILLZONE 2 multiplayer strategy, which he worked on for the best part of 2008. Alex also implemented the badge abilities and multiplayer specific behaviors.

TAKE AWAY

DOWNLOADS

Discussion 1 Comments

Remco Straatman on August 25th, 2009

Hi all, just thought it was fair to give credit where it is due: the work on the multiplayer bots planning domains has mainly been done by Tim Verweij and Alex Champandard, the work on the HTN planner itself has mainly been done by two other members of my team, Robert Morcus and Hylke Kleve.

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