We need to improve collision detection. I think we have to do it in one go.

We noticed last time that the collision-finding logic is messy, and we made it more so:

function Universe:findCollisions()
    -- we clone the asteroids collection to allow live editing
    local needNewWave = true
    for i,a in pairs(clone(self.asteroids)) do
        needNewWave = false
        self:checkMissileCollisions(a)
        if self.ship then self:checkShipCollision(a) end
    end
    if needNewWave == true then
        if self.timeOfNextWave == 0 then
            self.timeOfNextWave = self.currentTime + self.timeBetweenWaves
        end
    end
end

function Universe:checkShipCollision(asteroid)
    if self.ship.pos:dist(asteroid.pos) < asteroid:killDist() then
        asteroid:score()
        asteroid:split()
        self:killShip()
    end
end

function Universe:checkMissileCollisions(asteroid)
    for k,m in pairs(self.missiles) do
        if self.ship and m.pos:dist(self.ship.pos) < self.ship:killDist() then
            self:killShip()
            m:die()
        end
        if m.pos:dist(asteroid.pos) < asteroid:killDist() then
            asteroid:score()
            asteroid:split()
            m:die()
        end
    end
end

The original plan was just to compare asteroids and missiles … then we added in the ship, the the saucer, and the logic got more and more strange. Part of the motivation was that the complexity just grew – true technical debt – and part was a desire not to have to compare every object with every other.

The result so far includes several different collections of objects: asteroids, missiles, ships (there’s only one), saucers (only one), and these collections are managed separately. And we have logic in Universe deciding whether things have collided, which is quite arguably up to them. We’ve had to handle the collections with kid gloves, whatever that means, protecting against premature object death by cloning the asteroids collection, after adding and destroying in mid loop uncovered a very mysterious Codea anomaly.

It’s time to fix this, and I have a plan. It’s too big and it goes like this:

  • Keep all the objects in a single collection;
  • for collision-checking use a double loop over the objects
  • ask each pair to decide what to do about colliding
  • (possibly deciding in the loop whether collision is possible)
  • use double-dispatch to leave handling collisions up to the parties involved
  • build lists of added objects and objects to be deleted as we go
  • apply deletes and adds after the loops are complete

Let me give a bit more detail of the double-dispatch idea.

The two loops over objects are looping over all the objects and (if the plan holds up) they will just ask each pair to decide if they’re colliding and what to do about it. Suppose at some point we have in hand a missile, m1, and another missile, m2. We send:

m1:collide(m2)

collide is implemented the same in every object:

function XXX:collide(anObject)
  anObject:collideWithXXX(self)
end

So m1 receives collide(m2) and sends

m2:collideWithMissile(self)

Missiles don’t destroy each other (at least not now) so

function Missile:collideWithMissile(aMissile)
end

Nothing happens. Suppose instead we have an asteroid a and a missile m, and they are in fact close enough to collide. We send:

a:collide(m)

and then a sends

m:collideWithAsteroid(a)

That’s implemented, roughly:

function Missile:collideWithAsteroid(a)
  if we're not close enough to a to kill it then return
  a:hitByMissile(self)
  U:delete(self)
end

And

function Asteroid:hitByMissileMissile(m)
  U:add new asteroids if needed
  U:delete(self)

The upshot of this is that every object will explicitly know what to do when it is in range of or hit by another object, based on what kind of object it is … without anyone checking objects for type.

This may seem rather tricky to you, but it is the standard way to deal with interactions between two objects of different types. Tell one “intaractWith”, it tells the other interactWithMyType and now there’s a place for code based on both types without ever checking.

I’m sure it may seem weird, but I’m also sure by the time it’s done we’ll be happy with it in every way. Or, if not, we’ll have learned something, even if it’s just that I like it and you don’t.

It’s a thing to know how to do, anyway.

My concern is that, at first glance, I don’t see how to do it incrementally, but doing it all at once feels too big to get done in one go. We have a couple of options.

First, we could just go for it. Rip out the old logic, put in the new logic, and just keep going until done. I think we’re likely to run out of time for that. What do I mean? I mean that so far, every couple of hour session has ended with the program running a little bit better than the time before. It is a fundamental notion of mine that that is always possible. Here I have my doubts.

Second, we could figure out a way to do this in smaller steps. At this moment, I don’t quite see that, but it seems safer. Let’s think about that:

What are some small steps we could take?

Make the master collection
It should be easy to make the big collection of objects since we are already making all the little ones. We could just add everything to the big collection in those locations. Then later we could remove the others.
Build collision logic incrementally
We have a loop that checks missiles against an asteroid. We could change that one to do the missile:collide(asteroid) thing, and leave it in place, moving on to the next possibility. That would let us sort out a single case that could serve as a pattern for the others. And I expect we’ll find out something about my raw idea that isn’t quite right.

