Python Asteroids on GitHub

I’ve left in two tests that aren’t testing anything, and I still want to improve targeting. Let’s see what we can manage. (Answer: Not much. Final thought on story estimation.)

There are two tests that use a function that we no longer use. We used to have a small hack that allowed un-targeted missiles from the saucer to accrue the saucer’s velocity, making them go faster when fired forward, slower when backward, while assigning an unaffected velocity to targeted missiles. We removed that feature, and now never adjust the missile’s velocity:

    def fire_available_missile(self, chance, fleets, saucer, ship_or_none):
        ship_position = self.select_aiming_point(chance, saucer, ship_or_none)
        velocity_adjustment = Vector2(0, 0)
        self.create_targeted_missile(saucer.position, ship_position, velocity_adjustment, fleets)

    def create_targeted_missile(self, from_position, to_position, velocity_adjustment, fleets):
        angle = self.angle_to_hit(to_position, from_position)
        missile = self.missile_at_angle(from_position, angle, velocity_adjustment)
        fleets.append(missile)

    def missile_at_angle(self, position, desired_angle, velocity_adjustment):
        missile_velocity = Vector2(u.MISSILE_SPEED, 0).rotate(desired_angle) + velocity_adjustment
        offset = Vector2(2 * self._radius, 0).rotate(desired_angle)
        return Missile.from_saucer(position + offset, missile_velocity)

If we’re going to keep it this way, and even if not, we should remove the unused parameter. It was never obvious and it certainly isn’t obvious now. What about the unused method and tests?

    def select_missile_UNUSED_METHOD(self, chance_of_targeting, fleets, saucer, ship_position):
        if saucer.always_target or chance_of_targeting <= u.SAUCER_TARGETING_FRACTION:
            velocity_adjustment = Vector2(0, 0)
        else:
            velocity_adjustment = saucer.velocity
        self.create_targeted_missile(saucer.position, ship_position, velocity_adjustment, fleets)

The tests just check to see whether, with the right settings, the large saucer does not target the ship, and the small one does. I’d like to have that tested, but not this way, which tests nothing. Let’s keep the test headings and make them fail. I just put an assert False at the end of each, thinking that the setup might be of value for an improved test.

Wait. Maybe it’s easy to bring them up to speed. Let’s look at the small saucer one:

    def test_small_saucer_does_target(self):
        pos = Vector2(100, 100)
        fleets = Fleets()
        fi = FI(fleets)
        small_saucer = Saucer(1)
        small_saucer._location.position = Vector2(100, 50)
        small_gunner = small_saucer._gunner
        small_gunner.select_missile_UNUSED_METHOD(1, fleets, small_saucer, pos)
        missiles = fi.missiles
        assert missiles
        missile = missiles[0]
        velocity = missile.velocity_testing_only
        assert velocity.x == 0
        assert velocity.y == pytest.approx(u.MISSILE_SPEED, 0.001)  # straight up
        assert False

If instead of calling the unused method, we called fire_available_missile here, I think it should pass. Yes! This passes:

    def test_small_saucer_does_target(self):
        pos = Vector2(100, 100)
        fleets = Fleets()
        fi = FI(fleets)
        ship = Ship(Vector2(100, 100))
        small_saucer = Saucer(1)
        small_saucer._location.position = Vector2(100, 50)
        small_gunner = small_saucer._gunner
        small_gunner.fire_available_missile(0, fleets, small_saucer, ship)
        missiles = fi.missiles
        assert missiles
        missile = missiles[0]
        velocity = missile.velocity_testing_only
        assert velocity.x == 0
        assert velocity.y == pytest.approx(u.MISSILE_SPEED, 0.001)  # straight up

I just had to add in a ship at the right place, and call the fire method. This is great, we keep some key testing. Now to fix up the other similarly.

