Kotlin 185: Better Targeting

GitHub Repo

Yes, I know there’s a closed-form solution for targeting. Let’s see if there’s something simpler. But first, a bit more safety.

I had occasion to be at the computer yesterday, and was playing the game, when something truly irritating happened. It turns out that when the Ship has just been destroyed, it has already set its location to the center of the screen. So, it turns out that if the saucer is still flying and firing, it will fire at universe center because, if I recall, it isn’t checking to see if the ship actually exists, just checks to see where it is. So my ship got killed somehow, and rematerialized at the center of the screen just in time to be hit by a saucer missile. Rude!

There is a safety check before emergence from having been killed. (There is no safety check if you’re emerging from hyperspace. Things are tough in hyperspace.) So, I fiddled with the safety code a bit to make it better. I think we can do better still, but here it is now:

class ShipMaker ...
    override val subscriptions = Subscriptions (
        beforeInteractions = {
            safeToEmerge = true
            asteroidTally = 0
            missileTally = 0
        },
        interactWithMissile = { _, _ -> safeToEmerge = false },
        interactWithAsteroid = { asteroid, _ ->
            asteroidTally += 1
            safeToEmerge = isAnythingInTheWay(asteroid)
        },
        interactWithSaucer = { saucer, _ ->
            safeToEmerge = isAnythingInTheWay(saucer)
        },
        afterInteractions = { trans->
            if (ship.inHyperspace || elapsedTime > U.MAKER_DELAY && safeToEmerge) {
                replaceTheShip(trans)
            }
        }
    )


    private fun isAnythingInTheWay(collider: Collider) = safeToEmerge && !tooClose(collider)

    private fun tooClose(collider: Collider): Boolean {
        return ship.position.distanceTo(collider.position) < U.SAFE_SHIP_DISTANCE
    }

Why is that missileTally there? Well, at one point, for reasons I cannot explain, I was counting the missiles and then at the end deciding whether to emerge based on count > 0. Not too bright, we can just set the safeToEmerge flag false if we see a missile. The idea is to wait until there are no missiles. So let’s remove that line.

We want the asteroidTally because it is a factor in deciding whether hyperspace is fatal.

But let’s do one more thing. Let’s not emerge when the saucer is present. That’s an easy addition, using the same pattern. Instead of this:

    interactWithSaucer = { saucer, _ ->
        safeToEmerge = isAnythingInTheWay(saucer)
    },

We’ll just set it to false. As written, that code checks to see if we are close to the saucer. We want to wait until it goes away.

    interactWithSaucer = { _, _ ->
        safeToEmerge = false
    },

That should do it. I’ll try it in the game but I’m wondering whether there’s any easy way to test this logic.

The game play works. Since I am so terrible at playing the game, it doesn’t take long for me to encounter a situation where I’m dead and the saucer is on the screen.

What would a test for this look like? Well, let’s try something …

I do have a test and I think we can use it or improve it:

    @Test
    fun `asteroid or saucer clears safeToEmerge`() {
        val ship = Ship(
            position = U.CENTER_OF_UNIVERSE
        )
        val asteroid = Asteroid(U.CENTER_OF_UNIVERSE)
        val saucer = Saucer()
        saucer.position = U.CENTER_OF_UNIVERSE
        val maker = ShipMaker(ship)
        val ignored = Transaction()
        maker.subscriptions.beforeInteractions()
        assertThat(maker.safeToEmerge).isEqualTo(true)
        maker.subscriptions.interactWithAsteroid(asteroid, ignored)
        assertThat(maker.safeToEmerge).isEqualTo(false)
        maker.subscriptions.beforeInteractions()
        assertThat(maker.safeToEmerge).isEqualTo(true)
        maker.subscriptions.interactWithSaucer(saucer, ignored)
        assertThat(maker.safeToEmerge).isEqualTo(false)
    }

Let’s first just add a missile check:

        maker.subscriptions.beforeInteractions()
        assertThat(maker.safeToEmerge).isEqualTo(true)
        maker.subscriptions.interactWithMissile(missile, ignored)
        assertThat(maker.safeToEmerge).isEqualTo(false)

