Asteroids 37: Who does what to whom?
I’m sure my double dispatch approach will work fine. But the pattern seems simpler than that …
Musings
N.B. Seriously consider skipping down to “Never underestimate the value of a break”, unless you want to read a stream of consciousness which is accurate but wandering, as consciousness does. Mine, anyway.
I was delighted yesterday when Bill Wake (@wwake) commented on yesterday’s article. Bill’s an outstanding programmer, agilist, author, and mentor, and he even said nice things.
He also reminded me of a key fact: the pattern for “who does what to whom” in this game is very simple and quite symmetrical. If I were to write it all down at once, it might go like this:
- Two objects of the same kind do not interact. (Unless we decide to allow shooting down missiles.)
- Some objects don’t interact with anything. (Explosions, Splats)
- Any two other objects, if close enough together, mutually destroy each other.
It’s generally considered to be bad practice to ask objects their type or class. It’s considered to be better design to build things so that you send messages to objects and they do the right thing. If we write code that is conditioned on the type of an object, that code almost certainly pertains specifically to that type, and therefore “should” be part of it.
We have this rather simple design, that generally requires us to know that two object are of different type if they are going to interact. The best pattern I know for that is double dispatch. We send a generic message to one of them, including the other, and the one sends a message to the other admitting its type or some other refining information. Then the other has enough information to decide what to do.
Yesterday’s work convinced me that we can readily do that, and that we’re going to find up with methods like this in each class, take “A” as an example
- collide(obj), which sends obj:collideWithA(self),
- collideWithA(obj), which does nothing,
- collideWithB(obj), which destroys both ojbects,
- collideWithC(obj), which destroys both objects,
- collideWithD(obj), which destroys both objects.
The objects that can be destroyed will all look like that. Fairly simple, and will surely work. But is it really simple? No, certainly not. There will be five methods in each of the four mutual destructible classes. In each case there is one right way and three wrong ways to set up those five methods. Not what I’d call Really Simple.
But what would be better, darn it?
Bill suggested a thing “how do you behave on collision?” And he said “in some domains, you can do operation(f(x), g(x))”. He envisioned my table as an “operator table”, rather like a times table, a*b and so on.
There is no doubt that what we have here is like that. AM destroys, AA does not, M*A does, M*M does not. It’s like a …
It’s like exclusive or! Suppose each of the types had a number, and you xor’d them together. Then A xor A would be zero but A xor M would be non zero. This is just type checking by another name, of course. Is it “simpler”? It’s surely less code.
Handling the other objects, which we’re assuming are in the same collection, would be tricky, because they’d have to xor as zero against everyone. But we could do it in methods, perhaps.
How do you behave on collision … ah, that’s not the right question. “Tell, don’t ask”.
Right now the design is that an object gets the collide message and tells the other guy, in essence, “I’m a missile and I hit you”. What if, instead, he said, “I’m a mutual destroyer with asteroids, ships, and saucers”, and the other object said to itself, well, I fit that pattern, here we go.
Interesting. But no. It requires every object to know all the classes that exist. No, we already have to know that. Every time we add another object that interacts, our present scheme requires us to add knowledge of that object to all the other interacting classes. It’s only a question of how we do it, as methods or data.
Doing it with data, in a lookup table, as Bill seems to suggest, is very tempting. It would isolate the concerns.
What about a “Collider” object of some kind? It might go like this:
- The main loops produce objects p and q to check for collision.
- Create a Collider(p,q)
- The collider says p:collide(self), q:collide(self)
- p and q announce themselves back to the collider
- the collider now knows what it needs to embody any collision policy we can imagine.
This is still just a roundabout way of determining the class or type of an object. But it might be better …
Never underestimate the value of a break …
N.B. Seriously consider skipping down to “Options”. This is still pretty speculative.
I’m back from a brief break, with a banana and a granola bar. And an idea.
There are only five cases for destruction:
- nothing destroys me
- ship: asteroids, missiles, saucers destroy me
- asteroid: missiles, ships, saucers destroy me
- saucer: missiles, ships, asteroids destroy me
- missile: asteroids, ships, saucers destroy me
We could make five things … objects, tables, classes, each with one of those five behaviors built in. When a collision needs to be checked, we send collide to one of them and he returns his table, and then the other guy shoots at that table …
Hmm. Let’s consider Asteroid, hit by:
- Asteroid: nothing.
- Missile, Ship, Saucer: mutual destruction.
What about a table:, called a collider:
asteroidCollider = {
asteroid=RETURN,
missile=MAD,
ship=MAD,
saucer=MAD
}
function MAD(a,b)
U:destroyBoth(a,b)
end
function RETURN(a,b)
end
The top level collision logic is (mostly):
for a,p do
for b,q do
local collider = b:collider()
local projectile = a:projectile()
action = collider[projectile]
action(p,q)
end
end
It’s still sort of answering class name, but not quite, since we could, for example, create instances of Missile that had projectile names “shipKiller” and “saucerKiller” depending on who had fired them.
This could work, I think. It’s also premature, since just now we have no need of it. We’re nearly there, however, and we could get to needing it quickly if we wanted to, by beginning to use our new objects collection instead of the specialized ones.
Let’s think about some options:
Options
Regarding collision:
- Assume we can solve the collision problem, since we now have at least two ways, the Collider idea and the double dispatch idea. The latter has been shown to work by our tests from last time.
- Push the Collider idea as far as we did with double dispatch. That would let us compare the two ideas more fairly.
Of these two, I prefer the latter. The idea is fresh in my mind and I’m curious to find out what it would really look like. But it does feel a bit premature.
Regarding the objects collection:
- Push now to using the
objectscollection instead of the specialized ones. Make the code work either by selecting fromobjectsby type, or by building in small versions of whatever collision approach we want to use. - Refactor the collision logic more slowly, extracting bits and improving them one at a time, removing duplication as we discover it, until it converges somewhere nice.
Of these, my normal operational mode would be the latter. I always prefer to refactor incrementally and see how good code emerges as we clean things up. Generally, good abstractions appear as needed.
However, we are in the middle of a committed notion, the single collection for all colliding objects (or, at present, all objects, colliding or not), and it would be nice to progress that effort further. Doing so would soon make the need for a solution to collision, at which point we could do what seemed best.
To decide, let’s look at where we stand on the objects collection.
Object Collections
I think we have completed centralizing the adding and deleting of asteroids, explosions, missiles, ships, and saucers. We’ve left splats out of the equation for now.
The result so far is a proliferation of methods in the Universe like this:
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
There’s a bit of special handling in deleteShip that would have to be dealt with, but that should be left to the ship.
Everything is now being stored both in the general collection objects and in its corresponding specific collection. We’ve even put the single ship and single saucer into the objects collection.
When we’re finished with this bit, there will only be two methods on Universe for this purpose, addObject and deleteObject, and everything of interest will be dealt with from there.
What would it take to convert to using the objects collection?
The collision logic looks like this:
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:deleteShip(self.ship)
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:deleteShip(self.ship)
m:die()
end
if m.pos:dist(asteroid.pos) < asteroid:killDist() then
asteroid:score()
asteroid:split()
m:die()
end
end
end
We could convert this to use the central collection immediately, by adding helper methods like Universe:asteroids that selected asteroids from the objects. We could do the same for missiles, and retain the special storage of the ship in a member variable. The collision code ignores the saucer at the moment: we cannot as yet shoot it down. (It would be easy enough to add, and if we need an excuse to clean up this code, adding saucer hits would be a good one.
I’m so tempted to just go in and rewrite the whole thing. In this case, I feel that I could surely do it in a couple of hours, and if not, I could revert and either do it again or go some other direction with more understanding tomorrow.
For this program, that would be OK. For a real legacy program, the rewrite might take longer. I know of one that took 42 elapsed days. I know of one that took a year. I know of some that never completed.
My advice is “never rewrite, always refactor”. I guess I have to stick with that.
Let’s refactor a while, while keeping all these ideas near our mind. Improving this code can only help with the decisions.
Refactoring Collisions.
Look at that first method:
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
Get serious, that’s doing two very different things, checking collisions, and deciding whether there should be a new wave and setting the new wave timer. That latter bit is just answering the question: are there any asteroids left and using the answer.
If we have our asteroids along with all the other objects in a single collection, finding out if there are any asteroids is in fact potentially costly. But this code is too complex. Let’s break it apart, leave it expensive for now, and deal with the cost separately:
At the end of our draw method we have this:
self:drawMissiles()
drawSplats()
self:drawScore()
popStyle()
self:findCollisions()
end
We’ll add to that: self:checkNewWave, and implement that, for now, this way:
function Universe:checkNewWave()
local count = self:asteroidCount()
if count == 0 then
if self.timeOfNextWave == 0 then
self.timeOfNextWave = self.currentTime + self.timeBetweenWaves
end
end
end
function Universe:asteroidCount()
local c = 0
for i,a in pairs(self.asteroids) do
c = c + 1
end
return c
end
We have asteroidCount lying around unused anyway. Now findCollisions:
function Universe:findCollisions()
-- we clone the asteroids collection to allow live editing
for i,a in pairs(clone(self.asteroids)) do
self:checkMissileCollisions(a)
if self.ship then self:checkShipCollision(a) end
end
end
That’s better already. Let’s see if it works. I feel confident.
That works fine. I notice that the saucer kills a lot of asteroids. Almost makes me think his missiles shouldn’t do that, it’s almost too helpful. Anyway we can commit: “new wave separate from findCollisions”.
Now What?
You know, the more I think about this, the more troubled I am by one aspect of the single collection idea. In space, there are many asteroids, many missiles, one ship and at most one saucer.
Maybe this isn’t optimal …
It does make sense to check all the asteroids against all the missiles, and against the ship and the saucer. It does not make sense to check them against themselves. (It may, however, make sense to check the missiles against each other: it’d be kind of neat if you could shoot down that missile from the saucer.)
On the other hand, I think there are at most 44 asteroids, and if we followed the original game, at most 4 missiles from the ship. I ‘m not sure if the saucer could have more than one on screen or not. It’s not very many objects. Less than 350 comparisons, and usually more like 100, at a guess.
Ah. Think of it this way:
Keeping saucers and ships separate, keeping missiles and asteroids separate, is an optimization. We should do optimizations when a measurement tells us one is needed. Meanwhile, having done the optimizations, somewhat by accident, our code is messy.
We don’t worry about optimal when we’re worrying about clean design.
We’ll clean the code, confident that we can devise an optimization if we need one. As you were.
First we’ll switch the outer loop to use the objects collection.
What if we changed the outer loop right now to use the objects collection (but cloned, because we know we need to do something about adding and removing from a live collection (like not do it)).
Let’s do that and see what breaks.
function Universe:findCollisions()
-- we clone the asteroids collection to allow live editing
for i,a in pairs(clone(self.objects)) do -- <----
self:checkMissileCollisions(a)
if self.ship then self:checkShipCollision(a) end
end
end
What breaks is:
Universe:205: attempt to call a nil value (method 'score')
stack traceback:
Universe:205: in method 'checkShipCollision'
Universe:199: in method 'findCollisions'
Universe:80: in method 'draw'
Main:12: in function 'draw'
That line has decided that an asteroid has hit the ship and intends to destroy it and the ship:
function Universe:checkShipCollision(asteroid)
if self.ship.pos:dist(asteroid.pos) < asteroid:killDist() then
asteroid:score() -- line 205
asteroid:split()
self:deleteShip(self.ship)
end
end
I reckon we are colliding the ship with itself. No one else was near it. How about adding this:
function Universe:checkShipCollision(asteroid)
if not asteroid:is_a(Asteroid) then return end
if self.ship.pos:dist(asteroid.pos) < asteroid:killDist() then
print(tostring(asteroid))
asteroid:score()
asteroid:split()
self:deleteShip(self.ship)
end
end
We just don’t check if it isn’t an asteroid. At some future time we’ll improve that, is our theory. Right now, we’re trying to get to using our central collection.
With this in place we get this:
Universe:219: attempt to call a nil value (method 'killDist')
stack traceback:
Universe:219: in method 'checkMissileCollisions'
Universe:198: in method 'findCollisions'
Universe:80: in method 'draw'
Main:12: in function 'draw'
We can likely fix this by checking for an asteroid in checkMissileCollisions, similarly to what we did above. It’s tempting to wonder what a large negative kill radius would do, but probably nothing good.
function Universe:checkMissileCollisions(asteroid)
if not asteroid:is_a(Asteroid) then return end
for k,m in pairs(self.missiles) do
if self.ship and m.pos:dist(self.ship.pos) < self.ship:killDist() then
self:deleteShip(self.ship)
m:die()
end
if m.pos:dist(asteroid.pos) < asteroid:killDist() then
asteroid:score()
asteroid:split()
m:die()
end
end
end
The first bit there is what lets saucer missiles kill the ship. It seems to have nothing to do with individual asteroids. This is happening on every asteroid, it appears. That’s hardly optimal. Anyway with the asteroid check here, everything works.
Let’s see about that redundant check of ship and missiles. We do want to do that ship check for every asteroid for ever missile, just for every missile. Let’s break that out:
function Universe:findCollisions()
-- we clone the asteroids collection to allow live editing
for i,a in pairs(clone(self.objects)) do
self:checkMissileCollisions(a)
if self.ship then self:checkShipCollision(a) end
end
if self.ship then
for i,m in pairs(clone(self.missiles)) do
self:checkMissileHitShip(m, self.ship)
end
end
end
function Universe:checkMissileHitShip(missile, ship)
if missile.pos:dist(ship.pos) < ship:killDist() then
self:deleteShip(ship)
missile:die()
end
end
This works, though it took me a long time to be sure a missile still killed a ship. The saucer can’t hit a thing when you’re watching it.
Now we can change missiles loops similarly.
Now if we change the loops on self.missiles to self.objects, we’ll have to put in a couple more typechecks, but then we’ll be running on our single collection (and our distinguished ship and saucer variables).
A brief interlude of confusion.
OK this is weird. this code shows a confusing issue: it doesn’t seem to process
function Universe:checkMissileCollisions(asteroid)
if not asteroid:is_a(Asteroid) then return end
for k,m in pairs(self.missiles) do
if m.is_a(Missile) then
if m.pos:dist(asteroid.pos) < asteroid:killDist() then
asteroid:score()
asteroid:split()
m:die()
end
end
end
end
Excuse me. After way longer than I should admit, I noticed that says m.is_a, not m:is_a. I can’t even cheat right.
function Universe:checkMissileCollisions(asteroid)
if not asteroid:is_a(Asteroid) then return end
for k,m in pairs(self.objects) do
if m:is_a(Missile) then
if m.pos:dist(asteroid.pos) < asteroid:killDist() then
asteroid:score()
asteroid:split()
m:die()
end
end
end
end
This works, and I believe we are now running all the collisions on the objects collection, except for our use of the special variable ship.
Now we can remove all uses of the special collections.
Let’s look for other users of .missiles and .asteroids. We want to get rid of all of them before we move on. Ah. We change this:
function Universe:asteroidCount()
local c = 0
for i,a in pairs(self.objects) do
if a:is_a(Asteroid) then c = c + 1 end
end
return c
end
We find the methods addAsteroid and deleteAsteroid and replace those and their callers with addObject and deleteObject.
function Universe:addObject(object)
self.objects[object] = object
end
function Universe:deleteObject(object)
self.objects[object] = nil
end
We realize we should have committed before we did that. Oh well …
We have this in drawAsterids:
function Universe:drawAsteroids()
pushStyle()
stroke(255)
fill(0,0,0, 0)
strokeWidth(2)
rectMode(CENTER)
for i,asteroid in pairs(self.asteroids) do
asteroid:draw()
asteroid:move()
end
popStyle()
end
That becomes:
function Universe:drawAsteroids()
pushStyle()
stroke(255)
fill(0,0,0, 0)
strokeWidth(2)
rectMode(CENTER)
for i,asteroid in pairs(self.objects) do
if asteroid:is_a(Asteroid) then
asteroid:draw()
asteroid:move()
end
end
popStyle()
end
We’re certainly getting a lot of type-checking in here. That’s not good but it’s what we expect for this phase.
We search for and find addAsteroid and fix it:
function Asteroid:init(pos, size)
self.pos = pos or vec2(math.random(WIDTH), math.random(HEIGHT))
self.scale = size or 16
self.shape = Rocks[math.random(1,4)]
local angle = math.random()*2*math.pi
self.step = vec2(Vel,0):rotate(angle)
U:addObject(self)
end
Same with deleteAsteroid:
function Asteroid:split()
self:bang()
Splat(self.pos)
if self.scale ~= 4 then
Asteroid(self.pos, self.scale//2)
Asteroid(self.pos, self.scale//2)
end
U:deleteObject(self)
end
The only other reference to the asteroids collection is in the tests. It’s the newWave test and it is ignored. I think we’re done.
Tests run, game runs. Commit: “game uses object collection for asteroids and missiles, asteroids collection removed. missiles remains”.
Now the same for .missiles:
We have the same inits, removed. We removed the add and delete methods and make missile use the Object versions.
And we have this:
function Universe:drawMissiles()
pushStyle()
pushMatrix()
fill(255)
stroke(255)
for k, missile in pairs(self.missiles) do
missile:draw()
end
popMatrix()
popStyle()
for k, missile in pairs(self.missiles) do
missile:move()
end
end
Looking at Missile:draw, we find this:
function Missile:draw()
ellipse(self.pos.x, self.pos.y, 6)
end
Let’s make him responsible for his own mess:
function Missile:draw()
pushStyle()
pushMatrix()
fill(255)
stroke(255)
ellipse(self.pos.x, self.pos.y, 6)
popMatrix()
popStyle()
end
That leaves this:
function Universe:drawMissiles()
for k, missile in pairs(self.missiles) do
missile:draw()
end
for k, missile in pairs(self.missiles) do
missile:move()
end
end
We convert to objects at some expense:
function Universe:drawMissiles()
for k, missile in pairs(self.objects) do
if missile:is_a(Missile) then missile:draw() end
end
for k, missile in pairs(self.objects) do
if missile:is_a(Missile) then missile:move() end
end
end
The game runs. Two of our tests fail, the ones done yesterday that tested out the double-dispatch logic. They fail because the FakeUniverse doesn’t understand addObject.
I’m torn, because I think those tests are obsolete, but now’s not the time, so I change the fake addMissile to this:
function FakeUniverse:addObject(missile)
self.missile = missile
end
And the tests and the game run. We’ve converted missile to use the objects collection. Commit: “missile uses objects collection”.
Time to break, reflect, and sum up:
Summing Up
Well. That was productive, though a bit long. I spent at least an hour at the beginning of the session, just considering options and rejecting most of them. I considered a few different paths, and finally chose the one based on principle.
I believe that all good designs can come about through small, simple refactoring. As tempted as I was to dive in and create some special collider object or go all the way to my double dispatch idea, I stuck with principle and started refactoring the collision logic.
It got improved by removing new wave detection, and we discovered one patch of code that was being done for every asteroid but only needed to be done once.
And we removed all references to the special collections asteroids and missiles. That allowed us to remove some type-specific methods like ‘addMissile”, at the present cost of doing run-time type checking in the collision loops, to be sure that our specialized code inside those loops never sees anything it shouldn’t.
And it all works. It’s better in that it is moving toward a design contraction due to removing specialized collections, and it’s worse due to the type checking.
Overall, I’m pleased. And despite the length of the session, The code never stayed broken very long and I almost never got confused.
Long one, though. I hope you skipped most of it, unless you just like to see me maundering.