First, I do it like this, to see it fail:

    def test_large_saucer_does_not_target(self):
        pos = Vector2(100, 100)
        fleets = Fleets()
        fi = FI(fleets)
        ship = Ship(Vector2(100, 100))
        large_saucer = Saucer(2)
        large_saucer._location.position = Vector2(100, 50)
        large_gunner = large_saucer._gunner
        large_gunner.fire_available_missile(0, fleets, large_saucer, ship)
        missiles = fi.missiles
        assert missiles
        missile = missiles[0]
        velocity = missile.velocity_testing_only
        assert velocity.x != 0 or velocity.y != pytest.approx(u.MISSILE_SPEED, .001)  # not straight up

It fails because of the zero parameter on fire_available_missile. That is a very unlucky die roll that causes the saucer to target, since even the large saucer targets 1/4 of its missiles. If we set that value > 0.25 we should not target.

        large_gunner.fire_available_missile(0.26, fleets, large_saucer, ship)

And we are green! We have saved a couple of actually useful tests. Remove the unused method. Commit: repair unused tests, remove unused method.

Reflection

Well, that was nice. Rather than just lose those tests, we managed to save them, and it was quite easy. I’m glad that I took a moment to think about making them useful: it would have been awfully easy just to remove them. If I had made that decision yesterday, I’d surely have lost the tests. Today I was feeling a bit guilty about removing tests right here in front of you, so I pushed just hard enough to realize saving them was so easy.

I’m sure it’s almost always better to save a test than to remove it. Yay, me! And thanks for being here, I would have flaked if you hadn’t been watching me.

Back to the plan

Now lets remove that velocity adjustment parameter from the methods shown above. I’ll start at the bottom one, with Change Signature refactoring.

    def missile_at_angle(self, position, desired_angle, velocity_adjustment):
        missile_velocity = Vector2(u.MISSILE_SPEED, 0).rotate(desired_angle) + velocity_adjustment
        offset = Vector2(2 * self._radius, 0).rotate(desired_angle)
        return Missile.from_saucer(position + offset, missile_velocity)

First, stop using the adjustment:

    def missile_at_angle(self, position, desired_angle, velocity_adjustment):
        missile_velocity = Vector2(u.MISSILE_SPEED, 0).rotate(desired_angle)
        offset = Vector2(2 * self._radius, 0).rotate(desired_angle)
        return Missile.from_saucer(position + offset, missile_velocity)

Tests are green. Commit: missile_at_angle ignores velocity_adjustment, which is always zero anyway.

Don’t you just love it when the commit message takes longer to type than the code change? Tiny steps FTW, seriously.

Change Signature, Command+F6:

    def missile_at_angle(self, position, desired_angle):
        missile_velocity = Vector2(u.MISSILE_SPEED, 0).rotate(desired_angle)
        offset = Vector2(2 * self._radius, 0).rotate(desired_angle)
        return Missile.from_saucer(position + offset, missile_velocity)

Commit: remove velocity_adjustment parameter from missile_at_angle.

Again, here:

    def create_targeted_missile(self, from_position, to_position, velocity_adjustment, fleets):
        angle = self.angle_to_hit(to_position, from_position)
        missile = self.missile_at_angle(from_position, angle)
        fleets.append(missile)

Resulting:

    def create_targeted_missile(self, from_position, to_position, fleets):
        angle = self.angle_to_hit(to_position, from_position)
        missile = self.missile_at_angle(from_position, angle)
        fleets.append(missile)

Commit: remove velocity_adjustment parameter from create_targeted_missile.

I cleverly made the message from the previous commit easy to edit. Saved literally tens of keystrokes, which I’m sure I shall receive as a reward in the next world.

Now we find senders of that method:

    def fire_available_missile(self, chance, fleets, saucer, ship_or_none):
        ship_position = self.select_aiming_point(chance, saucer, ship_or_none)
        velocity_adjustment = Vector2(0, 0)
        self.create_targeted_missile(saucer.position, ship_position, fleets)

