Collisions Revisited

OK, the collision logic, short as it is, has shown itself to be too weird. Not only is it implicated in an obscure Codea exception, but it isn’t even doing what we intended. So let’s do a bit of thinking before we revise it.

Here are a few topics, as they come to me, relating to collisions:

  • a ship might be easier to hit than a missile: collision radius or profile
  • it might take more than one missile strike to kill a ship
  • some items, like the sun, might do infinite damage to anything that hits them
  • some items, like the sun, might be completely immune to damage
  • some items might be visible but immune to collisions
  • some items might be subject to damage sometimes and not others
  • some items might be damaged by some other items and not other
  • a collision may cause objects to be deleted
  • a collision may cause objects to be added
  • there might be interaction at a distance
  • everything interesting happens inside the draw loop
  • editing collections over which you’re iterating is dangerous at best
  • in principle, any object on the screen might collide with any other

We can sum up a lot of these into the notion that what happens between two objects depends on the objects:

  • they may or may not interact, based on distance or some other criterion
  • actions taken depend on the pair: e.g. ship v missile is different from missile v missile

I am inclined, therefore, to accept that we need to check every object against every other object, probably every time through the draw loop. It would be nice not to check twice, that is, not to interact Ship1 v Missile5 and Missile5 v Ship1. However, we should probably build things so that the “right thing” happens if they are interacted twice. What’s the right thing, and how will it be determined? I’m inclined to leave it up to the objects. What that means, I’m not sure.

Note the Ship1:Missile5 battle. Proceeding naively, we’ll process both Ship1:Missile5 and Missile5:Ship1. We’d like Ship1 not to take double damage from Missile5. Our options include things like these:

  • make the collision loop process each pair only once. (we have that now but it is obscure).
  • make missile damage depend on the missile being alive. kill it when it first interacts. the second interaction will be benign.
  • have the missile and ship know that they have interacted before in this cycle and decline to interact again.

In the end, my design sense is to push decisions down to the lowest level that can handle them, in this case down to the individual ships and missiles and other space debris. It’s tempting to think that a decision should be made as early as possible, because it might be more efficient or more centralized. It might even be a good idea but I’m going the other way.

One more thing. I’m going to try to go with a much simpler interaction loop, just accepting the N-squared time and the double calls at the top. In aid of that, I’m going to assume that each draw cycle may come up with new objects to add (like the explosion) and objects to remove (like dead missiles). My design this time will not allow for an add or a delete during the draw event. If something has to act differently having been shot or killed, it is up to the object to handle that case even if it has scheduled itself for deletion.

So I plan to have collections U:Adds and U:Removes in addition to the main U:Drawn collection.

And I plan to keep the game working while I do this. Enough talk: here goes. Here’s current draw logic:

function draw()
    if not U.Running then return end
    
    U.Tick = U.Tick + 1
    background(40, 40, 50)
    
    for _,obj in pairs(U.Drawn) do
        obj:move()
    end
    
    collisions()
    
    for _,obj in pairs(U.Drawn) do
        obj:draw()
    end
end

We looked at collisions up above. I note that we’re not using U.Running, so I’m going to delete it for now. We’ll put it back if and when we need it. And I’m going back to an array style: the key-value style in U:Drawn didn’t buy us anything useful. Here we go, by intention:

function draw()
    U.Tick = U.Tick + 1
    
    moveAll()
    interactAll()
    drawAll()
end

function moveAll()
    for _, obj in ipairs(U.Drawn) do
        obj:move()
    end
end

function interactAll()
    -- nothing
end

function drawAll()
    background(40, 40, 50)
    for _, obj in ipairs(U.Drawn) do
        obj:draw()
    end
end

function addDrawnAtTop(anObject)
    table.insert(U.Drawn, 1, anObject)
end

function addDrawnAtBottom(anObject)
    table.insert(U.Drawn, anObject)
end

Note that I’ve converted to ipairs, and that I’m doing no interactions. Everything in the game works except that missiles and ship collisions don’t do anything. That took moments. However, the next bit will be trickier. I think I’ll follow the previous version and tell objects to die at first, then push the behavior down. So …

function interactAll()
    for _, a in ipairs(U.Drawn) do
        for _, b in ipairs(U.Drawn) do
            if colliding(a,b) then
                a:die()
                b:die()
            end
        end
    end
end

I scarcely even looked at colliding: I’m just going to run this and see what it does. No, not quite. I’ll look at the die() methods first. Missile, Ship, and Explosion all implement die():

-- Explosion
function Explosion:die()
    U.Drawn[self] = nil
end

-- Missile
function Missile:die()
    U.Drawn[self] = nil
end

-- Ship
function Ship:die()
    U.Drawn[self] = nil
    Explosion(self)
end

OK,, the first two want to die, the second wants to add something I’m really wanting an abstraction here, up in U[niverse]. These guys know too much about how the universe works. Universe probably wants to become a class. But not now. Instead, however, I’ll build a function on U and use it. I change them each like this:

function Explosion:die()
    U.kill(self)
end

And I do this in the setup of U:

-- The Universe

U = {}
U.Tick = 0
U.Adds ={}
U.Drawn = {}
U.Removes = {}
U.Touched = {}
U.Running = true
U.MissileKillDistance = 20
U.kill = function(objToRemove)
    table.insert(U.Removes, objToRemove)
end

