Rule-Based AI

Rule-Based AI

In this chapter we're going to study rule-based AI systems. Rule-based AI systems are probably the most widely used AI systems for both real-world and game AI applications. In their simplest form, rule-based systems consist of a set of if-then style rules that are used to make inferences or action decisions. Technically, we've already looked at one form of rule-based system on finite state machines. There we used rules to handle state transitions. We also looked at another type of rule-based system in the previous chapter on fuzzy logic.

In this chapter, we're going to look specifically at rule-based systems that commonly are used in so-called expert systems. Examples of real-world, rule-based expert systems include medical diagnosis, fraud protection, and engineering fault analysis. One advantage of rule-based systems is that they mimic the way people tend to think and reason given a set of known facts and their knowledge about the particular problem domain. Another advantage of this sort of rule-based system is that it is fairly easy to program and manage because the knowledge encoded in the rules is modular and rules can be coded in any order. This gives some flexibility both when coding the system and modifying the system at a later time. These advantages hopefully will become clearer to you as we move through the material in this chapter. Before we get into the details, though, let's discuss a couple of game examples that can use rule-based systems.

Imagine you're writing a real-time strategy simulation game involving the typical technology tree, whereby players must train peasants, build facilities, and harvest resources. An illustrative technology tree is shown .

Figure 1. Example technology tree

What we aim to do here is enable the computer opponent to keep track of the player's current state of technology so that the computer opponent can plan and deploy offensive and defensive resources accordingly. Now, you could cheat and give the computer opponent perfect knowledge of the player's state of technology. However, it would be fair and more realistic to have the computer gain knowledge and make inferences on the state of the player's technology in much the same way that the player will have to so that she can assess the computer opponent's state of technology. Both player and computer will have to send out scouts to collect information and then make inferences given the information as it is received. We can achieve this using a fairly simple rule-based system, as you'll see in this chapter.

Let's consider another example. Say you're writing a martial arts fighting game and you want to give the computer the ability to anticipate the player's next strike so that the computer opponent can make the appropriate countermove, such as a counter strike, a dodge, or a parry. The trick here is to somehow keep track of the player's strike patterns—combinations of kicks and punches—and to learn which strike most likely will follow an observed set of previous strikes. For example, if during the fight the player throws a punch, punch combination, what will the player most likely throw next: a punch, a low kick, or a high kick? We can use a rule-based system to achieve such anticipation. We'll come back to this example in much more detail later in this chapter.

Game Situation

Game Situation

When making a strategic decision in a deathmatch game, players consider many aspects of the game world. The concepts behind both factors and features are introduced in greater depth in , "Fighting Conditions," which covers decision making for weapon selection.

Influential Factors

The most important factors in the decision are those depicting combat situations and the progression of the fight. Strategic decisions have an even broader scope than weapon selection, so additional factors of the game are considered.

Player State

Decisions are very subjective by nature. Aspects of the player's status play an important role in influencing the outcome. For example, both health and armor levels may affect tactical decisions, as do weapons and ammunition available. To a lesser extent, other items in the inventory may become factors of the decision.

Enemy Status

In deathmatch games, strategies revolve around the other player(s), too. Visible properties of the enemies, such as their position or orientation, contribute the decision because they affect the player's situation in the game. As well as the relationship between players and their situation in space, the observed weapons and estimated health can become decision factors.

Environment Layout

The terrain affects the movement of all players, as well as the projectiles. The layout of the world can serve as cover and secure an escape, but can also trap the players and make them vulnerable. The disposition of the items is space also affects the best tactic. As such, high-level decisions should take the role of the environment into account.

Features of the Decision

Although factors are aspects of the game that could potentially be taken into account, features are used as inputs to the problem. Features are relevant bits of information required to make the best decision. Different properties of the environment, situation, and progression of the combat are used as features in the decision.

A set of features can be considered as an array of floating-point values corresponding to the strength of the feature: F = [f₁,f₂,K,f_n]. This strength value is easily understood when constrained to the range [0..1]—interpreted as either a probability or plausibility (fuzzy degree of truth). The decision process can take into account either interpretation as long as all the values are consistent.

Fuzzy Logic

Fuzzy Logic

In 1965 Lotfi Zadeh, a professor at the University of California Berkeley, wrote his original paper laying out fuzzy set theory. We find no better way of explaining what fuzzy logic is than by quoting the father of fuzzy logic himself. In a 1994 interview of Zadeh conducted by Jack Woehr of Dr. Dobbs Journal, Woehr paraphrases Zadeh when he says "fuzzy logic is a means of presenting problems to computers in a way akin to the way humans solve them." Zadeh later goes on to say that "the essence of fuzzy logic is that everything is a matter of degree." We'll now elaborate on these two fundamental principles of fuzzy logic.