Test, should be green. Yes. Now let’s at least split that test into three for clarity.

    @Test
    fun `asteroid clears safeToEmerge`() {
        val ship = Ship(U.CENTER_OF_UNIVERSE)
        val asteroid = Asteroid(U.CENTER_OF_UNIVERSE)
        val maker = ShipMaker(ship)
        val ignored = Transaction()
        maker.subscriptions.beforeInteractions()
        assertThat(maker.safeToEmerge).isEqualTo(true)
        maker.subscriptions.interactWithAsteroid(asteroid, ignored)
        assertThat(maker.safeToEmerge).isEqualTo(false)
    }

    @Test
    fun `saucer clears safeToEmerge`() {
        val ship = Ship(U.CENTER_OF_UNIVERSE)
        val saucer = Saucer()
        saucer.position = U.CENTER_OF_UNIVERSE
        val maker = ShipMaker(ship)
        val ignored = Transaction()
        maker.subscriptions.beforeInteractions()
        assertThat(maker.safeToEmerge).isEqualTo(true)
        maker.subscriptions.interactWithSaucer(saucer, ignored)
        assertThat(maker.safeToEmerge).isEqualTo(false)
    }

    @Test
    fun `missile clears safeToEmerge`() {
        val ship = Ship(U.CENTER_OF_UNIVERSE)
        val missile = Missile(Point.ZERO)
        val maker = ShipMaker(ship)
        val ignored = Transaction()
        maker.subscriptions.beforeInteractions()
        assertThat(maker.safeToEmerge).isEqualTo(true)
        maker.subscriptions.interactWithMissile(missile, ignored)
        assertThat(maker.safeToEmerge).isEqualTo(false)
    }

Much better. Now you have a chance of figuring out what’s going on. Green. Commit: Ship will not respawn until saucer and missiles are gone, and no asteroids too close.

I thought of having the saucer not emerge when the ship is gone but I like the effect when in GAME OVER, where the saucer comes out and shoots down asteroids while you wait, so we’ll leave that as it is.

Now then, what about targeting?

Targeting

The present scheme for targeting is that when we shoot a targeted missile from the Saucer, we aim directly at the ship:

    private fun fireTargeted(trans: Transaction) {
        timeSinceLastMissileFired = 0.0
        val directionToShip = (shipPosition - position)
        val heading = atan2(y = directionToShip.y, x = directionToShip.x).asDegrees
        val missile = Missile(position, heading, killRadius, Velocity.ZERO, ColorRGBa.RED)
        trans.add(missile)
    }

Since missiles are fired according to our “heading”, adjusting heading is all that’s really needed to aim the missile. An issue is, of course, if the ship is moving, that point we aimed at is guaranteed not to be where the ship will be when the missile gets there. We can still score a hit, depending on how the ship is moving, but generally we’ll miss.

I’ve done my research on hitting moving targets and the usual idea is this:

Imagine that you fire in all directions at once. Consider the circle formed by the missiles as they expand away from the Saucer at missile velocity. Consider the line traced by the Ship if it moves at its current velocity. As time t increases, the circle gets larger and the line gets longer. If the circle and the line ever intersect, that point is t seconds away from the ship i ship time, and t seconds away from the saucer in missile time. Therefore they will collide. Therefore aim and fire at that point.

The math for this is extensive and easy to get wrong. You need to set up a system of equations, and factor around for a while. Finally you come down to a quadratic equation in time, with coefficients equal to sums and products of the x and y velocities of the ship and missile and their x and y positions. If you get all the coefficients right, and solve the quadratic, it will give you a firing solution if there is one.

I don’t want to do that, and I’m pretty sure that Atari didn’t do that on the tiny processor they had in the Asteroids box. I want a simpler solution.

Now i just checked what I do in the Lua Asteroids that I wrote a while back:

function SaucerMissile:aimedFromSaucer(saucer, ship)
    local gunPos = saucer.pos
    local tgtPos = ship.pos + ship.step*120
    local toTarget = tgtPos - gunPos
    local ang = vec2(1,0):angleBetween(toTarget)
    local bulletStep = vec2(saucer.shotSpeed, 0):rotate(ang)
    return SaucerMissile(gunPos, bulletStep)
end

What this code does is predict where the ship will be in two seconds (120 sixtieths) and aim there. Not an entirely bad idea. I was thinking along similar lines for this game, before looking there. I was thinking, first of an iterative solution and then of just iterating once. It would go like this:

Get the missile time to the present position of the ship. Compute where the ship will be in that amount of time. If the missile time to that location is close enough to the same, fire there. Otherwise, iterate the process for positions near that location.

I managed to remember one little glitch: the missile doesn’t start at the Saucer, it starts outside the kill radius of the saucer, so its flight time should be calculated from that point. Shouldn’t be a problem, the difference is a constant, the flight time of a missile over the offset difference.

