Python Asteroids on GitHub

I really don’t like the fact that I am either too dull or too lazy to derive the quadratic targeting calculation. Either it goes, or I do, and I get to choose.

### Last Night

Last night, I studied a few more targeting articles, scrawled a little math, and again determined that I don’t understand the “quadratic” thing we have and am not interested in deriving one from first principles, due to the aforementioned combination of dullness and laziness. So instead, I did an experiment in Codea Lua, which is a bit easier to work with on my iPad than Python. It looks like this:

function setup()
ship = vec2(700,700)
gun = vec2(100,100)
miss = vec2(100,100)
vtarg = vec2(-10,10)
speed = 100
pt = ship
pt = aim(ship)
pt = aim(pt)
pt = aim(pt)
delta = pt - gun
vmiss = delta:normalize()*speed
end

function move()
ship = ship + vtarg*DeltaTime
miss = miss + vmiss*DeltaTime
end

function aim(t)
dist = t:dist(gun)
time = dist/speed
tdist = time*vtarg
new = ship + tdist
return new
end

function draw()
background(40, 40, 50)
strokeWidth(5)
stroke(255,0,0)
fill(255, 14, 0)

ellipse(ship.x, ship.y, 25)
stroke(0,255,0)
fill(0, 255, 0)
ellipse(miss.x, miss.y, 25)
ellipse(pt.x, pt.y, 25)

move()
end

I apologize for the horrible names. If you were typing with one finger on an iPad in your lap, you, too, might use short 1960’s style names. Also, everything in there is global. That’s just how Lua works unless you tell it otherwise.

The interesting bit here is the function aim, which the program iterates three times. Let’s look at it in a bit more detail.

function aim(t)
dist = t:dist(gun)
time = dist/speed
tdist = time*vtarg
new = ship + tdist
return new
end

t is the target, a 2D vector. It starts out as ship. We calculate the distance between t and the gun, a fixed 2D vector representing the position of the gun, or saucer in our case.

Given the distance and the missile speed speed, we get the time needed for the missile to hit the target. We then get the distance, tdist that the target will move in that amount of time, and new, the position of the ship at that time.

We can be certain that the first time through this function, the ship will have moved away from its starting position to its new position, and the missile, well named, will miss.

So we iterate, aiming at pt=new this time. Since that point is further forward from the ship’s starting position, the error will be smaller, unless of course the ship is moving away faster than a missile, in which case we’re out of luck.

If the missile can hit the ship, given enough range, the next call to aim will provide a smaller adjustment and the missile will come closer to hitting the ship. On my iPad, three iterations was enough to do the job, with the randomly chosen starting values I used.

### This Morning

So that was last night. This morning (it is 0640) I plan to put this solution into Asteroids, and thus be rid of the quadratic code that I do not understand. Let’s look to see where this needs to go. The function as written returns the point at which the saucer should aim.

Oh. Let me mention that I think it should be easy to accommodate the saucer’s missile-firing offset in this scheme. I haven’t done it yet but I did think about it before falling asleep.

Here is the relevant code in ShotOptimizer:

class ShotOptimizer:
@property
def targeted_solution(self):
if not self.ship:
return self.random_solution
shooter_position = self.saucer.position
best_target_position = self.closest_aiming_point(shooter_position, self.ship.position, u.SCREEN_SIZE)
vector_to_target = best_target_position - shooter_position
aim_time, speed_adjustment = self.optimal_shot(vector_to_target, self.ship.velocity, safe_distance)
target_position = best_target_position + self.ship.velocity * aim_time

Our new scheme returns a target position, and we won’t need a speed adjustment if I’m right about my tentative plan.

I think I’d like to test-drive this new thing, although I am not quite sure how that will go. Let’s just try it. Here’s my first test:

def test_aiming_point(self):
ship_position = Vector2(100, 100)
ship_velocity = Vector2(10, 10)
saucer_position = Vector2(0, 0)
missile_speed = 100
starting_distance = 141.42  # trig
flight_time = starting_distance/100
ship_move = ship_velocity*flight_time
new_ship_position = ship_position + ship_move
new_target = aiming_point(ship_position, ship_velocity, saucer_position, missile_speed)
dist = new_target.distance_to(new_ship_position)
assert dist < 0.001

All this does is hand-calculate the missile transit time and project the ship, then ask for the aiming point, which should be the same location. Therefore the distance between the aiming point and hand-projected ship position should be small.

Now let’s see about hitting the thing.

