Category Archives: Computer Graphics

Probabalistic Models of Cognition

This week began with a visit from Pat Hanrahan, currently a professor at Stanford and formerly at Princeton, where I was lucky enough to meet him. He came by to talk about probabilistic programming languages, which are an interesting topic that he and his students have made some interesting progress in solving difficult problems. I don’t have much to say about it, except that it seemed very cool in a way which I’ve come to expect from Pat: he has a tendency to find interesting cross disciplinary connections and exploit them in ways that seem remarkable. I haven’t had much time this week to think about his stuff more, but he did mention this website which gives examples of probabilistic computation and cognition, which seemed pretty cool. I’m mostly bookmarking it for later consumption.

Deconstructing the Classic Atari Game: Star Raiders

Gasp, I know. It’s been some time since I posted here. A combination of life and work events have conspired to sap me of my usual exuberant energy for the nerdy, geeky pointless topics that I usually like to post about here. But nerdy, geeky, pointless endeavors do continue (even if at a reduced pace) so I thought I’d post about one here that I’ve killed a few hours on.

I have fallen back into thinking about retrocomputing, not so much out of a sense of nostalgia, but because I was trying to understand the complex path that connected a 12 year old boy growing up in Oregon to the one who now exists. I think in no small part, I can draw it back to this game:

atari011

The classic 1979 Atari game Star Raiders. I’m pretty sure it was the second cartridge I bought for my Atari 400, right after Atari BASIC. Within it’s 8K boundaries, a first person space simulation was created. Not the boring, type “LRS” to get long range scan respresented in crude ASCII charts, but instead a visceral battle against the Zylon menace.

As much as I liked the game (and have played it a few times in the last few days, it still pretty much holds up) it also inspired me back then to learn how such highly interactive, real time games could be written. I got a copy of De Re Atari, and worked on learning about machine language programming, and how to manipulate POKEY and ANTIC to do my bidding. I used to say that the Atari was the last computer that I understood completely. Perhaps that was a little bit of bragging, combined with the humble realization that modern computers were far more of a black box than I felt I could understand.

But in the last couple of weeks, I thought to myself, “there must be some good programming hidden away in that 8K.” The scientist in me recognizes beauty not just in the final form of the organism, but in its constituent parts. So, I decided to see if I could take the raw ROM image of Star Raiders, and turn it back into an annotated chunk of source code. In theory, you could use this to make changes (I hesitate to say “fixes”, because it’s so brilliant) but really, it was just so I can learn something about how it works.

Luckily for me, modern tools have made this much simpler. I have a Linux box far more powerful than any computer I could have dreamed of back in the day, and retrocomputing pioneers have traveled this path already, and left tools that I could use along the way. I decided to use cc65, a freeware C compiler suite that can generate code for a variety of classic 6502 based systems. It includes da65, a disassembler that will take an “info” file which describes where the code starts and some machine specific labels, and then tries to disassemble the ROM back into assembly code. It more of less seems to default to the idea that the ROM is entirely code, and only inserts “.byte” assembly instructions when it can’t find a valid instruction at a particular location. By beginning at the known jump address, you can follow code and find areas where data instructions access tables and the like, and then use the .info file to describe block those out, slowly converging to more or less legible code. For instance, the decoded code that starts the cartridge looks like this:

; ----------------------------------------------------------------------------
CARTBOOT:
        lda     #$00                            ; A14A A9 00                    ..
        sta     SKCTL                           ; A14C 8D 0F D2                 ...
        sta     $66                             ; A14F 85 66                    .f
        sta     $62                             ; A151 85 62                    .b
        sta     $63                             ; A153 85 63                    .c
        lda     #$03                            ; A155 A9 03                    ..
        sta     SKCTL                           ; A157 8D 0F D2                 ...
LA15A:  ldy     #$2F                            ; A15A A0 2F                    ./
LA15C:  lda     #$FF                            ; A15C A9 FF                    ..
LA15E:  sty     $65                             ; A15E 84 65                    .e
        sta     $64                             ; A160 85 64                    .d
        lda     #$00                            ; A162 A9 00                    ..
        tax                                     ; A164 AA                       .
LA165:  sta     HPOSP0,x                        ; A165 9D 00 D0                 ...
        sta     DMACTL,x                        ; A168 9D 00 D4                 ...
        cpx     #$0F                            ; A16B E0 0F                    ..
        bcs     LA172                           ; A16D B0 03                    ..
        sta     AUDF1,x                         ; A16F 9D 00 D2                 ...