What does the statement "problems are presented to computers in a way similar to how humans solve them" really mean? The idea here is that humans very often analyze situations, or solve problems, in a rather imprecise manner. We might not have all the facts, the facts might be uncertain, or perhaps we can only generalize the facts without the benefit of precise data or measurements.

For example, say you're playing a friendly game of basketball with your buddies. When sizing up an opponent on the court to decide whether you or someone else should guard him, you might base your decision on the opponent's height and dexterity. You might decide the opponent is tall and quick, and therefore, you'd be better off guarding someone else. Or perhaps you'd say he is very tall but somewhat slow, so you might do fine against him. You normally wouldn't say to yourself something such as, "He's 6 feet 5.5 inches tall and can run the length of the court in 5.7 seconds."

Fuzzy logic enables you to pose and solve problems using linguistic terms similar to what you might use; in theory you could have the computer, using fuzzy logic, tell you whether to guard a particular opponent given that he is very tall and slow, and so on. Although this is not necessarily a practical application of fuzzy logic, it does illustrate a key point—fuzzy logic enables you to think as you normally do while using very precise tools such as computers.

The second principle, that everything is a matter of degree, can be illustrated using the same basketball opponent example. When you say the opponent is tall versus average or very tall, you don't necessarily have fixed boundaries in mind for such distinctions or categories. You can pretty much judge that the guy is tall or very tall without having to say to yourself that if he is more than 7 feet, he's very tall, whereas if he is less than 7 feet, he's tall. What about if he is 6 feet 11.5 inches tall? Certainly you'd still consider that to be very tall, though not to the same degree as if he were 7 feet 4 inches. The border defining your view of tall versus very tall is rather gray and has some overlap.

Traditional Boolean logic forces us to define a point above which we'd consider the guy very tall and below which we'd consider the guy just tall. We'd be forced to say he is either very tall or not very tall. You can circumvent this true or false/on or off characteristic of traditional Boolean logic using fuzzy logic. Fuzzy logic allows gray areas, or degrees, of being very tall, for example.

In fact, you can think of everything in terms of fuzzy logic as being true, but to varying degrees. If we say that something is true to degree 1 in fuzzy logic, it is absolutely true. A truth to degree 0 is an absolute false. So, in fuzzy logic we can have something that is either absolutely true, or absolutely false, or anything in between—something with a degree between 0 and 1. We'll look at the mechanisms that enable us to quantify degrees of truth a little later.

Another aspect of the ability to have varying degrees of truth in fuzzy logic is that in control applications, for example, responses to fuzzy input are smooth. Using traditional Boolean logic forces us to switch response states to some given input in an abrupt manner. To alleviate very abrupt state transitions, we'd have to discretize the input into a larger number of sufficiently small ranges. We can avoid these problems using fuzzy logic because the response will vary smoothly given the degree of truth, or strength, of the input condition.

Let's consider an example. A standard home central air conditioner is equipped with a thermostat, which the homeowner sets to a specific temperature. Given the thermostat's design, it will turn on when the temperature rises higher than the thermostat setting and cut off when the temperature reaches or falls lower than the thermostat setting. Where we're from in Southern Louisiana, our air conditioner units constantly are switching on and off as the temperature rises and falls due to the warming of the summer sun and subsequent cooling by the air conditioner. Such switching is hard on the air conditioner and often results in significant wear and tear on the unit.

One can envision in this scenario a fuzzy thermostat that modulates the cooling fan so as to keep the temperature about ideal. As the temperature rises the fan speeds up, and as the temperature drops the fan slows down, all the while maintaining some equilibrium temperature right around our prescribed ideal. This would be done without the unit having to switch on and off constantly. Indeed, such systems do exist, and they represent one of the early applications of fuzzy control. Other applications that have benefited from fuzzy control include train and subway control and robot control, to name a few.

Fuzzy logic applications are not limited to control systems. You can use fuzzy logic for decision-making applications as well. One typical example includes stock portfolio analysis or management, whereby one can use fuzzy logic to make buy or sell decisions. Pretty much any problem that involves decision making based on subjective, imprecise, or vague information is a candidate for fuzzy logic.