Unused line there, delete it.

    def fire_available_missile(self, chance, fleets, saucer, ship_or_none):
        ship_position = self.select_aiming_point(chance, saucer, ship_or_none)
        self.create_targeted_missile(saucer.position, ship_position, fleets)

Green. Commit: fire_available_missile no longer computes unused value.

Reflection

OK, good job, we’ve simplified things a bit. I think I’d like to review the code and see if it’s hanging together, and I’d really like to find a way to compensate for the missile’s starting point.

Reminder
Our calculation of the ideal aiming point computes a time at which the two missiles can arrive at the same location. Then we use that time to compute an aiming point by predicting where the ship will be at that time, projecting its current path. Then we aim at that point.

The problem is this. So that our missile does not kill us, we start it, not at our center, but twice our saucer radius away, in the direction of the target. So the missile gets a little head start and often crosses the ship’s path just a bit too soon.

How much too soon, you’re asking. Darn good question, it occurs to me. When the ship hits the target point, the missile will be two saucer radii past the ship. That’s 40 Interplanetary Standard Space Distance Units for the large ship and 20 for the small. The ship radius is 25, so the large saucer is very likely to miss. The small one misses less often but you can often see the missile crossing right ahead of the ship’s nose.

So, I think it is worth fixing. We want the targeted missiles to be really good. If they are perfectly aimed, I think they should hit unless the ship changes direction.

So my cunning plan was that we should slow down the targeted missile by just enough to hit the crossing point at the right time.

However, when testing just now with the small saucer, I noticed an odd thing. It always fires at some future point along the ship’s projected path. However, if it is trailing the ship, that point is so far in the future that it cannot possibly hit the ship. So you get a few feeble shots moving slowly away from the saucer.

If the shot isn’t going to get to the ship within missile lifetime, it will look better if we just fire randomly.

In addition, though I hate to say it, shots look better when adjusted by saucer velocity: forward shots just crawl away and it doesn’t look good.

It’s almost like we want velocity_adjustment back, isn’t it? But the good news is that we removed it. Why is that good news? Because now we have a chance of finding a way to do it right.

Code Review

With all that in mind, let’s review the Gunner code. We’re interested in randomizing shots that cannot hit the target and possible interested in adding the saucer’s velocity back into the shots, at least the random ones.

It would be fantastically good if we could use the combined velocity of saucer and missile in targeted shots. Some of them would really fly at you. But the quadratic code is adopted from the Internet and I do not understand it. But maybe we can see how to adjust it.

Review the code. The action starts here, where we actually know we’ll fire a missile:

    def fire_available_missile(self, chance, fleets, saucer, ship_or_none):
        ship_position = self.select_aiming_point(chance, saucer, ship_or_none)
        self.create_targeted_missile(saucer.position, ship_position, fleets)

So we pick an aiming point and then, well, create a missile aimed at the point. The select is:

    def select_aiming_point(self, chance, saucer, ship_or_none):
        if not ship_or_none:
            return self.random_position()
        elif saucer.always_target:
            return self.optimal_aiming_point(saucer, ship_or_none)
        elif chance < u.SAUCER_TARGETING_FRACTION:
            return self.optimal_aiming_point(saucer, ship_or_none)
        else:
            return self.random_position()

The optimal point is found like this:

    def optimal_aiming_point(self, saucer, ship):
        target_position = self.closest_aiming_point(saucer.position, ship.position, u.SCREEN_SIZE)
        delta_position = target_position - saucer.position
        aim_time = self.time_to_target(delta_position, ship.velocity)
        return target_position + ship.velocity * aim_time

