Tuesday, October 18, 2011

Part Three - Making the Kid come to life

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.

5 comments:

  1. Nice! I wonder how did you solve masking when the character is running behind some walls. How many sprites were needed for a single animation frame? Sometimes is looks like it needs 3 or 4?

    ReplyDelete
  2. very nice effort. If you are willing to share to labeled assembly code, I would love to port it to C.

    ReplyDelete
  3. I'm interested in an open source C clone as well. This is great stuff!

    ReplyDelete
  4. @Og2t in the video above the background is a static image behidn the animation. I guess we have the level drawing code coming up in a later part.

    @mrsid I just wanted to say how great this is to read. Also, much respect for doing it all and only then publishing it. Congratulations on this great project.

    ReplyDelete
  5. Awesome! Very interesting to read, looking forward to the next posts!

    ReplyDelete