Military Analysis: Influence Maps

An influence map (IM) is a data structure that allows us to perform queries useful to tactical analysis. Once built, an IM can tell the AI system about the balance of power, frontlines, flanks, and so on with very simple queries. The data structure is dynamic in nature, so it responds well to changes in the conditions. Entities can be added, others suppressed due to dying, and some others might move, and the IM will still be valid. All that needs to be done is to recompute the structure every few seconds to ensure the analysis is based on current conditions.

An IM is a 2D array of numeric values. Integers, floats, and so on can all be used. The map is very similar to a field in physics. The values held at each 2D position represent the influence of a certain variable. As a very simple example, imagine two armies. Each soldier on a side will have a value of –1, whereas soldiers on the opposite side will have a value of 1. Then, cells in the array holding one soldier will have the soldier's value, whereas the remaining cells will simply be interpolated, so there is a smooth gradation in neighboring cells. IMs are thus rather easy to build and can provide useful information to the tactician if analyzed well. The trick is that once abstract information has been mapped to a 2D array, obtaining information is a matter of image analysis, which is a well-known, deeply researched science.

For example, analyzing the map and searching for zero-valued points will give us the exact location of the frontline between the two armies, the point at which both armies are equidistant. Searching the point on the map that is a local maxima will give us unit locations; and selecting between these, the point whose neighbors are more distant (in value) to the central point will give us the more isolated enemy unit, which is more suitable for targeting.

Once the basics of IMs have been explained, we will explore implementation details for the data structure as well as a collection of IM analysis routines.

Data Structure

IMs are usually just 2D arrays (see Figure 8.7 for an example) with size depending on the size of the scenario. Choosing the right size is essential: Bigger maps take longer to compute, whereas smaller maps can lose some detail. In some circumstances, hierarchical maps can be used in a way similar to mip-maps; each map being half the size of its ancestor.

The cell value can be any numeric value or a list of numeric values. IMs are not limited to mapping a single value. One of their main uses is analyzing several parameters in parallel, so all of them can then be used to create a plan. For example, here is the declaration of an IM holding the balance of power and information relative to the speed of the units as a 2D map:

typedef struct
   {
   float speed;
   float value;
   } cell;

class influencemap
   {
   cell **data;
   int sizex,sizez;
   };

The structure is rather simple. Only the dynamic nature of the 2D array can be a problem for less advanced programmers. Then, a routine to update the structure is needed. In a simple scenario, the routine would be something like this:

for (ix=0;ix<sizex;ix++)
   for (iz=0;iz<sizez;iz++)
      for each primitive
         compute the influence of the primitive on the cell (ix,iz)

This is a three-times nested loop, which is not very good in terms of efficiency.

Some Useful Tests

This section provides a listing of useful tests for IMs. These tests provide the 2D analysis routine and the "tactical meaning" of the analysis for the AI engine.

• Balance of Power. Using the balance of power test, we compute the summation of the whole IM. If the value is greater than zero, the side represented by positive values is winning. If the value is smaller, the other side wins. This test should be applied to an IM where each cell holds the value of each unit. This value can be as simple as the life level plus the damage value, or some more complex computation.

• Frontline Location. In an IM map, such as the one previously mentioned, locate the zeros. If you want the frontline as a strict distance metric from opposite units, consider only locations with +1 and –1 and forget each unit's life level. If you use the life level, a strong unit displaces the frontline toward the enemy.

• Breakability of Enemy Forces. Use an IM as the one previously mentioned. Then, detect the two largest (or smallest) values on the enemy side of the field. Trace a line between those two points and compare the values along the line with the values at both tips. If the line's values differ by more than a given threshold, the enemy is basically divided, so you can charge the weakest spot to divide and conquer.

• Weakest Enemy. The weakest enemy is the minimum (or maximum) value on the enemy field that is surrounded by smaller values. If the enemy is assigned negative values, we must look for a point on the map that is minimal regarding its neighbors, but which itself is the least negative minimum. This implies a unit of least value.

• Detecting Charges. To detect whether the enemy is charging toward us, we store the map at regular intervals (say, every second). Then, a progressive drop in value in a point near our units (assuming the enemy is negatively valued) means that enemies are approaching. The faster the drop, the faster they move. Similarly, the opposite implies if they are retreating.

• Safe Routes. To detect whether a moving unit will enter an enemy zone, we must make sure each and every cell the unit visits has the same sign as the unit. This means the unit will be closer to its own army than to any enemy.

  Many more tests can be implemented using simple math on the IM. All that's needed is some imagination of how to express tactically relevant tests in terms of simple additions and so on.