Geometric AI

A standard problem in computer wargames is figuring the line. The military units of each side line up along the frontline and duke it out, attempting to penetrate the enemy line and hold their own line. The first task for the AI to perform is to figure out where the line is. This is not so easy a task. Consider the map shown in Figure 22.2 of opposing units in two ragged lines:

22.2. Units of opposing sides.

There are difficult judgments to make about this line. For example, should the black line be drawn 1-2-3-5 or should it include unit 4? That is, should unit 4 be treated as a member of the front line or a reserve unit? How far back or forward must unit 4 be to be excluded or included?

Black unit 7 provides us with another quandary. Is it part of the black line, or should it be treated as a unit cut off behind enemy lines? We could draw the black line as 5-6-7-8-9 or 5-6-8-9. Which is better?

One would expect that the line would be built according to the proximity of units. That is, the line is a sequence of units in proximity to each other. This creates problems of its own. For example, white unit 2 is closer to white unit 3 than white unit 5; this would pull the line through 3 and on to 4. Then the line would have to double back on itself to get back to white unit 5. Obviously, proximity alone is an insufficient criterion for building the line.

I tackled these problems with a sequence of algorithms. The first algorithm draws not a line but a polygon. The polygon is constructed as follows:

1. Start with an arbitrarily chosen unit; call it UnitA.

2. Choose the closest unit and draw a line to that unit; call it UnitB (see Figure 22.3).

   22.3. A line to UnitB.

   

3. Now choose the closest available unit to UnitB and draw a line to that unit (see Figure 22.4).

   22.4. A line to the unit closest to UnitB.

   

4. Continue until all units have been chosen; then draw a line back to UnitA (see Figure 22.5).

   22.5. Returning to UnitA.

   

5. While drawing the polygon, keep a running sum of the line lengths; this is equal to the circumference of the polygon (see Figure 22.6).

   22.6. Distance of line lengths to calculate circumference.

   

6. Store that circumference.

7. In like fashion, draw every possible polygon and select the polygon with the smallest circumference. This is the most convex polygon and is the best initial choice for building the line. It may seem excessive to draw every possible polygon, but with only a few dozen units the number of available polygons is within reach and some elementary pruning methods can make the computation reasonable.

8. The next step is to convert a polygon to a line (see Figure 22.7). This is done by anchoring the easternmost and westernmost ends of the polygon to the edges of the map. We sweep along the polygon looking for the easternmost and westernmost units in the polygon and snip the polygon at those units, extending the line to the edges of the map. A few complexities arise if we want to be able to have the line go to other map edges, but these are complexities of detail, not fundamental algorithmic issues.

   22.7. Convert the polygon to a line.

   

9. The next task is to clip out tight bends in the line (see Figure 22.8). This is done by a simple sweep down the line, looking at groups of three points. With each group of points A, B, and C, we calculate the distances AB, BC, and AC. If AB+BC is greater than twice AC, then the bend in the line introduced by unit B is too great and B is removed from the line. This is a very simple test, yet it works quite well in play. Its only weakness is that it does not consider the significance of enemy units. In the sample line presented earlier, black unit 7 would be included in the line regardless of the presence of white units 6 and 7.

   22.8. Clip out bends in the line.

   

Looking Over Your Shoulder

The most difficult algorithm in the project arose from the need to check behind units to make sure that they are not in danger of being cut off. Since the military scenario in Patton Versus Rommel presumes a wide-open battle with fragmented lines for both sides, I could not rely on a simple-minded search for any unit behind the line. To be threatened, a unit had to find an enemy unit in its own rear. This raised many tricky problems. Exactly what constitutes the rear area of a frontline unit?

My solution makes use of the sketch shown in Figure 22.9 (not drawn accurately).

22.9. Calculating the rear area of a unit.

Units A, B, and C are frontline units; we are considering the rear area of unit B. We first calculate Point 1, the point on the line connecting B with C that is as far from B as A is from B. This makes triangle A, B, Point 1 an isosceles triangle. We then calculate the midpoint of the baseline, Point 2. This is easily done by averaging the coordinates of A and Point 1.

