GitHub Repo

An insight and an idea show me a way to approach centralized control. I think it’ll be quite nice.

As I begin to wake up in the early hours, it is my habit to think about programming. This helps me avoid thinking about darker things, which might otherwise plague me. This morning, in some order, I had an insight and an idea.

The Insight
The original Asteroids program does collision detection with two loops, both over the same table. But it doesn’t loop from top to bottom twice. Instead, the outer loop loops over the missiles, the ship, and the saucer, while the inner loop covers the ship, the saucer, and the asteroids.

The insight is this: the outer loop considers only objects that can destroy other objects. The inner loop considers only objects that can be destroyed. There is some overlap (ship and saucer) and that is dealt with by a bit of checking to avoid doing things twice.

I’m pleased to have recognized the “why” behind what is otherwise just rather odd code.

Now, I’ve been thinking that it would be interesting to do Asteroids with centralized control, as a comparison to the very decentralized control model we have now, where the center knows almost nothing, and the objects decide what to do based on how they interact. The game sort of “emerges” from their collective behavior, rather than being created by a more compact centralized object that choreographs everything.

I had been thinking that to come up with the comparison, I’d have to start over. But then …

The Idea
The SpaceObjectCollection object in our current implementation holds a single collection of all the objects in the system, in the single game-owned instance, knownObjects. The collection makes no distinction between the objects, it just adds them and removes them as requested by Transaction instances. But it could make distinctions.

And if the SpaceObjectCollection kept some additional collections, call them attackers and targets, it would be possible to write a centralized collision detection loop that mimics the original quite closely.

And that would mean that we could “convert” our current program to use centralized control, perhaps even fairly incrementally, rather than having to rewrite it. We could explore the differences without mass quantities of work!

Let’s Do It

I think that it should be possible to do this so that the program works both ways, based on a flag or some such thing. That seems good to me, as it can preserve all the goodness of both versions. Plus, it seems like fun. So we’ll start down that road.

I propose that the first thing will be to modify SpaceObjectCollection to maintain two new lists, attackers and targets. Let’s have a look at that class.

class SpaceObjectCollection {
    val spaceObjects = mutableListOf<ISpaceObject>()

    fun add(spaceObject: ISpaceObject) {
        spaceObjects.add(spaceObject)
    }
    
    fun addAll(newbies: Collection<ISpaceObject>) {
        newbies.forEach{ add(it) }
    }

    fun any(predicate: (ISpaceObject)-> Boolean): Boolean {
        return spaceObjects.any(predicate)
    }

    fun applyChanges(transaction: Transaction) = transaction.applyChanges(this)

    fun clear() {
        spaceObjects.clear()
    }

    fun forEach(spaceObject: (ISpaceObject)->Unit) = spaceObjects.forEach(spaceObject)

    fun contains(obj:ISpaceObject): Boolean {
        return spaceObjects.contains(obj)
    }

    fun pairsToCheck(): List<Pair<ISpaceObject, ISpaceObject>> {
        val pairs = mutableListOf<Pair<ISpaceObject, ISpaceObject>>()
        spaceObjects.indices.forEach { i ->
            spaceObjects.indices.minus(0..i).forEach { j ->
                pairs.add(spaceObjects[i] to spaceObjects[j])
            }
        }
        return pairs
    }

    fun removeAndFinalizeAll(moribund: Set<ISpaceObject>): Boolean{
        moribund.forEach { spaceObjects += it.subscriptions.finalize() }
        return spaceObjects.removeAll(moribund)
    }

    val size get() = spaceObjects.size
}

We do have some tests for SpaceObjectCollection. Two of them are testing some collision stuff, and one of them does check the add:

    @Test
    fun `create flyers instance`() {
        val spaceObjectCollection = SpaceObjectCollection()
        val a = Asteroid(Vector2(100.0, 100.0))
        spaceObjectCollection.add(a)
        val s = Ship(
            position = Vector2(100.0, 150.0)
        )
        spaceObjectCollection.add(s)
        assertThat(spaceObjectCollection.size).isEqualTo(2)
    }

Not much testing. I probably rationalized that other tests would exercise the object sufficiently. I think now that we’re going to make it a bit more complicated, we should do a bit more testing.

    @Test
    fun `missiles are attackers`() {
        val s = SpaceObjectCollection()
        val m = Missile(Point(100.0, 200.0))
        s.add(m)
        assertThat(s.attackers).contains(m)
    }

This should get us started. IDEA informs me that attackers is unknown. I am not surprised. Let’s code just enough:

class SpaceObjectCollection {
    val spaceObjects = mutableListOf<ISpaceObject>()
    val attackers = mutableListOf<ISpaceObject>()