There are complicating issues, including:

• If the ship is further away than missile flight time, a shot may be useless. (But it could be coming toward us …)
• If the ship is too far away, a short over the border might be better. Imagine Saucer at (100,100) and ship at (100, 900). It’s 800 away for a direct shot, but it’s only 200 away if we fire vertically.

Let me grab an envelope to do some rough calculations.

Curiously enough, Missile speed is not yet in the universal constants. It’s here:

val missileOwnVelocity = Velocity(U.SPEED_OF_LIGHT / 3.0, 0.0).rotate(shooterHeading)

Let’s create the constant

object Universe
    const val MISSILE_SPEED = SPEED_OF_LIGHT / 3.0

class Missile
        val missileOwnVelocity = Velocity(U.MISSILE_SPEED, 0.0).rotate(shooterHeading)

So the missile lives for … oh, wow this needs to be promoted as well:

    private val timeOut = OneShot(3.0) {
        it.remove(this)
        it.add(Splat(this))
    }

That 3.0 needs to be

    const val MISSILE_LIFETIME = 3.0

And we need to use it in the OneShot:

    private val timeOut = OneShot(U.MISSILE_LIFETIME) {
        it.remove(this)
        it.add(Splat(this))
    }

Both of those changes are tested and committed. As I was saying, the missile lives for 3 seconds and travels at Light/3, or one light second, or 500 units. (Speed of light is 500.) (Should we make that 512? Why, other than some numerological reason?) Anyway it is about half a universe.

Suppose we consider dx to be the distance from saucer to ship in x and dy the distance in y. (Maybe from saucer plus that firing offset.) If dx or dy is greater than 500 (by some margin), we’ll do better to fire across the border. Maybe we shouldn’t worry about that. Let’s just think about firing at a given point.

What point should we fire at? Since the universe is a torus (donut shape), there are 8 adjacent cells, plus our own, that we could fire at that would eventually hit the target, if the missile flew far enough. We won’t consider the next ring of cells, they are invariably worse.

Assume the target is stationary and also not moving. Furthermore, assume that it is staying in one place. In one of those nine cells, the target is closest to us. That’s the one we should fire at. Given that the coordinates of the actual target are (x,y), what are the nine possible points where we might aim?

Hmm. This is interesting. Setting aside the projection into the future, if we were merely to select from these possibilities when we aim, instead of just using “actual”, we could fire over the border with better chances of hitting the ship.

Can we select independently, or must we check all nine? I think we can check independently.

Let’s spike this. No … let’s do a little test. I start with this much:

fun preferred(shooter: Int, target: Int) : Int {
    return target
}

class TargetingTest {
    @Test
    fun `closest x coordinate`() {
        val shooterX = 100
        val targetX = 200
        val preferredX = preferred(shooterX, targetX)
        assertThat(preferredX).isEqualTo(200)
    }
}

Now, as practice, let’s do lots of tiny tests.

    @Test
    fun `left better`() {
        assertThat(preferred(100, 900)).isEqualTo(-124)
    }

This goes red. We need to improve preferred. Hm, this is actually a bit tricky. I think I need to compare the absolute values of the distances.

I convert to Doubles, because we’re going to go there and Kotlin / IDEA are more able to provide me with the imports that I want.

fun preferred(shooter: Double, target: Double) : Double {
    val actualDist = abs(target-shooter)
    val leftDist = abs(target-1024 - shooter)
    if ( actualDist < leftDist ) return target
    else return target-1024
}

fun preferred(shooter: Int, target: Int): Double {
    return preferred(shooter.toDouble(), target.toDouble())
}

Green so far. Try the other direction:

    @Test
    fun `right better`() {
        assertThat(preferred(1000, 100)).isEqualTo(1124.0)
    }

And in preferred:

fun preferred(shooter: Double, target: Double) : Double {
    val actualDist = abs(target-shooter)
    val leftDist = abs(target-1024 - shooter)
    val rightDist = abs(target+1024 - shooter)
    if (leftDist < actualDist) return target-1024
    else if (rightDist < actualDist) return target+1024
    else return target
}

That runs green. I think it’s correct, but I don’t like how it reads. Would it be better with more extracts?

fun preferred(shooter: Double, target: Double) : Double {
    val actualDist = abs(target-shooter)
    val leftDist = abs(leftTarget(target) - shooter)
    val rightDist = abs(rightTarget(target) - shooter)
    if (leftDist < actualDist) return leftTarget(target)
    else if (rightDist < actualDist) return rightTarget(target)
    else return target
}

