I get some good advice from a reader (!) and ten (unrelated) consider a demonic idea. I lift a solution from the Internet. Some nice little refactoring. A few tests. Saucer is deadly. Could be more deadly.

Thanks

The very kind Ajahn Jhanarto from Western Australia has suggested that I would do well to read about pytest fixtures, and linked me to a nice article about them. I’m sure that I’d do well to learn better ways of using pytest. I’m really only scratching the surface of what it can do. I’ll read the article and see whether they’ll help me. Thank you, Bhante!

It’s always good to hear from readers, who are often quite distant from me in many dimensions.

Demonic Idea

In other versions of Asteroids, I have done a thing which I think is quite demonic. When a Saucer fires a targeted missile, instead of aiming at the then-current position of the ship, lead the ship by aiming at a point further along the path it is currently on. Project its position a bit into the future and aim there.

As things stand, if you keep the ship moving, the Saucer will generally not hit you, unless you are moving directly toward or away from it when it fires. It will aim where you are, and by the time the missile gets there, you are not there any more. Leading will give it a better chance of nailing you.

This is easy to implement naively. We have this code:

class Gunner:
    def fire(self, delta_time, saucer, ship_or_none: Ship | None, fleets):
        if ship_or_none:
            ship_position = ship_or_none.position
        else:
            ship_position = self.random_position()
        self._timer.tick(delta_time, self.fire_missile, saucer, ship_position, fleets)

If we have a ship, we set ship_position to its position and that becomes the target. So if we do this:

    def fire(self, delta_time, saucer, ship_or_none: Ship | None, fleets):
        if ship_or_none:
            ship_position = ship_or_none.position + 
            	ship_or_none.velocity_testing_only
        else:
            ship_position = self.random_position()
        self._timer.tick(delta_time, self.fire_missile, saucer, ship_position, fleets)

Now we’re aiming at the ship one second further along its path. I need to try this in the game, because tests will not see this happening. It sort of works, but of course the estimate of a one second lead is weak. We should actually consider how far away we are.

Let’s see, if we were to compute the distance between saucer and ship and divide that by missile speed, that would be a decent guess at how far to lead.

    def fire(self, delta_time, saucer, ship_or_none: Ship | None, fleets):
        if ship_or_none:
            position = ship_or_none.position
            dist = position.distance_to(saucer.position)
            time = dist/u.MISSILE_SPEED
            ship_position = position + 
            	ship_or_none.velocity_testing_only*time
        else:
            ship_position = self.random_position()
        self._timer.tick(delta_time, self.fire_missile, saucer, ship_position, fleets)

That works rather well, but not as well as I would have expected. The spike code above is assuming that the distance between ship and saucer will be the same at the aiming point as it is now. If the ship is moving away, the shot will fall behind. If they are moving toward one another, the shot will arrive early. This is still better than if we do not adjust, but it’s not as demonic as I had hoped.

I think there is some clever intersection between line and hyperbola thing to be done here, but it’s 0700 here and while I am up for programming, I’m not up for that.

Can’t solve easily, can still read …

After some scribbling and verifying that I’m definitely not up for solving this problem, I do a bit of searching and find this article.

