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
        safe_distance = self.saucer.missile_head_start
        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
        return FiringSolution(target_position, shooter_position, safe_distance, speed_adjustment)

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
        safe_distance = self.saucer.missile_head_start
        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
        return FiringSolution(target_position, shooter_position, safe_distance, speed_adjustment)

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
        safe_distance = self.saucer.missile_head_start
        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
        adjustment_ratio = self.velocity_adjustment(aim_time, initial_offset)
        return aim_time, adjustment_ratio

    def velocity_adjustment(self, aim_time, initial_offset):
        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.

That removed the dreaded quadratic from the game, by the way.

This is unused, remove it:

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

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
        safe_distance = self.saucer.missile_head_start
        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
        safe_distance = self.saucer.missile_head_start
        target_position = self.lead_the_target(best_target_position, safe_distance, shooter_position)
        return FiringSolution(target_position, shooter_position, safe_distance, 1)

    def lead_the_target(self, best_target_position, safe_distance, 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 target_position

Better. Commit: extract lead_the_target

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:

    def lead_the_target(self, best_target_position, safe_distance, shooter_position):
        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

How about this?

    @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!