private fun rightTarget(target: Double) = target + 1024

private fun leftTarget(target: Double) = target - 1024

No, that’s worse, I think.

Extract constants?

fun preferred(shooter: Double, target: Double) : Double {
    val lowerTarget = target - 1024
    val higherTarget = target + 1024
    val actualDistance = abs(target-shooter)
    val lowerDistance = abs(lowerTarget - shooter)
    val higherDistance = abs(higherTarget - shooter)
    if (lowerDistance < actualDistance) return lowerTarget
    else if (higherDistance < actualDistance) return higherTarget
    else return target
}

Better, I think. Let’s try this:

fun preferred(shooter: Double, target: Double) : Double {
    val lowerTarget = target - 1024
    val higherTarget = target + 1024
    val actualDistance = abs(target-shooter)
    val lowerDistance = abs(lowerTarget - shooter)
    val higherDistance = abs(higherTarget - shooter)
    return when {
        lowerDistance < actualDistance -> lowerTarget
        higherDistance < actualDistance -> higherTarget
        else -> target
    }
}

Yes, I like that, I think. Commit:

Now let’s make a function that, given two points, a shooter and a target, returns a new target vector that optimizes both x and y. We need a test.

    @Test
    fun `optimize point target`() {
        val shooter = Point(100.0, 1000.0)
        val target = Point(900.0, 100.0)
        val optimized = optimizeShot(shooter, target)
        assertThat(optimized).isEqualTo(Point(-124.0, 1124.0))
    }

That is easy to implement:

fun optimizeShot(shooter: Point, target:Point): Point {
    return Point(preferred(shooter.x,target.x), preferred(shooter.y,target.y))
}

We are green. Commit: TargetingTest implements optimizeShot.

Nice. I’d like to plug this into the Saucer. Let’s just move the whole kit into its own Kotlin file. I could imagine that we want it implemented on Point, but that’s not really a class, it’s just a type alias.

Could we maybe make it an object? A ShotOptimizer? Let’s try that, in place in the test.

Yes:

object ShotOptimizer {
    fun preferred(shooter: Double, target: Double): Double {
        val lowerTarget = target - 1024
        val higherTarget = target + 1024
        val actualDistance = abs(target - shooter)
        val lowerDistance = abs(lowerTarget - shooter)
        val higherDistance = abs(higherTarget - shooter)
        return when {
            lowerDistance < actualDistance -> lowerTarget
            higherDistance < actualDistance -> higherTarget
            else -> target
        }
    }

    fun optimizeShot(shooter: Point, target: Point): Point {
        return Point(preferred(shooter.x, target.x), preferred(shooter.y, target.y))
    }

    fun preferred(shooter: Int, target: Int): Double {
        return preferred(shooter.toDouble(), target.toDouble())
    }
}

class TargetingTest {
    @Test
    fun `closest x coordinate`() {
        val shooterX = 100.0
        val targetX = 200.0
        val preferredX = ShotOptimizer.preferred(shooterX, targetX)
        assertThat(preferredX).isEqualTo(200.0)
    }

    @Test
    fun `left better`() {
        assertThat(ShotOptimizer.preferred(100, 900)).isEqualTo(-124.0)
    }

    @Test
    fun `right better`() {
        assertThat(ShotOptimizer.preferred(1000, 100)).isEqualTo(1124.0)
    }

    @Test
    fun `optimize point target`() {
        val shooter = Point(100.0, 1000.0)
        val target = Point(900.0, 100.0)
        val optimized = ShotOptimizer.optimizeShot(shooter, target)
        assertThat(optimized).isEqualTo(Point(-124.0, 1124.0))
    }
}

Now IDEA will move that for me. Move to ShotOptimizer in the main source root.

Tests are green. Commit: ShotOptimizer object now in main source root.

Now for fun let’s modify Saucer to use optimized targets and to fire for effect every time. I want to see this on the screen.

    private fun fireTargeted(trans: Transaction) {
        timeSinceLastMissileFired = 0.0
        val targetPosition = ShotOptimizer.optimizeShot(position, shipPosition)
        val directionToShip = (targetPosition - position)
        val heading = atan2(y = directionToShip.y, x = directionToShip.x).asDegrees
        val missile = Missile(position, heading, killRadius, Velocity.ZERO, ColorRGBa.RED)
        trans.add(missile)
    }

    private fun fire(trans: Transaction) {
        if (Random.nextInt(4) < 4 ) fireTargeted(trans)
        else fireRandom(trans)
    }