The closest bit just decides whether to try a shot across the border. If there is a border-crossing shot that is closer, we’ll use it. And time_to_target is our quadratic. Let’s review that, because maybe we can tweak it.

    def time_to_target(self, delta_position, relative_velocity):
        # from https://www.gamedeveloper.com/programming/shooting-a-moving-target#close-modal
        # return time for hit or -1
        # quadratic
        a = relative_velocity.dot(relative_velocity) - u.MISSILE_SPEED*u.MISSILE_SPEED
        b = 2 * relative_velocity.dot(delta_position)
        c = delta_position.dot(delta_position)
        disc = b*b - 4*a*c
        if disc < 0:
            return 0
        else:
            divisor = (math.sqrt(disc) - b)
            if divisor:
                return 2*c / divisor
            else:
                return 0

Ah, we note that we do provide relative velocity here. And, aside, if the time returned here is greater than the missile lifetime, we are out of luck and would prefer to fire randomly.

What would happen, I wonder, if we were to pass in here, not just ship.velocity, but the actual relative velocity, ship minus saucer … and unconditionally add the saucer velocity back in to the missile?

Let’s spike.

A raft of tests fail. I’ve done this:

class Gunner:
    def __init__(self, saucer_radius=20):
        self._timer = Timer(u.SAUCER_MISSILE_DELAY)
        self._radius = saucer_radius
        self._saucer = None

    def fire(self, delta_time, saucer, ship_or_none: Ship | None, fleets):
        self._saucer = saucer
        self._timer.tick(delta_time, self.fire_if_missile_available, saucer, ship_or_none, fleets)

    def optimal_aiming_point(self, saucer, ship):
        target_position = self.closest_aiming_point(saucer.position, ship.position, u.SCREEN_SIZE)
        delta_position = target_position - saucer.position
        aim_time = self.time_to_target(delta_position, ship.velocity - saucer.velocity)
        return target_position + ship.velocity * aim_time

    def missile_at_angle(self, position, desired_angle):
        missile_velocity = Vector2(u.MISSILE_SPEED, 0).rotate(desired_angle) + self._saucer.velocity
        offset = Vector2(2 * self._radius, 0).rotate(desired_angle)
        return Missile.from_saucer(position + offset, missile_velocity)

I don’t have the saucer down in missile_at_angle, so I just scarfed up the input parameter and cached it. Nasty but this is a spike. Tests are failing all over.

Let’s see what the game does. Bad news, I guess. The saucer basically cannot hit me. So my guess at what would happen is mistaken. Roll back that spike and think.

Attempted Thinking

I was going to belay the velocity idea and do the randomization, but after a short break to walk down the hall, I think I want to try this idea again and observe more carefully. I almost wish I hadn’t rolled it back.

Spiking again.

I find that I cannot import Saucer into Gunner, presumably because Saucer imports Gunner. Irritating.

Ah. As I spike a second time, I notice this:

    def create_targeted_missile(self, from_position, to_position, fleets):
        angle = self.angle_to_hit(to_position, from_position)
        missile = self.missile_at_angle(from_position, angle)
        fleets.append(missile)

    @staticmethod
    def angle_to_hit(best_aiming_point, saucer_position):
        return Vector2(0, 0).angle_to(best_aiming_point - saucer_position)

    def missile_at_angle(self, position, desired_angle):
        missile_velocity = Vector2(u.MISSILE_SPEED, 0).rotate(desired_angle) + self._saucer.velocity
        offset = Vector2(2 * self._radius, 0).rotate(desired_angle)
        return Missile.from_saucer(position + offset, missile_velocity)

Clearly we can’t fire at that angle if we aim and then add in the saucer velocity. Can that go before the rotate?

    def missile_at_angle(self, position, desired_angle):
        missile_velocity = (Vector2(u.MISSILE_SPEED, 0) + self._saucer.velocity).rotate(desired_angle)
        offset = Vector2(2 * self._radius, 0).rotate(desired_angle)
        return Missile.from_saucer(position + offset, missile_velocity)

Try that in game. Still no good. Back it out again.

I am not well pleased. The saucer targeting is simply not as good as I’d like. And with the small saucer always targeting, it just doesn’t look very good, because so many of its missiles just crawl along. I’ve even seen it run into its own missile.

