Part Six - Playing hide and seek with pixels

At the beginning of August 2009, I had already progressed quite far. In the previous two months I got to the point where I could run with the Prince through the first level, except that none of the interactive elements of the game worked yet.
And there was one big visual problem. Walking behind the pillars in the level didn't cause the character to be occluded. The prince was simply a set of sprites on top of the level background graphics. Not good enough.


In the Apple II original (and almost all other versions of the game) this issue is solved easily because the Kid is drawn into the same frame buffer as the level graphics. Then afterwards the occluding front pieces of each block are simply drawn again, overdrawing the parts of the player that should be invisible. It's as common a technique as possible.
But since the C64 has a color attribute system where you can only specify colors for each 8x8 block and not per pixel, using the same kind of drawing system would've caused the player to look very weird. The colors used for floors and other nearby parts would bleed into the player image. A problem which is commonly known as "color clash". Look no further than the ZX Spectrum version, which suffers from this problem, albeit they did try to hide it as much as possible.

On the ZX Spectrum, the colors of the torch bleed into the image of the character

I knew that I definitely wanted to avoid this problem on the C64. That's why I initially set out to use sprites, which have their own set of colors and therefore won't clash with the background colors.

Now generally you would solve the visibility of a sprite on the C64 using the sprite/background priority system. The VIC-II chip considers two of the 4 possible color bit-pairs as background and the other two as foreground. Each sprite can be selected to be either above foreground and background, or between foreground and background. Unfortunately this means that the foreground colors (bit pairs 10 and 11) are always drawn on top of sprites, so it's not possible to fully occlude a sprite with all of the possible colors.

The other method typically used to obscure certain parts of a sprite is by overlaying them with another sprite that has a higher priority and contains the same graphics as the background. This however requires that sprite to share some of its colors with the background, which puts a restriction on the colors to use for the actual sprite (two out of three sprite colors are shared).
Another trick is to put one sprite behind the foreground layer and the lower priority sprite in front of the foreground layer. This will perform the same masking but the foreground graphics will hide the sprite that is causing the masking.
But I knew already from the size of the animation images that I'll need a lot of sprites and that using extra sprites for masking would be pretty much impossible. Plus that would've meant even higher memory usage.

After considering all of these options and also taking their complexities into account, I've decided for the one solution that would be slowest, but would yield the most accurate results: Actually modifying the sprite data in memory, for each frame, every time. Ouch. After all, I wanted to have pixel-precise occlusion.
So whenever the character would walk behind a pillar or other occluding object, I would have to mask out those pixels of the sprites and replace them with the transparent color bit-pair.
I was confident that I could optimize the code to the point where it would be fast enough.

To simplify the masking code, I decided to use a whole bitmap (8KB of data) to buffer the mask for the whole screen. I thought that it should be easy to piggyback the drawing of the mask onto the normal drawing code, which I already was familiar with.
I basically just modified the function that draws the front piece images (182F:drawFrontPieceImage) to also draw into the mask bitmap, and added a simple set of images to be used as masks.
The result looked like this:

The mask bitmap for the first screen of the game. Just think of it as a 1-bit depth buffer

The black parts of the image are pixels where the sprites of the Prince should be invisible. Basically using an AND operation of this bitmap with the sprite data would mask out the occluded parts.

I probably went through 6 or 7 different versions of this masking code. In the beginning it was very unoptimized and therefore really slow. One of the reasons why it was so CPU intensive was the fact that the mask data needed to be shifted to align with the sprite data, depending on the X coordinate of the character on screen.

It took a lot of work, but in the end I was quite happy with the performance, but I'm sure someone is going to find some cycles to save to make it even faster. I have specialized the routines for 2, 3, 4, 5 and 6 byte-wide character images, here's an excerpt that performs reading of the mask, shifting and anding for one pixel row of a sprite that contains a two-byte wide image:

            ; get branch offset for shift array
            ldy ImageXOffset
            lda BlockOffsetToShiftBranchOffset2,y
            sta ShiftBranchOffset

            ; read 3 bytes from mask
            ldy #$00
            lda (MaskBitmapPtr),y
            sta CurrentMask
            
            ldy #$08
            lda (MaskBitmapPtr),y
            sta CurrentMask+1

            ldy #$10
            lda (MaskBitmapPtr),y
            sta CurrentMask+2

            ; shift the mask to align with the sprite
            clv
ShiftBranchOffset = *+1
            bvc ShiftBranchOffset
            asl CurrentMask+2
            rol CurrentMask+1
            rol CurrentMask+0
            asl CurrentMask+2
            rol CurrentMask+1
            rol CurrentMask+0
            asl CurrentMask+2
            rol CurrentMask+1
            rol CurrentMask+0
            asl CurrentMask+2
            rol CurrentMask+1
            rol CurrentMask+0
            asl CurrentMask+2
            rol CurrentMask+1
            rol CurrentMask+0
            asl CurrentMask+2
            rol CurrentMask+1
            rol CurrentMask+0
            asl CurrentMask+2
            rol CurrentMask+1
            rol CurrentMask+0
            asl CurrentMask+2
            rol CurrentMask+1
            rol CurrentMask+0

            txa
            tay
            
            ; mask and store the pixel row
            lda CurrentMask
            and (RomSpriteImagePtr),y
            sta (SpriteImagePtr),y

            iny

            lda CurrentMask+1
            and (RomSpriteImagePtr),y
            sta (SpriteImagePtr),y