For better viewing, I also turn off the asteroids.

This is working. I’ll try to get a video of it, though it’s a bit hard to set up.

Now you can see in the video that even if the ship is moving the least little bit, the missiles tend to miss. Of course, that’s because we’re not projecting the ship position forward.

What if we were to project the ship position forward by a constant, maybe the same two seconds used in the Lua game? Easily done. We’ll have to save the ship, not just its position, in Saucer:

class Saucer
    private var ship: Ship? = null

        interactWithShip = { shipSeen, trans ->
            ship = shipSeen
            checkCollision(ship!!, trans) },

    private fun fireTargeted(trans: Transaction) {
        timeSinceLastMissileFired = 0.0
        if (ship != null ) {
            val futureShipPosition = ship!!.position + ship!!.velocity*2.0
            val targetPosition = ShotOptimizer.optimizeShot(position, futureShipPosition)
            val directionToShip = (targetPosition - position)
            val heading = atan2(y = directionToShip.y, x = directionToShip.x).asDegrees
            val missile = Missile(position, heading, killRadius, Velocity.ZERO, ColorRGBa.RED)
            trans.add(missile)
        }
    }

I might prefer to do that differently, but this should be interesting as it stands. It works better: now it hits the ship more often, even when it is moving. Why doesn’t it always hit? Because the travel distance isn’t always 2 seconds. Let’s do this differently.

We’ll pick the target position first, then project it and aim there.

    private fun fireTargeted(trans: Transaction) {
        timeSinceLastMissileFired = 0.0
        if (ship != null ) {
            val targetPosition = ShotOptimizer.optimizeShot(position, ship!!.position)
            val travelDistance = targetPosition.distanceTo(position)
            val travelTime = travelDistance/U.MISSILE_SPEED
            val futureTargetPosition = targetPosition + ship!!.velocity*travelTime
            val directionToShip = (futureTargetPosition - position)
            val heading = atan2(y = directionToShip.y, x = directionToShip.x).asDegrees
            val missile = Missile(position, heading, killRadius, Velocity.ZERO, ColorRGBa.RED)
            trans.add(missile)
        }
    }

This is better, but it’s still far from perfect. If I crank the missile speed up, it gets deadly accurate. If I set missile speed to 3 times light speed, it hits me on the first shot almost mo matter what I do.

Amusing and informative. Given that the ship is moving at a constant speed, why do we miss? It must be because the new travel time, to the projected point, is not the same as the time we used to project. And it wouldn’t be, unless we were traveling at a very specific angle to the saucer, essentially returning to the same distance from it that we were when the calculation was made. In terms of the circle model I tale about above, it’ll hit us if we intersect the imaginary circle of radius flight-time, right at time = flight-time.

Odds are not good. Oh, wait … before we do anything else, I forgot to adjust for the fact that the missile starts a bit away from the saucer. We start at 2*(shooter kill radius + missile kill radius).

That value is 10, um, space distance units. That will translate to pixels, and it may seem small, but let’s factor it in anyway.

    val travelDistance = targetPosition.distanceTo(position) - 2*(U.KILL_MISSILE + U.KILL_SAUCER)

That might be slightly better, but it’s hard to tell.

What if we did this? What if could iterate a couple of times? Let’s think about the timing.

We get the time to target at the time of firing (now). We project the ship’s position that many seconds. Now there are three cases: we hit it, that is, the new time to target is still the same, or the tie to target is now less than it was, or, of course, it might be greater.

If it’s greater, then the ship is moving away from us. We cannot hit it because it’s outside the expanding circle of fire. If it’s less, then the ship is moving toward us, but it will be inside our range for a while. We can’t hold our fire: we must fire now. If we fire at a wider angle than the current estimate, we might find that the ship crosses our radius again. (It seems that it must: it’s inside the circle.)

We’re back to a quadratic, if we’re not careful. We want an approximation. I wish I remembered Newton’s method perfectly. (I could look it up but fact is I’m looking for something more naive.)

We need only consider missile flight time between 0 and MISSILE_LIFETIME. As a function of time, let’s compute (for “all” values of t):

1. S(t), the position of the ship at time t;
2. D(t), the distance from firing point to S(t), including the fudge factor;
3. M(t), the time the missile needs to get to S(t), namely D(t)/MISSILE_SPEED.
4. If M(t) equals T, we should aim at S(t).

So we know that at t = 0, M(t) is greater than t (unless we are sitting on the ship).

