Thursday, October 20, 2011

Part Four - To bitmap, or not to bitmap, that is the question!

Now that I had a somewhat basic understanding of the way the game handles the player animations, controls and collision detection, there was a big unknown area left. How does it draw the background graphics? How does it handle the visibility of the Kid when he goes behind a pillar?

Thankfully the document explains quite a bit about the drawing system.

First, let's have a closer look at how the level data looks like. Each level consists of 24 screens, and each screen is divided into three rows of 10 blocks each. So 30 blocks in total per screen. Blocks can be identified by their X and Y coordinates or by their block index, e.g. the block in the bottom right corner has X/Y of 9/2 or a block index of 29 (we start to count at zero).

Block indices

The data structure to describe the layout of a screen is simply 30 bytes, one for each block, containing a 5-bit object id number per block. The object ids were not listed in the document, but luckily someone else had already reverse-engineered them (see page 12 of this document). I list them here for completeness sake with the names that Jordan used:


Here's the data describing the first screen of the game (note that the values need to be AND-ed with $1f to get object ids):
$00 $00 $00 $21 $01 $21 $21 $21 $34 $34
$33 $33 $21 $23 $00 $34 $14 $14 $14 $34
$14 $14 $34 $34 $2E $23 $0B $01 $21 $34

Interestingly, the PC version has an additional object id, even though the levels are basically identical to the Apple II version. That extra type is OBJID_TORCH_WITH_RUBBLE with id $1e.
When a falling floor lands, it replaces the current block with OBJID_RUBBLE. But if that happens at a block of type OBJID_TORCH then the torch will suddenly disappear, because OBJID_RUBBLE does not include a torch. This bug has been fixed in the PC version (and probably others as well), where the block will be replaced with OBJID_TORCH_WITH_RUBBLE if it was OBJID_TORCH.

So each screen is 30 bytes and there are 24 screens, which yields a total size of 720 bytes for the whole level layout. This part of the level data is called BlueType.
There's a second set of 720 bytes per level (BlueSpec) which contains a state value byte for each block. Here the game keeps track of animation states (how far a gate has been raised, how far the spikes are extended, etc.)

All of the above has been documented already, so nothing here was really new to me. But it didn't really help me with figuring out how to draw the screens yet. I had to do more code digging to find out.

After having looked through the collision code earlier, I was able to identify a few crucial memory locations that deal with screens:


VisScrn is the currently visible screen number (1 to 24).
If NewVisScrn is not equal to VisScrn, then it will cause a new screen to be drawn (after which VisScrn is set to NewVisScrn).
There's also a routine I named


which fills in the other variables, the 8 screens surrounding the currently visible screen.

I experimentally found out that it's easy to force the game to draw a new screen, by setting NewVisScreen to the desired screen number, but when doing that the Kid was still in the old room (i.e. collision detection was performed in that one), but I quickly noticed that I also had to change KidScrn ($5b) to the new screen to fully teleport the player.

Now I was finally making a bit of progress. The code that changes NewVisScrn is triggered by


whose name was mentioned in the document. Basically the game checks if a character is exiting the screen (5B08:checkIfCharIsOffscreen) and changes CharScrn ($4b) if that's the case (5415:changeCharScrn). Then it sets NewVisScrn to CharScrn.

After that


detects the screen change and sets ScreenHasNotBeenDrawn to 1, which indicates that the drawing code has to do a full screen refresh.

At this point, I understood enough to really find the main update loop and make sense of it. This allowed me to make my own program structure to be more like the Apple II game.

I identified mainLoop to be


and with all final labels it looks like this:

            jsr updateAndGetRandomNumber
            lda #$00
            sta KidStrengthDelta
            sta ShadStrengthDelta
            jsr updateInputDevices
            jsr isButtonPressed
            bpl l21a2

            lda #$01
            jmp initGameAndLevelImpl
            jsr updateTimers
            jsr updateCharacters
            jsr activateScreenFlash
            jsr updateScreen
            jsr updateSoundEffects
            jsr clearSoundEffectBuffer
            jsr updateScreenFlash
            jsr updateMusic
            lda NextLevel
            cmp CurrentLevel
            beq mainLoop
            jsr l27e5                         ; does something special before level 2
            jmp activateNextLevelOrCutscene

Back then I didn't know what most of these do, but updateScreen stood out because it did something with ScreenHasNotBeenDrawn. It checks if it's 0 or 1 and then branches, to either draw the whole screen (2439:initialDrawScreen) or just the parts that have changed in the current frame (2482:redrawScreen).
Initially I had no idea what redrawScreen did. All I cared about was initialDrawScreen. I remember that at this point I didn't stop until I had all of its sub-routines documented. It turned out to be a pretty straight forward system.
It basically scans through the blue print data of the screen (1290:iterateScreen) using the helper function (04CC:getScrnEntryInBluePrint) and calls (161E:drawBlock) for each block.

At this point it really dawned on me that I will probably have to reproduce the whole screen drawing using a bitmap. Initially I still thought that I could probably use the old C64 shortcut of using a modified character set, which means to you only have to store one or two bytes to draw a whole 8x8 pixel block on the screen. But using bitmaps meant that I not only have to write 8 times as much data, also I'll need significantly more memory as frame buffer. And it was already tight.
I finally noticed that the screen can not be nicely divided into 8x8 blocks. The height of one block row was not 64 pixels, but 63 pixels. This was because the top three pixels of the screen actually show the bottom 3 pixels of the screen above. That was something which was necessary for the player to see and break loose floors of that screen.
Of course I could have fudged it a bit. Make each row 64 pixels high, draw the status display in the screen border using sprites, use the topmost 8 pixels for that special top row. Or maybe even force a badline at the right place to shorten one character row to 7 pixels.
But what would the implications be? Would I have to change animation tables or hard-coded values to be able to climb and grab ledges if the screen rows are of a different height?
How would I animate the dynamic parts of the screen? Could I fit it all into characters for every possible screen? I didn't want to rule out the possibility of using a level editor to create completely new levels.
There were many things that I didn't know yet, so I decided to go for the safe route. Don't deviate from the original too much, until I know how it all works, and then reconsider. Better than painting myself into a corner by doing a premature optimization.

So to this day, I still don't know if character mode would've been an option. I guess I'll have to wait for someone else to try it.

Next time I'm gonna dive into how each block is actually drawn and how the game handles the isometric perspective and its visibility issues. And how I'm finally able to run through the first level.


  1. Thanks for both the amazing game port and this development blog, it's very interesting to read about the detective work that went into the reverse engineering - and (well, at least I guess it will be coming in later entries :D) the ingenuity needed to get it working on the C64!

  2. Even if character mode isn't possible, forcing badlines to give you 32x63 tiles should speed up rendering noticably. The top 3 lines could be done for free with 24 line mode and scrolling up a line, or forcing a badline one line early to match the format of the other tiles… Of course it all depends on how the tile rendering code is laid out, which I'm hoping is part 5 :)

  3. Fantastic diary, it's the technical cousin of Jordan's original and I love it!

  4. char mode seems to be the better choice, but lets wait until the next post :)

  5. Awesome stuff! Waiting for part 5. Also I'd like to pick up my commodore collection at my parents place and get pop on a cartridge, too bad I'm so busy and I don't really have the room here.

  6. Well, you know my thoughts on the subject ;)

    It somehow seems pointless to rewrite PoP AGAIN just to prove a point when this version is as good as it is, but I'm trying to push the A8 guys in the char direction ;)

    The biggest problem with it is using a 64 high tile AND the original code/data, but I was going for a rewrite anyway using the available data as a basis.