Ever since it was first announced, the game S.T.A.L.K.E.R. has captured the imagination of avid gamers fascinated by the idea of a massive world populated by an A-Life system. The game also piqued the interest of AI developers here at AiGameDev.com, making it into the finalists for best AI and runner up for technical innovation in the Game AI Awards for 2007.
It’s therefore a pleasure to announce this exclusive interview with Dmitriy Iassenev, the mastermind behind the AI and A-Life system in S.T.A.L.K.E.R., who agreed to answer some questions about the engine and its implementation. As it turns out, there’s some pretty amazing technology under the hood to — and not only on the surface!
Screenshot 1: Non-player characters grouped around a campfire in S.T.A.L.K.E.R.
Alex Champandard: Hi, Dmitriy. Thanks for taking the time to answer these questions. Could you introduce yourself briefly and tell us about your background in AI and game development?
Dmitriy Iassenev: Hi, Alex. I am the lead programmer at GSC Game World on S.T.A.L.K.E.R.: Clear Sky.
The first thing I got acquainted with in this matter was the intelligence for the board game filler at the AI course in the university. Further on, this interest grew into the creation of a program that can play othello(reversi); it did not become the best, though it had won one championship on a synchro-random games (opponents play the same position for white and black simultaneously, after finishing both games the winner is determined by sum of the results). After graduating from university in 2002, I started working at GSC Game World as the artificial intelligence programmer on S.T.A.L.K.E.R.: Shadow of Chernobyl.
AC: One of the key features of S.T.A.L.K.E.R. is the A-Life system. Could you describe what you think is the essence of A-life, and how it can be applied?
DI: The gist of the A-life is that the characters in the game live their own lives and exist all the time, not only when they are in the player’s field of view. It eventually runs counter to the customary optimization processes used in games development (why perform operations invisible to the player?). Thus, such a scheme is reasonable to be used only when you know exactly what you want to have in the end. We had the game designers’ requirements to have the characters that could not only live inside a certain level, but move between the levels, memorizing the information they obtained during their existence. Consequently, we have decided that each character should come with only one logical essence regardless of the level he is at; whereas we could try to implement that with various tricks involved.
AC: There’s a fine line between a game and a simulation. How far does your implementation in S.T.A.L.K.E.R. take these ideas of A-Life?
DI: Our A-life implementation does not claim to be full and pure. The concept of a living world, where each character has his own goal is vast and complicated, indeed. Therefore, its realization to the fullest extent is a large and difficult task. Especially, when the matter concerns shooters, with their detailed elaboration of the actions, and when good-looking animations can be more significant than the high-level character actions. (This is much spoken about; the question of why the AI methods of RTS cannot be carried over to FPS has been discussed at your web-site, for example. I would also like to ask the AI developers in FPS games, how much time they devote to low level and how much to the high. I’d say that it would be great if the ratio is 10 to 1.)
[Editor: This topic will be the subject of an upcoming developer discussion here at AiGameDev.com. Be sure to subscribe to the site to find out how much time FPS developers spend on different aspects of their AI.]
Screenshot 2: Artificial life populating the area around Chernobyl.
AC: Could you tell us more about how you implemented the A-Life?
DI: Our A-life implementation is quite simple. We have introduced two terms that characterize 2 patterns of character’s behavior, different in implementation details: offline and online. The offline behavior is very simple: the character does not play animations or sounds, does not manage his inventory actively, does not build detailed and smooth paths (although he does build paths according to the global navigation graph, but more on that later), etc. In contrast, online behavior is fully detailed. Thus, offline behavior can be considered the LoD (level of detail) of the online.
“The A-life system follows the player’s movements, and switches the characters to online/offline as necessary.”
In our system the player acts in a level, other characters live in other levels, i.e. they are offline, i.e. they are using the offline behavior. Moreover, considering the high density of characters in a level, not all characters in the player’s level have the online behavior, but only those who are in a predefined radius from the player (can vary from level to level, but usually it is about 150 meters), or what the game designer sets it to. To achieve this, the A-life system follows the player’s and offline characters’ movements, and switches the latter to online/offline as necessary.
Next, navigation of objects in online and offline should be mentioned. Our game has levels, for each of which a separate navigation graph is build and is used by characters for movement in online mode. We call it the detailed graph. For each graph a less detailed version is created, the vertices of which can be connected with vertices of graphs from other levels. This is the graph used by characters for navigation in offline. It is also used by online characters for carrying out strategic objectives. For example, if an online character decides to move to the location on another level, he searches for the path on the global graph, then uses the current level’s detailed graph to create the path from his current position to a vertex of the global graph. If that point is already on another level, the character teleports there and switches to offline mode. To prevent the player from seeing this, we have placed these points further than the player’s transition points, somewhere “around the corner.”
Screenshot 3: A stalker getting into trouble with the army!
AC: What were the other important parts of the system for developing the A-Life in S.T.A.L.K.E.R.?
DI: Every character in the game always has a goal: to uncover the mystery of the Zone. In early versions of the simulator, a character knew one or several dealers, which had sets of quests that they generated based on the map of anomalous activity and requests from organizations, which wanted to get rich from artefacts found in the Zone. Completion of a quest brought the character closer to his goal. There was only one type of quest at the time — “bring an artefact”. The character would take on a quest to search for the artefact, go to the approximate area in which it could be found, if able to find the artefact, brought it back to the dealer, traded it, then picked a new quest. Along the way he could encounter enemies and fight them. In offline mode this was simulated as a TBS: the opponents took turns making moves, the result calculated based on a formula and the random factor. The effect was that one opponent could run away from another, sometimes characters got killed, sometimes they did not even notice each other or decided to avoid confrontation. If the character was a stalker and met a neutral or a friend, they traded with each other, guided by a developed trading scheme. All of this worked both in offline and in online modes. To notify player about the offline activity, we used news, which were generated if some character could see an event or its consequences.
“Every character in the game always has a goal: to uncover the mystery of the Zone.”
It was planned that the number of types of quests would later increase, and character behavior would diversify due to introduction of requirements of food and sleep. We also planned that our characters would be able to uncover the mystery of the Zone before the player, or at least collect a certain amount of information.
Then we changed the way quests were generated. Characters would now get quests not from dealers, but from the so-called smart terrains (not the same as in Sims). A character’s life now worked in such a way, that he took the quest generated by some smart terrain, then walked to the destination it had set for him. After getting there, he would get points, and the smart terrain would take him under control for some time. Under the control of a smart terrain, the character prioritized and carried out the available tasks. This is how the game got faction bases, stalkers by campfires, and such.
That is, migration of characters from place to place, their movement between levels, all was caused by changing goals.
Screenshot 4: The camp of an AI faction in the zone.
AC: How do these ideas tie in to the character AI at the lower level?
DI: Regarding AI at the single character level, we should look at the two models: offline and online, separately, even though they have some things in common.
Offline character AI is very simple: if there is no goal, try to get one. If a goal cannot be found, wonder about aimlessly. If there is a goal, go to the place at which it can be achieved. When a character is under smart terrain control, he can get additional commands for movement, but performs no other actions.
Online character AI consists of three layers:
collection and processing of information
a set of low-level controllers
A character has three types of receptors: visual, sound, and damage. Out of the information received from receptors, the character picks the interesting bits — enemies, threats, objects that can be picked up.
AC: How do characters make decisions in S.T.A.L.K.E.R.?
DI: The decision-making model has undergone many changes during the course of its development. There have been four iterations in total. First, we used hand written stack-based FSM. Then we switched to a hierarchical FSM, then I read the remarkable GOAP (Goal Oriented Action Planning) article by Jeff Orkin in Game Programing Wisdom II, then an article about motivational graphs, and we started using motivational graphs for goal selection and GOAP for action selection.
There are several nuances here, which I have discussed in correspondence with Jeff Orkin. We have decided to use planning exclusively for action selection. That is, we only needed a plan for selecting the first action. All the other parts of the plan were ignored. The value of the first action is in the fact that it is chosen not arbitrarily, but in the context of some plan. This is very good for debugging — you always know what your character is doing and, more importantly, why. This also makes it easier to tell if a plan is still valid, since our plan is always valid.
“Goal-oriented action planning is very good for debugging — you always know what your character is doing and, more importantly, why.”
To keep the plan valid, our implementation of GOAP kept querying those properties of the world that it needed to create the plan of least weight. We did not keep rebuilding plans, but only queried the properties of the world that the planner used to create the current plan. If any one of them changed value, then the whole plan was rebuilt.
On the other hand, a character must always have some non-empty plan. An empty plan meant that the character did not know what to do, since there was no sequence of actions that could transfer current world state to the target one using a set of available operators (or its attainment required too many vertices to visit, which happened, though rarely. In 99% of cases it meant that there was no such sequence, but the planner could not prove it, due to the limit on the number of visited vertices). The condition of existence of a non-empty plan demanded that we make a property of the world that always had a single value, which is probably not very elegant.
Screenshot 5: Armed soldiers patrolling in S.T.A.L.K.E.R.
To set a character’s (stalker’s) behavior we used several dozens of operators (about 70). To easily control such a number of operators, we used hierarchies of planners. That is, an operator could itself be a planner. Interaction of planners of different levels was carried out like this: if the top-level planner changed plan, with which the current state also changed, then the previous planner was informed that it should finish. If the operator was itself a planner, it informed its own current planner, and so on. It should be noted that finishing was an instantaneous action, i.e. if the action could not be stopped at once, this had to be taken into account not only at its level, but also at others, which introduces additional complexity.
“To easily control several dozens of operators, we used hierarchies of planners.”
That is why we decided not to use GOAP for the monsters behaviors, since monsters rely extremely on animations which cannot be interrupted or blended. Therefore we used hierarchical FSM for them, but, actually, it did not solve non-instantaneous action issue. In prequel we get solution to this complexity by transferring part of the logic into the low level controllers: high level logic selects goals for the low-level controllers. Therefore instantaneous action change in the high level doesn’t mean instantaneous action change in the low level.
There is also a nuance in combining two methods for manipulating logic. At first, we introduced motivational graphs for taking some load off the GOAP planner. Eventually it was found that the planner coped with its task well, and the search never exceeded 200 vertices. Besides, determining the logic for traversing targets consisted of the topology graph author taking some of the work onto himself. Eventually, we stopped using motivational graphs at all, since it became easier to set all logic in a single place. Different goals were used only for live and dead characters (for clutching the trigger while dying).
Low-level controllers were responsible for animation, movement, controlling objects, sound, character orientation. Implementation of these controllers is not particularly interesting, except that we also used GOAP for controlling objects (and quite successfully, at that). In my view, it would be interesting to see an approach using a controller manager that would perform some partially ordered planning on operators of low-level controllers. Here, of course, the speed aspect of its performance is very important, since low-level controllers are typically updated each frame. On the other hand, it could also take up many issues with implicit interaction between the controllers. Maybe it could even be used not only for logic of low-level controllers, but for all of a character’s logic, as has been discussed on your site (Rethinking the AI/Animation Interface).
AC: Since the final game had a story element to it, you also had certain areas in the game that were “scripted” in a more traditional way. Could you tell us more about how you integrated the A-Life system with the scripts?
DI: As has been mentioned above, quests in the game are generated by smart terrains. This also applies to the storyline. Story quests have higher priority. Moreover, storyline areas are surrounded by so-called space restrictors. Their purpose consists of keeping the storyline characters from running too far away, and non-storyline characters from interfering with storyline elements. That is, there a significant amount of control over simulation. On the other hand, after the player completes the storyline scene, storyline characters become regular and follow regular rules, i.e. choose quests and go carry them out in the appropriate smart terrain locations. At the same time, the area is freed from all limitations.
Screenshot 6: The danger zone around the power plant itself.
AC: Was the process of integrating these scripted areas with A-Life a difficult process for the designers? How did they approach the process?
DI: It was difficult without space restrictors. Then, any “outsider” character would either break the storyline scene by distracting other characters, or, if they were not permitted to pay attention, stupid situations would occur, like having a character be bitten by a dog, not pay it any attention and finally die fully armed.
To generalize, one could say that space restrictors, along with careful management of information coming from receptors, solved this problem practically completely, in time.
AC: In retrospect, what parts of the system and/or development process were you particularly happy with?
DI: I was very happy with the work done when I followed a stalker from one level to another, saw how he searched for artefacts, found them, returned to the dealer, approached him, traded, picked a new quest, went on — too bad this did not make it into the original game. It was very interesting to witness.
When we were just implementing GOAP, it was very interesting to watch two hostile unarmed characters that knew were to get weapons and ammo: they first run to the weapons, find that they have no ammo, then run to the ammo, the first one to get there causes the other to panic if he is still far away from weapons and ammo, the panickier gets wounded and falls, the other approaches to finish him (this did not make it into the original game, since all characters received unlimited ammo, and such situations could not take place).
It was very interesting to watch a fight of several dogs and one stalker — it was breathtaking to see this sight, as he flees the dogs, switching covers. Sometimes he died quickly, sometimes managed to take down 4-5 dogs, and sometimes all 6.
Screenshot 7: Soldiers using the environment to take cover and return fire.
AC: How about disappointments? Was there anything in particular about the system or its development that you would have done differently?
In simulation: I would very much like to play a game in which characters would live their own lives, each would have his own goal in the game, each would have human-like (or some specific for monsters) needs that the character would have to satisfy. Now, instead of creation of an algorithm for choice of current needs and their satisfaction, a simpler model has been used, which offloaded this work to the smart terrains, responsible for change of tasks by characters, able to assign tasks like “sleeping”, which, of course, is not the same thing.
In visuals: much can be done to improve fights, teamwork, efficiency of combat and efficiency of characters’ actions. I really want to switch from imitation of team actions, to real team AI, even if it means only a few actions.
In intellect: adaptation and teaching characters the player’s game style. The emotional part would also be very interesting.
Miscellaneous: I would really like to teach characters to adequately react to the surrounding world: walk around dynamic obstacles, each other, use the terrain (path and smart objects) in various ways, be able to drive vehicles, fly the helicopter, etc. There are many things they cannot do for various reasons, but in the future iterations of our game we will try to gradually add the missing elements.
AC: What about the lessons learned? If you had thirty seconds to give advice to other game developers out there, what would it be?
Do not reinvent the wheel. Use the Internet to find solutions to your problems.
Have a clear idea of the game you are making, of which features it will have and which it will not, use prototyping to avoid implementing features that do not make it into the release.
Debug characters with comfortable tools: each component should have its debug draw/mode/screen. Draw paths (all the iterations, all the smooth stages and so on), draw visibility checks to find out why character doesn’t see, draw covers information and so on. To debug characters behavior we created their debug screen with all the data from all the layers, so we can easily pick the character and find out what is wrong with him. Pause and time factor are invaluable for the animation/movement/orientation debug.
Let programmers do programmer work and designers design. Designer is a bad programmer, programmer is a bad designer. This could become a problem when using scripts. Let people do things in which they are strong. Instead of advancing designers in programming, create WYSIWYP editor with many options to tune.
Be aware of all the new developments in your area, read Internet resources, like AiGameDev.com :)
Implement something new in your game. Maybe it is only one thing (since several can be too much for a single project), but necessarily new. We see an excellent implementation of decision trees in Black & White, Jeff Orkin has created an exceptional implementation of a GOAP planner in F.E.A.R., we have tried to make a kind of approximated A-Life in a shooter, maybe someone will make something new tomorrow — this will benefit the players, who will get diverse games, and developers themselves, who will set an example of a good method or approach.
Screenshot 8: Debug screen for S.T.A.L.K.E.R. See this forum thread for the original.
AC: Can you tell us about the S.T.A.L.K.E.R. prequel you are working on? Where would you like to take the A-Life technology?
DI: Information from our site:
“The story of S.T.A.L.K.E.R.: Clear Sky brings the players one year prior to the events of the original S.T.A.L.K.E.R. game in 2011.
A group of stalkers has for the first time reached the very heart of the Zone – Chernobyl Nuclear Power Plant, and brings about a cataclysm on the brink of a catastrophe. An immense blowout of anomalous energy changes the Zone. There are no more reliable and relatively safe roads. The entire levels vanish in the outbursts of anomalies. Stalkers and even expeditions die or end up sealed on the lost territories. New areas, which remained unknown since the time of the Zone emergence, appear on the Zone map. The Zone continues to shake with blowouts. The Zone is unstable. The anomalous activity is at its maximum.
Changes of the Zone map known to stalkers shake the fragile balance of forces in the Zone. Among the groupings, there flare up hostilities for the new territories, artefact fields and spheres of influence. There are no more old enemies or friends – now everyone is for himself. The Factions War has started between the groupings.
The protagonist is a mercenary who appeared at the edge of the opposition between stalker factions, Strelok and even the Zone itself. The main character will have to play the key role in the events, which led to creation of the Zone up to the point from which the original S.T.A.L.K.E.R. game begins.”
We changed the role of factions in simulations. i.e it used to be some smart terrain, one of a hundred, that generated quests with the precondition that they could only be taken by members of certain factions, but now the faction itself is a game entity, it has its own goals within the simulation, fights other factions, while the player can assist this and immediately see the result of his actions.
Also, we made several changes to the character’s combat behavior. Now they fight more efficiently and became more believable.
Video 9: Official Trailer for S.T.A.L.K.E.R. — Clear Sky
AC: Many thanks for your time Dmitriy, and best of luck with the upcoming project!