Traditional logic practitioners argue that you also can solve these problems using traditional rules-based approaches and logic. That might be true; however, fuzzy logic affords us the use of intuitive linguistic terms such as near, far, very far, and so on, when setting up the problem, developing rules, and assessing output. This usually makes the system more readable and easier to understand and maintain. Further, Timothy Masters, in his book Practical Neural Network Recipes in C++, (Morgan Kauffman) reports that fuzzy-rules systems generally require 50% to 80% fewer rules than traditional rules systems to accomplish identical tasks. These benefits make fuzzy logic well worth taking a look at for game AI that is typically replete with if-then style rules and Boolean logic. With this motivation, let's consider a few illustrative examples of how we can use fuzzy

Defining the Search Area

Defining the Search Area

The first step in pathfinding is to define the search area. We need some way to represent the game world in a manner that allows the search algorithm to search for and find the best path. Ultimately, the game world needs to be represented by points that both the game characters and objects can occupy. It is the pathfinding algorithm's job to find the best path between any two points, avoiding any obstacles. How the actual game world will be represented depends on the type of game. In some cases, the game world might have to be simplified. For example, a game which uses a continuous environment would probably be made up of a very large number of points that the game characters would be able to occupy. The A* algorithm would not be practical for this type of search space. It simply would be too large. However, it might work if the search area could be simplified. This would involve placing nodes throughout the game world. We then would be able to build paths between nodes, but not necessarily between every possible point in the world. This is illustrated in Figure 1.

Figure 1. Simplifying the search area

The tanks in Figure 1 are free to occupy any point in their coordinate system, but for the purposes of pathfinding, the game world is simplified by placing nodes throughout the game environment. These nodes do not correspond directly to every possible tank position. That would require too many nodes. We need to reduce the nodes to a manageable number, which is what we mean when we say we need to simplify the search area.

Of course, we need to maintain a list of the connections between the nodes. The search algorithm needs to know how the nodes connect. Once it knows how they link together, the A* algorithm can calculate a path from any node to any other node. The more nodes placed in the world, the slower the pathfinding process. If pathfinding is taking too many CPU cycles, one alternative is to simplify the search area by using fewer nodes.

On the other hand, a game that uses a tiled world would be a good candidate for the A* algorithm, assuming, of course, that the world isn't unreasonably large. It would be a good candidate because essentially the world already would be divided into nodes. Each tile would be a node in the search area. This is illustrated in Figure 2.

Figure 2. Tiled search area

Tiled environments, such as the one shown in Figure 2, are well suited to the A* algorithm. Each tile serves as a node in the search area. You don't need to maintain a list of links between the nodes because they are already adjacent in the game world. If necessary, you also can simplify tiled environments. You can place a single node to cover multiple tiles. In the case of very large tiled environments, you can set up the pathfinding algorithm to search only a subset of the world. Think of it as a smaller square within a larger square. If a path cannot be found within the confines of the smaller square, you can assume that no reasonable path exists.

Bresenham algorithm

Bresenham algorithm

if (deltaCol >deltaRow)

    {

     fraction = deltaRow *2-deltaCol;

     while (nextCol != endCol)

      {

       if (fraction >=0)

        {

         nextRow =nextRow +stepRow;

         fraction =fraction -deltaCol;

        }

       nextCol=nextCol+stepCol;

       fraction=fraction +deltaRow;

       pathRow[currentStep]=nextRow;

       pathCol[currentStep]=nextCol;

       currentStep++;

      }

    }

   else

    {

     fraction =deltaCol *2-deltaRow;

     while (nextRow !=endRow)

      {

       if (fraction >=0)

        {

         nextCol=nextCol+stepCol;

         fraction=fraction -deltaRow;

        }

       nextRow =nextRow +stepRow;

       fraction=fraction +deltaCol;

       pathRow[currentStep]=nextRow;

       pathCol[currentStep]=nextCol;

       currentStep++;

      }

     }

    }

The initial if conditional uses the values in deltaCol and deltaRow to determine which axis is the longest. The first block of code after the if statement will be executed if the column axis is the longest. The else part will be executed if the row axis is the longest. The algorithm will then traverse the longest axis, calculating each point of the line along the way. Figure 1 shows an example of the path the troll would follow using the Bresenham line-of-sight algorithm. In this case, the row axis is the longest, so the else part of the main if conditional would be executed.

Figure 1 . Bresenham tile-based chase

Figure 1 shows the troll's path, but of course this function doesn't actually draw the path. Instead of drawing the line points, this function stores each row and column coordinate in the pathRow and pathCol arrays. These stored values are then used by an outside function to guide the troll along a path that leads to the player.

Movement in Game Worlds : Testing Conditions

