Flanking Total War’s AI: 11 Tricks to Conquer for Your Game

The Total War series revolutionized strategy games by letting the player control thousands of foot soldiers, archers, and cavalry. It featured on my list of Top 10 Most Influential AI Games because of it. The game offers months of replayability: the battles are among the best forms of entertainment on PC.

The Total War games use innovative ideas to build an AI scalable enough to support this kind of gameplay. In this week’s technical review, you’ll learn about the best parts of the artificial intelligence: things to conquer as well as what to avoid.

Battle Behaviors

In terms of AI, Total War innovates mostly with its real-time battles. Whole units respond to their situation realistically, and individual actors also behave in a unique way.

Screenshot 1: Dismounted nights defending a castle in Medieval II Total War.

1) Books & Manuals for Inspiration

For each battle unit to have a realistic tactical behavior, the developers took inspiration from Sun Tzu’s The Art of War, which provides very detailed tactics for units on the battlefield.

Here’s how Michael DePlater, producer of the original Shogun game, describes it [1]:

“[The Art of War] has been of enormous help in the tactical side of the game. It’s the best book ever written in this area, and it’s very practical and structured which helps us to integrate it in a way that makes a real difference to the gameplay.”

This approach works to great effect in Total War because the units are simulated in a very real fashion on the battleground.

2) Rule-based Tactics & Reactions

Sun Tzu’s The Art of War provides very structured rules for attacking and defending, for example:

• If you outnumber the enemy 10:1, surround them.

• If you outnumber the enemy 5:1, attack them directly.

• If you outnumber the enemy 2:1, divide them up.

In the Total War game uses these rules for the implementation of AI’s tactics. It’s not necessary to use a rule-based system to implement this logic; no doubt the developers used a traditional C++ class or possibly a script to achieve the same results.

3) Neural Networks for Individual Behaviors

Michael DePlater mentions in the same interview [1]:

“On this level John, our AI lead, has applied neural network technology and complexity theory to ensure that the behavior of your troops is a lot more flexible and smarter.”

This is certainly a promotional statement, and it’s uncertain what they mean by “neural network”. Presumably this is nothing more than a set of weighted connections (called perceptrons) used to determine a course of action based on the situation of each soldier.

Of course, this is hard to do efficiently, so there are noticeable problems with individuals when you zoom in: soldiers getting stuck in loops, archers shooting other units, etc. But despite rare exceptions, units manage to accomplish the orders they are given.

4) Emergent Behaviors

The major benefit of these interacting rules, both at the individual level and the tactical level, is that patterns emerge:

• Individual archers will flee from incoming cavalry or any other threat.

• Whole armies start routing if shaken or flanked even by a weaker opponent.

This is the foundation of the rock/paper/scissor dynamic that makes the game so much fun on a tactical level. It’s these emergent behaviors that make this kind of gameplay possible.

5) Genetic Algorithms to Improve Strategy

At the turn-based strategy level on the top-down map, different AI techniques are used to balance the game, offer different opportunities for victory, and provide more realism. Again, from the interview:

“On the turn based strategy map we have applied a combination of traditional AI and genetic algorithms to create a set of Daimyo opponents who play according to different temperaments and skills, for example some are warmongers, others are into espionage and subterfuge, others are clever diplomats.”

The key to doing this is to build customizable AI logic (e.g., using scripts), and then running many simulations with different settings. The best settings, using criteria determined by the designers, can then be used in the final game as the behavior of specific opponents.

6) Player Control by Orders

Another interesting feature is that the player never controls the units directly, as orders are only taken as suggestions by the AI. At any time, the emotions of the units, such as the desire to get into cover from archers, or hide from oncoming cavalry may override the behavior. This isn’t unique to Total War, but it’s worth noting for two reasons:

1. It challenges the players to understand the functioning of the units under their command.

2. It provides a working and fun example of indirect control of avatars via the AI

This approach opens the door for many innovations in different games where it’s too complex for the player to control everything, and Total War is a good example of this done on a large scale.

Technology & Implementation

By playing the game, you can get a feel for how the development team managed to get it running efficiently.

Screenshot 2: Archers assaulting a castle in Medieval II Total War.

7) Reactive Movement Behaviors

When dealing with hundreds of actors per military unit, and dozens of unit per army, it’s not possible to have each unit perform detailed pathfinding individually. Instead, it’s important to keep things simple. A big part of that is avoiding unnecessary computation for movement.

In many cases, like moving a unit a small distance, changing its orientation, or moving straight on a landscape, it’s possible to use only reactive behaviors (which require no planning ahead). A combination of seeking behavior for individual actors and convex obstacle avoidance covers the majority of the movement cases in Total War. You’ll notice this is used when your units move through forests, they literally float around trees as they reach them.

8) Group Path-finding and Formations

In the cases where more complex pathfinding is required, a few tricks can help:

1. Calculate paths for groups of actors only, rather than individually.

2. Use an offset to the unit’s path center to create a formation.

3. Add maximum width information to the path if the unit formation does not fit, for example through doors and gates.

4. If the formation does not fit on the path, reduce the size of the formation appropriately — potentially even becoming a queue (near doors).

This trick can be used to reduce computation in groups of smaller sizes too, like in Rockstar’s The Warriors for example where many mobsters follow their leader in formation.

9) Random Bounce off Obstacles

Recent games in the Total War series have complex geometry inside castles, and actors get stuck regularly. A surprisingly easy trick to get them out of trouble is to bounce backwards in a randomized direction off the wall or building that was hit, then resume following the path.

This trick works in most cases the first time, but in other cases the AI can get stuck in a loop of bouncing off an obstacle and getting stuck again. (This is obvious near gates when you have large armies.) To fix this, after a few collisions, the actor should default to following its unit’s path at the center rather than trying to keep formation.

10) Memory Usage

Memory is one of the largest problems of having to deal with thousands of units. There are a few tricks that can help in these cases:

• Even on PC, use a custom memory allocation scheme: avoid dynamic allocations, recycle memory in pools, avoid fragmentation by keeping related data together.

• Think wisely about what data is really unique, and what data is shared among multiple actors. Look into the flyweight pattern to make instances of objects very cheap.

It’s unclear to what extent the Total War games do this for the AI, but there are swapping performance problems on machines even with reasonable amounts of memory (most likely graphics related).

11) Level-of-Detail AI

In Total War, there’s cut-off distance for rendering individual actors. When actors are not drawn, it’s not necessary to work out individually what they are doing. Then, it’s only necessary to simulate what’s going on at the unit level.

This approach can be seen as a level-of-detail strategy with two different levels of the simulation. It has many performance benefits, but you must pay careful attention that the two levels of detail are similar, and that it’s possible to transition between the two (by discarding or generating information procedurally).

References

[1] Lessons on the Art of War
Interview with Michael DePlater
http://pc.ign.com/articles/066/066804p1.html
IGN, 1999

Next week’s review on AiGameDev.com will delve into a game that’s more of a research project with interesting technology from academia.