Prince of Persia C64 - Development Blog

Part Ten - The final push

2012-03-02T14:24:00.000-08:00

The last few months of the project were pretty unexciting. There's a certain mode that you get in, if you can see a project coming to an end. It's basically becoming a bit of a grind, where you're trying to finish off as many of the lose ends that are still left. After all, you want to get this over with, and there's no easy way of doing that.

Having been through this a few times before, I knew that the best way for me is to make a TODO list now, of every thing that still needs to be done, which had about 100 items in the end. Ticking things off that list helps in seeing the light at the end of the tunnel...

    ...
    [x] Add title screen graphics and logic
    [x] Add cheat keys
    [x] Fix Jaffar positioning in level 13
    [x] Fix shadow not running fully out of screen
    [x] Make strength indicator blink if only one left
    [x] Fix little drawing glitch when C section is overlapping top block area
    ...

One of the remaining things was the frame of the game: The title screen along with the text cards inspired by the silent movie era. I knew that I wouldn't have to reverse-engineer that code, as it would be much easier to achieve the same thing and faster using custom code. This was one of the easiest parts and very satisfying work.

I started out with STE's initial work on the background for the title screens. I did take the liberty to change it a bit to make it look more like the graphics in the PC version (mostly the border of the image).

Original title background from DOS version (by Avril Harrison)

C64 multi-color background without ornaments (by Steve Day)

For the little symbols in the corners, I decided to go with hires sprites, because the 160x200 multicolor mode used by the picture made them look really bad, and I wanted to be pixel precise where possible. STE had the idea to add his own signature in the lower left corner, instead of Avril Harrison's "ah".

With hi-res sprite overlays in the corners