Testing Conditions
Because we are aiming for state-of-the-art NPC intelligence, nothing less than complex 3D worlds will be satisfactory—like those humans deal with. This needs to be an environment frequently used by human players, and not a simplified test bed for the sake of AI development. By keeping the experimentation process up to standard with the realism of actual game worlds, fewer problems will arise due to fundamentally flawed assumptions. Keeping the test "levels" and scenarios diverse will unconsciously prevent these problems. Such guidelines need to be followed throughout the development of the movement.

To be realistic, it should include doors and corridors, stairs and ladders, narrow ledges and dead ends, floors with gaps and irregular terrain, closed rooms and open spaces, jump pads and teleporters.

Now that the environments have been explained and defined, our focus can be set on the actual movement. As discussed, the world has a very important impact on the movement, but it takes certain capabilities from games characters to use it to their advantage.

Movement in Game Worlds : Assumptions

Assumptions
Given knowledge from the game simulation, let's outline our assumptions. There is a physics system that takes care of applying the motor commands to the data structures representing each player. We'll suppose it is done with kinematics, in a physically plausible fashion. A physics system will also resolve any conflicts that happen within the simulation. This is the locomotion, which falls outside of the control of the AI.

We'll also assume that an animation system takes care of the low-level aspects of motion. Specifically, moving individual limbs and blending the appropriate animation cycles is handled transparently from the AI.

For the interface to be of any use to the animat, it's essential for the information returned to be consistent with the physics of the environment. Consequently, we'll assume the backend implementation of these interfaces rely on the movement simulation.

Movement in Game Worlds : Handling Movement

Handling Movement The type of environment has a direct effect on the creatures that inhabit it. In fact, the type of movement is imposed upon the creatures by the environment. Regardless of the dimensionality the environment, movement is handled in a similar fashion in both cases (2D or 3D). Although there are many possible ways of implementing this, a pattern arises in each of these designs: simulation loop, integration, and collision detection. The details classify as engine development rather than AI, but an overview of the principles will come in handy later. The game engine has to take into account movement requests from all the players and creatures in the world. The physics system is in charge of resolving the collisions with the environment as well as with other entities. Each of the data structures representing in-game objects will then be updated accordingly, with new velocities, positions, and orientations. To date, animation systems take care of low-level limb "control" as predefined animation cycles (for example, walk and run) are combined to move the player's entire body. Such animation cycles can be chosen based on the higher-level control of the players. Therefore, characters in the game are not actually walking (active behavior), they are merely animated (passive process). This animation system requires a minimal amount of coordination with the physics system to prevent breaking the illusion with inconsistencies (for instance, walking on the spot when stuck against walls, running in midair). For all intent and purposes, the low-level aspects of movement are abstracted from the player—greatly simplifying the process. This underlying layer can be referred to as a locomotion layer. Computer-controlled characters can also rely on such locomotive capabilities. Indeed, handling the movement for AI and human players together is becoming commonplace in game development now; it's a good way to reduce the amount of code by inheriting AI classes from human-player classes (that is, with the same locomotive functions). In the near future, there are prospects of the AI taking over low-level limb control, done in a fully dynamic fashion. For human players, controls are unlikely to change as they often prove complex enough. Humans will just have to adjust to having the AI control their character's legs in the game! For nonplayer characters (NPCs), the AI could theoretically control the entire body as a whole, dealing with locomotion at the same time as high-level requests. However, keeping the locomotion separate has many advantages (for example, simplicity and little redundancy), so it is advantageous to retain this distinction in the future.

Movement in Game Worlds : Types of Game Worlds

Types of Game Worlds

It's surprising how many games rely on movement as their most fundamental concept. They range from chiefly strategic logic games such as Chess or Diplomacy, or the more entertaining alternatives such as Horses or Downfall. Let's not forget computer games of course; first-person shooters, real-time strategy, or even role-playing games would be extremely dull without motion!

Despite virtual worlds being widespread, they come in many varieties. Notably, there are worlds of different dimensions (for instance, 2D or 3D), with different sizes and precision. Some worlds are based on grids (discrete), and some are free of restrictions (continuous).

Conceptually, there is a big difference between these variations, which translates into the feel and style of the gameplay. Behind the scenes in the engine, distinct data structures and implementation tricks are used in each case, but this discussion focuses on the consequences for the AI.

On Dimensions

Some games can take place in 2D levels like top-down worlds (Warcraft II), or side views with moving platforms and smooth scrolling (Super Mario Brothers). Alternatively, the world itself can be fully 3D, with different floors in buildings (Half Life), or even tunnels (Descent 3).

