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.
# 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.