The right amount of shift operations is performed by modifying the parameter of the branch instruction. Three mask bytes are required temporarily, even though only two will be used to actually mask the sprite data afterwards.

Here's an early version of the masking code in action, a video I captured on August 9th, 2009:

You can see that the masking is not really precise yet (there's a one pixel offset, because the sprites are positioned on the full 320 pixel horizontal grid), and that it gets quite choppy when the player image is at its maximum width during a jump.

Download a C64 .prg of the build from 09-Aug-2009. Like the previous one, this will require a REU to run.

I wanted to press on now, to get to the point where the level is fully playable. So I entered another long phase of reverse-engineering the disassembled code to understand the parts that deal with animating the dynamic blocks, such as torches, gates, spikes, etc.
From reading the document, I saw that this was all a bit complicated. Starting on page 10 there's an explanation of the "redraw buffers". Those are 30 byte buffers, which contain a redraw count for each block on the screen. Typically these are filled with a value of 2 for a block to make sure it gets redrawn in both frame buffers (since the game uses double-buffering).
It didn't take me very long to find the redraw buffers and the code that deals with them, but it did take quite a while to identify each buffer correctly, because they're all a bit similar:

5E3C:HalfBuf
5E5A:RedBuf
5E78:FRedBuf
5E96:FloorBuf
5EB4:WipeBuf
5ED2:MoveBuf
5EF0:ObjBuf
5F0E:WhiteBuf
5F2C:TopBuf

The simplest redraw buffer is RedBuf. Setting an entry for a block in RedBuf causes the whole block to be redrawn. To get a correct redraw it's often necessary to clear the block first, this is done by using WipeBuf with a certain wipe height (which is stored in WhiteBuf). So, for example, a wipe height of $3f (63 pixels) would wipe the whole block. The reference point is the bottom of the block.

So typically a redraw of a block is triggered by both storing a value in WipeBuf and RedBuf:

            lda #$3f
            sta ImageTableEntry     ; ImageTableEntry is used for wipe height and stored in WhiteBuf

            ; Get the current position of the character and 
            ; convert it to a block index in Y
            jsr convertCharXAndYToBlockIndexInY  

            lda #$02
            jsr storeRedBufValue    ; store into RedBuf at offset Y
            jsr storeWipeBufValue   ; store into WipeBuf at offset Y

It doesn't matter if storeWipBufValue is called after storeRedBufValue, since the order of performing the redraws is fixed, and the wipe will always come before the redraw.

In the end there's one function dealing with applying the redraw buffers and it's called for every block from an iteration loop that is very much like iterateScreen:

1293:iterateScreenForRedraw
164B:redrawBlock

So as expected, redrawBlock has a certain fixed order in which it handles all of the redraw buffers. Wipes come first, then normal redraws, and so on until the last buffer, which is FRedBuf, for redrawing front pieces:

;----------------------------------
redrawBlock:
            lda WipeBuf,y
            beq noWipeNeeded

            sec
            sbc #$01
            sta WipeBuf,y

            jsr wipeBlock
            ldy ScreenUpdateBlockIndex

noWipeNeeded:

            lda RedBuf,y
            beq noRedrawNeeded

            sec
            sbc #$01
            sta RedBuf,y

            jsr switchToBgImageList
            jsr drawBlock
            ldy ScreenUpdateBlockIndex

noRedrawNeeded:

            [...]

            lda FRedBuf,y
            beq noFrontPieceRedrawNeeded

            sec
            sbc #$01
            sta FRedBuf,y

            jsr drawFrontPieceImage
            ldy ScreenUpdateBlockIndex

noFrontPieceRedrawNeeded:
            rts
;----------------------------------

Oh it looks quite simple now, but that took me a while. Many wrong leads that caused me to go off in the wrong direction, but thankfully redrawing calls the same basic drawing functions like drawBlock which I already knew from drawing the initial screen, so that helped in understanding how it all works together.

So as soon as I put in working versions of redrawBlock and iterateScreenForRedraw, I was able to add the code that stores values into the redraw buffers. The first one I tried were the torches.
Those are "transitional objects", so they use MoveBuf to redraw themselves. Most of the trans objects have specialized drawing code, e.g. the gate updates itself by drawing a tiled sequence of gate parts, depending on how high the gate currently is raised. The code for drawing the torches is specialized to only draw the flame itself, skipping the rest of the block.

The starting point for the trans object system is this function:

EE00:animateTransObjs

For each active trans object, it maintains the movement direction (e.g. for gates and spikes), the block index and the screen number, and then calls animateTransObj to update it.

F0FE:animateTransObj

Depending on the object id, this function dispatches to one of many different individual ones:

F194:animateExitTransObj
F1EC:animateGateTransObj
F264:animatePressPlateTransObj
F287:animateJawTransObj
F2DF:animateFlaskTransObj
F302:animateSwordTransObj
F31B:animateTorchTransObj
F354:animateSpikesTransObj
F386:animateLooseFloorTransObj

Their main job is to update the BlueSpec value for their block and store into the redraw buffers to make sure they're updated during the next redraw loop.

It is now late August 2009. I had various redraws working, and I started to also set video and color RAM differently for each block, to introduce a bit of color into my screens. Due to many changes some of the drawing was often broken, so the versions from this time were not really playable. But here's how it looked like with some early flame animations in place:

Some colors to make the new torch flame animations a bit prettier

So that's it for this time. In the next part we're gonna look at bit more at the redrawing of gates and spikes, and why I was suddenly forced to reveal my project to the public.