It's important to note that the dimensions of the game world are independent from the rendering. For example, the original Doom is in fact a 2D world with the floors at different levels. Even recent 3D first-person shooters have a lot in common with Doom. This leads to the assumption that the underlying properties of the environment are very similar. Indeed, much of the technology is applicable in 2D and 3D.

Most academic research projects deal with top-down 2D AI movement algorithms, for example [Seymour01], which provides a nice amalgamation of past research. The same goes for the most of the figures here; they show the problem projected onto the floor. This is primarily because 2D movement is simpler than its 3D counterpart.

As a justification, one often read that "2D generalizes to 3D," so it's fine to focus on the simpler alternative. With an algorithm defined for two dimensions, the same concept is re-applied again to an additional dimension! This is mostly the case, although special care needs to be taken to devise a solution that scales up with respect to the number of dimensions.

For movement in 3D games, this simplification is also acceptable. In realistic environments, gravity plays an important role. All creatures are on the floor most of the time, which almost simplifies the problem to a 2D one. It is not quite 2D because the floor surfaces can superimposed at different heights (for instance, a spiraling staircase); this type of world is often known as 2.5D, halfway between the complexity of two and three dimensions.

In the process of applying, or generalizing, our 2D solution to 3D, watch out for a couple of pitfalls:

• Complex environments often exhibit tricky contraptions (for example, jump pads or lifts), which are quite rare in flat worlds.

• Instead of naively applying an original algorithm, it can be tailored to make the most of the problem at hand.

These factors influence the design the solution.

Discrete Versus Continuous

Another property of game worlds is their precision, in both time and space. There are two different approaches, discrete and continuous events (in space or time), as shown in Figure 5.1. A discrete variable can accept only a finite number of values, whereas a continuous variable theoretically takes infinite values.

Figure 5.1. Two types of game environments observed top-down. On the left, space is continuous, whereas the world on the right is based on a grid (discrete).

Conceptually speaking, there is little difference between a continuous domain and a discrete one. Indeed, when the discretization is too fine to notice, the domain appears continuous. This doesn't apply mathematically, of course, but on modern computers, there are hardware limitations. To simulate continuous media, current software must select an appropriate discrete representation.

Using examples for space and time in game worlds shows how it's not only a game design issue, but also a fundamental element for the AI. (It's an independent AI design decision.)

Space

The game environment can be limited to cells of a grid; it's discrete if there are a finite number of grid coordinates. Continuous environments have unlimited locations because they are not restricted to grids.

To store the coordinates in the world, data types must be chosen. These are usually single precision floating-point numbers, which essentially allocate 32 bits to discretize those dimensions. Although there are benefits to using a double representation (64 bits), single representations are enough to make each object seem like it can take every possible position and orientation in space.

Time

Actions can be discrete in time, taking place at regular intervals—like in turn-based strategy games. Alternatively, actions can be continuous, happening smoothly through time as in fast-pace action games.

Similar floating-point data types can be chosen to represent this dimension. However, this choice is slightly more complicated because the programmer can't "manipulate" time as easily. Conceptually, single processors can only execute one logical process at a time—despite being able to perform multiple atomic operations in parallel. Consequently, it's not possible for each object in the world to be simulated continuously. The closest the computer can get is an approximation; a portion of code determines what happened since the last update (for example, every 0.1 seconds). So despite being very precise, a floating-point number will not be entirely necessary to represent a value in time (see Figure 5.2).

Figure 5.2. On the top, a continuous timeline with events happening at any point in time. On the bottom, the same timeline, but discrete. The time of each event is rounded to the closest mark every two seconds.

Conversions

Fundamentally, because of the limitations of computers, each of these dimensions can be considered as discrete—although it does not appear that way. Regardless, these data types can be converted to one another by simple mapping; this involves scaling, converting to an integer by rounding, and rescaling back. Arbitrary discretizations can thereby be obtained.

In practice, it's possible for the world to have one type of discretization and use a different discretization for the AI. For example, mapping continuous onto discrete domains enables us to exploit similarities in the AI design, and reuse existing AI routines (for instance, standard grid-based A* pathfinding). Of course, we may not necessarily want to perform the conversion for many reasons (for example, compromising behavior quality or sacrificing the complexity of environment). But at least AI engineers have the luxury to decide!

Movement in Game Worlds : The Environment and Space

The Environment and Space

Let's focus on the game world where movement takes place. The environment is planned by the designer, created with modeling tools by the graphics artist, and updated and displayed within the game by the programmer's engine. A wide variety of technologies can be used along this production pipeline, but it is mostly inconsequential from the AI's perspective.

