Designing Artificial Intelligence for Games (part 3)

By Donald Kehoe

Tactical and Strategic AI


When last we left out heroes (intelligent agents, or IAs), they had just been given the ability to see what is around them and to figure out where they are going. In this article, I show you how to give your agents higher orders of intelligence. The agents can already deal with the immediate situation they find themselves in: Now, you are working toward artificial intelligence (AI) that deals with broader goals and the bigger picture of what’s going on.


Tactical AI


The role of tactical AI is to coordinate the efforts of groups of IAs in the game. The implementation of this type of AI is important for many styles of game: Squads in a tactical first-person shooter (FPS) game as well as groups of units in a real-time strategy game all use tactical methods. Groups are more effective, because they can support each other and act a single unit, all sharing information and the load of acquiring the information.

The concept of tactical AI is built around group dynamics, which requires the game to keep track of different groups of entities. Each group needs to be updated separately from the individuals. You can handle this updating with a dedicated update module that keeps track of different groups, their goals, and their composition. Because this method requires development of a separate system for the engine, however, I prefer to use the group captain method.

A single unit of the group can be assigned the role of group captain. Every other member of the group keeps a link to this captain, and they get their behavioral cues from checking the orders of the group captain. The group captain handles all the tactical AI calculations for the whole group.

Group Movement: Path Finding


Entity movement is an area of implementation that can be improved with group dynamics. Movement can be made more efficient as well as more life-like when IAs function as a unit.

Path finding can be a time-consuming process, even when sped up with pre-computed path maps and multi-threaded AI. The stress put on the path-finding system can be greatly lessened with group dynamics.

When a group of units is given a goal to move (either through the player or AI instructions), the unit closest to the goal is set as the group captain, and all other members are assigned to follow that captain. When the group captain is updated, it queries the path system. With path in hand, the group captain sets out to reach the goal. All the other units in the group merely have to follow their group captain wherever he (or she or it) goes.

Group Movement: Formations


With your group moving as a unit, you have managed to reduce the load that your pathing system has to bear. Unfortunately, the way the units end up moving is more like a mob than an organized unit. Enter formations. With formations, the group can move in a nice pattern such as a phalanx (in a historical simulation) or a triangle (how the minions work in Codemaster’s Overlord*, shown in Figure 1).


Figure 1. In Overlord, the minions (the red guys) work as a team and move in formation at the command of the player (the guy in armor).

The setup for formations is really quite easy, and it extends the concept of the group captain. In a formation, every unit has a specific role that must be played. When formed, each member of the group will be assigned a spot in the formation, just like a single unit is assigned the role of group captain. It is the goal of every unit in the group to keep its position a relative distance away from other members of the formation.

Take the example of the minions in Overlord. They move in the pyramid formation. In Figure 2, the group captain “C” only has to follow the path. Unit 1 will follow a set pace behind and a little to the left of its target unit, “C.” Unit 2 stays aware of and keeps in step with unit 1, just off to the side. Unit 3 does exactly what unit 1 does but follows unit 1 instead of the captain. This pattern is followed for every unit in the group.


Figure 2. A setup for a triangle movement formation

Group Tactics


There is more to tactics than merely marching in formation. There is also supporting and fighting as a team. The captain assumes the burden of planning and coordinating the team. After all, the lives of the captain’s unit are the responsibility of the commanding officer.

The implementation of group tactics can be governed by the systems discussed in previous articles, such as rules-based systems or finite state machines (FSMs). Here are some examples of typical group behaviors (see Figure 3):

  • Healing support. In games with healing support units (medics or clerics), it is important for the medics to keep aware of the health levels of the units in their group. This can be compounded with the intentions of the group captain. Medics can be ordered to stay near units that are likely to come under fire.
  • Scouting. In games like Enemy Territory Quake Wars*, there are units that help provide for the rest of the team. The spy classes in the game can deploy radar to provide information on the movements of enemy units. Even without radar, any enemies spotted by one unit will be added to the group radar of the whole team. When approaching areas with no coverage, it’s possible to send someone into an unknown area to scout for enemy positions. This is made easier for any spy classes in disguise.
  • Covering fire. When an area is well defended, supporting units can provide covering fire and converge on the enemy defenses, engaging the defenses (hopefully) long enough for the goal to be reached.
  • Sacrifice. When under heavy attack and loss of units is inevitable, some units in the group may be considered expendable. The units in the group that are mission critical (like the engineer, in some situations) need to be protected, both by prioritizing enemy units that target your engineer and by getting in the line of fire to protect the engineer with the unit's life.



 
Figure 3. In Enemy Territory Quake Wars by Id Software* and Splash Damage, Ltd.*, there are five classes with distinct roles to play in the group dynamic.

Another level of analysis that may help the group is a self-analysis of each member of the group’s capabilities. It is important for the captain to know which situations the group can be effective in, when the group will have an advantage, and when the group should retreat.

For example, in a strategy game like Blizzard's Starcraft*, there are flying units and ground units. Not every ground unit can hit a flying unit. It is important for any group to know if it has this capability. If the group does not have any units that can hit a flying unit, then when a flying unit is encountered, it would be best to run away. Even if the unit does not have that many units that can hit flying units, as long as there are support units that can heal or improve the units that can hit the flying units, it would probably be best to stay and fight.

Diversity of entity abilities and the numbers of units that have them can be used to weigh the combat effectiveness of the group in different situations. Groups that take this into account will be far more effective than groups that do not.


Strategic AI