Belay That
I made a mistake in the calling sequence. I need the original ship position and the new target position. I now have two tests:
def test_aiming_point(self):
ship_position = Vector2(100, 100)
ship_velocity = Vector2(10, 10)
saucer_position = Vector2(0, 0)
missile_speed = 100
starting_distance = 141.42  # trig
flight_time = starting_distance/100
ship_move = ship_velocity*flight_time
new_ship_position = ship_position + ship_move
new_target = aiming_point(
ship_position,
ship_velocity,
ship_position,
saucer_position,
missile_speed)
dist = new_target.distance_to(new_ship_position)
assert dist < 0.001

def test_iterated_aiming_point(self):
ship_position = Vector2(100, 100)
ship_velocity = Vector2(10, 10)
saucer_position = Vector2(0, 0)
missile_speed = 100
new_target = ship_position
for _ in range(5):
new_target = aiming_point(
new_target,
ship_velocity,
ship_position,
saucer_position,
missile_speed)
ship_speed = ship_velocity.length()
ship_move_distance = ship_position.distance_to(new_target)
ship_time = ship_move_distance / ship_speed
missile_move_distance = saucer_position.distance_to(new_target)
missile_time = missile_move_distance / missile_speed
assert ship_time == pytest.approx(missile_time, 0.01)

The first one is the same except with the extended calling sequence. The second iterates five times and checks that the two flight times are sufficiently near to equal.

And here is the function:

def aiming_point(
target_pos,
target_velocity,
ship_pos,
gunner_pos,
missile_speed):
distance = target_pos.distance_to(gunner_pos)
time = distance/missile_speed
target_move = time*target_velocity
new_target_pos = ship_pos + target_move
return new_target_pos

Setting the iteration range to 3 still passes the second test.

Now I promised that we would deal with the missile offset from the saucer. Here’s the small insight that I had:

Because we’re going to aim at the target and because we’ll have the offset in that exact direction, the missile will have to fly just a little bit shorter distance. If we use that shorter distance to calculate the time, we should hit the target exactly.

Let’s add a parameter and keep the tests running, then write a new test.

def aiming_point(
target_pos,
target_velocity,
ship_pos,
gunner_pos,
missile_speed,
missile_offset):
distance = target_pos.distance_to(gunner_pos)
time = (distance - missile_offset)/missile_speed
target_move = time*target_velocity
new_target_pos = ship_pos + target_move
return new_target_pos

The old tests have zero as the offset. Now let’s do a harder one.

def test_iterated_offset_aiming_point(self):
ship_position = Vector2(100, 100)
ship_velocity = Vector2(10, 10)
saucer_position = Vector2(0, 0)
missile_speed = 100
missile_offset = 20
new_target = ship_position
for _ in range(3):
new_target = aiming_point(
new_target,
ship_velocity,
ship_position,
saucer_position,
missile_speed,
missile_offset)
ship_speed = ship_velocity.length()
ship_move_distance = ship_position.distance_to(new_target)
ship_time = ship_move_distance / ship_speed
missile_move_distance = saucer_position.distance_to(new_target) - missile_offset
missile_time = missile_move_distance / missile_speed
assert ship_time == pytest.approx(missile_time, 0.01)

That passes. We are pleased. I think this is going to work out well.

Let’s move the new function over to ShotOptimizer, where it probably belongs.

Now let’s use it, replacing this:

@property
def targeted_solution(self):
if not self.ship:
return self.random_solution
shooter_position = self.saucer.position
best_target_position = self.closest_aiming_point(shooter_position, self.ship.position, u.SCREEN_SIZE)
vector_to_target = best_target_position - shooter_position
aim_time, speed_adjustment = self.optimal_shot(vector_to_target, self.ship.velocity, safe_distance)
target_position = best_target_position + self.ship.velocity * aim_time

With this:

def targeted_solution(self):
if not self.ship:
return self.random_solution
shooter_position = self.saucer.position
best_target_position = self.closest_aiming_point(shooter_position, self.ship.position, u.SCREEN_SIZE)
vector_to_target = best_target_position - shooter_position
target_position = best_target_position
for _ in range(3):
target_position = self.aiming_point(
target_position,
self.ship.velocity,
best_target_position,
shooter_position,
u.MISSILE_SPEED,
safe_distance)
return FiringSolution(target_position, shooter_position, safe_distance, 1)

This works in the game—I couldn’t resist—and breaks two tests. They are easily fixed, just needed to take the new scheme into account. One was checking for an adjusted velocity, which no longer happens, and the other needed to take the missile safety margin into account.

I’m committing: ShotOptimizer now uses new iterated aiming_point method.

Now let’s see what we can remove and what needs improvement.