What's important is the information contained implicitly within the world. Most environments are split into two components: structure and detail. After discussing them separately, this section looks at how they combine to define space.

Sum of Its Parts

The information about the environment provided to the players can be conceptually divided into two main components: structure and detail. This is more than just a theory, because most game engines strongly distinguish the two for efficiency reasons. The physics simulation handles the structure, and the detail is for graphics rendering. In the real world, of course, the boundaries between them are much more debatable, so we should consider ourselves lucky to be dealing with computer games!

• The structure is the part of the environment that can physically affect movement. Naturally this includes the floor, walls, doors; chairs, tables, and other furniture; trees, roads, and bridges; and so on. This list is not exhaustive, and should include all the elements in the world that are mostly static—those the players cannot trivially push aside.

• As for the detail, it consists of the "cosmetic" part of the environment: the things game characters cannot collide with (or if so, insignificantly)—books, kitchen utensils, or bits of food; grass, shrubs, and small ledges; among many others.

There is one important omission to notice from the preceding definitions. What happens to living creatures and other mobile entities? Although not necessarily created with the same tools as the rest of the game world, they too are arguably part of the environment. We could argue that game characters have properties of both the structure and the detail. However, some developers (and robotics researchers) believe that they should be treated separately, as an entirely different set. Generally in games, the set of living creatures ends up being forced into one category or the other (for instance, players are detail that's ignored during movement, or players are part of the environment structure that movement takes into account).

Essentially, the problem is about combining these three components of the environment together to create an understanding of space. We want to understand space as best possible to develop high-quality movement. Considering moving creatures as either detail or structure can have a negative effect on the movement, especially when the problem has not been identified beforehand.

Fortunately, we have the luxury of being able to decide how to handle living creatures as we design the AI. In a deathmatch, for example, it's fine to ignore the other animats for movement; they can be blown up with a rocket if they get in the way! In cooperative mode, however, a separate category is needed for nonplayer characters (NPCs) so that they can ask each other to move. Finally, other players can be considered as obstacles in large crowds.

Each of these three interpretations is a way of understanding the environment, but most importantly space—which relates to the NPC AI.

Defining Space

Fundamentally, the game world describes space. As the shape of the environment, the structure plays an important role; as far as the physics engine is concerned, all the movement is defined by the structure. However, both human players and AI characters cannot always match this physical knowledge of space; it will be extremely difficult, if not impossible, for them to understand the environment perfectly.

In some cases, when a simple world is stored in an explicit fashion (for instance, a 2D grid), understanding it can be a manageable task. As the design becomes more complex, many elements combine to define the environment in an intricate fashion (for example, a realistic 3D world). However, no matter how well the environment is defined or how accurate its physical rules are, it is not necessarily as clear to players and NPC.

• Human players have to assimilate the environment based on imperfect visual information. The detail of the environment plays an important part visually.

• AI characters usually get a simplified version of this world before the game starts (offline), in both an imprecise and incomplete fashion (for instance, waypoints as guides). Alternatively, the environment can be perceived and interpreted online (as humans would).

For all intents and purposes, space is an abstract concept that cannot be fully understood. Different techniques will have varying degrees of precision, but all will be flawed. Don't see this as a problem, just accept it and embrace it; perfection is overrated! This lesson was learned in robotics thanks to the wave of nouvelle AI robots.

After space has been figured out, it's possible to determine which parts are free space and which can be considered solid. This implicitly defines all movement: what is possible and what isn't. Only then can intelligent movement be considered.

Ref : By Alex J. Champandard

FEAR: A Platform for Experimentation

Game AI generally takes a lot of work to implement—not directly for the AI techniques, but to integrate custom AI, or even middleware, within the game. This is an unavoidable consequence of current engine design, and can be difficult to deal with when starting out in AI development.

This book provides a real game for testing the AI, and not just a toy environment or command prompt. For this, the open source FEAR project is used, integrated with a commercial first-person shooter game engine. Some other game engines use similar frameworks to assist the AI development (but they're not as flexible). FEAR provides some helpful facilities, including the following:

• World interfaces for the AI to interact with the game engine (physics simulation and logic)

• Modules that implement AI functionality on their own or by depending on other modules

• Flexible architectures that enable engineers to assemble arbitrary components together

• Tools to create animats and their source files using minimal programming

As the combination of these elements and more, FEAR provides an ideal foundation for the examples in this book—and many other prototypes, thanks to its flexibility.

World Interface The exchange of information with the world is an extremely important part of AI. For animats, this takes the form of interfaces between the brain and the body. In terms of information flow, this leads to two different types of interfaces: Sensors provide a way to acquire information from the surrounding environment. Effectors allow the brain to control the body to act upon the world. Although it is possible to separate these two types of interfaces in the implementation, FEAR no longer imposes this. Respecting this convention is unnecessary and leads to overly complex code. Instead, it's more convenient to group world interfaces by functionality: Weapon interface allows query of the state of the weapon, change and reload, and then actually use it. Movement interface allows forward/backward and side steps to be performed, as well as turning actions. Physics interface allows the animat to query its internal state: in water, midair, or colliding with a wall. This approach generally reduces the amount of code required to implement the interfaces. Also, this separation enables you to import different functionality into the AI independently. The implementation of the world interfaces is called the backend (as far as the AI is concerned). FEAR's framework can be plugged in to arbitrary platforms (for instance, game engines) that implement the backend for the interfaces. Currently, the recommended platform supported by FEAR is Quake 2. The engine offers a great variety of game types, enabling programmers to develop animats for deathmatch, single player, or even capture the flag. The low-key graphics leave much computational power to the AI. There is tremendous community support for the game, including custom levels and various tools. The entire source code is available, too, making Quake 2 one of the best choices for pure AI development.

Modules

Modules are essentially implementations of AI techniques. When the modules are instantiated within the architecture, they're called components. For example, there is only one rule-based system implementation (module), but different rule-based behaviors can be used for movement and tactical decisions (components).

Interfaces

The module interfaces are purposefully made high level. Only the core functionality is exposed by the interfaces (for instance, movement requests). This approach emphasizes the purpose of the module, which helps understanding and the design.

Such interfaces have many advantages in terms of modularity—just as in software development in general. Essentially, the implementation can be completely abstracted from the other components, which reduces dependencies.

Many AI techniques have similar capabilities, such as pattern recognition, prediction, function approximation, and so on. This functionality can often be expressed as one concise interface, but implemented in different ways.

Data Loading

Special interfaces are used to store data on disk. These interfaces are also specified formally, so the meta-programming tools generate functions that save and load data from disk. The low-level details of the storage are thereby handled automatically. The programmer is only responsible for postprocessing the data as appropriate after it has been loaded.

Dependencies

Each module may import specific interfaces. Conceptually, this means the module depends on other implementations to provide its own functionality.

At runtime, this translates into nested components. The internal components are called on when their output is needed to produce the final result. For example, nested components could be used to implement a subsumption architecture for navigation, or even a voting system handling combat—as explained in the preceding chapter.

Flexible Architecture

FEAR supports entire architectures, defined as hierarchies of components. A hierarchy is the most generic type of architecture, because both monolithic and flat can be considered a specific subtype.

Each component has access to its children. (This access is called the scope of the component.) FEAR's dynamic C++ framework initializes the components automatically during initialization, so none of the standard code to import interfaces needs to be written manually (as with DirectX).

At the time of writing, all forms of arbitration (independent, suppression, combination, sequence) are supported indirectly; the programmer can implement each as modules in a customized fashion.

Creating an Animat

The process of creating an animat in FEAR is threefold, as described in this section.

Description of the Architecture

Create a file with the description of the architecture. This specifies which components the brain of the animat needs and other recursive dependencies for those components.

Generating the Source Code

To create all the project files, we need to process this architecture definition with the toolset. The resulting animat should compile by default, effectively creating a brain-dead animat!

Adding behaviors to the animat involves adding code to a few files—usually those with "to-do" comments inside them. Other generated files are managed by the toolset (stored in the Generated folder of the project) and should not be edited manually; their content may disappear when the tools are used again.

Preparations for the Game

The compiled files need to be accessible by the game engine. This involves copying the brain dynamic link library (DLL) into the correct directory, along with a descriptive file to tell the framework about the architecture required. All the data files for the animats are stored in their own directory, too.

Installation Note

Each of the animats can be downloaded separately, or in a complete package. The full source is available as well as the compiled demos. It's best to start by running the demos to get a feel for the platform. The instructions for installing the tools and building each animat are detailed on the web site at http://AiGameDev.com/.

Ref : By Alex J. Champandard

Architectures Designing (game) AI

Architectures
Designing (game) AI is about assembling many weak components together. The components provide functionality for each other and communicate together to collectively solve the problem. This set of nested components is known as an architecture.

These architectures are reactive when they are driven by sensory input, and decide on output actions deterministically. Such architectures are very common for systems that need to react in a timely fashion, whether to external requests or stimuli from the environment (for instance, robots and washing machines).

Components
A component can be understood as a black box with a mystery AI technique inside. Alternatively, the component may be built as a subsystem of smaller components. Components interact with others via their interfaces, using inputs and outputs.

Internally, as mentioned previously, there is no theoretically difference between a deliberative component and a reactive component. This correspondence applies for the interfaces, too! Any deliberative planning component can be considered as reactive. All the necessary information is provided via the interfaces in the same fashion; only the underlying technology changes.

This is a tremendous advantage during the design phase, because the underlying implementation can be disregarded. Then, if a reactive technique is not suitable, a deliberative component can be inserted transparently.

Another consequence of the black box paradigm is that you can use other components during implementation. These components are nested inside others. This is the epitome of modularity in AI.

Organization
Naturally, there are many ways to combine components together. This is the purpose of architectures, because they define the relationship between components. Figure 3.4 shows three example architectures with different internal organizations:

Figure 3.4. Three example architectures with different internal organizations. From left to right, monolithic, flat, and hierarchical architectures.


Monolithic architectures include only one component.

Flat architectures have many components in parallel.

Hierarchical models have components nested within others.

As an example of a hierarchical architecture for games, the brain may be built as a collection of behaviors (for instance, hunt, evade, patrol), which are components within the brain. Each behavior in turn may depend on components for moving and shooting. This is a three-level hierarchy.

In general, selecting the organization of an architecture is about problem complexity. Simple problems will manage with monolithic architecture, more sophisticated problems may need flat architectures, whereas hierarchical architectures can handle almost any problem by breaking it down. (Chapter 21, "Knowledge of the Problem," and Chapter 28, "Understanding the Solution," discuss these points further.)

Decomposition
Instead of thinking of an architecture as a combination of components (bottom-up), it can be understood in a top-down fashion: "How can this problem be split up?" This concept of decomposition is central to AI development in general.

There are many types of decompositions. The idea is to split the problem according to certain criteria—whichever proves the most appropriate for solving it! This applies equally well to software design as to the creation of game AI:

Structural decomposition splits the solution according to the function of each component. For example, there may be a component responsible for movement, and another for handling the weapon. These are different functions.

Behavioral decomposition is based on the distinctive activities of the system. These can be understood as different modes such as hunting, fleeing, collecting ammo, or celebrating. Different components would handle these behaviors.

Goal decomposition uses the overall purpose of the system to determine how to split it into components. In game AI, goals depend on the behavior (for instance, finding a weapon). Although goals do not provide clear policies for decomposing the problem, they are always a criteria in the decisions [Koopman95].

Naturally, the decomposition can happen on multiple levels using many different criteria. For example, the initial problem may be decomposed as behaviors, then each behavior may be expanded as different functionality, using different criteria known as a hybrid decomposition, as opposed to using one criteria throughout the architecture (or pure decomposition).

Behavioral decompositions are very appropriate for computer games. The functional decomposition is also used in this book, as we develop common abilities that can be reused by the nonplayer character (NPC) AI.

Arbitration
Given a set of subcomponents, how are they connected together? Specifically, how are all the outputs interpreted to form the output of the component itself? There are four different ways of doing this:

Independent sum essentially connects each component to different outputs so no clashes can occur.

Combination allows the outputs of different components to be blended together to obtain the final result.

Suppression means that certain components get priority over others, so weaker ones are ignored.

Sequential arbitration sees the output of different components alternating over time.

There really is no right or wrong method of arbitration. Each of these methods is equally applicable to computer games.

Examples
There are many different combinations of architectures. Figure 3.5 shows two common examples to illustrate the issue.

Figure 3.5. Two popular reactive architectures. On the left, the subsumption architecture with its horizontal layers. On the right, a voting system that combines the votes of four nested components.


Subsumption
The subsumption architecture is a behavior-based decomposition, using a flat organization with suppression on the outputs [Brooks86].

The system can be seen as a set of horizontal layers. The higher the layer, the greater the priority. Layers can thereby subsume the ones beneath by overriding their output. This architecture is explained further, and applied to deathmatch behaviors in Chapter 45, "Implementing Tactical Intelligence."

Voting System
Voting systems generally use a functional decomposition, with a flat organization using combination to merge the outputs together. Chapter 25 uses a voting system for weapon selection.

The system can be interpreted as a set of distributed components that are all connected to a smaller component responsible for counting votes. The output with the most votes becomes the output for the global output.
Ref : By Alex J. Champandard

Reactive Techniques in Game Development

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

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

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

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