I undergo several significant interruptions, disrupting my thoughts. I decide to write a sort of test, winding up with this after some futzing and refining to help me understand.

    @Test
    fun `approximations`() {
        val S = Point(4.0, 4.0)
        val Vs = Velocity(1.0,-2.0)
        val M = Point(0.0, 0.0)
        val Sm = 3.0
        var t = 0.0
        while (t <= 3.0 ) {
            approximate(S, Vs, t, M, Sm)
            t += 0.5
        }
        assertThat(2).isEqualTo(1)
    }

    private fun approximate(
        S: Point,
        Vs: Velocity,
        t: Double,
        M: Point,
        Sm: Double
    ) {
        val St = S + Vs * t
        val Dt = M.distanceTo(St)
        val Mt = Dt / Sm
        println("At time $t, ${status(t, Mt)}, missile time = $Mt, S at $St")
    }

    private fun status (t1:Double, t2: Double): String {
        if (t1==t2) return "perfect"
        if (t1<t2) return "slow"
        return "fast"
    }

That prints this:

At time 0.0, slow, missile time = 1.885618083164127, S at Vector2(x=4.0, y=4.0)
At time 0.5, slow, missile time = 1.8027756377319948, S at Vector2(x=4.5, y=3.0)
At time 1.0, slow, missile time = 1.7950549357115013, S at Vector2(x=5.0, y=2.0)
At time 1.5, slow, missile time = 1.863389981249825, S at Vector2(x=5.5, y=1.0)
At time 2.0, perfect, missile time = 2.0, S at Vector2(x=6.0, y=0.0)
At time 2.5, fast, missile time = 2.1921577396609844, S at Vector2(x=6.5, y=-1.0)
At time 3.0, fast, missile time = 2.4267032964268394, S at Vector2(x=7.0, y=-2.0)

Comparing the two times, if pure time < how long it’ll take the missile to go that far, we’re too slow (should have fired sooner). If t is greater than missile time, we fired too soon, and the missile will be past the ship by the time it gets to that point. And, of course, if they’re equal, we’re good.

This sketch doesn’t include the offset reduction, nor does it consider the damage radii. There’s actually a fairly wide window of time when we can kill the ship, basically the time it take the missile to fly a ship diameter, or about a distance of 48. At speeds of 166, that’s about a quarter of a second leeway.

Can we now approximate this? Thinking about the numbers, there are a number of cases to consider. In many of them there is no firing solution: the ship is too far away and never gets close enough. (Close enough means that there is a time t between 0 and MISSILE_LIFETIME such that the distance between the missile and the ship is less than the kill distance, KILL_SHIP + KILL_MISSILE).

We could certainly just search along the lime at a sufficiently small screen. A better thing to do would be to do a more directed search, sort of a binary chop or newton kind of thing. What can we say about that?

Well, if t < Mt (slow), we need t to increase. If t > Mt (fast), we need t to decrease.

Let’s try some truly brute force. I just want to know if this makes any sense at all. I can’t quite see my way to the end of it. Probably I should be able to, and maybe with more time on paper and less here at my desk, I could. but what if we just generated all the pairs of times at some tiny mesh size, and picked the best one?

Let’s do a bit more spiking. This a a crock but interesting:

    private fun fireTargeted(trans: Transaction) {
        timeSinceLastMissileFired = 0.0
        val timeStep = 0.01
        var time = 0.0
        var bestPosition  = ship!!.position
        var bestError = Double.MAX_VALUE
        while (time <= U.MISSILE_LIFETIME) {
            val futureTargetPosition = ship!!.position + ship!!.velocity*time
            val optimalPosition = ShotOptimizer.optimizeShot(position, futureTargetPosition)
            val distance = optimalPosition.distanceTo(position)
            val travelTime = distance/U.MISSILE_SPEED
            val error = abs(time-travelTime)
            if (error < bestError) {
                bestPosition = optimalPosition
                bestError = error
            }
            time += timeStep
        }
        val accept = 0.01
        if (bestError < accept) println(bestError)
        val color = if (bestError < accept)  ColorRGBa.RED else ColorRGBa.GREEN
        val directionToShip = bestPosition - position
        val heading = atan2(y = directionToShip.y, x = directionToShip.x).asDegrees
        val missile = Missile(position, heading, killRadius, Velocity.ZERO, color)
        trans.add(missile)
    }