Now comes a cute trick: The perpendicular to a line is easily calculated by taking the negative inverse of its slope. This allows us to calculate the perpendicular to the line Point1 Point 2. The significance of this perpendicular is that it points toward the rear of Unit B. Now, we could get very messy here with the problem of getting our perpendicular to pass through Point 2. It would involve the equation for a line with a given slope passing through a given point, and it would be ugly. Fortunately, we don't need the full-blown equation; all we need is a single point, Point 3. For reasons to be seen later, we desire this point to fall on the perpendicular at a distance equal to the distance Point 1 Point 2. Rather than belabor the argument, I shall simply show the code to calculate Point 3:

 DX = X2 - X1; DY = Y2 - Y1; IF ((DX>0) && (DY>0)) OR ((DX<0) && (DY<0)) THEN { DX = -DX; DY = -DY; } X3 = X2 - DY; Y3 = Y2 - DX; 

In this code fragment, I use "X#" to refer to the X-coordinate of the #th point, and similarly for Y. DX and DY refer to delta-X and delta-Y. (Delta-X is the difference in X-coordinates; delta-Y is the difference in Y-coordinates.)

Note that the negative inversion of the slope is handled by reversing and negating the coordinates in the last two lines of the code fragment.

Now that we have Point 3, things get easy. Point 3 forms two isosceles triangles:

A Point 2 Point 3

Point 1 Point 2 Point 3

I shall begin with the latter triangle. We can bisect the segment Point 1 Point 3 by averaging their coordinates; this yields Point 4. Since the triangle is an isosceles right triangle, the line Point Point 4 lies at 45 degrees to line Point 2 Point 3. Unfortunately, Point 4 is not quite what we need, as it yields a line based on Point 2, and Point 2 is displaced from Unit B. This is easily corrected by creating Point 5, a point displaced from Point 4 by exactly the amount that Unit B is displaced from Point 2. This means that the line Unit B Point 5 runs 45 degrees out from the line to Unit B's rear.

A similar calculation yields Point 6 and Point 7. With the two 45-degree lines produced by these computations, we can define a triangular region bounded by these lines as the rear area of Unit B. Any enemy unit placed in this area constitutes a threat to Unit B. To determine whether an enemy unit falls inside this region, we perform some analytic geometry:

 AX = XB - X5; AY = YB - Y5; BX = XEnemy - XB; BY = YEnemy - YB; CX = X7 - XB; CY = Y7 - YB; DX = XEnemy - X7; DY = YEnemy - Y7; IF (((AX * BY) - (AY * BX)) < 0) AND (((CX * DY) - (CY * DX)) < 0) THEN {Yes, he is behind us!} 

This last IF-statement makes use of the equations for the two lines. The inequalities express the notion that the tested point falls on a particular side of a line.

By modern standards, this is pretty clunky stuff, but given the weakness of the CPUs in those days no, we didn't have floating point processors this algorithm's ability to carry out complex geometric calculations without resorting to trigonometry was important.

Results

Patton Versus Rommel was released in mid-1986. It was ported to several other machines and sold moderately well, but it was certainly not a hit. As far as I was concerned, it was the last wargame I would ever design. There were some interesting ideas in it, but wargame designers didn't seem to take much note of those ideas. In particular, I had hoped that the elimination of grids would be applied in other games, but few wargame designers seemed interested. And indeed, when I reluctantly decided to create one last wargame (Patton Strikes Back), I went back to the rectgrid system.

My deal with Electronic Arts proved to be the source of some chagrin. They had presented me with a 55-page contract, obviating every possible means by which I could let them down. Apparently, at the end of each project, the lawyers interviewed the producer to discover any procedural problems, and then wrote a new paragraph into the standard contract to ensure that the problems wouldn't arise again. The result was a tedious and picayune contract, but I suppose that they were burned enough times to adopt a defensive stance. I certainly did not resent their careful protection of their interests; I just hoped that this mound of legalese was not designed to screw me.

Sadly, I turned out to be wrong. After a year or so of sales, EA decided that Patton Versus Rommel was nearing the end of its product life, and decided to squeeze a last bit of revenue out of it. They made it a promotional item for some of their internally generated games. Buy our new game and get Patton Versus Rommel for just 1 cent more! This cleared out their inventory and boosted sales of their new products. However, their contract with me specified that I was to get a percentage of their net revenues on sales of my game. Thus, for each of those copies of Patton Versus Rommel that they sold, they paid me a fraction of a cent in royalties. It was a clever way to enhance their own profits and clear out inventory and I was the only loser in the deal. And it was all perfectly legal.

LESSON 58

Publishers hold all the cards; designers are lucky to get whatever they can.