Though I rarely do this, it’s early in the morning and I want to see what happens. I type in the code from that article and apply it:

    def aim_ahead(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 -1
        else:
            return 2*c/(math.sqrt(disc) - b)

    def fire(self, delta_time, saucer, ship_or_none: Ship | None, fleets):
        if ship_or_none:
            delta_position = ship_or_none.position - saucer.position
            velocity = ship_or_none.velocity_testing_only
            aim_time = self.aim_ahead(delta_position, velocity)
            if aim_time == -1:
                ship_position = ship_or_none.position
            else:
                ship_position = ship_or_none.position + ship_or_none.velocity_testing_only*aim_time
        else:
            ship_position = self.random_position()

With this code in place, the small saucer is pretty deadly. In fact it’s a monster. In game play, it seems to shoot me down every time it comes out, unless I start cavorting like mad, in which case I tend to run into asteroids.

I am not sure about keeping this. It seems quite good, but I have code here that I do not understand. And one test is broken: this 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(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(166.666, 0.001)  # straight up

Expected :166.666 ± 1.7e-01
Actual   :250.0

That diagnostic tells me that I don’t understand what approx does, so I’ll look that up. I thought we were providing the actual allowed difference but 1.7e-01 doesn’t look like that to me. But why did we get 250? I’m only calling select_missile: my new code isn’t even involved here. Oh! I changed the missile velocity to see if faster missiles were more fun.

An easy fix:

    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(1, fleets, small_saucer, pos)
        missiles = fi.missiles
        assert missiles
        missile = missiles[0]
        velocity = missile.velocity_testing_only
        assert velocity.x == 0
        # fix on next line:
        assert velocity.y == pytest.approx(u.MISSILE_SPEED, 0.001)  # straight up

So the tests are good. I have no test for the actual quadratic code. Let’s do some refactoring and extraction on Gunner.

From:

    def fire(self, delta_time, saucer, ship_or_none: Ship | None, fleets):
        if ship_or_none:
            delta_position = ship_or_none.position - saucer.position
            velocity = ship_or_none.velocity_testing_only
            aim_time = self.aim_ahead(delta_position, velocity)
            if aim_time == -1:
                ship_position = ship_or_none.position
            else:
                ship_position = ship_or_none.position + ship_or_none.velocity_testing_only*aim_time
        else:
            ship_position = self.random_position()
        self._timer.tick(delta_time, self.fire_missile, saucer, ship_position, fleets)

First invert the if for clarity:I don’t like a long if and then a short else:

    def fire(self, delta_time, saucer, ship_or_none: Ship | None, fleets):
        if not ship_or_none:
            ship_position = self.random_position()
        else:
            delta_position = ship_or_none.position - saucer.position
            velocity = ship_or_none.velocity_testing_only
            aim_time = self.aim_ahead(delta_position, velocity)
            if aim_time == -1:
                ship_position = ship_or_none.position
            else:
                ship_position = ship_or_none.position + ship_or_none.velocity_testing_only*aim_time
        self._timer.tick(delta_time, self.fire_missile, saucer, ship_position, fleets)

Now extract that big else:

    def fire(self, delta_time, saucer, ship_or_none: Ship | None, fleets):
        if not ship_or_none:
            ship_position = self.random_position()
        else:
            ship_position = self.choose_aiming_point(saucer, ship_or_none)
        self._timer.tick(delta_time, self.fire_missile, saucer, ship_position, fleets)

    def choose_aiming_point(self, saucer, ship_or_none):
        delta_position = ship_or_none.position - saucer.position
        velocity = ship_or_none.velocity_testing_only
        aim_time = self.aim_ahead(delta_position, velocity)
        if aim_time == -1:
            ship_position = ship_or_none.position
        else:
            ship_position = ship_or_none.position + ship_or_none.velocity_testing_only * aim_time
        return ship_position

Rename ship_or_none in the choose function: we know we have a ship. Add a velocity property to ship (not shown).

    def choose_aiming_point(self, saucer, ship):
        delta_position = ship.position - saucer.position
        velocity = ship.velocity
        aim_time = self.aim_ahead(delta_position, velocity)
        if aim_time == -1:
            ship_position = ship.position
        else:
            ship_position = ship.position + ship.velocity_testing_only * aim_time
        return ship_position

Rename aim_ahead to time_to_target.

    def choose_aiming_point(self, saucer, ship):
        delta_position = ship.position - saucer.position
        velocity = ship.velocity
        aim_time = self.time_to_target(delta_position, velocity)
        if aim_time == -1:
            ship_position = ship.position
        else:
            ship_position = ship.position + ship.velocity_testing_only * aim_time
        return ship_position

I’m doing all these with PyCharm’s machine refactorings, so I feel confident that I’m not breaking this untested code.

Inline velocity temp:

    def choose_aiming_point(self, saucer, ship):
        delta_position = ship.position - saucer.position
        aim_time = self.time_to_target(delta_position, ship.velocity)
        if aim_time == -1:
            ship_position = ship.position
        else:
            ship_position = ship.position + ship.velocity_testing_only * aim_time
        return ship_position

An issue comes to mind. We rez the missile, not at the saucer’s center, but at its radius. That will change the flying time. We should take that into account in this calculation. Note made.

What about returning instead of assigning? Better yet, what if we returned zero instead of -1 from time_to_target?

    def fire(self, delta_time, saucer, ship_or_none: Ship | None, fleets):
        if not ship_or_none:
            ship_position = self.random_position()
        else:
            ship_position = self.choose_aiming_point(saucer, ship_or_none)
        self._timer.tick(delta_time, self.fire_missile, saucer, ship_position, fleets)

    def choose_aiming_point(self, saucer, ship):
        delta_position = ship.position - saucer.position
        aim_time = self.time_to_target(delta_position, ship.velocity)
        return ship.position + ship.velocity * aim_time

    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:
            return 2*c/(math.sqrt(disc) - b)

Now it seems that we can test choose_aiming_point and time_to_target independently. (Yes, that does suggest they are quite possibly wanting to be in some other object.) I still don’t understand the math, but I can at least generate some numbers and look at them.

Here’s an easy one, since it uses zero velocity:

    def test_time_to_target_1(self):
        gunner = Gunner(10)
        time = gunner.time_to_target(Vector2(0, 50), Vector2(0, 0))
        assert time == 50/u.MISSILE_SPEED

That passes. Let’s do a harder one:

    def test_time_to_target_harder(self):
        gunner = Gunner(10)
        time = gunner.time_to_target(Vector2(0, 50), Vector2(0, 10))
        assert time == 50/u.MISSILE_SPEED

Here the ship is moving directly away from the saucer at speed 50. The answer isn’t 50/speed, and the test tells me so:

Expected :0.2
Actual   :0.20833333333333334

What should be the case is that the position of a missile fired at MISSILE_SPEED, straight up, after 0.208 seconds, should be equal to the position of the ship at that same time. So:

    def test_time_to_target_harder(self):
        gunner = Gunner(10)
        time = gunner.time_to_target(Vector2(0, 50), Vector2(0, 10))
        missile_position = u.MISSILE_SPEED * time
        ship_distance = 10*time
        ship_position = 50 + ship_distance
        assert missile_position == ship_position

This passes. New test: a speed greater than or equal to MISSILE_SPEED should return zero as impossible.

    def test_time_to_target_impossible(self):
        gunner = Gunner(10)
        time = gunner.time_to_target(Vector2(0, 50), Vector2(0, u.MISSILE_SPEED))
        assert time == 0

This finds a bug, division by zero. Internet code doesn’t check for the case.

    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:
        	# changes below here
            divisor = (math.sqrt(disc) - b)
            if divisor:
                return 2*c / divisor
            else:
                return 0

This is incredibly unlikely but could happen. And did.

    def test_time_to_target_long(self):
        gunner = Gunner(10)
        time = gunner.time_to_target(Vector2(0, 50), Vector2(0, u.MISSILE_SPEED - 1))
        assert time == 50

These tests are all straight-line shots. If the velocity is not straight away, I don’t know how to predict the answer other than by hand-calculating the equation, which is pointless. It is what it is.

We could test that the aiming point is the adjusted position of the ship at the time to target, but the code is direct, so I don’t see the point.

N.B.: I could be wrong here. There may be a test that we could write that actually gives us a bit of confidence. Note made.

Adjusting the missile speed back to the original SPEED_OF_LIGHT/3, I find the need to use approx again.

    def test_time_to_target_harder(self):
        gunner = Gunner(10)
        time = gunner.time_to_target(Vector2(0, 50), Vector2(0, 10))
        missile_position = u.MISSILE_SPEED * time
        ship_distance = 10*time
        ship_position = 50 + ship_distance
        assert missile_position == pytest.approx(ship_position)

I have not yet studied approx but a quick read tells me that it defaults to one part in a million. I’ll read further and report back if it’s interesting, at some future time or never.

These are not great tests and I freely grant that I do not understand why that particular code computes what we want. So I am not happy about leaving it in, but I like how it works and it seems never to be worse than firing randomly. (How could it be?)

I’ll review my diffs and commit this: Saucer now uses mysterious quadratic targeting which seems nearly good. Should take radius into account for even more demonic results.

Let’s wrap up.

Summary

After porting in the quadratic code that returns ideal time to target, I refactored it down to its nubbins and then wrote some elementary tests against it. There is no test for the true quadratic nature of the solution. It would be easy to write one and set the answer into the asserts, which would catch changes in the code but would not give me any more certainty than I now have that it’s actually correct, except that we should adjust for the saucer radius. One way to do that would be to make the saucer impervious to its own missiles …

I think the Gunner code could use some further refactoring. We now decide way too soon where to aim … we’re deciding, at some small expense, 60 times a second, before we even know whether we can fire at all. We should push the optimization code down a bit further down into the less frequently running code. We’ll save that for some future session.

So. A nice little feature, installed with what seems to me to be decent accuracy, but not ideal positioning, and a little less testing than I’d like. But I am satisfied.

It’s unusual for me to adopt code from the Internet: I like figuring things out. But this one wasn’t quite within the reach of what I could write on a card, so at least for now it will do the job.

Clearly I would do well to learn a bit more about pytest. I’ll put that on my list of things to do.

See you next time!