At this point I was wondering if I should put my own name and copyright notice into the title screen. But doing that felt wrong somehow. So I decided to go with what Brøderbund would've made back in the days: The same logo and "a game by Jordan Mechner", which seemed appropriate.
I added versions of the background image with black outlines for white hi-res sprite overlays. Although the outlines are not pixel precise (since they're in 160x200 resolution), they're good enough when covered with the sprites to make the final image look a lot like the PC screens.

Black outlines in background image for Brøderbund logo

Sprite overlay for Brøderbund logo

The composited result

For the title cards containing the text which explains the game's story, I had a similar plan. I also wanted to make sure to get the full 320x200 graphics ported over, since any 160x200 experiment I made was looking awful.

The trick was simple, I just used raster interrupts to switch from lo-res to hi-res bitmap mode in the area where the text needs to be displayed. Since that would also affect the border on the left and right edge of the screen I simply put a multiplexed column of multi-color sprites there. It doesn't get much easier than that.

One of the text screens, without the sprites used for the border

I added the necessary logic and drawing code to flip through the different screens. That wasn't hard because I used the two screen buffers which were already set up for the game, but it needed some care to hide drawing glitches that were be visible, by making sure that the color RAM updates happen at the right times during the screen refresh.

To complete the flow of the title screen, I had to add the intro cutscene now. It's certainly the most complicated of all the cutscenes in the game, but fortunately I learned enough about that already, so it didn't really pose a challenge anymore. Here's the code for that cutscene:

;----------------------------------
cutsceneBeforeLevel1:
            jsr triggerVizierStanding
            jsr saveKid
            jsr triggerPrincessStanding
            jsr saveShad
            lda #$02
            jsr runCutsceneLoop
            
            ; princess waiting (just music)
            lda #$07
            ldx #$08
            jsr runCutsceneLoopWithMusic
            lda #$05
            jsr runCutsceneLoop
            
            ; princess turns around
            lda #$62
            jsr triggerShadSequence
            lda #$09
            jsr runCutsceneLoop

            ; door opens (music used as sound effect)
            lda #$08
            ldx #$00
            jsr runCutsceneLoopWithMusic
            lda #$07
            sta CutsceneDelay
            lda #$05
            jsr runCutsceneLoop
            
            ; jaffar enters
            lda #$60
            jsr triggerKidSequence
            lda #$06
            jsr runCutsceneLoop
            lda #$61
            jsr triggerKidSequence
            lda #$04
            jsr runCutsceneLoop
            
            ; jaffar stands (just music)
            lda #$09
            ldx #$0c
            jsr runCutsceneLoopWithMusic
            lda #$04
            jsr runCutsceneLoop
            
            ; jaffar approaches
            lda #$60
            jsr triggerKidSequence
            lda #$1e
            jsr runCutsceneLoop
            lda #$61
            jsr triggerKidSequence
            lda #$04
            jsr runCutsceneLoop
            
            ; jaffar stands in front of princess (tension building music)
            lda #$0a
            ldx #$19
            jsr runCutsceneLoopWithMusic
            
            ; jaffar reaching for princess
            lda #$66
            jsr triggerKidSequence
            lda #$01
            jsr runCutsceneLoop
            
            ; princess retreats
            lda #$63
            jsr triggerShadSequence
            lda #$0d
            jsr runCutsceneLoop
            
            ; jaffar spawns hour glass
            ldx #$00
            jsr initHourglass
            lda #$05
            sta ScreenFlashLength
            lda #$ff
            sta ScreenFlashFillByte
            lda #$0c
            sta CutsceneDelay
            lda #$05
            jsr runCutsceneLoop
            lda #$00
            sta CutsceneSandCounter
            lda #$0b
            ldx #$08
            jsr runCutsceneLoopWithMusic
            lda #$07
            sta CutsceneDelay
            
            ; jaffar turns around and leaves (sand starts falling)
            lda #$64
            jsr triggerKidSequence
            lda #$11
            jsr runCutsceneLoop
            ldx #$01
            jsr initHourglass
            lda #$0c
            jsr runCutsceneLoop
            
            ; princess is sad
            lda #$71
            jsr triggerShadSequence
            lda #$1c
            jsr runCutsceneLoop
            
            ; jaffar has left the screen
            lda #$0c
            sta CutsceneDelay
            lda #$0c
            ldx #$14
            jmp runCutsceneLoopWithMusic
;----------------------------------

Like in the other cutscenes, the princess uses the Shad slot, and in this case Jaffar is using the Kid slot. Since the Apple II is challenged when it comes to sound and music, you can't have animation and music at the same time. So they alternate each other. A bit of animation, then a bit of music and so on.
The timing is either determined by the number of frames passed to runCutsceneLoop (in case of an animated part) or the length of the music (in case of runCutsceneLoopWithMusic). If music is disabled, then runCutsceneLoopWithMusic just calls runCutsceneLoop and uses the X register contents as the number of frames.
For now I had no music system in place, so all I got was that alternative timing:

After I got this intro cutscene working initially, I spent some time to tweak the character positioning to match the background graphics as good as possible and to make sure that the distance between princess, vizier and the hourglass is proper, since the general layout of the screen differs a bit from the Apple II version.

Oh, but what about the music? Turns out that is a longer story...
I asked a few different musicians while working on the game, and even though they showed some interest, it quickly became apparent to me that the idea of converting music is not as appealing to a composer as writing something original is.
So after trying to get someone else to do it for some time, I hit a point where getting some music into the game became a high priority, and that's when I decided to give it a go myself.
Now I have to add that even though I know lots of things about the SID, ripped many tunes during my adolescent years and generally am a huge fan of C64 music, one thing I've never done myself is write a SID music routine. Mostly because I'm not a composer, and writing a player also typically means that you have to write an editor for it, which feels like a lot of tedious work.

So having decided to make my own music conversion (mostly as a test, because back then I was still hoping that a real musician would come forward with some work) I first did some reverse-engineering into the music player of the Apple II version, out of interest. Well, let's just say that that was funny and scary at the same time and I quickly stopped doing that. :)

I then took a closer look at the MIDI files that I had extracted from the data of the PC version. I wrote a little Python script to parse the MIDI files so I could examine the tracks and the note data they contain. One thing that was important to me was to see how many tracks the music had and if it was feasible to play it using just the three voices of the SID.
Turns out that I was really lucky there, because even though the MIDI files had more than 3 tracks, those were generally not essential to the music, e.g. most of the additional tracks were just there to make a certain instrument fatter by playing the same sequence of notes one octave down or up. Those tracks were labelled "Bass" and "Bass dbl-v" or "melody" and "melody dbl". Removing the dbl tracks from the MIDI files made each file contain just 3 tracks, and the music was still complete and easily recognizable, i.e. it didn't miss large chunks or whole instruments.
It seemed like someone had already planned it like this.

Full title theme

Reduced title theme to only 3 tracks

So the plan was clear. I needed to get the data out of the MIDI file and into shape for a C64 music player. And I had to write one. The first problem that came up was the issue of timing. MIDI files can have various different tempi, and they're usually specified in ticks per quarter note, and ticks can be very precise. Also they typically don't nicely line up with the 50Hz or 60Hz ticks of SID players which are driven by the screen refresh.
But since the Apple II is so restricted in the music department, it meant that I didn't have to clock my music player that way. Whenever music is supposed to play in the Apple II version, the game pauses and waits until the music is done. In the PC version there's some music overlapping the actual game play, but it's not really required. The game still works if game and music are mutually exclusive.
That meant that I could use a timer interrupt to drive the music, and the music player could change the timer count rate to have true variable tempo with precise timing, something which is usually never done with SID music.

So I started by adding code to the Python script to save out the note data in a binary format suitable for C64 use. I then implemented a simple playback engine that reads this data and plays it on the SID. I added some simple effects for the instruments, such as vibrato and pulse/filter sweeps. Nothing too fancy, but enough to make it sound better than a music program in BASIC. Luckily the music didn't use drums.

Since at this point I had no RAM left, I fit the whole player and all the music data into a single 8KB ROM bank, so it can be banked in and executed easily. The data is quite large, since there are no patterns to be reused, it is basically a stream of notes and instrument changes, with timing information.
You can listen to the result here:

SID version of title theme

Putting it all together, I still had to add code to sync the title screen updates with the music timing. I hope the result is respectable, considering it's my first SID music player... :)

I guess this kinda concludes this story. I wouldn't want to bore you with details about the three months of final testing and bug fixing that I did. Or the endless amount of pixel fine-tuning on some of the graphics (Thanks, Mikael!). Or how Conrad jumped in at the very end to provide some awesome sound effects in practically no time, using custom code.

Once again, you can download the Apple II memory dump disassembly that I built up during this project, which might be helpful to port Prince of Persia to other platforms (not necessarily just 6502-based ones). I hope you had a good time reading this, and maybe I'll have some more interesting stuff to talk about in the future. Until then, take care, and keep the C64 spirit alive.

Part Nine - Optimizations for the Princess

2012-01-14T14:54:00.000-08:00

Let me tell you a thing about airplane coding. It's where I get things done. As soon as the plane has taken off and it's fine to use electronic devices again, I put on my headphones and start getting productive. Trying to cram as much work into a few hours allows me to work in a very focused manner.
That was also true on my flight to Barcelona. The stuff that I struggled with before was suddenly much clearer. I came up with a really good optimization for the redrawing of background graphics, which allowed the game to run at a much smoother frame rate.
Just before I went on the flight I added profiling code for the bitmap drawing routines. I needed to measure how much time is spent pushing pixels. Traditionally on the C64 this is achieved by changing the screen colors to visualize the raster time used by a function.

The initial measurement was quite sobering. It looked like this:

Drawing the flames, before optimization

The green color means it's drawing an opaque bitmap (i.e. black pixels overwrite the destination). Red means that the width of the bitmap is 2 bytes (16 pixels). These bars therefore represent the redrawing of the torches. You can see that it takes about 37 raster lines which is about 2.3ms.
After optimization it looked more like this:

Drawing the flames, after optimization

The time spent in redrawing the flame bitmaps is now only about 0.9ms. Naturally the same speedup also applied to all other redrawing of transitional objects, so jiggling floors, raising/lowering gates and spikes shooting out of the floor were all much smoother now.
With this thing off my mind, I was able to have a relaxed time in Barcelona. On my flight back I did add the little damage indicators that appear when a character gets hit.

Now I did try to optimize this code before, but didn't really make this much progress. The main idea now was to specialize the code for every possible width (1, 2, 3, and 4 bytes) and iterate for each row. This meant that the code required a lot more memory than before, which was problematic because it needed to be in RAM. During drawing the ROM has to be turned off, as it covers the same memory area as the bitmap buffers. For non-opaque drawing, I have to read from the bitmap and then OR the new pixels on top of that.

Opaque drawing is easier, it basically boils down to this:

;----------------------------------
draw2ColumnsOpaque: 
{
        ldx #$00
        {
            lda BgImageBuffer+2,x   ; read byte from image
            ldy #$00
            sta (BitmapPtr),y       ; and store in bitmap
            inx

            lda BgImageBuffer+2,x   ; read byte from image
            ldy #$08
            sta (BitmapPtr),y       ; and store in bitmap
            inx
            
            lda BitmapPtr
            and #$07
            beq oneRowUp
            
            dec BitmapPtr
            dec BlockImageVisibleHeight
            bne _cont
            jmp endDraw

oneRowUp:               
            lda BitmapPtr               ; move one char row up
            sec
            sbc #$39
            sta BitmapPtr
            
            lda BitmapPtr+1
            sbc #$01
            sta BitmapPtr+1
        
            dec BlockImageVisibleHeight
            bne _cont
        }

        jmp endDraw
;----------------------------------
}

For transparent images (i.e. black pixels are not written) there's a lot more work necessary:

;----------------------------------
draw3ColumnsNormal:
{
        ldx #$00
        {
            ldy #$00
            lda (BitmapPtr),y       ; read from bitmap 
            ldy BgImageBuffer+2,x   ; read byte from image
            and MaskTable,y         ; get masking outline of image byte and clear covered bits in bitmap
            ora BgImageBuffer+2,x   ; now or the image bytes on top of the background
            ldy #$00
            sta (BitmapPtr),y       ; and store in bitmap
            inx

            ldy #$08
            lda (BitmapPtr),y       ; read from bitmap 
            ldy BgImageBuffer+2,x   ; read byte from image
            and MaskTable,y         ; get masking outline of image byte and clear covered bits in bitmap
            ora BgImageBuffer+2,x   ; now or the image bytes on top of the background
            ldy #$08
            sta (BitmapPtr),y       ; and store in bitmap
            inx

            ldy #$10
            lda (BitmapPtr),y       ; read from bitmap 
            ldy BgImageBuffer+2,x   ; read byte from image
            and MaskTable,y         ; get masking outline of image byte and clear covered bits in bitmap
            ora BgImageBuffer+2,x   ; now or the image bytes on top of the background
            ldy #$10
            sta (BitmapPtr),y       ; and store in bitmap
            inx

            lda BitmapPtr
            and #$07
            beq oneRowUp                

            dec BitmapPtr
            dec BlockImageVisibleHeight
            bne _cont
            jmp endDraw

oneRowUp:               
            lda BitmapPtr               ; move one char row up
            sec
            sbc #$39
            sta BitmapPtr
            
            lda BitmapPtr+1
            sbc #$01
            sta BitmapPtr+1
        
            dec BlockImageVisibleHeight
            bne _cont
        }

        jmp endDraw
;----------------------------------
}

At this point (in early June 2011) I was hitting the most important milestone: Being able to play through the whole game. What's generally known as an "alpha" build. Some things didn't quite work 100% (end fight with Jaffar was messed up), some things were missing (no falling floors), and the graphics for the palace levels were mostly just dungeon tiles with different colors.

That meant that I had to tackle the next big unknown, the cutscene animation system. I previously only found bits and pieces of this code and was unsure how much there was. I was hoping that it would fit into my current structure. I decided to first concentrate on the in-game cutscenes (between certain levels) and the final cutscene of the game first, as those would not require the whole title screen logic, which I didn't have yet. I knew that those cutscene must be triggered from the game code somewhere.
Luckily I had already received graphics for the princess room and all the animations of the princess and vizier from STE. But I first had to find out how to put them to use. So I was back into doing serious reverse engineering.

At the end of the mainLoop there's this end condition:

            lda NextLevel
            cmp CurrentLevel
            beq mainLoop         ; nope, level hasn't changed, keep playing
startNextLevel:
            jsr l27e5
            jmp activateNextLevelOrCutscene

The code at l27e5 is something I haven't spent much time looking at. My hunch is that it's showing the message prompting the user to insert the correct disk for the upcoming level. Not something I was interested in.
The jump to activateNextLevelOrCutscene is more interesting, not just because it's completely unnecessary, since activateNextLevelOrCutscene begins immediately after this instruction.
It calls checkForCutscene which looks at the NextLevel variable and branches to different pieces of code for levels 2, 4, 6, 8, 9 and 12. Turns out these are the levels that begin with a cutscene, showing the princess waiting for the kid in some form. For any other level the code branches immediately to initLevel.

            lda NextLevel
            sta CurrentLevel   ; the next level is now the current level
            cmp #$02
            beq l2225          ; branch to cutscene for level 2
l220e:
            cmp #$04
            beq l223a          ; branch to cutscene for level 4
l2212:
            cmp #$06
            beq l223e          ; branch to cutscene for level 6
l2216:
            cmp #$08
            beq l224a          ; branch to cutscene for level 8
l221a:
            cmp #$09
            beq l2242          ; branch to cutscene for level 9
l221e:
            cmp #$0c
            beq l2246          ; branch to cutscene for level 12
endCutscene:
            jmp initLevelImpl  ; next level has no cutscene, so just start it immediately

Let's take the cutscene before level 2 as an example. This is just the generic "princess waits while standing" scene:

Just standing here, waiting for my prince to come...

l2225:
            lda #$01                     ; cutscene id
l2227:
            pha
retry:
            jsr loadCutsceneBackground   ; loads the bitmap for the princess room
            jsr l4c4b                    ; Apple II specific file error handling?
            jsr l4c4e                    ; Apple II specific file error handling?
            bne retry
l2233:
            pla
            jsr triggerCutscene          ; execute the cutscene
            jmp endCutscene              ; jumps to initLevel, continues game after cutscene

So far so good. I identified triggerCutscene to be the main entry point for all cutscenes, which gets the cutscene id passed in through the accumulator.
It looks like this:

;----------------------------------
triggerCutsceneImpl:
            pha
            jsr initCutscene
            pla
            tax
            lda CutsceneJumpTableLo,x
            sta le214
            lda CutsceneJumpTableHi,x
            sta le215
    le214 = * + 1
    le215 = * + 2
            jsr $ffff
            lda #$01
            sta CutsceneDelay
            rts
;----------------------------------

Oh, this is as easy as it gets. A simple jump table for each cutscene. The entry for level 2 is also used for level 6 (since it's the same cutscene) and the function it points to is very short:

;----------------------------------
cutsceneBeforeLevel2And6:
            jsr getTimeLeftForCutscene ; check how much time is left in the game
            jsr initCutsceneTimers  ; initializes hour glass state and sand animation timer
            jsr triggerPrincessStandingFacingRight
            jsr saveShad
            lda #$02                ; run the cutscene loop for two frames
            jsr runCutsceneLoop
            ldx #$32                ; run for this many frames if music is disabled                
            lda #$0d                ; id of the background music, cutscene runs until music ends
            jmp cutsceneLoopWithOptionalCharacterAnim
;----------------------------------

The core of it is triggerPrincessStandingFacingRight:

;----------------------------------
triggerPrincessStandingFacingRight:
            jsr triggerPrincessStanding    ; spawn princess (looks left by default)
            lda #$00                       ; make her look right instead
            sta CharFace
            rts
;----------------------------------

;----------------------------------
triggerPrincessStanding:
            lda #$05                       ; princess uses CharID 5 (see below)
            sta CharID
            lda #$78                       ; X position
            sta CharX
            lda #$97                       ; Y position
            sta CharY
            lda #$ff                       ; looking left
            sta CharFace
            lda #$5e                       ; standing sequence
            jsr setSequence
            jmp animChar                   ; execute first frame of sequence
;----------------------------------

I'd seen this last bit of code before, when I was looking at all the places where setSequence is used. Back then I wasn't able to identify all of the sequences, because some of them just seemed broken. Turns out that those were cutscene animations, and they were in the normal sequence table already. So there's no animation sequence data loaded for the cutscene. They obviously looked weird when played with the Kid frame def list.

So basically the cutscene system is just using the normal game engine to draw the characters. They have special CharIDs as described in the PoP source code documentation.

5 = princess (in princess scenes)
6 = vizier (in princess scenes)

Since cutsceneBeforeLevel2And6 calls saveShad, the princess is actually drawn as a guard.
Just like for guards, reading from the frame def list is overridden for these characters by overrideFrameDefListForCharacter, so it's going through indexIntoCutsceneFrameDefList rather than the normal code.

After setting up the CharData for the princess and saving it to the Shad slot, the game runs runCutsceneLoop which is a little mini game loop just for the cutscenes. It handles keyboard and joystick (to be able to skip the scene), updates the character animations (much like the game itself does) and updates the screen:

;----------------------------------
updateCutsceneScreen:
            jsr drawCutsceneFrame
            jsr waitForVBlank
            jmp flipFrontAndBackBuffer
;----------------------------------

In drawCutsceneFrame we find code to draw the hour glass, the flames of the torches, the stars outside the window and the sand of the hour glass. This is all very specialized code, but it uses the existing drawing functions used by the game to blit images onto the screen.

It was relatively easy now to get this system up and running. First I replaced loadCutsceneBackground with my own code that copies a multicolor bitmap into both screen buffers and draws a rectangle for the right pillar into the mask bitmap.

The hourglass drawing I replaced with a very simple copy loop that stamps one of the hourglass images onto the normal princess room bitmap (and screen and color RAM). There are 9 different images used, depending on the current time left in the game. At the beginning the hourglass is still full and in the end it's empty. I also made two variants which are alternated between to get the sand animation going. The Apple II original had special sand animation images which were drawn on top of the hourglass, but I decided that this wasn't really necessary, so my code just redraws the whole hourglass every time. No problem.

The blinking stars outside the windows were also more easily solved on the C64. I just placed them nicely in the bitmap and then added some code to play around with the color RAM entries. Easy enough.

The flames are the same as the ones used in the level background graphics, and a lot of the drawing code is shared with the in-game code.

And after adding some special code to switch the lower half of the character sprites to use a different color I finally had the princess on the screen in her room, as expected. This made me really happy.

I now started to quickly decipher the other cutscene code, which was all very similar. I decided to do the final cutscene of the game next, because that one seemed the most complicated to me. From converting the animation images I knew that at some point it switches from using two characters (for princess and kid) to a single one for both, as they embrace.

;----------------------------------
cutsceneFinal:
            lda #$08
            sta CutsceneDelay
            lda #$01
            sta SoundEnabled
            sta MusicEnabled
            jsr triggerPrincessStandingFacingLeftBeforeTurn
            jsr saveShad
            lda #$08
            jsr runCutsceneLoop
            jsr triggerKidArriving  ; plays kid running sequence (facing left)
            jsr saveKid
            lda #$08
            jsr runCutsceneLoop
            lda #$6c
            jsr triggerShadSequence ; princess turning around and embracing kid
            lda #$05
            jsr runCutsceneLoop
            lda #$0d
            jsr triggerKidSequence  ; kid stops from run
            lda #$02
            jsr runCutsceneLoop
            lda #$00
            sta KidFrame            ; disable kid, the embrace has both characters in one image
            lda #$09
            jsr runCutsceneLoop
            lda #$0f               ; the music to play
            jsr le449              ; just animates cutscene background graphics
            jsr triggerMouseJoiningPrincessAndKid ; mouse comes in and joins the couple
            jsr saveKid
            lda #$0c
            jsr runCutsceneLoop
            lda #$65               ; stop mouse - I changed this to #$72 to make
            jsr triggerKidSequence ; the mouse rise like in the PC version
            lda #$1e
            jmp runCutsceneLoop
;----------------------------------

As soon as I had this cutscene somewhat working (I tweaked the positioning later to make it look nicer) I captured a video and uploaded it on June 13th 2011:

I was quite satisfied after having understood how the cutscene system works. It felt like being on the home stretch. But there was still some things left to do. The intro cutscene was within my grasp now, but I also needed to come up with all the title screen code. Oh, and what about the music? We'll find out about that in the next part.

Part Eight - Everything comes to him who waits

2011-12-07T14:43:00.000-08:00

After having put the Prince of Persia project on hiatus, I went on to do other things. One of them was a GameBase64 browser for Mac OS X (for my own personal use) and the other was a conversion of the Flash/iOS game Canabalt for the C64 (not to be confused with C64anabalt, the other Canabalt version for the C64 by Paul Koller).

A port of Canabalt, the popular one-button jump'n'run, was an interesting diversion

But Prince of Persia was still at the back of my mind, mostly because it's such a great project and I got so far already. I still intended to finish it some day, but I didn't have the energy and most of all, I couldn't see the light at the end of the tunnel. I had no plan how to continue.

I wanted to release Canabalt in March of 2011, but as it turned out, I had to wait a long time for somebody to do the music for the game. In April I still hadn't received it, so I kinda became bored with waiting and my thoughts wandered off.

Before long I found myself thinking about Prince of Persia again. I had the idea to look into C64 cartridge technology to decide if that would be a feasible route to go. I only had a very minimal idea of how some of the advanced cartridges with bank-switching logic (the ones used by Ocean and System 3) worked in detail. I started investigating and in my head I began to rearrange the memory layout of my existing code base.

Which things can I move into the cartridge ROM? Which things have to stay in RAM? Where's the best place to put graphics data? How much work would it be to rewrite my existing REU-based code to get this up and running?
I was quite aware that those cartridges offered a unique possibility. Not only would I be able to move all the big animation data into ROM, but I could also have code there and run it from ROM. This meant it would be possible to free up even more RAM, which is something I needed to fit in all the parts that I hadn't touched yet. Guards and fighting logic, among other things.

But most of all I was hoping that it would allow me to fit two full frame buffers into memory, to get rid of all the ugly redrawing glitches.
So off I went, tearing my old code apart and rearranging it. I initially planned to use an Ocean cartridge but quickly found some inconsistencies in VICE's emulation of that type of cartridge, which meant that my code worked in VICE but didn't work on real hardware. I decided to continue working within VICE and got it up and running in a few days, after which I made a little video capture to show off the double-buffered drawing code.

Now I was finally able to add new features. I added Steve's player sprites and did the status display on the bottom. Things started to become easy again.

Getting annoyed by Ocean cartridge limitations I decided to switch to EasyFlash. It was a clean, well documented standard, with excellent support in VICE. I was amazed by enthusi's conversions of Maniac Mansion and Zak McKracken and I liked the fact that the cartridge could be flashed using just a C64, eliminating the need for dodgy Windows software. Also the prize was affordable, so I ordered a pre-built cartridge and it arrived at the beginning of May. I was very excited that I could finally play the cartridge-based build on real hardware so I made a little movie.

I still had a good chunk of work ahead of me. The most pressing issue now was to get the guards in, and to do a serious amount of performance optimizations.
To help with the first I was lucky that Steve had already released his conversions of those animation frames. So I now had to figure out which part of the code was dealing with the second character.

The basic idea of the game engine is that most of it can deal with either the Prince or a guard. The routines use the CharData structures, so the same animation code is used to animate them both. That gave me a hint that I should have almost all of the code already in place.
I had to do a bit of cleaning up and structure it more like the original. The low-level functions for executing the sequence and looking up frame definitions were shared. The code calling those was split up into two parts: updateKidAnimation and updateShadAnimation.

The first of the two loads KidData into CharData and ShadData into OppData using loadKidAndShad. It then runs the input control code (updateControlAndCheckForDeath), parses the sequence table (animChar), applies acceleration and velocity to the character, then updates the position. Afterwards it does collision detection and resolution.

The other function, updateShadAnimation uses loadShadAndKid to load ShadData into CharData and KidData into OppData, but otherwise does many of the same things. It obviously doesn't run the input code but instead it checks the type of opponent and then runs updateOpponent which handles hard-wired behaviors of mouse, skeleton and shadow man and generic sword fighting movement for guards (updateNormalGuardImpl). It then goes through much of the same code as updateKidAnimation to animate the character and update its position.

Since the guards only have a small subset of animation frames compared to the Prince, they also only have a smaller frame def list. To deal with this, readFrameDef calls a routine which I called overrideFrameDefListForCharacter. It checks CharID and then reads from the alternative frame def list via indexIntoGuardFrameDefList.

After updateCharacters is done with dealing with the Kid and the Shad separately it handles common code needed for fighting (checkIfStabbingOrBlocking, checkIfCharacterIsHit, checkIfStabbingOpponent) before updating the strength of both characters. Now all the state variables of the characters are final and the game is ready to update the screen.

Having made many mistakes in reverse engineering all of this code at first, I was quite happy to finally see a second animated character on the screen. Initially the fighting code didn't quite work, but that also came together after a few days. I had reached the point now where I had to move some of the code to ROM, and the guard AI logic was the prime candidate for that. So I still had room to grow the game.

The skeleton is just a normal guard that can't be killed

By now I had already became a bit bored of the first level in the game. So I added the blueprint data for all 14 levels, also because I wanted to see the skeleton in level 3. It turned out really nicely.

Within a month of rebooting the project, I had made a lot of progress and was confident that I could finish this game. But because I was unsure about the remaining parts I still expected it to take another year. The requirements for cutscenes and title screen scared me a bit. I had no idea how much work that would be. Also I had no music or sound effects, no final background graphics and performance was still abysmal. The latter now became a real problem. I had to tackle that one first. But I was just about to leave for vacation to Barcelona. Would that be a problem or a blessing? Find out in the next part.

Part Seven - Hitting the memory and motivation barrier

2011-11-09T13:31:00.000-08:00

Throughout September and October of 2009 I worked tirelessly to implement all the various gameplay features. I went through all the transitional objects and implemented them one by one.
Unfortunately I quickly ran into problems due to the fact that I didn't have a double-buffered drawing system.

This video was captured on 25th October 2009, and it shows that basically all of the gameplay features work now. But there's horrible ugly flashing artifacts and generally the performance is rather bad.

I did try various ways to see if I could hide the drawing artifacts, by not wiping the blocks that are redrawn, but rather redrawing them in a way that will clear the previously drawn pixels. This works a bit for the gates (except in the beginning, when they still overlap with the floor), but in general I had to come to the conclusion that this is not a solution for everything.
But I hadn't given up yet.

Then something interesting happened. On 4th November 2009, STE'86 (Steven Day) of Compunet fame posted on the Lemon64 forum that he was working on converting the Prince of Persia animations to C64 sprites: http://www.lemon64.com/forum/viewtopic.php?t=31893

People showed some interest, including Poharai Attila, who did the old preview for the C64 that I mentioned in my first post. I was still a long way from finishing my version, but I clearly had progressed far. So I panicked. I had to announce what I was doing to make sure nobody else spends a lot of time getting to where I am now only to find out that was much further along. I knew that this would be a serious bummer. :)

So I made a post stating that I'm working on Prince of Persia, but with the intention of not letting myself get dragged into a long discussion that would divert my time from the project. But some people reacted positively and that felt good. I sent a few screenshots and movies to STE'86 and his partner in crime, JCB (PeteD), to prove to them that I've reached a playable prototype stage.

At this point I was still convinced that the REU as a requirement would be enough to fit the game into memory. I considered a cartridge-based solution as an alternative for people without REU but didn't know any details about the cartridge technology, so I only considered it as something for later.
To give you an idea, this is what my memory map looked like in November of 2009:

; Runtime memory:
;
; $0000-$03FF : Game state + various buffers
; $0400-$3FFF : Code
; $4000-$5FFF : Bitmap
; $6000-$63FF : Screen + Sprite pointers
; $6400-$6FFF : Sprite buffers
; $7000-$79FF : Seqtable
; $7A00-$7EAF : Framedef list
; $7EB0-$7FFF : Tables 2
; $8000-$A80B : Background imagetable
; $A80C-$AFFF : FREE (to be used by additional bg images in palace levels)
; $B000-$B5FF : Tables 3
; $BC00-$BDFD : Kid imagetable header (pointers into REU where to get each image from)
; $BDFE-$BFFF : Kid image buffer
; $C000-$DFFF : Mask bitmap
; $E000-$EBFF : FREE => music/sfx
; $EC00-$F4FF : Level blueprint
; $F500-$FFE8 : Tables

I did put all the Kid images into the REU (pre-mirrored) and DMA-ed them in when needed. Doing the same for background images turned out to be prohibitively slow when redrawing, so I decided to keep them in memory.
The size of the code had almost reached the $4000 barrier, but I didn't have any guard AI or sword fighting in there yet.
And then of course I would need another set of bitmap and screen for the double buffering.

I spent some time to auto-convert the images for a guard, and added those to the REU memory too, but I didn't get anywhere with the code, so I didn't really use them in game yet. I spent some time moving things around and changing the memory layout, and many of the more daring changes would've required me to rewrite a lot of the existing masking code. It started to get annoying.

As it turned out, I had drained my motivation reservoir. By now I had worked six months on this project. While I made some progress, I had no real plan for how to finish it. Having announced it also took a huge chunk out of my desire to further spend time working on this game.

So I slowly stopped working on Prince of Persia. I kept thinking about possible ways to solve my issues, but soon enough I was getting interested in other things and my mind was no longer on the case. It would take 17 months for me to get back to that project.

I leave you this time with the thing that I've promised at the beginning. All my reverse-engineering work of the Apple II version, labels and disassembler output. It's not 100% complete, since I didn't fully investigate the low-level Apple II bits that I didn't need to understand, but it's more than enough to document the high-level logic and game structure which makes it possible to port it to another platform.
You can download the package and get cracking, but please do read the readme.txt file first.

The next time you'll learn how I re-booted the project and what happened next.

Part Six - Playing hide and seek with pixels

2011-10-29T10:45:00.000-07:00

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.

Part Five - Painting a pretty dungeon

2011-10-24T14:30:00.000-07:00

It's now late July 2009, and I finally had to really start looking into that interesting drawing that Jordan put in his document:

Jordan Mechner's sketch of the sections of a block and their drawing order

So it seemed that every block is drawn by first drawing the things that it overlaps with. The C-section from the block left below, and the B-section of the block to the left. After that it draws the actual visible parts of that block, divided into D-section and A-section, where the D-section is just the part that would be visible if the block was one of those top row blocks, i.e. just 3 pixels high. I didn't yet know what the "frontpiece" was, but it seemed like it must be related with making sure the players goes behind certain parts of the block.

Here's a slow motion version of the drawing loop, building up the whole screen with the painter's algorithm for each block:

Drawing the first screen in the game, a process which is normally not visible

At this point, I looked into the individual block images that I had extracted from the PC level graphics (VDUNGEON.DAT) using PR. And sure enough, those were also divided into those different sections. What I've noticed was that the bitmaps for each section where only as large as they needed to be, i.e. the B-section of most blocks didn't reach all the way to the bottom of the block, and the C-Section often was only as wide as the visible parts that it covered. Here's an example:

Sections of a block, and the actual sizes of the bitmaps in the DOS version

So I had two things on my todo list now. First converting all the DOS VGA images to C64 colors and resolution. For that I used the same method that I applied to the character animation frames, but this time I had to do more manual fixing, because it wasn't possible to use a simple color mapping.
The other thing was to identify all of the images correctly. The data extracted from PR had nice names, but it wasn't always clear what each block was. There were some obvious ones, but most of the parts used for floors and pressure plates were ambiguous. I needed to clearly map them to the correct image, preferably also in the right order. My main guide there was the list on page 23 of the PDF, which lists all the individual images and clearly marks them as A, B, C or D. Turned out that this list was absolutely invaluable.

So I had that list of image names from the Apple II version, and a folder containing images from the PC version. How could I make the connection between the two? Furthermore, it seemed like some of them didn't match up, e.g. there were a lot more images for wall blocks that didn't make sense. It felt like that the data was similar, but not exactly the same. I needed to really look at the Apple II images. I had to extract them.

Fortunately, the page before the background image list in the document describes the data structure of those image tables. And with a bit of hunting in the disassembled code, I managed to find the locations of them in the memory snapshot.

6000:BgTab1
8400:BgTab2

At this point I have to put my "Ode to Python". I use it to quickly generate one-off scripts to perform a simple task, like data conversion or extraction. I love doing that, it's fast and I get my results in a very short time. Python rules! :)

You can download the extracted image tables if you're interested. They're single-color Apple II images, with the MSB stripped, so they're nicer to look at.

Here's the same block as above, this time taken from the Apple II version, with its width of 28 pixels per block, compared to 32 pixels on the PC.

Apple II block sections of the "pillars" block

Now I had a definitive list of images and their names as given by "the Book of Jordan". This allowed me to match them to the converted PC images I already had, and it also helped me to understand the differences. I knew that I had to match that image list with my own bitmap files and if I did then it should be fine.

In the previous part I mentioned the core of the iterateScreen loop, a routine called drawBlock. Here's what it looked like to me, after I figured out its constituent parts:

;----------------------------------
drawBlock:
            jsr drawCSectionLeftBelowStencil
            jsr drawCSectionLeftBelowImage
            jsr drawBSectionLeftImage
            jsr drawTransitionalObjImage
            jsr drawDSectionImage
            jsr drawDSectionIfLooseFloor
            jsr drawASectionImage
            jsr drawTransitionalObjASection
            jmp drawFrontPieceImage
;----------------------------------

And it has a little brother, for drawing the top row blocks (which has not A-section):

;----------------------------------
drawTopBlock:
            jsr drawCSectionLeftBelowStencil
            jsr drawCSectionLeftBelowImage
            jsr drawBSectionLeftImage
            jsr drawDSectionImage
            jsr drawDSectionIfLooseFloor
            jmp drawFrontPieceImage
;----------------------------------

There are a bunch of ZP memory locations used as input to these functions:

0029:ScreenUpdateLeftObjId
002A:ScreenUpdateLeftBlueSpec
00E9:ScreenUpdateRow
00EA:ScreenUpdateColumn
00EB:ScreenUpdateBlockIndex
00EC:ScreenUpdateObjId
00ED:ScreenUpdateBlueSpec
00EE:ScreenUpdateYCoordMinus3
00EF:ScreenUpdateYCoord
00F3:ScreenUpdateXCoordInBytes

Their job is to setup the actual low-level bitmap drawing code. But as described in the source code documentation (page 9 in the PDF), these hires routines are never called directly. Instead there's an extra indirection layer, called "image lists".
Basically every draw operation is added to one of the image lists, which are then executed in one step:

0403:executeImageLists

Here I decided to take a shortcut. The requirement for deferring every drawing operation to happen at a later point seemed unnecessary and slow to me. I took a bit of a gamble and used the functions that add to the image list as my interface to my own low-level drawing code.
I started to implement

1A5F:addToImageList

to do my bitmap blitting immediately to the screen.
The information which image to draw (or in the original: which one to add to the image list) is again passed in a set of ZP variables (as explained on page 10 of the PDF):

0001:ImageXPosInBytes
0002:ImageYPos
0003:ImageXOffset
0004:ImageTableEntry
0005:ImageWidthInBytes
0006:ImageOpacity
0007:ImageTableLo
0008:ImageTableHi
000F:ImageTopCutoff
0010:ImageLeftCutoff
0011:ImageRightCutoff
0012:ImageTableBank
0013:ImageBottomCutoff

I wrote a function that takes these parameters and draws my own bitmaps. The ImageOpacity one is especially interesting. It's not documented in detail, but I managed to find out that it basically describes the blitting operation:

IMAGE_OP_AND  = $00
IMAGE_OP_ORA  = $01
IMAGE_OP_STA  = $02
IMAGE_OP_EOR  = $03
IMAGE_OP_AND2 = $04
IMAGE_OP_STA2 = $05  ; unused

On the Apple II, this variable is directly used to modify the opcode in the inner blitting loop. It's using AND to draw a stencil with a mask bitmap, ORA to draw blocks with 0 bits being transparent, STA to simply overwrite, and EOR to invert.
After a lot of failed attempts, I finally got something on the screen. And since I already had all the animation system up and running, and had correctly added the code to trigger the screen drawing, I very quickly got to a point where I could run through the level. Lots of little problems, but the result was undeniably working. Although since animated objects didn't work yet, gates didn't open and loose floors didn't break, I wasn't able leave the first room. I decided to move the starting position to a different screen, to be able to roam around.

But there's one thing I didn't mention yet. Getting to this point wasn't really doable with 64K of RAM, not with this approach and my unoptimized code. So I decided to use a REU (Ram Expansion Unit). I added code to upload all the images and DMA in the data I needed to draw on demand. I didn't know if that would be a workable solution for the final game, but it allowed me to progress, which was the most important thing at that moment: To push forward!

Here's a little video of the build from July 28th 2009:

You can also download a C64 .prg file of this build, but please be aware that it will require a REU and it has not been tested on a real C64, so your mileage may vary.

Next time I'm gonna tell a bit about masking and redrawing. Sounds boring, but is essential in order to make the Prince and his environment feel real. Oh, and it's a real pain in the ass, too! :)

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