This is actually pretty idiomatic Lua, putting a function into a table. I’m not entirely comfortable with that style, because I’m an object kind of guy. But we’re here to drain the swamp right now, and we’ll let it be. We might even come to like it.

Now to use that U.Removes table in draw(). I think the plan should be, at the beginningof draw, remove everyone who needs removing before doing anything. Then clear the table, letting it build up dead guys as we do things. The alternative was to clear the table at the end of draw, but I’m imagining something might happen outside of draw, like in touched. Here it is:

function draw()
    U.Tick = U.Tick + 1
    remove()
    moveAll()
    interactAll()
    drawAll()
end

function remove()
    for obj in ipairs(U.Removes) do
        table.remove(U.Drawn, obj)
    end
    U.Removes = {}
end

I have a brief twinge about this: table.remove crunches up the array, so there will be a lot of indexing going on here. That was one reason why the key-value table might have been better. I’m not going to worry about performance right now. That only leads to trouble. I’ve not run this yet, so here goes … and something weird happens. Watch this and note that when his bullet strikes the lower guy, the top guy is the one to die:

MOVIE HERE

It happens that way when I fire one across and two down. It does not happen when I just fire one down. I am surprised. Is there some way to write a unit test for this? I sure don’t see one. I resort to print.

Ah, OK. This just won’t work. We can’t remove an object by its identity, only by its index. So for this scheme to work at all, we’d have to save the indices in U.Removes and then remove them, in reverse order, when we’re done. Back to the key-value scheme, I’m afraid. No problem, it’ll be quick:

-- Main
-- HAVE YOU PUSHED TO GITHUB TODAY?

-- S3 Spacewar

-- The Universe

U = {}
U.Tick = 0
U.Adds ={}
U.Drawn = {}
U.Removes = {}
U.Touched = {}
U.Running = true
U.MissileKillDistance = 20
U.kill = function(objToRemove)
    table.insert(U.Removes, objToRemove)
end
U.add = function(objToAdd)
    table.insert(U.Adds, objToAdd)
end

function setup()
    Ship(1)
    Ship(2)
    U.Running = true
end

function touched(touchid)
    for _,obj in ipairs(U.Touched) do
        obj:touched(touchid)
    end
end

function draw()
    U.Tick = U.Tick + 1
    remove()
    add()
    moveAll()
    interactAll()
    drawAll()
end

function remove()
    for _, obj in ipairs(U.Removes) do
        U.Drawn[obj] = nil
    end
    U.Removes = {}
end

function add()
    for _, obj in ipairs(U.Adds) do
        U.Drawn[obj] = obj
    end
    U.Adds = {}
end

function moveAll()
    for _, obj in pairs(U.Drawn) do
        obj:move()
    end
end

function interactAll()
    for _, a in pairs(U.Drawn) do
        for _, b in pairs(U.Drawn) do
            if colliding(a,b) then
                a:die()
                b:die()
            end
        end
    end
end

function drawAll()
    background(40, 40, 50)
    for _, obj in pairs(U.Drawn) do
        obj:draw()
    end
end

function addTouched(anObject)
    table.insert(U.Touched, anObject)
end

function clip_to_screen(vec)
    return vec2(vec.x%WIDTH, vec.y%HEIGHT)
end

function colliding(obj1, obj2)
    if obj1 == nil then return false end
    if obj2 == nil then return false end
    if obj1.cannotCollide then return false end
    if obj2.cannotCollide then return false end
    if obj1 == obj2 then return false end
    local d = obj1.pos:dist(obj2.pos)
    local result = d < U.MissileKillDistance
    return result
end

The necessary changes are made elsewhere, to use add instead of addDrawnAtBottom and so on. Everything is working cleanly:

MOVIE HERE

Any lessons?

What have we learned in class today, Ron? Well, these things come to mind:

  • My inexperience with Lua arrays leads me to make mistakes. This isn’t very surprising: I’ve avoided using untyped array-like collections for decades. That said, they don’t seem useful here, since we’ll have many objects and few removals at any given draw cycle, so the key-value style is probably better.
  • I’d like to have had better support from testing but even now I’m not sure what tests I could write. Relatedly, the collision test that we do have is now broken, because it is not following the new adding / removing convention. I’ll improve that next time, or explain why I decided to remove it. But I don’t think I’ll remove it: it gives me at least a foothold for testing the more powerful logic where objects handle more of the interaction logic.
  • We’re back to colliding objects just die, and while we see no evidence of it, we are surely killing the ship and missile that collide twice. This would be easy to see: a print in Ship:die should print twice. (And in fact it does: I just tried it.) That should sort out as we go forward with interaction behavior.
  • The logic of things in draw seems more straightforward, even though it does consider collisions twice. This will be cleaned up as we push interaction behavior down. At this moment, I think I’ll leave it up to the two objects who are interacting to even decide if they are colliding. It has to be done somewhere, but it seems to me that leaving it up to the objects is better design.

Overall, I’m feeling a bit disturbed by the amount of confusion I’m feeling, but I am not inclined to think that “more design” or “more thinking” would have made things better. I think that bumping my nose against reality is the best way to move forward, and I think a little nose bumping has left us in a better spot, even though we’ve kind of gone around in a circle. It doesn’t trouble me to try a new idea and have it turn out that the old idea was better. The worst that can happen is that I’ll learn something, and that’s never bad. The best that can happen, and it happened here, is that I wind up with a better understanding of how things work and what needs to be done.

See you next time!