Space Invaders 20

Is it worse luck when Friday the 13th comes a day early? Or a near miss? Time to dig further into bombs failing to miss shields. (Added Friday: It was worse luck.)

Things started out interestingly enough.

As he so often does, Dave1707 of the Codea forum wrote a useful patch of code, shown here for reference:

displayMode(STANDARD)

function setup()
    parameter.boolean("circ",false)
    fill(255,0,0)
    rectMode(CENTER)
    spriteMode(CENTER)

    missileWidth=10
    missileHeight=20
    missileTab={}

    shieldTab={}
    shieldImg={}
    for s=1,5 do
        shieldImg[s]=image(88,64)
        setContext(shieldImg[s])
        background(255)
        setContext()
        shieldTab[s]=shields(shieldImg[s],vec2(180*s,HEIGHT/2),88,64)
    end
end

function draw()
    background(0)
    text("tap multiple times near the bottom or top",WIDTH/2,100)    
    for a,b in pairs(missileTab) do
        rect(b.mx,b.my,missileWidth,missileHeight)
        b.my=b.my+b.mv
        if b.my>HEIGHT or b.my<0 then
            table.remove(missileTab,a)
        end
    end
    for s=1,#shieldTab do
        shieldTab[s]:draw()
    end
end

function touched(t)
    if t.state==BEGAN then 
        v=5
        if t.y>HEIGHT/2 then 
            v=-5
        end
        table.insert(missileTab,{mx=t.x,my=t.y,mv=v})
    end    
end

shields=class()

function shields:init(shld,pos,sw,sh)
    self.shield=shld
    self.center=pos
    self.width=sw
    self.height=sh 
    self.left=self.center.x-self.width/2
    self.right=self.center.x+self.width/2
    self.bottom=self.center.y-self.height/2
    self.top=self.center.y+self.height/2 
    self.withinRange=false
    self.hit=false
end

function shields:draw()
    sprite(self.shield,self.center.x,self.center.y)
    for a,b in pairs(missileTab) do
        self:shieldRange(b)
        self:shieldHit(b)
        if circ then
            self:shieldExplodeCirc(a,b)
        else
            self:shieldExplodeRec(a,b)
        end        
    end
end

function shields:shieldRange(b)
    if b.mx+missileWidth/2>=self.left and 
            b.mx-missileWidth/2<=self.right and 
            b.my+missileHeight/2>self.bottom and 
            b.my-missileHeight/2<self.top then
        self.withinRange=true
    end
end

function shields:shieldHit(b)
    if self.withinRange then        
        for x=-missileWidth/2,missileWidth/2 do
            for y=-missileHeight/2,missileHeight/2 do
                xx=(b.mx-(self.left)+x)//1
                yy=(b.my-(self.bottom)+y)//1
                if xx>=1 and xx<=self.width and yy>=1 and yy<=self.height then
                    r1,g1,b1=self.shield:get(xx,yy)
                    if r1+g1+b1>0 then
                        self.hit=true
                        self.withinRange=false
                        return
                    end
                end
            end
        end
    end
end