2011-10-20T14:10:00.000-07:00

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:

$00 = OBJID_EMPTY
$01 = OBJID_FLOOR
$02 = OBJID_SPIKES
$03 = OBJID_POSTS
$04 = OBJID_GATE
$05 = OBJID_STUCK_PRESSPLATE
$06 = OBJID_DOWN_PRESSPLATE
$07 = OBJID_PANEL
$08 = OBJID_PILLAR_BOTTOM
$09 = OBJID_PILLAR_TOP
$0a = OBJID_FLASK
$0b = OBJID_LOOSE_FLOOR
$0c = OBJID_PANEL_TOP
$0d = OBJID_MIRROR
$0e = OBJID_RUBBLE
$0f = OBJID_UP_PRESSPLATE
$10 = OBJID_EXIT1
$11 = OBJID_EXIT2
$12 = OBJID_JAW
$13 = OBJID_TORCH
$14 = OBJID_BLOCK
$15 = OBJID_SKELETON
$16 = OBJID_SWORD
$17 = OBJID_BALCONY1
$18 = OBJID_BALCONY2
$19 = OBJID_ARCH_PILLAR
$1a = OBJID_ARCH_SUPPORT
$1b = OBJID_ARCH_SMALL
$1c = OBJID_ARCH_TOP_LEFT
$1d = OBJID_ARCH_TOP_RIGHT

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:

00A6:NewVisScrn
00CB:VisScrn
0031:ScrnLeftOfVisScrn
0032:ScrnRightOfVisScrn
0033:ScrnAboveVisScrn
0034:ScrnBelowVisScrn
0035:ScrnLeftBelowOfVisScrn
0036:ScrnLeftAboveOfVisScrn
0037:ScrnRightAboveOfVisScrn
0038:ScrnRightBelowOfVisScrn

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

D02A:getScrnsSurroundingVisScrn

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

59E0:cutCheck

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

24D3:checkIfScreenHasChangedAndNeedsToBeDrawn

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

218C:mainLoop

and with all final labels it looks like this:

;----------------------------------
mainLoop:
            jsr updateAndGetRandomNumber
            lda #$00
            sta KidStrengthDelta
            sta ShadStrengthDelta
            jsr updateInputDevices
            jsr isButtonPressed
            bpl l21a2

            lda #$01
            jmp initGameAndLevelImpl
l21a2:
            jsr updateTimers
            jsr updateCharacters
            jsr activateScreenFlash
            jsr updateScreen
            jsr updateSoundEffects
            jsr clearSoundEffectBuffer
            jsr updateScreenFlash
            jsr updateMusic
            lda NextLevel
            cmp CurrentLevel
            beq mainLoop
