GitHub Repo

While I muse about a different design, there are a few things that we need to do, and I need something to distract myself. Things go oddly but turn out OK. Details in Summary.

Here’s a copy of my file JIRA.md:

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

  • 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?
  • √ (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?

  • √ 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.
  • √ (i, more to do) Improve generality of graphics, stroke width vs scale etc.
  • √ (i, more to do) Eliminate magic numbers, moving to Universe.
  • √ Saucer does not fire when ship is absent

Study of the original Asteroids

In my study of the original assembly code for Asteroids, I’ve learned some interesting new things, including:

  • There can only be at most 17 asteroids at a time. I’m not sure how the code enforces that.
  • The ship can only have four shots flying at a time. I believe but am not certain that you have to wait for a shot to finish before you can fire another.
  • The saucer can only have one shot at a time. I’m tempted to implement that right now, because firing all over the way it does, the saucer is a problem for me.

I’ve also been studying the hit detection logic and have this much tentatively figured out:

The hit detection is done in two loops. The outer loop loops over the bullets, the saucer, and the ship, which are all adjacent in memory. This amounts to seven array entries, five bullets, ship and saucer. The inner loop loops over ship, saucer, and all the asteroids: the asteroids follow the saucer in memory.

So the hit detection code has two entries in mind. The first is a bullet, the ship, or the saucer. The second is the ship, the saucer, or an asteroid. I am not clear at this point on just how it handles the case of ship as object and ship as object 2. It may be bumping the second index, or just comparing.

Then there is a long chunk of tricky branching and skipping code, including one bit that is there to avoid doing the same collision twice, as could happen with ship-saucer and saucer-ship. There is special handling for the cases of what has hit what. The ship is set to “exploding”, for example, by setting an explosion counter positive in one of its fields. I think bullets are just cleared. Asteroids get split and scored. I haven’t looked at the details of scoring to see how it handles the question of whether the player gets the score or not.

What does this mean for us?

In the current version, it might mean a few stories, like reducing the number of bullets. If I choose to do a new version to experiment with a different design, I don’t think I’d try to follow the original testing and skipping logic, but I might well take advantage of the asymmetric outer and inner loops, which makes a lot of sense in a design where all the logic is in one box. It makes a bit less sense with the current design, which is predicated on the center of the game not knowing which objects are interested in which other objects, or why: we just interact all pairs and let them sort it out.

Tentative design issues

Even if we do the experiment with the more centralized design, it’s hard for me to want to do away with objects entirely. Imagine that all the screen objects are represented with some simple, common data structure. That structure will include some way of knowing what the screen object is, because we have to draw different things differently. So there will be a type field, or conceivably some bizarre index-related knowledge so that if the index is greater than x it’s an asteroid. One way or another, we’ll know.

Suppose we do it by index. Then our drawing code might look something like this:

for (i in 0..4) drawBullet(table[i])
drawShip(table[4])
drawSaucer(table[5])
for (i in 6..24) drawAsteroid(table[i])

It’s hard for me to prefer that over having each entry be an instance of a class and coding

for (item in table) item.draw()

Now when memory is tight, the first way certainly saves memory. Heck, I think they packed each screen object down to three, maybe four bytes, and with objects, we’d surely consume four bytes just for the object pointer, before we even get to the data.

But here in the 21st century, we generally have memory and cycles to spare and we can use the tools to make our programming job easier. We can save the tricky stuff for when, if ever, it’s really needed.

When I started thinking about the rewrite, I was thinking all code, no objects, just functions and dumb data. But as my ideas mature, it seems to me that dumb data, here in the 21st century, is just not a good idea. I’m not making any final decisions about what I would do if I were to do it, but I think I might aim for a centralized “main loop” but with objects that can do at least some simple operations like drawing themselves.

We’ll see. I’ll probably do it.

Now let’s do a little work.

Friction

I think the first thing I’d like to do is to implement the friction story. In the original game, and in my Lua one, the ship slows down to a stop (or near stop) when you’re not accelerating.

I’m going to spike this, because I don’t have much of a sense of the numbers. I will do a test, I promise.

The way this will be done, is that on each tick, the ship will reduce its velocity a bit. Should we subtract a constant, or multiply by a fraction less than one? Let’s subtract a constant, that will get us down to zero.

The Ship moves here:

    private fun move(deltaTime: Double) {
        position = (position + velocity * deltaTime).cap()
    }
Voice Over, Post Commentary:
I start in a poor direction, kind of pantsing it, and things get confusing.

We should scale the value we subtract by deltaTime as well, since we don’t know the cycle time and we want the effect to be the same in real time. Velocity’s maximum is U.SPEED_OF_LIGHT, which is 500.0. Our velocity will usually be far less than that. I think the units of speed are 500 space units per second, so that at full speed we cross the screen in two seconds. Ship acceleration is 120, which will get us to top speed in a bit over 4 seconds. Hm. I seen an issue:

If deceleration is always applied, it will have to be smaller than acceleration or we’ll never get anywhere. I think we have to decelerate only if we’re not accelerating.

That’s done in Controls:

    private fun accelerate(ship:Ship, deltaTime: Double) {
        if (accelerate) {
            val deltaV = U.SHIP_ACCELERATION.rotate(ship.heading) * deltaTime
            ship.accelerate(deltaV)
        }
    }

Perfect. We’ll add an else here and pass in a negative deltaV. My first attempt is ludicrous:

    private fun accelerate(ship:Ship, deltaTime: Double) {
        val deltaV = U.SHIP_ACCELERATION.rotate(ship.heading) * deltaTime
        if (accelerate) {
            ship.accelerate(deltaV)
        } else {
            ship.accelerate(deltaV*-2.0)
        }
    }

The ship rapidly backs off the screen. Let’s fix that in accelerate:

    fun accelerate(deltaV: Acceleration) {
        if ( deltaV > 0 ) accelerating = true
        velocity = (velocity + deltaV).limitedToLightSpeed()
        if (velocity < 0) velocity = Velocity.ZERO
    }

I don’t like this spike but I’m just trying to get a sense of the value.

Darn. That code can’t work. I can’t compare deltaV or velocity to a constant: they are vectors. Worse yet, I can’t tell whether its an acceleration or deceleration without trig, involving my heading. Revert that, do again.

I’ve learned one useful thing: accelerating is true if we’re accelerating. I can use that fact in move to decide whether to slow down.

I begin to see why, in my Lua version, I multiplied by a fraction: I don’t see an easy way to determine whether the subtraction will cause us to back up.

Just to get my feet under me, I’m going with the multiply. After some experimentation, the deceleration from this is pretty decent on my machine:

    private fun move(deltaTime: Double) {
        position = (position + velocity * deltaTime).cap()
        if (! accelerating ) {
            velocity *= 0.995
        }
    }

But that’s not scaled by time, so on a slower or faster machine, the appearance will vary.

As for deltaTime, it varies:

0.0116695
0.004736041666666857
0.011865666666666996
0.0045714166666659395
0.01214387500000047
0.004690499999999709
0.01197883333333305
0.00482462500000036

We want to scale our 0.995 by deltaTime. If deltaTime is small, then our factor should be closer to 1.0.

I refactor to this:

    private fun move(deltaTime: Double) {
        position = (position + velocity * deltaTime).cap()
        if (! accelerating ) {
            val fraction = 0.005
            velocity *= 1.0 - fraction
        }
    }

Thinking that now I can scale fraction to be small when deltaTime is small. For some reason, I’m finding this difficult. Brain fog this morning? The average of deltaTime is 0.0083 and change. That’s basically 1/120. I could try 0.6*deltaTime.

    private fun move(deltaTime: Double) {
        position = (position + velocity * deltaTime).cap()
        if (! accelerating ) {
            val fraction = 0.6*deltaTime
            velocity *= 1.0 - fraction
        }
    }

That looks pretty good. Time for a break. Need to defog my brain somehow.

Voice Over:
This is still pretty hacked together and my thoughts aren’t clear yet. Soon, I’ll do some actual math.

Post Break

OK, I’m all nice clean and shaved and such. We have a sort of a scheme. What I like about it is that the ship sort of glides to a halt, slowing a lot when it’s moving fast, then less and less. What I don’t quite like is that, in principle, it never stops, because (presumably) fraction is never zero. What I like even less is that if deltaTime were ever to rise to, say, 1.7 seconds, fraction would exceed 1 and chaos would ensue. Of course, if the game is cycling once per second, it’s not going to be much fun anyway.

By eyeball, the ship come to near rest from full speed in about 5 seconds. I’d like to set the numbers based on some kind of principle. Since we’re multiplying speed by a fraction, We ought to be able to do some simple math and pick the numbers.

Think in terms of a constant time hack. Every second, we’re setting speed to 0.4 times speed, that is 1-0.6. So speed 1 will decline like this

time speed
1 1
2 0.4
3 0.16
4 0.064
5 0.0256
6 0.01024
7 0.004096

Interesting values there, but the point is just that they decline by the power of (1-fraction). And we see here why we’ll never quite stop, but I think we don’t care about that.

Anyway the ship is nearly still by 5 seconds by my one-Mississippi count. Suppose we want that to be more like 4 seconds to nearly still. We want the speed at 4 seconds to be about 0.256. Well,

speed(t) = dt
0.0256 = d4
0.02561/4 = d
0.7113 = d

Voice Over:
At this point, I finally stop messing around and start to come to grips with the problem and its solution. Yay, me!

OK, enough hackery. Do the real math.

We know that velocity at time t = velocity at time zero + acceleration times t, given a constant rate of acceleration.

So if we want velocity at time 1 to be p times the original velocity, for a sort of half-life scheme:

p*v0 = v0 + 1*a
p*v0 = v0 + a
a = p*v0 - v0
a = v0*(p - 1)

So, I don’t know what my current code is all about but here we can set v0 to 1, since all that matters is the value p - 1.

Voice Over:
I regroup again, deciding to reformulate a bit. Turns out to be a good idea.

Let’s instead consider this: we’ll calculate the acceleration to use to accelerate to a given new speed from a given current speed, in one second:

vNew = vCurrent + a*1
vNew-vCurrent = a

This is ridiculously simple. Something definitely wrong with my math brain this morning. Let’s have some tests:

    fun accelerateToNewSpeedInOneSecond(vNew:Double, vCurrent: Double): Double {
//        vNew = vCurrent + a*t
//        t = 1
//        a = vNew - vCurrent
        return vNew - vCurrent
    }

    @Test
    fun `deceleration by a quarter`() {
        var speed = 100.0
        val acceleration = accelerateToNewSpeedInOneSecond(75.0, 100.0)
        speed += acceleration
        assertThat(speed).isEqualTo(75.0, within(0.1))
    }

    @Test
    fun `deceleration scaled`() {
        var speed = 100.0
        var acceleration = accelerationFactor(0.75)
        val deltaTime = 0.1
        acceleration = accelerateToNewSpeedInOneSecond(75.0, 100.0)*deltaTime
        for (i in 1..10) {
            speed += acceleration
        }
        assertThat(speed).isEqualTo(75.0, within(0.1))
    }

These are green. I’ll commit the test file: Initial deceleration math tests.

I’m not happy with this yet. But let me try it in Ship.

    fun accelerateToNewSpeedInOneSecond(vNew:Velocity, vCurrent: Velocity): Velocity {
//        vNew = vCurrent + a*t
//        t = 1
//        a = vNew - vCurrent
        return vNew - vCurrent
    }

    private fun move(deltaTime: Double) {
        position = (position + velocity * deltaTime).cap()
        if (! accelerating ) {
            val acceleration = accelerateToNewSpeedInOneSecond(velocity*0.5, velocity)*deltaTime
            velocity += acceleration
        }
    }

What this does is cut the ship’s velocity in half every second that it isn’t accelerating. I suppose that in principle it might be oscillating a tiny bit, or drifting closer and closer to zero. Let’s force it to zero.

We’re cutting speed in half every second. The highest possible speed is 500, imagine it’s 512, so over a few seconds off the throttle we’ll be at 256, 128, 64, 32, 16 and in five seconds we look to be pretty still.

Voice Over
An OK idea, but doesn’t look good on screen.

Let’s try this:

    if ( velocity.length < 16.0) velocity = Velocity.ZERO

Watching that, I can see it suddenly stop. Bag it, we’ll let it refine forever. No harm done. We’ll go with this:

    private fun move(deltaTime: Double) {
        position = (position + velocity * deltaTime).cap()
        if (! accelerating ) {
            val acceleration = accelerateToNewSpeedInOneSecond(velocity*U.SHIP_DECELERATION_FACTOR, velocity)*deltaTime
            velocity += acceleration
        }
    }

Commit: Ship slows to half its current coasting speed every second.

Summary

Feature done. I could have hacked together some numbers and multiplied velocity times some fraction pulled out of the air, but now the value used actually makes sense in terms of the things going on in the world. Let’s move some constants up to U:

object U
...
    val SHIP_DECELERATION_FACTOR = 0.5 // speed reduces in half every second

class Ship
...
    private fun move(deltaTime: Double) {
        position = (position + velocity * deltaTime).cap()
        if (! accelerating ) {
            val acceleration = accelerateToNewSpeedInOneSecond(velocity*U.SHIP_DECELERATION_FACTOR, velocity)*deltaTime
            velocity += acceleration
        }
    }

Commit: Move deceleration factor to Universe.

What’s good about this is that it’s right with the world: it adjusts the ship’s speed down by 1/2 every second, and will work no matter what the cycle time is. (Unless it went over a second, in which case we’re out of luck.)

Am I certain of that? Not entirely, but pretty darn sure. I think I could do a few more tests to be sure that it does what I expect at more scales, but we do have this one:

    @Test
    fun `deceleration scaled`() {
        var speed = 100.0
        val deltaTime = 0.1
        val acceleration = accelerateToNewSpeedInOneSecond(75.0, 100.0)*deltaTime
        for (i in 1..10) {
            speed += acceleration
        }
        assertThat(speed).isEqualTo(75.0, within(0.1))
    }

These tests should be changed to use the function that’s currently in Ship, and the function probably belongs in the Universe file. Let’s add a couple of notes in JIRA.md:

  • M Change DecelerationTest to use the function that Ship uses.
  • M Move the Ship deceleration function to Universe?

What have I learned here? I think I’ve learned that I know two ways to make this feature happen. One of them just amounts to pulling a number out of the air and bashing it into the move function. The other involved doing the actual math, which turns out to be trivial once I look at things correctly, and using the actual mathematical result. I was not able to think clearly enough about the air number to adjust it, and I tried all odd kind of adds, subtracts, multiplies and divides without really clear understanding. The final math is so trivially simple that it hardly deserves a function of its own.

It was harder to do the math, in the sense that I have a few cards here with starting equations on them, but it makes the code make sense. The other way could have been hammered … I think … but the numbers would have been pretty random.

What is most surprising to me is that I thought this feature was trivial and that it would take just a few moments to do, and instead it has taken the whole morning to do the experiments, do the math, test visually, and write the article. I’d have thought less than an hour for this part of the article.

Fortunately, I don’t have to make estimates, and if I do make them and they’re wrong, no one jumps on my case about it.

We’ve made one small improvement, and learned a lesson to the effect that figuring out the math is possible and seems to be a better way to do things despite the apparent complexity in the code. If we want faster deceleration now, we know how to get it.

Future possibility?

As things stand now, the ship never stops: it’s actually drifting a tiny bit. It adjusts the speed by smaller and smaller values, never getting to exactly stopped. Suppose we wanted to decelerate in some orderly way, down to zero, in time t. Maybe t would be a function of current speed, but we want to decelerate, maybe uniformly, down to zero, in some given number of seconds. How might we do that?

Now, I think I’d expect that it never comes out even. Ships in space adjust their orbits all the time, because you can’t get it trimmed just right, to zero equals zero. But suppose we wanted to get to 0.01 in N seconds. How might we do that? Would we want a constant acceleration rate? That might be “better” in some sense, though this looks fine on the screen.

More math, and different code, because we’d probably want to set either a deceleration value based on velocity at the end of each acceleration cycle, and use that deceleration until further notice. Might be amusing. I’ll work on that on a scratchpad and decide if it would be fun to try.

For now, a new feature and a lesson that I would like to remember. Something about it being better to understand what we’re doing rather than just bash in a number somewhere, even if bashing seems easier.

See you next time!!