What this does is increment time in 0.01 second intervals, and picks the best error value (difference between time and time to target) and fires at that position. If the error is small, also 0.01, it colors the missile red, signifying that it expects a hit, otherwise sets it green.

Generally speaking, if the ship is moving at a constant speed, the first red missile kills it. But what confuses me is the setting of red vs green. For example, When the ship is not moving, I’d expect the firing solution to be exact and for all the colors to be red. That’s not the case: when the ship is motionless all the missiles are green.

A bit of thinking, then I need a break. No, I just need a break. Flush these changes, get back to wherever we were. The spike has taught me whatever it’s going to, and I need to think about it.

Tuesday 0815

Well. Here we are. We are back to the saucer firing directly at the Ship in fireTargeted:

    private fun fireTargeted(trans: Transaction) {
        timeSinceLastMissileFired = 0.0
        val directionToShip = (shipPosition - position)
        val heading = atan2(y = directionToShip.y, x = directionToShip.x).asDegrees
        val missile = Missile(position, heading, killRadius, Velocity.ZERO, ColorRGBa.RED)
        trans.add(missile)
    }

I checked out the original Asteroids assembly code, and to the best of my understanding, all it does to fire an accurate missile is to aim directly at the Ship. We’ve emulated that. The original only knows about 17 angles in every 90 degree sector, so we’re more accurate than that. It does, however, shoot over the borders. I had that working with the ShotOptimizer, and I saved those tests and code. Let’s settle for this:

1. Project the ship position a bit forward, maybe 1.5 seconds, in the mid range of our missile flight time.
2. Shoot at that point, optimizing for crossing borders if that’s closer.

Let’s do that and then talk about “settling”.

I recall that our present code saves the ship, not its position. But if we only want its future position, let’s just save that instead. Rename the member.

    private var shipFuturePosition = Point.ZERO

Assign it:

interactWithShip = { ship, trans ->
            shipFuturePosition = ship.position + ship.velocity*1.5
            checkCollision(ship, trans) },

Add the optimizer call:

    private fun fireTargeted(trans: Transaction) {
        timeSinceLastMissileFired = 0.0
        val targetPosition = ShotOptimizer.optimizeShot(position, shipFuturePosition)
        val directionToShip = (targetPosition - position)
        val heading = atan2(y = directionToShip.y, x = directionToShip.x).asDegrees
        val missile = Missile(position, heading, killRadius, Velocity.ZERO, ColorRGBa.RED)
        trans.add(missile)
    }

Quick game play shows me that this is working as intended. It shoots over the border when that’s a shorter shot, and it’s aimed at me fairly well. It’s definitely leading me. I’m tempted to have it lead by the full three second missile time, on the grounds that the odds are better that the saucer and ship will be far apart. We’ll let this ride for now.

What about tests? We have a sufficient test for the ShotOptimizer, did that yesterday, but we have no real test for the new algorithm. I do have that one “test” that was running the approximation spike. I think I’ll scrap that on the grounds that even if I do enhance targeting, I’ll do it more cleverly next time. No real point even saving this experiment. Poof, gone.

Now let’s do at least one test of the fireTargeted function.

Let’s have a test with the Ship near the top left corner and the Saucer near bottom left. We’ll give the ship a simple velocity, because if the test works, we’ll know that we picked up the velocity. I think I’d like to check the saucer’s selection of target, not the missile’s settings. Let’s refactor a bit:

    private fun fireTargeted(trans: Transaction) {
        timeSinceLastMissileFired = 0.0
        val targetPosition = getTargetPosition()
        val directionToShip = (targetPosition - position)
        val heading = atan2(y = directionToShip.y, x = directionToShip.x).asDegrees
        val missile = Missile(position, heading, killRadius, Velocity.ZERO, ColorRGBa.RED)
        trans.add(missile)
    }

    fun getTargetPosition() = ShotOptimizer.optimizeShot(position, shipFuturePosition)

As soon as I look at this, I realize that I need to test that the Saucer is tracking the Ship’s future position correctly. OK, we’ll do that as well. Let’s start the test:

    @Test
    fun `saucer records ship future position`() {
        val saucer = Saucer()
        saucer.position = Point(900.0,900.0)
        val ship = Ship(Point(100.0, 100.0))
        ship.velocity = Velocity(10.0, 0.0)
        saucer.subscriptions.interactWithShip(ship, Transaction())
        assertThat(saucer.shipFuturePosition).isEqualTo(Point(115.0, 100.0))
    }