These are unused:

def optimal_shot(self, delta_position, delta_velocity, initial_offset):
aim_time = TimeToTarget(delta_position, delta_velocity).time

return self.compensate_for_offset(aim_time, initial_offset) if aim_time else 1

TimeToTarget is unused except in tests. But those tests are often testing whether we hit the target or not. Let’s move the class to the test_gunner.py module. Done. Perhaps some of those tests only test the TimeToTarget class but some are using the time to assess whether we hit the ship.

Commit: move TimeToTarget over to test_gunner, unused in game.

This is unused, remove it:

class ShotOptimizer:
@staticmethod
def compensate_for_offset(aim_time, initial_offset):
distance_to_target = aim_time * u.MISSILE_SPEED

I think this method would like to be improved:

class ShotOptimizer:
@property
def targeted_solution(self):
if not self.ship:
return self.random_solution
shooter_position = self.saucer.position
best_target_position = self.closest_aiming_point(shooter_position, self.ship.position, u.SCREEN_SIZE)
vector_to_target = best_target_position - shooter_position
target_position = best_target_position
for _ in range(3):
target_position = self.aiming_point(
target_position,
self.ship.velocity,
best_target_position,
shooter_position,
u.MISSILE_SPEED,
safe_distance)
return FiringSolution(target_position, shooter_position, safe_distance, 1)

Let’s extract:

@property
def targeted_solution(self):
if not self.ship:
return self.random_solution
shooter_position = self.saucer.position
best_target_position = self.closest_aiming_point(shooter_position, self.ship.position, u.SCREEN_SIZE)
vector_to_target = best_target_position - shooter_position
return FiringSolution(target_position, shooter_position, safe_distance, 1)

target_position = best_target_position
for _ in range(3):
target_position = self.aiming_point(
target_position,
self.ship.velocity,
best_target_position,
shooter_position,
u.MISSILE_SPEED,
safe_distance)
return target_position

The aiming_point method takes quite a few arguments, but I hesitate to remove them because the tests used some made-up but easy to think about values.

I do think we could use a better name:

target_position = best_target_position
for _ in range(3):
target_position = self.improved_aiming_point(
target_position,
self.ship.velocity,
best_target_position,
shooter_position,
u.MISSILE_SPEED,
safe_distance)
return target_position

I think improved_aiming_point does a better job of saying what’s going on.

Commit: rename to improved_aiming_point.

Let’s improve the names here, then call it a morning:

@staticmethod
def improved_aiming_point(
target_pos,
target_velocity,
ship_pos,
gunner_pos,
missile_speed,
missile_offset):
distance = target_pos.distance_to(gunner_pos)
time = (distance - missile_offset) / missile_speed
target_move = time * target_velocity
new_target_pos = ship_pos + target_move
return new_target_pos

@staticmethod
def improved_aiming_point(
initial_aiming_point,
target_velocity,
target_starting_position,
gunner_position,
missile_speed,
missile_offset):
missile_travel_distance = gunner_position.distance_to(initial_aiming_point) - missile_offset
missile_travel_time = missile_travel_distance / missile_speed
target_motion = missile_travel_time * target_velocity
better_aiming_point = target_starting_position + target_motion
return better_aiming_point

A few renames, moved the offset to a better place, and reordered the parameters in the distance_to because it seemed better. Commit: tidying improved_aiming_point.

Let’s sum up.

## Summary

We have removed quite a few methods and an entire small class (well, moved it to testing at least for now). We have a simple iterative solution for targeting, instead of a poorly understood quadratic solution that makes less sense the more I look at it. We iterate our simple method three times and get good results. We save a square root call, if anyone cares. (At two shots per second, no one cares. Besides there’s probably one in distance_to.)

The overall process included a proof of concept in Lua, just because Codea was there, followed by test-driving the implementation in Python, followed by extending it to deal directly with the safety offset, which works out quite nicely in this scheme.

I can understand this scheme, where I still have not grokked the quadratic code in fullness. And I wrote this scheme rather than transliterating it from ancient cuneiform tablets, which gives me a small thrill of accomplishment and a lot more confidence in what’s going on.

The calling sequence to aiming_point is a bit long, and it might be worth adjusting it, but it’s solid and tested directly and indirectly, so I’ll treat that as low priority.

I am well pleased. A small but irritating thing is gone from the program. I might even argue that this approach is closer to what one would do in a game with no math functions, such as the original Asteroids. Hmm, I wonder how they did it. I must read the ancient tablets again.

A very pleasing result. I can’t wait to see what I do next.

See you then!