    fun add(spaceObject: ISpaceObject) {
        spaceObjects.add(spaceObject)
        if (spaceObject is Missile) attackers.add(spaceObject)

Test should run green. It does. Commit: SpaceObjectCollection keeps missiles in attackers collection.

    @Test
    fun `ship is an attacker`() {
        val s = SpaceObjectCollection()
        val toAdd = Ship(Point(100.0, 200.0))
        s.add(toAdd)
        assertThat(s.attackers).contains(toAdd)
    }

Test. Red. Fix:

    fun add(spaceObject: ISpaceObject) {
        spaceObjects.add(spaceObject)
        if (spaceObject is Missile) attackers.add(spaceObject)
        if (spaceObject is Ship) attackers.add(spaceObject)
    }

Green. Commit: Ship is an attacker.

Repeat for Saucer.

    @Test
    fun `saucer is an attacker`() {
        val s = SpaceObjectCollection()
        val toAdd = Saucer()
        s.add(toAdd)
        assertThat(s.attackers).contains(toAdd)
    }

Red. Fix:

    fun add(spaceObject: ISpaceObject) {
        spaceObjects.add(spaceObject)
        if (spaceObject is Missile) attackers.add(spaceObject)
        if (spaceObject is Ship) attackers.add(spaceObject)
        if (spaceObject is Saucer) attackers.add(spaceObject)
    }

Green. Commit: Saucer is an attacker.

Good time to reflect.

Reflection

Could I have done this with fewer tests and fewer commits? Of course, and probably correctly. I am always tempted to “save time” by going in larger steps. I don’t think it saves me much time when it works, and when it doesn’t work, it costs me larger chunks of time while I try to figure out what has gone wrong. In this case, I’m sure I could get away with larger steps, but I’m enjoying the practice of making just the smallest possible change to get it right. I’ll continue to work that way.

Now how about the code? Those if statements could be combined with ||. But why should we bother? Well, there is the duplication of addSpaceObject, which is taking up valuable mental space. But let’s hold off a bit.

What’s Next?

I think we really ought to do removes for these. I think I’d like to put the removes into the existing tests, because they tell a complete story. It wasn’t in, it was, it came out. Let’s try that and see what we think. I like these tiny tests but …

No. I’ll do new tests. It’s easy and we can look at them and decide what’s better.

    @Test
    fun `remove removes missiles from attackers`() {
        val s = SpaceObjectCollection()
        val toAdd = Missile(Point(100.0, 200.0))
        s.add(toAdd)
        s.remove(toAdd)
        assertThat(s.attackers).doesNotContain(toAdd)
    }

It turns out that SpaceObjectCollection does not have a remove. It just has that remove and finalize method.

Let’s give it a remove and improve it. From this:

    fun removeAndFinalizeAll(moribund: Set<ISpaceObject>): Boolean{
        moribund.forEach { spaceObjects += it.subscriptions.finalize() }
        return spaceObjects.removeAll(moribund)
    }

Hm, we have to return a Boolean. It is to be true if we actually removed anything. Is anyone using that Boolean? No. There is only one call and we do not check the Boolean. Change the signature.

    fun removeAndFinalizeAll(moribund: Set<ISpaceObject>) {
        moribund.forEach { spaceObjects += it.subscriptions.finalize() }
        spaceObjects.removeAll(moribund)
    }

And now let’s extract the final line to a new method:

    fun removeAndFinalizeAll(moribund: Set<ISpaceObject>) {
        moribund.forEach { spaceObjects += it.subscriptions.finalize() }
        removeAll(moribund)
    }

    private fun removeAll(moribund: Set<ISpaceObject>) {
        spaceObjects.removeAll(moribund)
    }

And add a new method, remove:

    fun remove(spaceObject: ISpaceObject) {
        removeAll(setOf(spaceObject))
    }

Why wrap this and call the other remove? To avoid duplicating what comes next, with the observation that the remove is only used in tests, so it should use the production removeAll. Otherwise we’d have to unwind removeAll ourselves, and that’s no fun.

Test should run red, because we’re not removing anything from attackers yet. It does. And now:

    private fun removeAll(moribund: Set<ISpaceObject>) {
        spaceObjects.removeAll(moribund)
        attackers.removeAll(moribund)
    }

Should be green. Yes. Commit: remove removes attackers.

The other two tests will run green, but I’ll do them:

    @Test
    fun `remove removes ship from attackers`() {
        val s = SpaceObjectCollection()
        val toAdd = Ship(Point(100.0, 200.0))
        s.add(toAdd)
        s.remove(toAdd)
        assertThat(s.attackers).doesNotContain(toAdd)
    }

    @Test
    fun `remove removes saucer from attackers`() {
        val s = SpaceObjectCollection()
        val toAdd = Saucer()
        s.add(toAdd)
        s.remove(toAdd)
        assertThat(s.attackers).doesNotContain(toAdd)
    }

Green. Commit: Additional remove tests.

Now we need to do similarly for targets. I forgive myself for what I’m about to do: I’m going to add checks to the ship and saucer tests to drive out targets. No, dammit, I’m not. I’m going full on tiny tests here, let’s stick to it.

    @Test
    fun `ship is a target`() {
        val s = SpaceObjectCollection()
        val toAdd = Ship(Point(100.0, 200.0))
        s.add(toAdd)
        assertThat(s.targets).contains(toAdd)
    }

Won’t compile.

class SpaceObjectCollection {
    val spaceObjects = mutableListOf<ISpaceObject>()
    val attackers = mutableListOf<ISpaceObject>()
    val targets = mutableListOf<ISpaceObject>()

    fun add(spaceObject: ISpaceObject) {
        spaceObjects.add(spaceObject)
        if (spaceObject is Missile) attackers.add(spaceObject)
        if (spaceObject is Ship) {
            attackers.add(spaceObject)
            targets.add(spaceObject)
        }
        if (spaceObject is Saucer) attackers.add(spaceObject)
    }

Expect green. Yes. Commit: ship is a target.

Let’s drive out the remove:

    @Test
    fun `remove removes ship from targets`() {
        val s = SpaceObjectCollection()
        val toAdd = Ship(Point(100.0, 200.0))
        s.add(toAdd)
        s.remove(toAdd)
        assertThat(s.targets).doesNotContain(toAdd)
    }

Red. Fix:

    private fun removeAll(moribund: Set<ISpaceObject>) {
        spaceObjects.removeAll(moribund)
        attackers.removeAll(moribund)
        targets.removeAll(moribund)
    }

Green. Commit: remove removes all moribund from targets (if present).

Complete the addition tests:

    @Test
    fun `saucer is a target`() {
        val s = SpaceObjectCollection()
        val toAdd = Saucer()
        s.add(toAdd)
        assertThat(s.targets).contains(toAdd)
    }

    @Test
    fun `Asteroid is a target`() {
        val s = SpaceObjectCollection()
        val toAdd = Asteroid(Point(100.0, 200.0))
        s.add(toAdd)
        assertThat(s.targets).contains(toAdd)
    }

Red. Both are red. Should not have written two. Fix one:

    fun add(spaceObject: ISpaceObject) {
        spaceObjects.add(spaceObject)
        if (spaceObject is Missile) attackers.add(spaceObject)
        if (spaceObject is Ship) {
            attackers.add(spaceObject)
            targets.add(spaceObject)
        }
        if (spaceObject is Saucer)  {
            attackers.add(spaceObject)
            targets.add(spaceObject)
        }
    }

Just one red. Fix that:

    fun add(spaceObject: ISpaceObject) {
        spaceObjects.add(spaceObject)
        if (spaceObject is Missile) attackers.add(spaceObject)
        if (spaceObject is Ship) {
            attackers.add(spaceObject)
            targets.add(spaceObject)
        }
        if (spaceObject is Saucer)  {
            attackers.add(spaceObject)
            targets.add(spaceObject)
        }
        if (spaceObject is Asteroid) targets.add(spaceObject)
    }

Green. Commit: saucer and asteroid are targets.

Write the confirming delete tests:

    @Test
    fun `remove removes saucer from targets`() {
        val s = SpaceObjectCollection()
        val toAdd = Saucer()
        s.add(toAdd)
        s.remove(toAdd)
        assertThat(s.targets).doesNotContain(toAdd)
    }

    @Test
    fun `remove removes asteroid from targets`() {
        val s = SpaceObjectCollection()
        val toAdd = Asteroid(Point(100.0, 200.0))
        s.add(toAdd)
        s.remove(toAdd)
        assertThat(s.targets).doesNotContain(toAdd)
    }

Green, as expected: Commit: saucer and asteroid correctly removed from targets.

Reflection

I think we’re done with this phase. We now have auxiliary collections attackers and targets in the SpaceObjectCollection, and we are confident that they are correctly maintained. We’ve done nine commits in 39 minutes, counting writing the article. Sweet.

I’ve only been working for about an hour and fifteen minutes, but I have an errand to run this morning, so let’s wrap up.

Summary

The overall idea is to experiment with centralized control for Asteroids, so as to get a good sense of how it compares to the current decentralized approach. (My guess is that we will deem it to be somewhat “simpler” but I’m not sure.)

Based on the insight that there are two overlapping sets of objects, ones that can destroy things, and ones that can be destroyed, we created two sub-collections in the SpaceObjectCollection, attackers and targets, which we’ll use in what follows.

That implementation was quite nicely test-driven, with yours truly managing to do minimal changes almost every time, and with lots of tests that just test one thing. And the code to do the work seems pretty clear:

    fun add(spaceObject: ISpaceObject) {
        spaceObjects.add(spaceObject)
        if (spaceObject is Missile) attackers.add(spaceObject)
        if (spaceObject is Ship) {
            attackers.add(spaceObject)
            targets.add(spaceObject)
        }
        if (spaceObject is Saucer)  {
            attackers.add(spaceObject)
            targets.add(spaceObject)
        }
        if (spaceObject is Asteroid) targets.add(spaceObject)
    }

    private fun removeAll(moribund: Set<ISpaceObject>) {
        spaceObjects.removeAll(moribund)
        attackers.removeAll(moribund)
        targets.removeAll(moribund)
    }

I am pleased with this outcome.

In subsequent work, I think we’ll define a flag to select centralized vs decentralized mode, and begin working on the centralized version. I’m not sure whether we’ll be able to keep the steps quite this tiny if we have to keep the game running, but we’ll see.

I hope you’ll join me in this bit of discovery. See you then!