That’s green. No surprise to me other than that I got the test right. Now for targeting:

    @Test
    fun `saucer fires across border`() {
        val x = 100.0
        val y = 50.0
        val saucer = Saucer()
        saucer.position = Point(900.0,900.0)
        val ship = Ship(Point(x,y))
        saucer.subscriptions.interactWithShip(ship, Transaction())
        val target = saucer.getTargetPosition()
        assertThat(target).isEqualTo(Point(x + 1024.0, y + 1024.0))
    }

Green. I think we’ll commit this version. Commit: Improved saucer targeting to shoot over borders if needed and to lead ship by 1.5 seconds.

Now let’s reflect on what we’ve done, and “settling”.

Reflection: Settling?

I freely grant that I was hoping I could come up with a simple approach to improved targeting that didn’t involve solving the quadratic. I’d have been OK with a simple iterative search for a firing solution, and I do think one is possible, but as yet, I don’t see it.

If we really wanted a perfect solution, we’d do the math, generate the quadratic, and solve it. The hard part is doing the math, because it involves a truly fascinating array of values, velocities, points, and times. Look up some of the articles on hitting a moving target and you’ll see what I mean. It’s not difficult math, there’s just a lot of it and we have to get all the products and signs right, to plug into your quadratic solver. Ultimately, we could do that. I’m sure there would be sign errors and other omissions along the way, but we could do it.

To me, a partial solution like the one we have is more in the spirit of the old game on a small processor. Even as things stand, we’ve got vector arithmetic, sines and cosines, and all that jazz, while the original had two-byte integers and looked up its trig in a table of numbers. I’m pretty sure the snow was three feet deep and they had to walk five miles to work, uphill both ways.

So I am a bit sad that I haven’t thought of anything more clever than a fixed lead. It seems like you could pick a lead, check it, adjust it a few times, and have a better one, but so far I don’t quite see the trick to knowing which way to adjust the estimate and by how much. I could of course look up Newton-Raphson and some of the other approximation techniques, and could of course figure out the slope of the weird curve traced by an object flying by, but I don’t want to. I want to find a sort of simple almost silly insight that can be coded up in a few adds and multiplies, maybe a divide if we’re feeling tough, with a better estimate coming out.

Yesterday’s final experiment, where I calculated almost every possible aiming point and picked the best one, shows that some kind of approximation is possible. I’ll think about it and maybe I’ll come up with it.

But we’re already past the requirements, which are, in essence, “Do it like Asteroids”. So I’m happy enough, for now.

There’s a lot to like. I like the implementation. I like the separate little ShotOptimizer object. I like that there are more tests for more cases. I’m pleased that it occurred to me to save the ship’s future position rather than compute it in the firing solution. I think it’s just a bit neater that way, since we have access to the ship velocity at that point. Better than saving the ship, in my view, as it limits our access to bad things.

What don’t I like? Well, I really miss the sound, and I’m resisting doing it because I know it’s going to be a pain to get set up, given my general weakness with the Java world and the IntelliJ ecology. Yeah, probably only a few hours of hassle, but I’m just not up for it.

What else? I suspect that the Saucer should vanish when the ship is killed. THat would make the return happen sooner, since there would be fewer missiles flying about. That should be a simple enough change to the Saucer. Maybe next time.

On my sticky notes on the desktop I have notes like:

• Allow window size other than 1024;
• Allow non-square window?
• Small saucer;
• Variable asteroid speed

Where’s that list of features? I should install Jira here at my house. Ah, here is it, updated:

Priority = H/M/L; Done = √; Internal Improvement = (i)

• √ Ship exhaust flare
• √ Ship turning seems a bit slow. 180->200. Accuracy seems fine.
• √ Ship acceleration seems sluggish. (1000 -> 1200)
• √ Hyperspace return away from edges for visibility.
• √ Check general scale of ship etc against original.
• H Ship should slow à la friction.
• H Sound???
• H Small saucer (1000 points) appears after 30,000 points.
• H Small saucer shot accuracy improves. (Needs research.)
• M Add a sun with gravity?
• M (i, more to do) Improve generality of graphics, stroke width vs scale etc.
• √ (i, more to do) Eliminate magic numbers, moving to Universe.
• M Ability to change some settings from keyboard (cheat codes)
• M (i) Timing code could be improved to be more consistent. OneShot?
• L Some write-ups say that small asteroids are faster. (Needs research)
• L Saucer zig-zagging could be a bit more random.
• L Allow for non-square windows?

Some improvement on that list. We’ll re-prioritize in a few days. For now, I think we’re good.

See you next time!