So far, I’ve covered how entities and groups of entities can handle themselves in tough situations. Now, I look at the AI concerned with the big picture. Strategic AI is the higher-order AI that commands the whole army and deals with the guiding strategies.

The strategic AI itself is most common in real-time strategy (RTS) games but has been making its way more and more into tactical FPS games. The player-controlled commander can be its own system or set up as an empty entity-one that does not have a place or graphic in the world but is updated and thinks.

The commanders are going to be guided by hierarchical rules systems and FSMs, which govern elements such as resource gathering, researching up the tech tree, building the army, and so on. For the most part, this basic upkeep of the game elements does not require much actual thought. What does require intelligence is the interactions with the other players.
Governing these interactions (or warfare) is where the real “meat and potatoes” lie with strategic AI. The commander needs to explore the game map to find the player, identify key points of interest such as choke points, build defenses, and analyze other player's defenses. How one would do this is not obvious but can be made easier with decision maps.

Decision Maps

Decision maps are two-dimensional arrays approximating the game map. Each cell in the array corresponds to a region in the game and is filled with important information about the region. These maps are used to help your strategic AI make meaningful decisions about the game as a whole.

Resource Maps

Resource maps contain information about where the resources are laid out in a strategy game. Knowing where on the maps resources are concentrated can influence many decisions that a commander will make. Where to deploy expansions or satellite bases (resources near the commander’s base), where the enemy is likely to deploy its expansions (resources near their base) and places likely to be contested (resources in the middle).

Getting a count of potential available resources also influences which units are supported and how to deploy the army. If resources are scarce, each unit must be used more carefully, because replacements are less likely. If resources are plentiful, it opens up the strategies of massing cheap units or building powerful units.

Objective Maps

These maps are filled with information about the goals of the commander-for example, locations of enemy bases, the positions of map objectives (blow something up, protect something, hack something, etc.), and key units of the commander’s army (main base, hero units, etc). Tracking this information guides the use of the commander's army. Points that need to be protected should be surrounded with defensive structures, and a contingent of units should always be near these points. Attack objectives will be sought out and defenses tested. Analysis of defenses around targets must be undertaken to figure out the optimal way to overcome them. This leads to the backbone of military games-conflict maps.

Conflict Maps

Conflict maps (see Figure 4) are used and updated far more often than the previous maps. Conflict maps keep track of where battle occurs throughout the level. Whenever one of the commander’s units engages in a fight with an enemy, the unit will update the conflict map with key information:

  • Type of conflict. Units, buildings, or both
  • Capabilities of units. Hits ground or air or both
  • Numbers. How many where encountered
  • Strength. How much damage potential is in this area

This information can be analyzed to determine the following:

  • When the enemy attacks, the AI will be able to determine whether the defenses deployed are effective, whether the defenses are engaged or ignored, and whether conflict arises close to defensive objectives. This can lead to the AI changing the layout and composition of its defenses.
  • When attacking the enemy (preferably with scouts), weaknesses in their defense can quickly be identified. If paths exist to the goal that can avoid conflict or keep it reduced to a minimum, you have an optimal strategy to deploy the troops.
  • Composition of the enemy’s military capabilities dictates the proper countermeasures. Because most strategy games attempt to keep some level of balance among the units, the computer will be able to determine the number and type of units needed to break through defenses at different points.


 
Figure 4. An example of how a conflict map might look laid over a view of the terrain. The darker the red, the more conflicts encountered.

Building and Applying Maps

I mentioned earlier that these maps are built by the units of the commander’s army. It will be part of the rules that govern the AI to send scouts out to explore as soon as possible in order to start building the maps. Good AI should periodically make sure that these maps stay up to date. Early in the game, when only a few units are maintaining these maps, updating should be no problem to the game engine. Later in the game, with massive numbers of units all providing information at the same time, it has the potential to affect performance.
Ensuring that the decision maps are maintained quickly is not too hard.  You can do so by putting the decision map system into its own thread.  Indeed, each AI controlled player should have its own thread to handle its own set of decisions maps.  The real performance gain happens if all of the entities are already broken up into multiple threads.  The decision map threads only need to handle the requests from the parallelized entity update messages.


Summary


The most basic form an intelligent system can take is that of a rules-based system. This system stretches the term artificial intelligence, as there is very little actual intelligence involved. A set of preset behaviors is used to determine the behavior of game entities. With a variety of actions, the overall result can be a behavior system that is not obvious.

The IAs of your game world are beginning to take shape. You have built on their basic ability to see and move and are now giving their decisions and behavior more meaning. Your IAs are now able to take a more proactive role in the games instead of just reacting to the situation at hand. You’re able to create more compelling and challenging foils for your players; in turn, better players will fork over dough for the sequel.

Concluding the series, the next article will take a more focused look at applying multithreading to artificial intelligence.  Even though, you have some clever and efficient algorithms for running your AI, they will inevitably grow increasingly complex as they are applied to more and more entities.  If you want your system to keep up with increased demand, you need to take advantage of multiple core processors.  The next article will show that it’s not hard to adapt your code to take advantage of the benefits that multithreading brings.



Author Bio


Donald “DJ” Kehoe: As an instructor for New Jersey Institute of Technology's Information Technology Program, DJ developed the specialization in game development and teaches many of the program's courses on Game Architecture, Programming and Level Design, as well as courses that integrate 3D graphics with games. He is currently working on his PhD in Biomedical Engineering where he applies game and virtual reality to enhance the effects of neuromuscular rehabilitation.

For more complete information about compiler optimizations, see our Optimization Notice.