startNextLevel:
            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.

Part Three - Making the Kid come to life

2011-10-18T14:34:00.000-07:00

After having successfully found my way into the animation code of Prince of Persia, my top priority was to take all of the information I gathered and integrate it into my current test program. I decided that I'm just gonna take the relevant parts to be able to animate the character and make him run around the screen, with all the right actions, climbing, jumping, etc.
So I had to completely dissect the code from the controls down to drawing the sprite onto the screen. I didn't plan to lose any time.

The first thing I noticed from looking at the sequence table parsing were the zero-page locations that it's using. CHX is modifying $41, CHY is modifying $42 and so on. At the end of that code, if the byte from the sequence table is not any of the instructions, it does this:

l4a2a:
                sta l40
                rts

So if it's not an instruction, but a frame number, it gets stored directly into $40.
Now it was very plain to see that these memory locations must be the "character data" variables mentioned on page 17 of the PDF.

Now was a good time to start creating a label file. This is a text file which contains a name for every memory location or code routine that has been identified. The disassembler will read it and start using those real names, instead of the generic address labels it uses by default. I also made the rule to use names from Jordan's document wherever possible, except when they were very non-descriptive.
The development system that he used back in the days on the Apple II surely had a limit for the length of a label. Typically most of the assembler tools back then enforced labels to be no longer than 8 characters. This was necessary to save memory and keep source and object code in memory at the same time, at least as long as possible, to speed up the development cycle.
Since I was using a modern cross-assembler (k2asm) I had no such limitation, so I took the liberty to use longer names where appropriate.
I also decided to rename "CharPosn" (which I've identified to be at $40 in memory) to CharFrame, because that seemed clearer to me. It's the index into the frame def list of the character, and represents the currently visible animation image.

So these labels I was very confident about:

0040:CharFrame
0041:CharX
0042:CharY
0043:CharFace
0044:CharBlockX
0045:CharBlockY
0046:CharAction
0047:CharXVel
0048:CharYVel
0049:CharSeqLo
004A:CharSeqHi
004B:CharScrn
004C:CharRepeat
004D:CharID
004E:CharSword
004F:CharLife

Together these 16 bytes make up the CharData. The document also mentions that there are multiple sets of CharData in the game: KidData (for the kid) and ShadData (for the opponent, which is always referred to as "Shad").

It describes the functions called LoadKid and SaveKid to load/save KidData to and from the working CharData set. These should be easy to find. And indeed there was a whole bunch of these routines:

;----------------------------------
ld835:                   ; copy 16 bytes from $50 to $40
            ldx #$0f
ld837:
            lda l50,x          
            sta l40,x
            dex
            bpl ld837
ld83e:
            rts
;----------------------------------
ld83f:                   ; copy 16 bytes from $40 to $50
            ldx #$0f
ld841:
            lda l40,x
            sta l50,x
            dex
            bpl ld841
ld848:
            rts
;----------------------------------

Copying 16 bytes from $50 to $40 and back, the same with $60 and $40, and variations that use $60 and $39c and $50 and $39c. Some of them even copying two sets at once.

Running into the room with the guard in level 1 using the emulator, breaking and looking at all those areas allowed me to identify them more precisely. The 14th byte in each set is "CharID", an identifier for the character. It's 0 for the kid, 1 for the shadow, 2 for guards and so on.

So CharData was the temporary working area at $40. KidData seemed to be at $50, since $5d always contained $00. At $6D I found $02 while the guard was on screen, so that must be ShadData. Then I assumed that the temporary area for storing the opponent, OppData must be $39c.
So I looked at the various transfer functions and gave them appropriate names:

D05A:loadKid
D05D:loadShad
D060:saveKid
D063:saveShad
D0A8:loadKidAndShad
D0AB:saveKidAndShad
D0B1:loadShadAndKid
D0B4:saveShadAndKid

I noticed that many of the routines were called via jump tables. So while $d05a is called when the game wants to load KidData into CharData, the actual function is at $d835.

;----------------------------------
ld05a:
            jmp ld835
;----------------------------------

In the disassembly, I've labelled the actual implementations with the ending "Impl":

;----------------------------------
loadKid:
            jmp loadKidImpl
;----------------------------------

The reason for this might have to do with the way Jordan's code was split into multiple object files and that he used these tables for linking. In any case, it was something I was able to optimize away. In the C64 version, loadKid is actually loadKidImpl. No jump tables.

The two bytes CharSeqLo and CharSeqHi in CharData are especially interesting. They point to the location in the sequence table where the next byte is read from. To switch animations, the game must change this location to point to a different sequence. Thus the control code is very likely tied to the sequence switching. Easy enough, I found it immediately:

;----------------------------------
setSequenceImpl:
            sec
            sbc #$01
            asl
            tax
            lda SeqTableLo,x
            sta CharSeqLo
            lda SeqTableHi,x
            sta CharSeqHi
            rts
;----------------------------------

The input in the accumulator is a "sequence id", subtracted by one and multiplied by two, it's used as the index into the beginning of the SeqTable data at $3000. Thus one of the pointers at the beginning is read and stored into CharSeqLo and CharSeqHi.
So I noticed that it will be important to find and understand all the points where setSequence is called. Oh, and it is called a lot!

For example like this:

;----------------------------------
triggerStartRun:
            lda #$01
            jmp setSequence
;----------------------------------

In lots of other cases also like this:

;----------------------------------
triggerFallLand:
            lda #$2e
            jsr setSequence
            jsr animChar
            [...]

The sequence is selected and then animChar is called. This routine is the sequence table parser I've explained in my previous post. So basically code like this sets the sequence and then immediately processes its first frame to make sure the CharData is up-to-date. Otherwise animChar is called only during the next normal frame update.

The find out what each sequence looks like, and therefore to be able to identify the right sequence triggering code, I made a little test program that allowed me to trigger each sequence and play it. I came up with a long list of sequence ids:

$01: STARTRUN
$02: STAND
$03: STANDING_JUMP
$04: RUNNING_JUMP
$05: TURN
$06: RUNNING_TURN
$07: FALL
[...]

and so on...

This made it possible to find functions like triggerStartRun above.

I then decided to roll up the code from the other end. Find the joystick code and see what it does. This was easy. Joysticks on the Apple II are analog and are read through the analog input registers at $c064. The code required for this is unusually complex (at least compared to the C64) but in the end I traced it to a handful of memory locations which I dubbed:

0018:InputXDirection
0019:InputYDirection
001A:InputButton0
001B:InputButton1

The latter two are or-ed together and stored in:

003D:InputButton

Quick checks in the emulator verified my assumptions.
Searching for these labels in the code now gave me lots of results. Many routines where reading these values and triggering various sequences. What I needed was the common root function that calls all of them. If I could find that, then I would be very close to the main update loop of the game.

At this point my disassembly and labeling efforts became a bit fuzzy. I had to identify too many functions at once, and I wasn't quite sure of what many of them did in detail. But I traced my way up the call stack and found a couple of crucial ones:

;----------------------------------
updateCharacter:
            lda CharFace
            bpl updateCharacterMirrored
            jmp updateCharacterNormal
;----------------------------------
updateCharacterMirrored:
            jsr swapLeftRight
            jsr updateCharacterNormal
            jmp swapLeftRight
;----------------------------------

After a while I found a function which was basically just a long list of JSR calls. It called loadKidAndShad at the beginning, it called animChar, then it read from the frame def list using CharFrame, and at the end it called saveKid. Many unknown calls in between.

At this point everything went really quickly. I took that function and called it:

22F4:update

I decided that this must be as close to the main loop as I can get with my limited understanding of the code. I started to rebuild the known parts of this function in my own code, with many of the unknown JSR calls commented out. I just wanted to get the basic loop working: read from input -> run animation code -> get frame -> update sprite.
I had the backend already, so I was making very quick progress.

From the document I also knew how the level data is laid out. It's called "Level Blueprint" and it's one of the few data structures which is not only fully described in the document (see page 12 in the PDF), but also has it's memory location listed:

B700:BlueType
B9D0:BlueSpec
BCA0:LinkLoc
BDA0:LinkMap
BEA0:Map
BF00:Info

I had already moved that chunk of memory into my own code. I found many routines dealing with these memory locations. I noticed that $24/$25 always points into the BlueType array, and $26/$27 points to BlueSpec:

0024:CurrentBlueTypePtrLo
0025:CurrentBlueTypePtrHi
0026:CurrentBlueSpecPtrLo
0027:CurrentBlueSpecPtrHi

I was looking at a function called from within "update", which reads parts of the level data into smaller buffers. It turned out to be the collision detection code.
It was easy enough to understand, I went through it and documented it almost completely in one go.

4500:collisionDetection
4503:applyCollisionDetectionResult
4506:isPathBlocked

I was on a roll. Within the next few days, I went through tons of code and the puzzle seemed to come together. I still had no idea what most of the code did, but the parts that I did understand were growing at a steady rate. It was hard to stop, since it was always possible to go on.
At one point I did force myself to put all of the known code into my C64 program and see if I could get it up and running.

I also took a screenshot of the DOS version and converted it to C64 specs. I decided that I need to have something in the background of my animation test.

My backdrop, just a static image, but it gives context to the animations

The program I was putting together had many jumps to unknown code. I commented out as much as possible, figuring it wouldn't be important for now. I could always figure those out later. I knew that I had all the input handling, the animation update and the drawing code in place. Many functions that triggered the right sequences. And even collision detection, at least partially. I was confident that it could work.

However it took my quite a few days and I had to fix many little problems along the way. Finally, on the 17th of July 2009, I managed to get it all working. I made this video:

You can download a C64 .prg of the work in progress version from 17-Jul-2009. It contains this single playable room. It's not possible to progress to the next screen.

I was very happy to have gotten this far. I had the Kid, the Prince of Persia, running and jumping on my screen. I was able to control it and perform all the normal actions. And it felt right. Timing, speed, animations. Of course it was spot on, it was using the original code written by Jordan Mechner, lifted from its Apple II grave and brought back to life, with a new purpose.

At this point I was sure I could do this. It would only be a matter of months. Oh boy, was I wrong.

In the next part, I'll talk about how I dived into the code that draws the screen and how I learned that 64KB of RAM is probably not going to cut it.

Part Two - In the beginning there was a binary data blob

2011-10-17T14:49:00.000-07:00

If you haven't guessed yet, it's going to become more technical. You've been warned.

So there I was on June 19th 2009. A printed copy of Jordan Mechner's PoP source code documentation in one hand, and Virtual II (an excellent Apple II emulator for Mac OS X) running the original Prince of Persia game.

Running the Apple II version of Prince of Persia in the Virtual II emulator

I managed to save a snapshot of the game state at the very beginning of level 1 into a .vii file, and using the memory inspector in Virtual II and a hex editor in tandem I was able to isolate the two 64KB banks of memory in the snapshot file. I saved them as two binary files bank1_0000.bin and bank2_0000.bin.

Isn't it a pretty blob?

Then I took my favorite 6502 disassembler (dxa) and let it process the data. I somehow ran it on bank 2 first, and that was a lucky coincidence, as it turned out that bank 2 contained most of the game's code. So let's just focus on that bank for now. To Apple II programmers, it is known as "Auxiliary Memory".
The unlabeled output of the disassembler can be found here. It's all just unknown code with generic labels. Disassemblers try to identify data regions within the code, but typically they only have limited success. I've already correctly assigned the data regions in this output file, but originally it looked much worse.

Here's the disassembled code of the hex editor window above, starting from $2000:

;----------------------------------
l2000:
            jmp l2015
;----------------------------------
l2003:
            jmp l20e2
;----------------------------------
l2006:
            jmp l201e
;----------------------------------
l2009:
            jmp l2029
;----------------------------------
l200c:
            jmp lfc00
;----------------------------------
l200f:
            jmp lfc00
;----------------------------------
l2012:
            jmp l25aa
;----------------------------------
l2015:
            sta lc009
            jsr l2046
            jmp l20e2
;----------------------------------

As you can see, this makes no sense. Yes, it's a jump table of sorts, but what is the purpose of these subroutines. What do they do? How can we find out?

One approach is to identify memory-mapped IO registers (soft switches in Apple II lingo). There's one right there: $c009. It's used to switch the zero page and stack areas of the 6502 ($0000-$01ff) to auxiliary memory.
Looking at all the code that's using soft switches allows you to find the parts where joysticks, keyboard and other hardware is accessed. This is one way of entering the terra incognito of the game's code.

However, I used a different approach. I started with the immediate goal of finding the data describing the animation frames, because that's what I needed to improve my existing program, which was still based on FreePrince.
So I consulted the source code documentation to see what it has to say about animation data.

One of the most interesting parts I noticed were the two pages titled "Character animation comments" (starting at page 17 of the PDF). They describe 16 bytes of data holding most of the character's state, its position, velocity, health, a pointer into the "sequence table" and its current entry in the "frame list". It mentioned frame #15 as being standing still. Guess what, the 15th frame extracted from the DOS version is the Prince "standing still". I was onto something.

In a different part of the document (on page 15) the sequence table is mentioned again, together with the "frame def list". It was clearly obvious that the frame def list contained information about each of the images used to animate the character. Index into image table, x and y shift, and more.
It seemed like the sequence table was a list of frames with embedded commands. Positive values are frames, negative values are commands. Simple. The commands were listed right there: goto, aboutface, up, down, etc.
It was clear to me that if I would find the frame def list or the sequence table in memory, I could use the Virtual II debugger to find the code accessing it, and then I would be right in the heart of the animation code. But where could they be?

It felt like searching for a needle in a haystack. Surely they can't be that small (frame def list is described to be 1200 bytes in size), but I just couldn't pinpoint them with enough confidence. I thought if the PC version is based on the same animation code, then maybe the same sequence table is used there. I looked at the data files that come with the Prince of Persia for DOS and only found level data. The data file format had been reverse engineered and was clearly documented. The files mostly just contained bitmap data, wav files, midi files and palettes. No sign of a frame list or animation sequence table.
Then it struck me. The data must be in the PRINCE.EXE file itself, not in an external data file. But that meant it was probably just as hard to find. Except if it really was similar to the Apple II table. From reading Jordan's journals it was clear to me that Lance Groody (who programmed the DOS version) was working off of Jordan's code and data. Why would he change the animation sequence table? He would have had no reason to do that.
So in a desperate attempt, I started my copy of Araxis Merge in binary comparison mode, dragged in bank2_0000.bin onto the left pane and PRINCE.EXE onto the right pane and was hoping for a comparison match. Nothing. Too many differences, no direct matches. I removed everything that looked like code and text from the .EXE file to make it easier for Araxis to find a match. Still nothing. I scrolled aimlessly through the files and then I saw it:

Similar data in the Apple II memory (left) and in the PC executable (right). Found it!

I traced the data pattern to its beginning in the Apple II memory dump, and saw that it starts at $2800. It seemed to be larger than 1200 bytes though. I scrolled on to find its end.
The memory layout clearly changed at the $3000 point, so that must be it. At that location I noticed something that looked like a table of addresses:

E9 30 16 31 09 32 43 32 AE 32 CF 32 50 33 C9 33 16 34 79 34 9A 34 C0 34 C6 34 DF 34 6D 35 F9 33 A2 37 91 33 76 33 D5 37 AD 33 17 38 AD 34 DE 33 46 34 7A 32 90 32 F4 34 17 37 0B 37 FB 36 EB 36 D6 36 C1 36 AC 36 92 36 8C 36 70 36 53 36 34 36 15 36 F6 35 C8 32 D2 35 7F 35 B4 35 75 35 12 35 2C 37 20 37 39 38 4C 38 4F 38 44 38 3A 31 89 31 A4 31 B2 31 F2 31 F9 31 D9 31 D4 31 DE 31 E4 31 EB 31 D0 31 6F 31 63 34 CA 31 58 38 29 38 F1 35 53 34 52 31 B8 31 7D 31 1E 31 82 37 90 32 01 32 FA 32 16 33 34 33 E4 30 24 38 98 31 1C 31 22 31 A2 32 37 31 43 37 53 37 74 37 14 39 B5 38 CE 38 E5 38 18 39 27 39 EC 38 ED 39 B9 38 3B 39 6F 33 C4 39 D2 39 DA 39 43 39 3F 39 65 39 69 39 7B 39 BF 39 D6 39

In little-endian format, the addresses $30e9, $3116, $3209, $3243, and so on. They ended at $30e4, suspiciously close to the first entry of $30e9. So a pointer table into a data structure.
I checked the data of the first pointer:

$30e9 : F9 01 01 02 03 04 FB 08 05 FB 03 06 FB 03 07 FB 05 08 FB 01 F2 01 09 FB 02

Negative number, some positive numbers, then a negative number, and so on. Could it be? Did I just look at the sequence table?

What if the sequence table instructions were listed starting at $FF?

My annotations of the sequence instructions in Jordan's document

So lets look at the sequence above. Given my assumption it would translate into:

F9 01    act 01 ; change action code to "running, jumping, ..."
01              ; show frame 1
02              ; show frame 2
03              ; show frame 3
04              ; show frame 4
FB 08    chx 08 ; KIDX := KIDX + 8
05              ; show frame 5
FB 03    chx 08 ; KIDX := KIDX + 3
06              ; show frame 6
FB 03    chx 08 ; KIDX := KIDX + 3
07              ; show frame 7
FB 05    chx 08 ; KIDX := KIDX + 5
08              ; show frame 8
FB 01    chx 08 ; KIDX := KIDX + 1
F2 01           ; was unknown at first, turned out the play the footstep sound
09              ; show frame 9
FB 02    chx 08 ; KIDX := KIDX + 2

and so on...

It made perfect sense. The first few frames in my list of images were part of the running animation. I was looking at the sequence for making the kid run. Although it seemed there were more than the 8 documented instructions used in the sequence table. I had to find out what the others did.

Now I was on fire. I quickly debugged through the code and set strategic memory watch points to find the code using these two tables. I found the sequence table parser first:

;----------------------------------
l4945:
            jsr ld003   ; read a byte from the seq table
            cmp #$fb    ; is it CHX?
            bne l4957   ; no, then go to l4957
l494c:
            jsr ld003   ; read parameter byte of CHX instruction
            jsr ld015   ; perform CHX instruction
            sta l41
            jmp l4945   ; loop back to read next byte
;----------------------------------
l4957:
            cmp #$fa    ; is it CHY?
            bne l4966   ; no, then go to l4966
l495b:
            jsr ld003   ; read parameter byte of CHY instruction
            clc         ; perform CHY instruction
            adc l42
            sta l42
            jmp l4945   ; loop back to read next byte
;----------------------------------
l4966:
            cmp #$fe    ; is it ABOUTFACE?
            bne l4973   ; no, then go to l4973
l496a:
            lda l43     ; perform ABOUTFACE instruction
            eor #$ff
            sta l43
            jmp l4945   ; loop back to read next byte

[and so on for all other commands]

I had the animation system by the balls. Can you guess which part I found next, just by looking at this parsing code? I'll tell you in the next part.

Part One - Why the hell would anyone want to do that?

2011-10-17T06:53:00.000-07:00

So how and when did I start to work on a C64 version of Prince of Persia? And for the love of god, why?

In October of 2008 I visited the X party, a Commodore 64 demo scene event in the Netherlands. This sparked my interest in actively doing C64 programming again, something I haven't really done in the 15 years before that, even though I still kept up with the developments in that community.
At this point I actively started looking for a C64 project, and a game conversion seemed like a good idea, given my background as a game developer. I was rusty and needed something bordering on the trivial to get my 6502 assembly juices flowing again.

Prince of Persia preview by Poharai Attila and Varga Viktor from Hungary

So in May of 2009 I found the Prince of Persia preview on CSDb. It's an attempt from the 1990s at converting Prince of Persia, that unfortunately only produced a slide show of some of the level graphics. But the comment beneath, by Mikael "Twoflower" Backlund got my attention: "A C64 version of this game would sure be something.". I immediately had the same feeling. And then he wrote: "Furthermore, the sourcecode to one of the 8-bit versions is out there.".

That made me all warm and fuzzy inside. But soon I had to find out that what he meant was the version of Prince of Persia for the SAM Coupe computer. Although an outstanding technical achievement, it was not a direct port of the original game, but rather a fan-made recreation, which was close to Jordan Mechner's classic, but also different in lots of ways. And it was for a Z80-based architecture, which I personally never worked on and have little passion for.

FreePrince project

But the idea stuck with me. Is there someone who has done the reverse-engineering work of Prince of Persia? Something that I could just take and port to the C64 quickly?
I kept digging and immediately came across the FreePrince project. This is your typical open-source version of a classic game, created by a group of enthusiasts, using the trusted SDL framework. I thought that I had struck gold. Although it seemed unmaintained and it was hard to find the source code, it was a somewhat working version of Prince of Persia using the original game's graphics and level data. It had a complex animation state machine and lots of things working, so I assumed that it was based on disassembly of the PC or Amiga version. Plus it pointed me towards the Princed project and their tool "PR", a Prince of Persia resource extraction tool.
The latter can be used to unpack the data files that came with the DOS version of Prince of Persia to get the individual images, sounds and palettes that make up the assets of the game.
So, without further ado, I started hacking away. I took the 216 animation frames of the Prince extracted by PR, and first converted them to C64 resolution and colors.

The C64 features a multi-color mode that is using two bits to represent one pixel. This means you can use four colors, which you can select from the sixteen available colors. Since the memory storage size for graphics is the same in single-color and in multi-color mode, the graphics chip has to halve the horizontal resolution of 320 pixels in order to use two bits per pixel instead of one. So the effective resolution for multi-color graphics is 160x200, which is also half of the resolution of the DOS game. And since one of the 4 colors has to be the transparent color that meant that only 3 colors are available for the Prince character. I quickly settled on white for the clothes, light red for the skin and brown or orange for the hair. Using semi-automatic conversion tools I came up with this:

Original image from DOS version

Automatic conversion to C64 resolution and colors

Yes, that's a lot of detail lost, but it was inline with other C64 games. I was sure I'd be able to find some graphics artist who could polish that up later.
Doing this conversion for all the 216 animation frames quickly gave me a complete set to be used on the C64.
So at this point I fired up my source code editor. I took at look at the source of Freeprince, and started to implement its animation state machine in assembly code. I laid out the Prince animation frames as sprites in memory and immediately noticed that it's gonna be tight. Those animations sure need a lot of memory. But that would be for later to worry about.
Within a couple of days I had a simple working version. Basic animations states were implemented, such as running, jumping, crouching, etc. On June 15th 2009 I captured a video and showed it to one or two people.

Download a C64 .prg file of the work in progress version from 15-Jun-2009.

The response was a bit muted. Not enough of the game there yet. Also the animations looked dodgy. The positioning of the frames used in FreePrince was not based on the original game. Someone must've redone that manually, and so the locations were wrong.
So I kinda went off in the wrong direction. FreePrince certainly wouldn't be good enough for a faithful conversion. It was also incomplete and not fully playable.

Back to square one. I had to look for better source material. Disassemble the DOS version?
In the meantime I found Jordan Mechner's blog. He had the courage and insight to post all of his old journals from the 1980s. He meticulously kept a log of his daily work. What a great read that was. Just a few days before I started looking for Prince of Persia information Jordan also posted this article on his blog. It contained a link to a PDF, which turned out to be the Prince of Persia source code documentation.

I was amazed. The source was lost on Apple II disks, but the document written just a few days after the release in 1989 was there, with all kinds of juicy little details about the graphics engine, the data structures, lists of images, and more. It was like someone had handed me the key to a long lost treasure. I didn't even know that there was an Apple II version of the game, and that it was the original version. I learned that all others were ports (or ports of ports) of that one original. And it was all in perfect 6502 code, which I could read and which would run fine on the 6510 (a 6502 variant) of the Commodore 64. Sure it said it would need 128KB of RAM, but at that time that seemed like a small challenge. I imagined it to be very inefficient code and easy to optimize. Piece of cake, right?

So how do you go about reverse-engineering 128K of code and data? It's all just a big pile of binary data. It's like one really big crossword puzzle.Where do you start?
I'll cover that in my next post.

Prince of Persia for Commodore 64/128 released

2011-10-16T00:19:00.000-07:00

The C64 conversion of Prince of Persia, based on the original Apple II code by Jordan Mechner has been released today.
It requires a Commodore 64 or 128 (or maybe even a C64GS if you own one) and an EasyFlash (or 100% compatible) cartridge.
You can download the cartridge image from this CSDb page

Here are some screenshots and a few movies of the game:

During the next couple of weeks I will post my development diary. Details about the work on this conversion, pitfalls and little success stories. In short, pure C64 coder drama. Don't miss it!