LA172:  sta     PORTA,x                         ; A172 9D 00 D3                 ...
        sta     a:$67,x                         ; A175 9D 67 00                 .g.
        inx                                     ; A178 E8                       .
        bne     LA165                           ; A179 D0 EA                    ..
        dex                                     ; A17B CA                       .
        txs                                     ; A17C 9A                       .
        cld                                     ; A17D D8                       .
        lda     #$02                            ; A17E A9 02                    ..
        jsr     LAE0F  

Seems like typical “begin the program” kind of stuff, the loop around LA165 is basically zeroing out a lot of I/O ports which control player missile graphic and audio, as well as lots of zero page memory starting around address $67. Not too exciting, but it gets you started.

A bit of poking (and review of old Atari programming manuals) made me realize that the system sets up the player missile graphics to be based from address zero. This means that the buffers for the player 0 will start at $400, for player 1 at $500, etc… Some further poking indicates that the display list (the list of ANTIC instructions that builds the display) begins at $280. I located a couple of data tables that contained a list of strings used in the game (with the first character in each having the high bit set). I located a fragment of a display list in ROM. I wrote a python program to generate a graphical version of each instruction (1s displayed as X’s, 0s as spaces) to see if I could locate some of the bit patterns from the game. This revealed that some font characters were defined starting right at the beginning of the ROM (mapped to address $A00) as well as the bit patterns for the TIE fighters, asteroids, etc…) in a variety of sizes:

B9B0:  X X
    :
    :X      X
    :X      X
    :X      X
    :X      X
    :X XXXX X
    :XXXXXXXX
B9B8:XXXXXXXX
    :X XXXX Xh
    :X      X
    :X      X
    :X      X
    :X      X
    :X     X
    :X     X
B9C0:X XXX X
    :XXXXXXX
    :XXXXXXX
    :X XXX X
    :X     X
    :X     X

That was helpful. But then progress began to slow a bit, and I wondered what other tools I could use. Back when I was teaching myself Atari 2600 programming, I found the Stella simulator to be absolutely key: it had an awesome single step debugger that I used to work out many a difficult chunk of code. Without any real research, I settled on using the atari800 simulator from sourceforge. A bit of digging uncovered that hitting F8 dropped you into a monitor. Not as sophisticated as the Stella one, but still quite helpful. For instance, if you type “DLIST”, you can get the currently active display list. During the “attract mode” of the game, you can break and find that the current display list is:

0280: 2x 8 BLANK
0282: LMS 1000 MODE D
0285: 10x MODE D
028F: 4 BLANK
0290: LMS 0D1F MODE 6
0293: LMS 12A8 MODE D
0296: 81x MODE D
02E7: JVB 0280

This is pretty helpful (although it’s probably gobblety-gook to most readers). Reading from top to bottom, it says that the display has 16 scanlines which are blank, then starts rendering with mode D (which is a 160 pixel resolution, 4 color mode, where each dot is 2 scanlines high). The LMS indicates that the graphics memory will start at $1000. There are a few more lines like that, then some blank lines followed by a mode 6 line (which is a 20 character display, 8 scanlines high). Then some more lines of Mode D (resetting the memory buffer to the appropriate address). The mode 6 line draws characters from the buffer beginning at $0D1F, which I had not identified in code anywhere. That presented a clue to me, enabling me to spot other useful chunks of code.

I’ll keep plodding away at this, it is kind of like working on a crossword puzzle. Each little bit you uncover allows you to understand more. Stay tuned.

Fourier Volume Rendering

Three years ago, I wrote a short post about volume rendering. I always meant to follow up, because I finally sorted out the problems with generating multiple, overlapping images. Here’s a new video generated with the improved code:



Fourier volume rendering is less flexible than raytracing, but it does have certain computational advantages, most notably in that you can generate images in less than O(n^3) time, which is the typical bound for conventional raytracing. It also has some applications in light field refocusing applications. But overall, I still thing that raytracing has a number of advantages. Perhaps that would make a good first serious Go program? I’ll ponder it more.

Making some wallpaper with the sum of cosines…

WordPress › Error

There has been a critical error on this website.

Learn more about troubleshooting WordPress.