We need a better scheme, ideally one that I understand well enough to make it work.

Let’s go back almost to first principles and figure out what we want. Things we want include:

  • Missiles should accrue vehicle velocity because they look better that way.
  • Targeted missiles should have a very good chance of hitting the ship.
  • When hitting the ship is impossible, consider firing randomly just to make it more interesting.
  • Targeting scheme should be well understood by programmer.

With those in mind, let’s look at the at_angle thing again.

    def missile_at_angle(self, position, desired_angle):
        missile_velocity = Vector2(u.MISSILE_SPEED, 0).rotate(desired_angle)
        offset = Vector2(2 * self._radius, 0).rotate(desired_angle)
        return Missile.from_saucer(position + offset, missile_velocity)

Let’s assume that we want the missile to actually travel at the desired angle. Then, it seems clear to me, we really should use the saucer’s velocity.

Therefore let’s get it passed in there.

The caller of missile_at_angle is this:

    def create_targeted_missile(self, from_position, to_position, fleets):
        angle = self.angle_to_hit(to_position, from_position)
        missile = self.missile_at_angle(from_position, angle)
        fleets.append(missile)

It does not have the saucer either. However its caller is this, which does have saucer:

    def fire_available_missile(self, chance, fleets, saucer, ship_or_none):
        ship_position = self.select_aiming_point(chance, saucer, ship_or_none)
        self.create_targeted_missile(saucer.position, ship_position, fleets)

Let’s change signatures to pass the saucer down. There are tests that might fail.

    def create_targeted_missile(self, saucer, to_position, fleets):
        angle = self.angle_to_hit(to_position, saucer.position)
        missile = self.missile_at_angle(saucer, angle)
        fleets.append(missile)

    def missile_at_angle(self, saucer, desired_angle):
        missile_velocity = Vector2(u.MISSILE_SPEED, 0).rotate(desired_angle)
        offset = Vector2(2 * self._radius, 0).rotate(desired_angle)
        return Missile.from_saucer(saucer.position + offset, missile_velocity)

Not very clever, Ron!

I’m doing these changes stupidly, by hand instead of relying on PyCharm where it can help. This may not work out. Why am I doing it this way? Because I am tired, and because I am thinking about too many things at once, and because I don’t see a clear series of refactoring steps.

Don’t be like my brother’s brother.

I’m breaking tests left and right. Maybe it’s OK, they are all targeting tests. I think we’re committing to breaking those.

I’m going to take a break, accept a Mac update, think, make a chai, and come back to this.

Before I go, I’ll record my current thinking.

“Thinking”

We could remove targeting, and ignore or remove the relevant tests. We could do a different kind of targeting. I think the original game targets by choosing a fraction of the sky to aim at, based on where the ship is. Our missile_at_angle could deal with that, and we should test it to be sure that it works correctly with saucer velocity factored in. Unless we want the saucer missiles to only have their intrinsic.

We could pick the angle at which to fire by estimating the time to target and projecting that value and aiming there. We could probably even iterate that approximation a couple of times.

I’ve had this idea before but it is more than fair to point out that Tomas Aschan made a similar iterative suggestion a day or so ago on Mastodon, so it may be his suggestion that brings it to mind. Thanks, Tomas!

Anyway, let’s get this machine updated and some chai made.

Later that morning …

I’m going to let this sit with the existing targeting, the new tests, and the unused method removed. I’m not sure about replacing the targeting, but I’m becoming more sure that I want the saucer missiles to have their intrinsic velocity, not intrinsic plus saucer. I think it looks better.

Some small progress, some near-learning if not learning from spiking. The code is a bit simpler, which will probably make it more ready for an improvement if I can think of one. We’ll leave that for later today, or for Monday.

For now … too many lines of writing for too little improvement? Well, that’s the way of it sometimes.

That’s why estimation at the story level is such a poor idea: the estimates are subject to very wide variance, depending on things that simply cannot be anticipated.

See you next time!