Part Five - Painting a pretty dungeon

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! :)