Simulation Algorithm

Instead of using a miracle equation to find the target collision point, a simulation can predict the outcome. In this case, an algorithm based on successive iterations finds a good estimate of the intersection. This is based on forward integration, applying Euler's equations to the position of the enemy and projectile as shown in Figure 16.1.

Figure 16.1. Simulating the trajectory of the enemy with forward integration, comparing it to the distance traveled by the projectile. During the simulation, the position of the enemy moves along the line, and the potential area covered by the projectiles increases as circles.

Essentially, the iteration starts at the current time and steps through time, predicting the position of the enemy along the way. When the projectile can reach the position of the enemy in the same amount of time, we've found the intersection. Listing 16.1 has more details.

Listing 16.1 Using Forward Integration to Find the Point of Collision Between the Enemy and the Projectile

 repeat      # update the position of the enemy for this time step      enemy.position += enemy.velocity * delta      # add the step to the current time      time += delta      # determine time taken by projectile to reach enemy      flight_time = length(enemy.position origin) / projectile.speed      # compute time difference for enemy and projectile reaching      difference = abs(time - flight_time) # stop if the projectile is very close, or too many iterations until difference < threshold or time > max_time 

Notice that this iteration is done step by step, which might seem somewhat inefficient. In most cases, however, only a few iterations will actually be needed, because of the speed of the projectiles.

A different kind of integration could resolve this problem, performing in log(n) average time. The idea is to use a much larger step. Then, if the simulation goes too far, we negate the step and reduce its size. This will narrow the exact solution much quicker, and with greater precision. The additional code in the loop is shown in Listing 16.2. A suitable delta to start with is the time taken by the projectile to reach the original position of the enemy.

Listing 16.2 Update to the Forward Integration Algorithm That Adjusts the Delta

 # if the sign changes, the simulation has gone too far if sign XOR time < time_flight then      # reduce the step size and reverse direction           delta = -delta / 2 end if # remember if the enemy is further away than the projectile sign = time < time_flight 

There are few cases where this updated version of the algorithm should be preferred. Indeed, it essentially computes the result of the previous equation, most likely in a slower fashion. So, if such precision is required, the mathematical approach should be chosen.

On the other hand, there are other advantages to the plain forward iteration algorithm. Indeed, at each time step, it is possible for the artificial intelligence (AI) to anticipate the velocity of the enemy. So, for example, if there were an obstacle in the way, the velocity of the enemy would be adjusted. This would lead to the prediction of paths that are not linear.

Practical Demo

Colin is an animat that attempts to anticipate the enemy based on what it can see. During the prediction, it tries to check whether there is a wall in the way of the enemy. If the wall can be sidestepped, the velocity will be adjusted slightly by guessing. If the wall is a major block, the simulation stops and that point is used as a target. You can find the source code as well as a step-by-step guide to launching Colin on the web site at http://AiGameDev.com/.