Reactive Techniques in Game Development
Just like the behaviors, reactive—or reflexive—techniques have many advantages. In fact, reactive AI techniques have been at the core of most games since the start of game development. As explained, these techniques are often enhanced to provide non-determinism, but this can often be simplified into a deterministic mapping.
Advantages in Standard Game AI
The major advantage of reactive techniques is that they are fully deterministic. Because the exact output is known given any input pattern, the underlying code and data structures can be optimized to shreds. The debugging process is also trivial. If something goes wrong, the exact reason can be pinpointed.
The time complexity for determining the output is generally constant. There is no thinking or deliberation; the answer is a reflex, available almost immediately. This makes reactive techniques ideally suited to games.
Success stories of such approaches are very common, and not only in computer games. Historically, these are the most widely used techniques since the dawn of game AI:
Scripts are small programs (mostly reactive) that compute a result given some parameters. Generally, only part of the programming language's flexibility is used to simplify the task.
Rule-based systems are a collection of "if...then" statements that are used to manipulate variables. These are more restrictive than scripts, but have other advantages.
Finite-state machines can be understood as rules defined for a limited number of situations, describing what to do next in each case.
These standard techniques have proven extremely successful. Scripts essentially involve using plain programming to solve a problem (see Chapter 25, "Scripting Tactical Decisions"), so they are often a good choice. Rule-based systems (covered in Part II) and finite-state machines (discussed in Part VI) can be achieved with scripting, but there are many advantages in handling them differently.
Advantages for Animats
The reactive approach also has benefits for animats, improving learning and dealing with embodiment extremely well.
Embodiment
With embodiment, most of the information perceived by the animat is from the surroundings, which needs to be interpreted to produce intelligence. Reactive behaviors are particularly well-suited to interpreting this local information about the world (as animals have evolved to do).
Also, it's possible to make the reactive behaviors more competent by providing the animat with more information about the environment. Thanks to their well-developed senses, humans perform very well with no advanced knowledge of their environment. Instead of using better AI, the environment can provide higher-level information—matching human levels of perception. Essentially, we make the environment smarter, not the animats.
Learning
Most learning techniques are based on learning reactive mappings. So if we actually want to harness the power of learning, problems need to be expressed as reactive.
Additionally, it's often very convenient to teach the AI using the supervised approach: "In this situation, execute this action." Reactive behaviors are the best suited to modeling this.
Ref : By Alex J. Champandard
AI Development Process
AI Development Process
Developing AI is often an informal process. Even starting out with the best of intentions and ending up with the perfect system, the methodology will often be left to improvisation, especially in the experimental stages. In fact, most developers will have their own favorite approach. Also keep in mind that different methodologies will be suited to different problems.
In a somewhat brittle attempt to formalize what is essentially a dark art, I developed the flow chart shown in Figure 2.1. This flow chart describes the creation of one unique behavior. Jumping back and forth between different stages is unavoidable, so only the most important feedback connections are drawn.
Figure 2.1. An interpretation of the dark art that is the AI development process.
Hopefully, Figure 2.1 makes the process seem less arbitrary! At the least, this method is the foundation for the rest of this book. We'll have ample opportunities to explore particular stages in later chapters, but a quick overview is necessary now.
Outline
The process begins with two informal stages that get the development started:
The analysis phase describes how the existing design and software (platform) affects a general task, notably looking into possible restrictions and assumptions.
The understanding phase provides a precise definition of the problem and high-level criteria used for testing.
Then, there are two more formal phases:
The specification phase defines the interfaces between the AI and the engine. This is a general "scaffolding" that is used to implement the solution.
The research phase investigates existing AI techniques and expresses the theory in a way that's ready to be implemented.
All this leads into a couple of programming stages:
The development phase actually implements the theory as a convenient AI module.
The application phase takes the definition of the problem and the scaffolding, using the module to solve the problem.
This is where the main testing loop begins:
The experimentation phase informally assesses a working prototype by putting it through arbitrary tests that proved problematic in previous prototypes.
The testing phase is a thorough series of evaluations used only on those prototype candidates that have a chance to become a valid solution.
Finally, there is a final postproduction phase:
The optimization phase attempts to make the actual implementation lean and mean.
These phases should not be considered as fixed because developing NPC AI is a complex and unpredictable process. Think of this methodology as agile—it should be adapted as necessary.
Iterations
These stages share many interdependencies, which is unavoidable because of the complexity of the task itself (just as with software development). It is possible to take precautions to minimize the size of the iterations by designing flexible interface specifications that don't need changing during the application phase.
The final product of this process is a single behavior. In most cases, however, multiple behaviors are required! So you need to repeat this process for each behavior. There is an iteration at the outer level, too, aiming to combine these behaviors. This methodology is in spirit of nouvelle AI, which is directly applicable to game development.
Luckily, it's possible to reduce the number of outer iterations by using a clever AI architecture design, which is discussed in the next chapter.
Ref : By Alex J. Champandard
Developing AI is often an informal process. Even starting out with the best of intentions and ending up with the perfect system, the methodology will often be left to improvisation, especially in the experimental stages. In fact, most developers will have their own favorite approach. Also keep in mind that different methodologies will be suited to different problems.
In a somewhat brittle attempt to formalize what is essentially a dark art, I developed the flow chart shown in Figure 2.1. This flow chart describes the creation of one unique behavior. Jumping back and forth between different stages is unavoidable, so only the most important feedback connections are drawn.
Figure 2.1. An interpretation of the dark art that is the AI development process.
Hopefully, Figure 2.1 makes the process seem less arbitrary! At the least, this method is the foundation for the rest of this book. We'll have ample opportunities to explore particular stages in later chapters, but a quick overview is necessary now.
Outline
The process begins with two informal stages that get the development started:
The analysis phase describes how the existing design and software (platform) affects a general task, notably looking into possible restrictions and assumptions.
The understanding phase provides a precise definition of the problem and high-level criteria used for testing.
Then, there are two more formal phases:
The specification phase defines the interfaces between the AI and the engine. This is a general "scaffolding" that is used to implement the solution.
The research phase investigates existing AI techniques and expresses the theory in a way that's ready to be implemented.
All this leads into a couple of programming stages:
The development phase actually implements the theory as a convenient AI module.
The application phase takes the definition of the problem and the scaffolding, using the module to solve the problem.
This is where the main testing loop begins:
The experimentation phase informally assesses a working prototype by putting it through arbitrary tests that proved problematic in previous prototypes.
The testing phase is a thorough series of evaluations used only on those prototype candidates that have a chance to become a valid solution.
Finally, there is a final postproduction phase:
The optimization phase attempts to make the actual implementation lean and mean.
These phases should not be considered as fixed because developing NPC AI is a complex and unpredictable process. Think of this methodology as agile—it should be adapted as necessary.
Iterations
These stages share many interdependencies, which is unavoidable because of the complexity of the task itself (just as with software development). It is possible to take precautions to minimize the size of the iterations by designing flexible interface specifications that don't need changing during the application phase.
The final product of this process is a single behavior. In most cases, however, multiple behaviors are required! So you need to repeat this process for each behavior. There is an iteration at the outer level, too, aiming to combine these behaviors. This methodology is in spirit of nouvelle AI, which is directly applicable to game development.
Luckily, it's possible to reduce the number of outer iterations by using a clever AI architecture design, which is discussed in the next chapter.
Ref : By Alex J. Champandard
Required Background
Required Background
Before discussing the process of creating such animats in games, it seems appropriate to list what skills are required to develop AI. This book assumes the reader has a few years of programming experience, but creating AI is an interdisciplinary process. The AI part of the software sits at the crossroads between the game engine and the AI data; the AI engineer also mediates with the other programmers and designers.
Programming
An important skill needed by an AI developer is programming knowledge. AI can get relatively complex in places, but a reasonable knowledge in programming can help significantly. In fact, most programmers would be able to produce rudimentary NPCs without much AI knowledge. That said, programming is rarely the bottleneck of an AI developer.
Note
In this book, the theory behind the algorithms is described in pseudo-code for the sake of simplicity. As such, it's possible to implement them in almost any language. Because the code available on the web site is C++, most of the programming idioms focus on that language.
Computer Science
Most programming skills are accompanied with elementary knowledge of computer science. Being comfortable with data structures (for example, lists, trees, and graphs) and basic algorithms is a tremendous help for creating AI, too. Don't worry, however; the necessary principles are covered by the book.
Mathematics
Math is essential improving as an AI programmer. Just like 3D programmers need knowledge of geometry to push the application programming interface (API) to its limits, mathematical understanding enables AI programmers to integrate cutting-edge theory from academia, and to optimize the theoretical aspects of each algorithm. It is possible to avoid the math by relying on pseudo-code and example implementations, but a more permanent solution requires that you not shy away from theory. This book gives ample opportunities for dedicated readers to understand the theory and make a step toward academic papers.
Software Engineering
Designing an intelligent system that can control a creature in a complex 3D world is no easy task. Applying common design patterns to the problem certainly helps simplify the system. This book explains the design patterns commonly used in AI and how they can be adapted to different problems.
Game Engine Architecture
Preliminary steps need to be climbed before the actual AI development itself can start. This generally involves preparing the engine architecture so that it can support AI. In most cases—especially when human players are already supported—this job is straightforward.
As a good framework is in place, it's actually possible to code AI without knowing too much about the underlying game. Chapter 4, "FEAR: A Platform for Experimentation," presents the framework used as the basis of this book, which is extremely useful from an educational or experimental point of view.
In a professional environment, groups of developers work together to build the game architecture. Experienced developers (those who know best?) can thereby assist the integration of the AI in design and implementation. AI developers can rely on other programmers to assist them when necessary.
Ref : By Alex J. Champandard
Before discussing the process of creating such animats in games, it seems appropriate to list what skills are required to develop AI. This book assumes the reader has a few years of programming experience, but creating AI is an interdisciplinary process. The AI part of the software sits at the crossroads between the game engine and the AI data; the AI engineer also mediates with the other programmers and designers.
Programming
An important skill needed by an AI developer is programming knowledge. AI can get relatively complex in places, but a reasonable knowledge in programming can help significantly. In fact, most programmers would be able to produce rudimentary NPCs without much AI knowledge. That said, programming is rarely the bottleneck of an AI developer.
Note
In this book, the theory behind the algorithms is described in pseudo-code for the sake of simplicity. As such, it's possible to implement them in almost any language. Because the code available on the web site is C++, most of the programming idioms focus on that language.
Computer Science
Most programming skills are accompanied with elementary knowledge of computer science. Being comfortable with data structures (for example, lists, trees, and graphs) and basic algorithms is a tremendous help for creating AI, too. Don't worry, however; the necessary principles are covered by the book.
Mathematics
Math is essential improving as an AI programmer. Just like 3D programmers need knowledge of geometry to push the application programming interface (API) to its limits, mathematical understanding enables AI programmers to integrate cutting-edge theory from academia, and to optimize the theoretical aspects of each algorithm. It is possible to avoid the math by relying on pseudo-code and example implementations, but a more permanent solution requires that you not shy away from theory. This book gives ample opportunities for dedicated readers to understand the theory and make a step toward academic papers.
Software Engineering
Designing an intelligent system that can control a creature in a complex 3D world is no easy task. Applying common design patterns to the problem certainly helps simplify the system. This book explains the design patterns commonly used in AI and how they can be adapted to different problems.
Game Engine Architecture
Preliminary steps need to be climbed before the actual AI development itself can start. This generally involves preparing the engine architecture so that it can support AI. In most cases—especially when human players are already supported—this job is straightforward.
As a good framework is in place, it's actually possible to code AI without knowing too much about the underlying game. Chapter 4, "FEAR: A Platform for Experimentation," presents the framework used as the basis of this book, which is extremely useful from an educational or experimental point of view.
In a professional environment, groups of developers work together to build the game architecture. Experienced developers (those who know best?) can thereby assist the integration of the AI in design and implementation. AI developers can rely on other programmers to assist them when necessary.
Ref : By Alex J. Champandard
A Modern Approach
A Modern Approach
Traditionally, AI is viewed as a code fragment that manipulates data. These small programs are generally known as agents. These agents are like software systems; they have layers. One central processor acquires information, processes it, deliberates a bit more, and executes some actions. Acting on behalf of the user, agents solve narrow problems with a human quality.
This view is problematic for building large and intelligent systems; the theory scales up poorly, and does not transfer from lab examples to other domains. Nouvelle AI rejects such focused AI, instead believing that true intelligence is about performance in the real world.
The 1980s witnessed a revolution based in robotics that eventually shook most of AI. The ideas, initially from Rodney Brooks (1986 and 1991), proposed using a different model for intelligence, allowing working systems to be built with more suitable methodologies [Brooks86, Brooks91].
This leads to studying embodied systems situated in realistic environments (such as robots or game characters). To solve the problems that occur in practice, new approaches to AI are needed (such as the behavior-based approach).
Brooks advocates that no central processor has to deliberate every move; instead, the system is distributed into behaviors that react instantly to their environment. Using this reactive approach, full systems are built up incrementally, by testing each set of components.
This revolution has continued since, notably influencing a group of researchers to focus on the simulation of adaptive behavior (SAB). The first conference was organized back in 1990 by the International Society for Adaptive Behavior [ISAB02].
"Every two years, the Animals to Animats Conference brings together researchers from ethology, psychology, ecology, artificial intelligence, artificial life, robotics, engineering, and related fields to further understanding of the behaviors and underlying mechanisms that allow natural and synthetic agents (animats) to adapt and survive in uncertain environments."
Animats are essentially synthetic creatures that live within a virtual environment. Because they are embodied, they interact with the world using only their body—making them fully autonomous. Animats can also adapt to their environment by using a variety of learning algorithms. But are these approaches suitable to games?
Animats in Games
Many game players, and even developers, would consider animats the "proper" way of dealing with AI NPCs. Wouldn't it be impressive to have each bot in the game as an accurately simulated creature? As far as game AI techniques are concerned, this nouvelle game AI approach is the opposite of standard techniques.
Are Animats Applicable to Games?
The major goal of game developers is believability; the accuracy of the simulation itself is not a concern. Still, animats have much to offer to computer games. By simulating the creatures accurately, fewer aspects of the behaviors need to be "faked." Because the AI is genuine, it can handle situations unforeseen by designers.
Already, similar (diluted) ideas are starting to leave their mark on the industry. Recent trends in game AI lean toward embodiment, notably in the simulation of sensory systems (Thief), the addition of noise to some actions (Quake 3), and even perceptual honesty (Black & White).
By extrapolating this progression, the result is fully embodied animats. This will certainly happen within a few years, but whether this is three or ten years away is anyone's guess. In the mean time, preliminary research in synthetic creatures shows that properties of animats, such as embodiment, actually lead to more genuine behaviors, which in turn improves believability [Isla02, Blumberg01].
As far as software engineering is concerned, the animat approach has much to offer from a design point of view. Embodiment is an elegant way of modeling the role of the AI in the game engine. The formal definitions of interfaces between the body and the brain is good practice (notably separating the AI from the logic and simulation). As for developing AI behaviors, animat and behavior-based research has revealed many ways of dealing with experimentation, such as incrementally building the AI system.
How Do We Create Animats Effectively?
How can such radical ideas be applied within game engines? Is it even feasible given time and computational constraints? As a matter of fact, it's more than feasible; different aspects of animats have already been demonstrated in popular games. This is the crucial observation; it's possible to integrate properties of animats into the standard AI design, which enables us to compromise between typical game AI approaches and the animat approach.
To date, no genuine animats have been shipped in commercial implementations, but this isn't too far in the future. Some animat prototypes have closely matched the skill level of standard game bots. In some cases, animat prototypes prove to be more reliable and realistic than game bots.
Instead of games using standard agents, animats can in fact be more efficient in many respects. The interaction of an animat with its environment is formalized so it can be optimized in the most appropriate format (for example, passing messages, function calls, shared variables). Learning techniques can minimize the processing power used to perform a particular behavior.
A Healthy Compromise
The animat approach has many benefits, regardless of policies on learning or embodiment. These advantages include improvements in the design and in the development pipeline. Naturally, genuine undiluted animats have the potential to be extremely successful within games, and the rest of this book investigates this noble goal. However, far from being on an idealistic crusade, this discussion attempts to identify places where the animat approach isn't appropriate in games, while trying to extract its advantages.
The remainder of this chapter investigates further these issues by tackling the two major characteristics of animats separately (embodiment and learning), looking into their potential benefits and pitfalls.
Embodiment
Embodiment is a different way of dealing with in-game creatures. Typically, NPCs are just agents: "smart" programs that manipulate data, like chatbots or web spiders. Such entities are purely virtual, whereas embodied agents live in a simulated world and have a synthetic body. Regardless of whether they are 2D sprites or complex 3D models, these bodies cannot do some things. Indeed, the bodies are influenced by the physical rules of the world.
Definition
An embodied agent is a living creature subject to the constraints of its environment.
Because the bodies of animats are physically constrained, the actions of their brains are limited. In general, the possible actions that can be executed by the body—and hence the AI—are restricted to the subset of actions consistent with the laws of the simulation. These actions often turn out to be physically plausible. However, embodiment generally does not limit what the AI can achieve; it just restricts how it is done.
Some characters in games represent human players who get to control the bodies. Many other characters are synthetic, similarly controlled by the computer. The AI itself can be understood as the brain, and the body offers the means for interaction with the game's physics and logic.
Consider a classical example: a standard agent can change its position itself to reach any point in space. An animat—with embodiment—needs to move itself relatively to the current position, having to actually avoid obstacles. It will not even have the capability to update its position directly. Nowadays, many games do this, effectively enforcing the simplest form of embodiment.
Actually simulating the body enables developers to add biologically plausible errors to the interaction with the environment. Errors might be present when information is perceived from the environment and in the actions. For example, animats could have difficulty perceiving the type of characters in the distance. There could even be parametric noise in the turning action, so aiming is not perfect (as with humans). Including such biologically plausible details allows the NPC to behave more realistically.
Motivation
Increasingly, agents with full access to the game data are becoming inconvenient. Having no restrictions on the reading and writing of data often results in internal chaos within the design of the engine. Because there is no formalized interface, the queries for information are left to the client (AI). Developers are actually starting to impose restrictions on these queries, notably limiting the subset of information available to the AI, such as preventing bots from seeing through walls.
For large games (such as massively multiplayer online games), it's essential to develop such hooks for the AI in the game engine. Using formal interfaces is essential because doing so allows the server to be distributed so that agents can reside on different machines if necessary. The AI can thereby be fully separated from the game logic and from the simulation of the world (physics).
So it seems formal interfaces, such as those that the AI Interface Standards Committee is attempting to define [AIISC03] will become increasingly important. Whether these can be standardized is another issue, but embodiment provides useful guidelines for drafting custom interfaces as the exchange of information between the body and the brain. Sensory data flows from the body to the brain, and actions are passed from the brain to the body.
This book anticipates the trend and uses such formal interfaces. In terms of code complexity, major improvements result from separating the acquisition of the data from its interpretation. As for efficiency, using embodiment often allows better optimizations.
Technology
With a formalized interface, the engineer can easily decide on the most appropriate format to communicate data to the AI—and do so mostly transparently using mechanisms such as messages, callbacks, abstract function calls, shared variables, and so on. Because a standard interface exists, its implementation can be particularly optimized for speed using the most appropriate mechanism.
Implementing embodiment efficiently requires a few common techniques to be used. These tricks are the major reasons why formal interfaces can actually outperform an AI implementation with direct access to the data:
Lazy evaluation means that no information is gathered from the world until it is actually requested by the AI. This prevents redundant computation.
Event-driven mechanisms mean that the AI does not need to check regularly for data. When relevant information is available, the AI is notified in an appropriate fashion.
Function inlining still allows the interfaces to be separated, but also optimized out by the compiler (if necessary). This is suitable for small functions, but larger ones benefit from being separate.
Custom optimizations can be used often to speed up the queries. By using spatial partitions of the world, only necessary information can be checked by visibility to gather the information.
Batching refers to collecting many queries or actions so that they can be processed later. Within the engine, the implementation can then decide the best way to deal with them to maintain memory coherence.
Used appropriately, these techniques can significantly reduce the cost of exchanging information between the AI and the engine, and make formal interfaces and embodiment a desirable property.
Learning
Learning is the second property of animats and characteristic of nouvelle game AI. Instead of the designer crafting fixed behaviors, the process is automated by adaptation and optimization techniques.
Definition
Regardless of their actions in the world, living creatures are constantly presented with a flow of sensory data. Biological animals are capable of assimilating this information and using it to adapt their behavior. There are no reasons why animats are not capable of learning; they too are presented with a stream of information from the environment, which they can interpret.
"Learning is the acquisition of new knowledge and abilities."
This definition identifies two kinds of learning: information and behavior. As far as the result is concerned, there is little difference between the two. Indeed, it's often possible to learn knowledge as a behavior; conversely, behaviors can be expressed as knowledge. So intrinsically, both these subtypes of learning can be considered identical in outcome.
In practice, a distinction exists between the two. A part of the animat does not change (phylogenetic), and another part can be adapted (ontogenetic). If the AI system itself is changed at runtime, the adaptation is called direct, and indirect otherwise [Manslow02] (Again, there's a fine line between the two.)
Motivation
Two main scenarios encourage the use of learning in computer games. Different terms are used for each of these cases—optimization and adaptation, respectively—during the development and within the game:
Optimization is about learning a solution to a known puzzle. This is essentially used to simplify the development process (offline) because learning might produce a better answer to the problem in less time than the manual approach.
Adaptation is about learning in unknown situations, and how best to deal with them. This scheme requires the AI to continuously update itself—to deal with different player styles during the game, for example (online).
Fundamentally, these scenarios may be considered as the same problem, too! Indeed, the exact same techniques can be used to perform either. However, both learning schemes are suited to different domains, implying different AI techniques are more appropriate.
The design of the AI can exploit these different types of learning, too. Optimization is often much easier to integrate into the development pipeline as a useful tool for creating believable characters. Adaptation, on the other hand, has repercussions within the game, so it requires a few more precautions in the design.
Technology
Many AI techniques can be used to perform both varieties of learning: neural networks, decision trees, genetic algorithms, reinforcement learning, classifier systems, and so forth. These different solutions are discussed throughout this book. From a conceptual point of view, there are the following four categories of algorithms:
Supervised learning algorithms need to be presented with examples. Apart from assimilating facts or behaviors, they can recognize patterns in the training samples. This allows the learning to generalize, and perform well on unseen examples.
Reinforcement learning evaluates the benefit of each action using a scalar number, instead of providing specific examples. This reward feedback is used to adapt the policy over time.
Evolutionary approaches provides scalar feedback for a sequence of actions, evaluating the fitness of episodes instead of giving a continuous reward.
Unsupervised learning does not rely on direct training. Instead, the designer provides high-level guidance, such as a performance metric.
Naturally, there are often ways to integrate these approaches—or even use one approach to solve the other (for example, self-supervision). These design issues come into consideration after the problem is identified.
Given techniques that learn (either supervised or not), the animats can be taught in different ways:
Teaching involves humans providing a set of examples that help the animat to behave until it's managed to understand what to do.
Imitation allows the animat to copy another player, who is usually human. It can thereby learn its behavior from a third-party experience.
Shaping sets up successive trials from which the animat can learn. After the animat learns to accomplish simple tasks, more complex ones are presented.
Trial and error places the animat in its environment and expects it to learn by trying out all the different approaches on its own.
Each of these methodologies can be followed during the development stage or during the actual game. Although these different approaches are presented in a practical fashion throughout this book, Chapter 35, "Designing Learning AI," specifically covers general technical and design issues.
For Skeptics
The key to successfully integrating learning within games is to use it with consideration. Some things are just not suited to learning. There will always be a need for "static" AI, even if it just acts as the glue between adaptive components.
The benefits of learning are undeniable! Learning enables the developer to save time whenever possible, and to add to the game's appeal by bringing ambitious designs to life.
However, it's debatable whether learning is capable of performing reliably within games. One of the major advantages of learning techniques is that they can be combined with other solutions. This enables the designer to modify or override the results of the learning. This book covers ways to indirectly control the learning, but directly supervise the outcome.
Finally, the fact that techniques can be applied to learning facts or behaviors, online or offline, and with so many different methodologies undoubtedly means that one flavor is suitable for every purpose.
Ref : By Alex J. Champandard
Traditionally, AI is viewed as a code fragment that manipulates data. These small programs are generally known as agents. These agents are like software systems; they have layers. One central processor acquires information, processes it, deliberates a bit more, and executes some actions. Acting on behalf of the user, agents solve narrow problems with a human quality.
This view is problematic for building large and intelligent systems; the theory scales up poorly, and does not transfer from lab examples to other domains. Nouvelle AI rejects such focused AI, instead believing that true intelligence is about performance in the real world.
The 1980s witnessed a revolution based in robotics that eventually shook most of AI. The ideas, initially from Rodney Brooks (1986 and 1991), proposed using a different model for intelligence, allowing working systems to be built with more suitable methodologies [Brooks86, Brooks91].
This leads to studying embodied systems situated in realistic environments (such as robots or game characters). To solve the problems that occur in practice, new approaches to AI are needed (such as the behavior-based approach).
Brooks advocates that no central processor has to deliberate every move; instead, the system is distributed into behaviors that react instantly to their environment. Using this reactive approach, full systems are built up incrementally, by testing each set of components.
This revolution has continued since, notably influencing a group of researchers to focus on the simulation of adaptive behavior (SAB). The first conference was organized back in 1990 by the International Society for Adaptive Behavior [ISAB02].
"Every two years, the Animals to Animats Conference brings together researchers from ethology, psychology, ecology, artificial intelligence, artificial life, robotics, engineering, and related fields to further understanding of the behaviors and underlying mechanisms that allow natural and synthetic agents (animats) to adapt and survive in uncertain environments."
Animats are essentially synthetic creatures that live within a virtual environment. Because they are embodied, they interact with the world using only their body—making them fully autonomous. Animats can also adapt to their environment by using a variety of learning algorithms. But are these approaches suitable to games?
Animats in Games
Many game players, and even developers, would consider animats the "proper" way of dealing with AI NPCs. Wouldn't it be impressive to have each bot in the game as an accurately simulated creature? As far as game AI techniques are concerned, this nouvelle game AI approach is the opposite of standard techniques.
Are Animats Applicable to Games?
The major goal of game developers is believability; the accuracy of the simulation itself is not a concern. Still, animats have much to offer to computer games. By simulating the creatures accurately, fewer aspects of the behaviors need to be "faked." Because the AI is genuine, it can handle situations unforeseen by designers.
Already, similar (diluted) ideas are starting to leave their mark on the industry. Recent trends in game AI lean toward embodiment, notably in the simulation of sensory systems (Thief), the addition of noise to some actions (Quake 3), and even perceptual honesty (Black & White).
By extrapolating this progression, the result is fully embodied animats. This will certainly happen within a few years, but whether this is three or ten years away is anyone's guess. In the mean time, preliminary research in synthetic creatures shows that properties of animats, such as embodiment, actually lead to more genuine behaviors, which in turn improves believability [Isla02, Blumberg01].
As far as software engineering is concerned, the animat approach has much to offer from a design point of view. Embodiment is an elegant way of modeling the role of the AI in the game engine. The formal definitions of interfaces between the body and the brain is good practice (notably separating the AI from the logic and simulation). As for developing AI behaviors, animat and behavior-based research has revealed many ways of dealing with experimentation, such as incrementally building the AI system.
How Do We Create Animats Effectively?
How can such radical ideas be applied within game engines? Is it even feasible given time and computational constraints? As a matter of fact, it's more than feasible; different aspects of animats have already been demonstrated in popular games. This is the crucial observation; it's possible to integrate properties of animats into the standard AI design, which enables us to compromise between typical game AI approaches and the animat approach.
To date, no genuine animats have been shipped in commercial implementations, but this isn't too far in the future. Some animat prototypes have closely matched the skill level of standard game bots. In some cases, animat prototypes prove to be more reliable and realistic than game bots.
Instead of games using standard agents, animats can in fact be more efficient in many respects. The interaction of an animat with its environment is formalized so it can be optimized in the most appropriate format (for example, passing messages, function calls, shared variables). Learning techniques can minimize the processing power used to perform a particular behavior.
A Healthy Compromise
The animat approach has many benefits, regardless of policies on learning or embodiment. These advantages include improvements in the design and in the development pipeline. Naturally, genuine undiluted animats have the potential to be extremely successful within games, and the rest of this book investigates this noble goal. However, far from being on an idealistic crusade, this discussion attempts to identify places where the animat approach isn't appropriate in games, while trying to extract its advantages.
The remainder of this chapter investigates further these issues by tackling the two major characteristics of animats separately (embodiment and learning), looking into their potential benefits and pitfalls.
Embodiment
Embodiment is a different way of dealing with in-game creatures. Typically, NPCs are just agents: "smart" programs that manipulate data, like chatbots or web spiders. Such entities are purely virtual, whereas embodied agents live in a simulated world and have a synthetic body. Regardless of whether they are 2D sprites or complex 3D models, these bodies cannot do some things. Indeed, the bodies are influenced by the physical rules of the world.
Definition
An embodied agent is a living creature subject to the constraints of its environment.
Because the bodies of animats are physically constrained, the actions of their brains are limited. In general, the possible actions that can be executed by the body—and hence the AI—are restricted to the subset of actions consistent with the laws of the simulation. These actions often turn out to be physically plausible. However, embodiment generally does not limit what the AI can achieve; it just restricts how it is done.
Some characters in games represent human players who get to control the bodies. Many other characters are synthetic, similarly controlled by the computer. The AI itself can be understood as the brain, and the body offers the means for interaction with the game's physics and logic.
Consider a classical example: a standard agent can change its position itself to reach any point in space. An animat—with embodiment—needs to move itself relatively to the current position, having to actually avoid obstacles. It will not even have the capability to update its position directly. Nowadays, many games do this, effectively enforcing the simplest form of embodiment.
Actually simulating the body enables developers to add biologically plausible errors to the interaction with the environment. Errors might be present when information is perceived from the environment and in the actions. For example, animats could have difficulty perceiving the type of characters in the distance. There could even be parametric noise in the turning action, so aiming is not perfect (as with humans). Including such biologically plausible details allows the NPC to behave more realistically.
Motivation
Increasingly, agents with full access to the game data are becoming inconvenient. Having no restrictions on the reading and writing of data often results in internal chaos within the design of the engine. Because there is no formalized interface, the queries for information are left to the client (AI). Developers are actually starting to impose restrictions on these queries, notably limiting the subset of information available to the AI, such as preventing bots from seeing through walls.
For large games (such as massively multiplayer online games), it's essential to develop such hooks for the AI in the game engine. Using formal interfaces is essential because doing so allows the server to be distributed so that agents can reside on different machines if necessary. The AI can thereby be fully separated from the game logic and from the simulation of the world (physics).
So it seems formal interfaces, such as those that the AI Interface Standards Committee is attempting to define [AIISC03] will become increasingly important. Whether these can be standardized is another issue, but embodiment provides useful guidelines for drafting custom interfaces as the exchange of information between the body and the brain. Sensory data flows from the body to the brain, and actions are passed from the brain to the body.
This book anticipates the trend and uses such formal interfaces. In terms of code complexity, major improvements result from separating the acquisition of the data from its interpretation. As for efficiency, using embodiment often allows better optimizations.
Technology
With a formalized interface, the engineer can easily decide on the most appropriate format to communicate data to the AI—and do so mostly transparently using mechanisms such as messages, callbacks, abstract function calls, shared variables, and so on. Because a standard interface exists, its implementation can be particularly optimized for speed using the most appropriate mechanism.
Implementing embodiment efficiently requires a few common techniques to be used. These tricks are the major reasons why formal interfaces can actually outperform an AI implementation with direct access to the data:
Lazy evaluation means that no information is gathered from the world until it is actually requested by the AI. This prevents redundant computation.
Event-driven mechanisms mean that the AI does not need to check regularly for data. When relevant information is available, the AI is notified in an appropriate fashion.
Function inlining still allows the interfaces to be separated, but also optimized out by the compiler (if necessary). This is suitable for small functions, but larger ones benefit from being separate.
Custom optimizations can be used often to speed up the queries. By using spatial partitions of the world, only necessary information can be checked by visibility to gather the information.
Batching refers to collecting many queries or actions so that they can be processed later. Within the engine, the implementation can then decide the best way to deal with them to maintain memory coherence.
Used appropriately, these techniques can significantly reduce the cost of exchanging information between the AI and the engine, and make formal interfaces and embodiment a desirable property.
Learning
Learning is the second property of animats and characteristic of nouvelle game AI. Instead of the designer crafting fixed behaviors, the process is automated by adaptation and optimization techniques.
Definition
Regardless of their actions in the world, living creatures are constantly presented with a flow of sensory data. Biological animals are capable of assimilating this information and using it to adapt their behavior. There are no reasons why animats are not capable of learning; they too are presented with a stream of information from the environment, which they can interpret.
"Learning is the acquisition of new knowledge and abilities."
This definition identifies two kinds of learning: information and behavior. As far as the result is concerned, there is little difference between the two. Indeed, it's often possible to learn knowledge as a behavior; conversely, behaviors can be expressed as knowledge. So intrinsically, both these subtypes of learning can be considered identical in outcome.
In practice, a distinction exists between the two. A part of the animat does not change (phylogenetic), and another part can be adapted (ontogenetic). If the AI system itself is changed at runtime, the adaptation is called direct, and indirect otherwise [Manslow02] (Again, there's a fine line between the two.)
Motivation
Two main scenarios encourage the use of learning in computer games. Different terms are used for each of these cases—optimization and adaptation, respectively—during the development and within the game:
Optimization is about learning a solution to a known puzzle. This is essentially used to simplify the development process (offline) because learning might produce a better answer to the problem in less time than the manual approach.
Adaptation is about learning in unknown situations, and how best to deal with them. This scheme requires the AI to continuously update itself—to deal with different player styles during the game, for example (online).
Fundamentally, these scenarios may be considered as the same problem, too! Indeed, the exact same techniques can be used to perform either. However, both learning schemes are suited to different domains, implying different AI techniques are more appropriate.
The design of the AI can exploit these different types of learning, too. Optimization is often much easier to integrate into the development pipeline as a useful tool for creating believable characters. Adaptation, on the other hand, has repercussions within the game, so it requires a few more precautions in the design.
Technology
Many AI techniques can be used to perform both varieties of learning: neural networks, decision trees, genetic algorithms, reinforcement learning, classifier systems, and so forth. These different solutions are discussed throughout this book. From a conceptual point of view, there are the following four categories of algorithms:
Supervised learning algorithms need to be presented with examples. Apart from assimilating facts or behaviors, they can recognize patterns in the training samples. This allows the learning to generalize, and perform well on unseen examples.
Reinforcement learning evaluates the benefit of each action using a scalar number, instead of providing specific examples. This reward feedback is used to adapt the policy over time.
Evolutionary approaches provides scalar feedback for a sequence of actions, evaluating the fitness of episodes instead of giving a continuous reward.
Unsupervised learning does not rely on direct training. Instead, the designer provides high-level guidance, such as a performance metric.
Naturally, there are often ways to integrate these approaches—or even use one approach to solve the other (for example, self-supervision). These design issues come into consideration after the problem is identified.
Given techniques that learn (either supervised or not), the animats can be taught in different ways:
Teaching involves humans providing a set of examples that help the animat to behave until it's managed to understand what to do.
Imitation allows the animat to copy another player, who is usually human. It can thereby learn its behavior from a third-party experience.
Shaping sets up successive trials from which the animat can learn. After the animat learns to accomplish simple tasks, more complex ones are presented.
Trial and error places the animat in its environment and expects it to learn by trying out all the different approaches on its own.
Each of these methodologies can be followed during the development stage or during the actual game. Although these different approaches are presented in a practical fashion throughout this book, Chapter 35, "Designing Learning AI," specifically covers general technical and design issues.
For Skeptics
The key to successfully integrating learning within games is to use it with consideration. Some things are just not suited to learning. There will always be a need for "static" AI, even if it just acts as the glue between adaptive components.
The benefits of learning are undeniable! Learning enables the developer to save time whenever possible, and to add to the game's appeal by bringing ambitious designs to life.
However, it's debatable whether learning is capable of performing reliably within games. One of the major advantages of learning techniques is that they can be combined with other solutions. This enables the designer to modify or override the results of the learning. This book covers ways to indirectly control the learning, but directly supervise the outcome.
Finally, the fact that techniques can be applied to learning facts or behaviors, online or offline, and with so many different methodologies undoubtedly means that one flavor is suitable for every purpose.
Ref : By Alex J. Champandard
Traditional Approach
Traditional Approach
How do developers tackle this problem generally? Creating game AI is certainly not the most formal of processes in software development; it requires many ad-hoc modifications and hours of empirical evaluation. The games industry is somewhat immature as a whole, but game AI is probably the furthest behind.
Until recently, AI code took barely a few hundred lines of code, being hacked together with a couple of months to spare before the deadline. Since the turn of the millennium, AI has suddenly been propelled into the limelight and it is expected to scale up—often becoming a centerpiece of the design.
A few different aspects about the typical approach to creating game AI merit analysis, notably the integration with the engine, the design of the system, and the guidelines used throughout the development.
Integration and Design
Historically, in-game agents were simulated as part of the game logic. The 2D positions of the characters were updated at each iteration, like in Pac-Man. Since then, things have moved on slowly. Thankfully, the AI code now is generally separated from the logic. However, the agent is generally given direct access to the game data, free to extract whatever it needs. The separation is only a programming trick to simplify the codebase.
As for software design, AI subsystems are often created as separate libraries (to handle movement, for example). Naturally, these are created in different ways, depending on the development style. The most common approach in game development is the hands-on approach, where you incrementally build up the interface and required functionality from scratch. This might not sound formal—at least in terms of classical software design—but modern agile approaches acknowledge the benefits of such rapid iterations. This is certainly well suited to AI because a large amount of experimentation is required.
Beyond these modular components, the code can become somewhat unmanageable because the unexpected complexity of the task or the deadline pressures sometimes catch programmers. For example, the AI for Return to Castle Wolfenstein uses C function pointers to simulate a finite-state machine, an approach that quickly becomes almost impossible to understand by anyone but the original developer.
Guidelines
Because of the limited resources available, the only important guideline for AI developers is to cut corners wherever possible yet still achieve efficiency. The responsibility of the AI itself is to control characters in a realistic fashion. How this is achieved under the hood is irrelevant. Many applicable techniques could be borrowed from AI research, but few are used in practice. All the common techniques used in classical game AI (for instance, search and scripting) arguably have their roots in computer science instead.
Often, the combination of these two requirements (efficiency and realism) leads to simple AI solutions, such as scripts. This approach is entirely justifiable because it solves the problem in a way that designers can easily control.
Discussion
This typical approach to game AI has been finely tuned over the years and seems to have reached satisfactory levels. AI in games is competent enough to not stand out. The standard design and integration has immediate benefits (such as simplicity), but can prove inconvenient in many ways.
First, letting the AI access information in the game directly is both dangerous and unnecessary. Second, manually developing all the behaviors for the AI can be tedious using plain programming and causes an exponential growth in time required.
There is undoubtedly room for improvement over these standard approaches, as shown by recent progress in game AI. There is an underlying trend in these innovations.
Ref : By Alex J. Champandard
How do developers tackle this problem generally? Creating game AI is certainly not the most formal of processes in software development; it requires many ad-hoc modifications and hours of empirical evaluation. The games industry is somewhat immature as a whole, but game AI is probably the furthest behind.
Until recently, AI code took barely a few hundred lines of code, being hacked together with a couple of months to spare before the deadline. Since the turn of the millennium, AI has suddenly been propelled into the limelight and it is expected to scale up—often becoming a centerpiece of the design.
A few different aspects about the typical approach to creating game AI merit analysis, notably the integration with the engine, the design of the system, and the guidelines used throughout the development.
Integration and Design
Historically, in-game agents were simulated as part of the game logic. The 2D positions of the characters were updated at each iteration, like in Pac-Man. Since then, things have moved on slowly. Thankfully, the AI code now is generally separated from the logic. However, the agent is generally given direct access to the game data, free to extract whatever it needs. The separation is only a programming trick to simplify the codebase.
As for software design, AI subsystems are often created as separate libraries (to handle movement, for example). Naturally, these are created in different ways, depending on the development style. The most common approach in game development is the hands-on approach, where you incrementally build up the interface and required functionality from scratch. This might not sound formal—at least in terms of classical software design—but modern agile approaches acknowledge the benefits of such rapid iterations. This is certainly well suited to AI because a large amount of experimentation is required.
Beyond these modular components, the code can become somewhat unmanageable because the unexpected complexity of the task or the deadline pressures sometimes catch programmers. For example, the AI for Return to Castle Wolfenstein uses C function pointers to simulate a finite-state machine, an approach that quickly becomes almost impossible to understand by anyone but the original developer.
Guidelines
Because of the limited resources available, the only important guideline for AI developers is to cut corners wherever possible yet still achieve efficiency. The responsibility of the AI itself is to control characters in a realistic fashion. How this is achieved under the hood is irrelevant. Many applicable techniques could be borrowed from AI research, but few are used in practice. All the common techniques used in classical game AI (for instance, search and scripting) arguably have their roots in computer science instead.
Often, the combination of these two requirements (efficiency and realism) leads to simple AI solutions, such as scripts. This approach is entirely justifiable because it solves the problem in a way that designers can easily control.
Discussion
This typical approach to game AI has been finely tuned over the years and seems to have reached satisfactory levels. AI in games is competent enough to not stand out. The standard design and integration has immediate benefits (such as simplicity), but can prove inconvenient in many ways.
First, letting the AI access information in the game directly is both dangerous and unnecessary. Second, manually developing all the behaviors for the AI can be tedious using plain programming and causes an exponential growth in time required.
There is undoubtedly room for improvement over these standard approaches, as shown by recent progress in game AI. There is an underlying trend in these innovations.
Ref : By Alex J. Champandard
Subscribe to:
Posts (Atom)