We can probably do all of asteroid::missile, ship::missile, and ship::asteroid without unwinding the logic shown above.

Do deletes and adds uniformly?
We can certainly build the delete and add lists during this process. Whether we can apply them is a question. When we go to the big collection, we can do all the removing and adding. But in the interim, we can’t go fully to using those lists unless we want to do something fancy, like check the types and put them into the right collection. That would be doable but tacky. We’d have to decide in the moment whether to do that or
At some point, bite the bullet and go for it
With the major interactions all done, we just have the loop replacement and all the interactions that do nothing, like asteroid::asteroid and missile::missile. (Unless we want to be able to shoot down missiles.) Sooner or later we have to do the big double loop and finish up. With luck, it’ll be a short reach by then.

There are other directions we could go in:

Make the big collection
As before, we can create this incrementally, maintaining the old collections.
Loop over the big collection, checking type
We presently have one major loop over asteroids, another over missiles. We could change those to use the big collection and select only asteroids for the one, only missiles for the other. Then relax the constraints slowly, type by type.

I’m not clear on how this one might be done, but it’s certainly able to be done.

But wait, there’s more

When all this is done, our drawing logic gets much simpler: we draw everything, move everything, collide everything. I think that ideally, we do that with three loops over all the objects, with only the third being nested.

In the end, everything will be much nicer, I’m sure of it. The trick is to move incrementally, not breaking anything, keeping the program running all the time.

We have to pick a way. I think a decent first step is to create the new collection objects and start getting everyone into it. That’s surely doable without harm.

I’ll start that now, even though it’s 3:20 AM.

Big collection

I’ll start by creating the collection in Universe:init:

function Universe:init()
    self.processorRatio = 1.0
    self.score = 0
    self.rotationStep = math.rad(1.5) -- degrees
    self.missileVelocity = vec2(MissileSpeed,0)
    self.frame64 = 0
    self.saucerInterval = 2
    self.timeBetweenWaves = 2
    self.timeOfNextWave= 0
    self:defineSounds()
    self.objects = {} -- <--- new
    self.button = {}
    self.asteroids = {}
    self.missiles = {}
    self.explosions = {}
    self.attractMode = true
end

By the way, I don’t think the buttons will go into objects everything else there will.

This code clearly runs, lets just make sure everyone adds to objects as well as their current home:

function Universe:addAsteroid(asteroid)
    self.objects[asteroid] = asteroid
    self.asteroids[asteroid] = asteroid
end

function Universe:deleteAsteroid(asteroid)
    self.objects[asteroid] = nil
    self.asteroids[asteroid] = nil
end

function Universe:addMissile(missile)
    self.objects[missile] = missile
    self.missiles[missile] = missile
end

function Universe:deleteMissile(missile)
    self.objects[missile] = nil
    self.missiles[missile] = nil
end

function Universe:addSaucer(saucer)
    self.objects[saucer] = saucer
    self.saucer = saucer
end

function Universe:deleteSaucer(saucer)
    self.objects[saucer] = nil
    self.saucer = nil
    self.saucerTime = self.currentTime
end

We need to look at Splat, and Explosion, to see how to handle them.

Universe calls global drawSplats, which is maintained by the Splat class. I think we can leave that be for now and fold it in later or never.

Explosion is a hybrid. It’s a class and Universe has the collection, but Explosion is still setting things into that collection:

function Explosion:init(ship)
    local f = function()
        U.explosions[self] = nil
    end
    self.pos = ship.pos
    self.step = vec2(0,0)
    U.explosions[self] = self
    tween(4, self, {}, tween.easing.linear, f)
end

Let’s test and commit what we have now, and then change Explosion.

We get an error when the Saucer times out:

Universe:117: table index is nil
stack traceback:
	Universe:117: in method 'deleteSaucer'
	Saucer:46: in method 'die'
	Saucer:5: in field 'callback'
	...in pairs(tweens) do
    c = c + 1
  end
  return c
end

I’m not dead certain why that has happened but what it means is that when we say:

    self.objects[saucer] = nil

the saucer parameter is nil, so we can’t put it away. Yes, well:

function Saucer:die()
    U:deleteSaucer()
end

It certainly is nil. Fix:

function Saucer:die()
    U:deleteSaucer(self)
end

We didn’t need that before because we just nilled the universe’s pointer to the saucer.

Now everything is working. Commit: “object collection for asteroids, missiles, saucer”.

That should do it for tonight. We’ve started the refactoring, made some progress, and have a running system again. I’ll include the zip file but its behavior is the same as last time. That’s refactoring for you. :)

Zipped Code