function shields:shieldExplodeRec(a,b)
    if self.hit then
        for x=-missileWidth,missileWidth do
            for y=1,15 do
                for z=1,15 do
                    a1=math.random(-15,15)
                    b1=math.random(25)
                    if b.mv<0 then
                        b1=-b1-missileHeight/2                        
                    end
                    self.shield:set((b.mx-self.left+x+a1)//1,
                        (b.my-self.bottom+y+b1)//1,0,0,0,0)
                end
            end
        end 
        self.hit=false
        table.remove(missileTab,a)   
    end    
end


function shields:shieldExplodeCirc(a,b)
    if self.hit then
        local rad=15
        local t=rad
        if b.mv<0 then
            t=-rad
        end
        xx=b.mx-self.left
        yy=b.my-self.bottom+t
        for xx1=-rad,rad do
            for yy1=-rad,yy+rad do
                if xx1^2+yy1^2<rad^2 then
                    self.shield:set((xx1+xx)//1,(yy1+yy)//1,0,0,0,0)
                end                
            end
        end
        self.hit=false
        table.remove(missileTab,a)   
    end    
end

Dave’s program demonstrates at least two interesting things. More obviously, as you can see in the picture, he shows how to clear bits in a shield, either randomly, as shown toward the left, or in a circle, as shown toward the right.

Internally, his code also checks to see if the missile has actually hit a non-zero pixel in the bitmap, so that if you drop several bombs in the same place, they ultimately dig through the shield. You’ll recall that the code I wrote yesterday (normally I’d say “we”, but I don’t want to make you share the blame for its inadequacies) … the code I wrote yesterday checks to see if the rectangle of the bomb intersects the rectangle of the shield, but that’s as far as it goes. So we would see a collision just now even if the shield were totally destroyed.

The code that does that checking is this:

function shields:shieldHit(b)
    if self.withinRange then        
        for x=-missileWidth/2,missileWidth/2 do
            for y=-missileHeight/2,missileHeight/2 do
                xx=(b.mx-(self.left)+x)//1
                yy=(b.my-(self.bottom)+y)//1
                if xx>=1 and xx<=self.width and yy>=1 and yy<=self.height then
                    r1,g1,b1=self.shield:get(xx,yy)
                    if r1+g1+b1>0 then
                        self.hit=true
                        self.withinRange=false
                        return
                    end
                end
            end
        end
    end
end

Let’s see if we can figure this out. Maybe we’ll need to refactor it a bit, maybe not.

Clearly it is looping with x going across the missile, and y going up the missile, so that x will range -width/2 to +width/2 and similarly for y. So he’s assuming the sprites are centered.

OK, so then this:

xx=(b.mx-(self.left)+x)//1
yy=(b.my-(self.bottom)+y)//1

We see below that he’s going to do a get(xx,yy) on the bitmap, so these must be intended to be the coordinates of the pixels in the shield that correspond to the pixels in the missile rectangle. Let’s see if we can see why.

b.mx is the bomb’s x coordinate. We can see that in the draw and elsewhere. What about left? In the shield init we see this:

function shields:init(shld,pos,sw,sh)
    self.shield=shld
    self.center=pos
    self.width=sw
    self.height=sh 
    self.left=self.center.x-self.width/2
    self.right=self.center.x+self.width/2
    self.bottom=self.center.y-self.height/2
    self.top=self.center.y+self.height/2 
    self.withinRange=false
    self.hit=false
end

Things begin to get a bit weird now, as we discover fractional pixel coordinates are being used.

So left is center x - the width over 2, so that should be the coordinate of the left edge, more or less. I say more or less. Suppose the width is 3 (which in our case it is), and center x is 100. Then left will be 100 - 3/2, which is 100-1.5, which is 98.5, which is a decent number but not enough of an integer to be a pixel index.

You may have noticed the //1 in the code above. That’s Lua’s way of forcing an integer divide, which will remove fractions. 2.5//1 is 2.0 -2.5//1 is -3.0. Is that “round toward minus infinity”? I can never remember.

Where we we? Oh, yes figuring out

xx=(b.mx-(self.left)+x)//1

So b.mx - self.left is the relative coordinate of the left edge bomb inside the shield, and that plus x is the position of the x-th pixel (-width to width) we’re interested in. And then forced to integer.

The next line is telling:

if xx>=1 and xx<=self.width and yy>=1 and yy<=self.height then

We’re checking to be sure we are within the actual rectangle of the shield, because some of the pixels of the bomb may not be inside yet. We don’t want to try to fetch pixels that don’t exist. The documentation says that will error. The fact appears to be that it returns as if the pixel were empty.

Now we can go on:

                if xx>=1 and xx<=self.width and yy>=1 and yy<=self.height then
                    r1,g1,b1=self.shield:get(xx,yy)
                    if r1+g1+b1>0 then
                        self.hit=true
                        self.withinRange=false
                        return
                    end
                end

This fetches the colors from the shield at the designated point and sums them. Since colors are always positive, if this sum is greater than zero, there’s a pixel there, we have hit the shield, and can return true.

This appears to work. I have issues with it.

The code is tricky and the coordinates go wonky between even-width and odd-width bitmaps.

First, the index manipulation is hard to understand after the fact, and harder to write before the fact. It makes my rectangle checker look obvious, which it really isn’t.

Second, there’s a lot of magic going on between what our code says and what Codea does. We are careful to set our bitmaps at integer coordinates, which helps. If the bitmap is 3 pixels wide, and we set it at 10,10, then its x coordinates will be 9,10,11. That’s nearly good.

But what if the bitmap is 4 pixels wide, set at 10,10? What are the pixel coordinates now? We don’t know what Codea does, and so far I’ve not been able to figure out a way to find out.

But maybe we shouldn’t care. Haha, I wish. The shields are 22x16. We have every reason to wonder where the overlap is. In addition, we’re at scale 4. What does that change?

I feel the need to do an experiment to see if I can drag out any facts. I’ll try drawing a rectangle and drawing some lines through it, and see what we can see. And I’ll do it at a large scale.

Experiment

I started with this:

-- CUBase

function setup()
    --runTests()
    map4 = image(4,4)
    for x = 1,4 do
        for y = 1,4 do
            if (x+y)%2 == 0 then
                c = color(255,0,0)
            else
                c = color(0,255,0)
            end
            map4:set(x,y,c)
        end
    end
    map4Left = map4.width/2
    print("map4Left", map4Left)
    map3 = image(3,3) 
    for x = 1,3 do
        for y = 1,3 do
            if (x+y)%2 == 0 then
                c = color(255,0,0)
            else
                c = color(0,255,0)
            end
            map3:set(x,y,c)
        end
    end
    map3Left = map3.width/2
    print("map3Left", map3Left)
end

function draw()
    background(200,200,200)
    pushMatrix()
    pushStyle()
    fontSize(50)
    textAlign(CENTER)
    --text(Console, WIDTH/2, HEIGHT-200)
    drawExample()
    popStyle()
    popMatrix()
end

function runTests()
    assert(CodeaUnit, "Please add CodeaUnit as a dependency")
    local det = CodeaUnit.detailed
    CodeaUnit.detailed = false
    Console = _.execute()
    CodeaUnit.detailed = det
end

function drawExample()
    pushMatrix()
    pushStyle()
    rectMode(CENTER)
    translate(WIDTH/2,HEIGHT/2)
    scale(16)
    sprite(map4,0,0)
    sprite(map3,0,10)
    strokeWidth(0.125)
    stroke(0)
    line(0,50, 0,-50)
    popStyle()
    popMatrix()
end

That draws this:

If you are color blind and can’t see that, please let me know. I’d like to use colors that work for you. Here is a different coloring:

By the way, I see a faint red border on the 4x4 one. That surely shouldn’t really be there. I mean come on, there are only 4 bits across!

Here’s a pic at scale 32:

There’s definitely a border. I wonder why. I didn’t fill the map first and there are ONLY FOUR PIXELS ACROSS!

Meh. Anyway I’m trying to figure out the math for things hitting things.

Imagine a 1 pixel wide object, centered, colliding. I’ll draw those too:

In the case of the one on top of the 3x3, we see that there are pixels underneath just fine and we can surely do some arithmetic and lift them out.

But in the case of the 4x4, there are TWO pixels under each of the bottom two pixels of my missile. What’s up with that?

Weirdly enough, testing made things worse. I became more confused.

I hate this kind of fiddly work. I guess I’ll write some tests now. I begin with this:

-- RJ 20200813
-- bitmap tests
    
function testCodeaUnitFunctionality()
    CodeaUnit.detailed = true

    _:describe("Bitmap Test Suite", function()

        _:before(function()
        end)

        _:after(function()
            -- Some teardown
        end)
        
        _:test("pixel offsets", function()
            findColors(map3,m3Center, bomb, b3Center)
        end)

    end)
end

function findColors(shield,shieldCenter, bomb, bombCenter)
    for x = -bomb.width/2,bomb.width/2 do
        print(x)
    end
end

This prints -0.5, 0.5, which is perhaps not surprising. Neither of these is an index into the bomb of course.

I’m definitely fumbling my way forward here, and checking every step. At this point it seems to me that with the width of the bomb being 1, I’d like to loop once. Maybe that’s a special case, but what if it were three? Then it would go -1.5, -0.5, 0.5, 1.5. That seems wrong. Of course if we had an even number of pixels across those values would make more sense.

Anyway … suppose we don’t mind the extra checking and we just want to get the pixels that correspond to wherever the bomb hit the shield, offset by those values.

I would start from the relative offset of the bomb in the shield. I’m going to work from the shield coordinates, assuming spriteMode(CENTER) for both. So if we consider

I literally stopped here. The more I thought, the worse it got. If we allow odds to overlap evens, as in my 4x4 graphic, we’ll be stuck with fractional coordinates.

Friday begins here.

First law of holes: If you find yourself in a hole, stop digging.

I do’t know who came up with that law, but it’s a good one. Yesterday, everything I did turned to sand in my hands. I tried to come up with a sensible way to understand what Codea would do, but if you’re drawing odd- and even-width bitmaps in CENTER mode, it’s clear that it will position the center between the pixels on the even ones, and down the middle of the pixel on the odd ones. And the arithmetic for that is more than I want to deal with.

So I stopped digging. I rested, ate, read a book, talked to the cat, wrote a ray-casting script, and generally set this problem down.

And a conclusion came to me, in that gentle way they sometimes do, as opposed to those ones that smack you in the forehead.

Use CORNER coordinates.

CORNER mode puts the (1,1) pixel of the bitmap at the exact coordinate you choose for the bitmap sprite. If everyone uses CORNER, even versus odd width won’t matter: the pixels will line up exactly on top of each other.

Of course everything will be shifted upward and to the left as a function of the thing’s actual size, but we can shift everything right and down … and do it in integer steps, so that the visual effect will line up with the logical tests. I don’t think you can see a half pixel at scale 4, but in any case we should be able to do it right.

I even tapped a quick change to the program into my other iPad, and it nearly worked fine.

Of course the collision logic was wrong, and I had to remember to set both rectMode and spriteMode to CORNER, which confused me for a while, because our invaders are rectangles now, but the shields are bitmap sprites.

In the course of that, I kept getting bombs that clearly missed destroying shields, and bombs that clearly hit not destroying them. In the course of that, I came to suspect that there was something wrong with my rectangle intersection function, and so I looked up how to do it on the internet and reimplemented it that way.

When it still failed was when I finally realized I’d set rectMode and not spriteMode.

Here, for the record, is the new rectangle intersection code:

function rectanglesIntersectAt(bl1,w1,h1, bl2,w2,h2)
   local tr1 = bl1 + vec2(w1,h1) - vec2(1,1)
   local tr2 = bl2 + vec2(w2,h2) - vec2(1,1)
   if bl1.y > tr2.y or bl2.y > tr1.y then return nil end
   if bl1.x > tr2.x or bl2.x > tr1.x then return nil end
   mark = bl1
   return bl1
end

The naming is weird, and I’ll probably change it, but “tr” stands for top right and “bl” stands for bottom left.

I’ll do that work in an article for today. Let’s get this one summed up and out of my face.

Summing Up

I think the only real lesson here is the First Law of Holes. And a bit of a sub-lesson:

I think that if I had not been writing this article at the same time as the work, I’d have kept digging. It was the thought that my reader would see me thrashing stupidly for pages and pages of deteriorating drivel until I lay panting on the floor in a pool of my own sweat, quivering like a flabby fish out of water, and laugh and the ignorant old man who somehow couldn’t manage a fraction or two …

Well, anyway, it was the fact that the article was going awry that really stopped me. And even then, I didn’t stop programming–or trying to program–for a while after that, until it was clear that I could never make sense of what I was doing.

In a team situation, I’d like to think that I’d ask for help, perhaps in a humorous self-deprecating fashion to limit the laughter. In a pairing situation, I’m sure we’d have stopped sooner because as soon as we were both out of ideas, we’d have asked for help or gone to the cafeteria.

On my own, I tend not to stop soon enough. Finally I do, I set my mind on something else, and usually an answer pops up.

So stop digging.

No code for Thursday the 13th, because no commits.

See you … well, today, actually. Whew!