经典复古游戏编程黑客技巧回顾（2013）

A Great Old-Timey Game-Programming Hack

Posted on December 14, 2013

Tags: assembly, 6809, games, hacks

A long time ago, when I was a college undergrad, I spent some time working on computer video games. This was in the 8-bit PC era, when the gaming hardware was almost impossibly slow by today’s standards.

It might not surprise you, then, to learn that game programmers of yore did all sorts of crazy things to make their games run at playable speeds. Crazy, crazy things.

This is a story about one of those things.

While I’ve done my best to recall the important details, I may have gotten some things wrong. If I have, please forgive me. It was a long time ago.

(Note: This post contains some small images as inline-data URLs that some feed readers apparently don’t handle well. If you can’t see the images in your feed, click through to the original article to see them.)

Update 2013-12-16: There have been lots of great comments about this story on Hacker News and Proggit, as well as here on the blog. Thanks for sharing, everyone!

The set-up

A friend of mine, a gifted programmer, was nearly finished with a new game. Somehow, he had squeezed into a 1980’s-era PC, pretty faithfully, what was at the time a graphically impressive coin-op game popular at the arcades.

The only problem was that his version of the game was unplayable. It was too slow, and the choppy motion broke the player’s immersion. It was after all a side-scroller.

My friend, who had been working on the game while also taking a full load of college courses, was starting to seem a little frazzled. Fearing that he had missed some easy optimization, he asked me to take a look at the code.

I did. But there was no easy optimization to be had.

The code was tight. Everywhere I looked, he had already done all the things I could think of. Loops had been unrolled. Unneeded draws had been eliminated. All evidence of waste had vanished.

And, with them, our hopes of an easy fix.

But what about a hard fix? A crazy fix?

Well, that was always a possibility.

Before I get to the crazy stuff, however, I should back up and explain how graphics hardware worked back then.

How graphics hardware worked back then

Here’s the quick version: The graphics hardware didn’t do jack squat.

On the PC in question, if you wanted to draw something onto the screen, you had to do that yourself, byte by byte. No texture mappers, no blitters. Just bytes. Bytes that you had to move yourself.

My friend’s game spent most of its time redrawing the background. (Again: side-scroller.) For every frame, it had to draw nearly a screen’s worth of background tiles, shifted for the player’s position.

If my memory serves me, each tile was 28 by 28 pixels. Each pixel was one of 16 colors, taking half a byte to represent. Therefore, tiles were represented in memory as 28 contiguous rows of 14 bytes each. The first 14 bytes represented the first row, the second 14 bytes the second row, and so on.

The screen, however, was 320 pixels wide by 240 pixels high. In memory, then, a screen buffer was laid out as 240 contiguous rows of 160 bytes each.

So when copying a tile at address X onto a screen buffer location starting at address Y, you had to copy 28 rows. To copy each row, you had to copy 14 bytes. Fortunately, the processor for this game was a 6809, which had a few 16-bit index registers and delightful “auto-increment” addressing modes (sort of like applying the postfix ++ operator to pointers in C). That meant you could copy 4 pixels at a time while advancing both the X and Y registers in passing:

LDU ,X++ ; read a 2-byte word (= 4 pixels) from source tile STU ,Y++ ; write it to screen buffer

To copy a full row, you had to do that seven times, so you might sandwich those lines within a 7-count loop:

LDB #7 ; remaining words <- tile width in words @LOOP LDU ,X++ ; read a 2-byte word (= 4 pixels) from source tile STU ,Y++ ; write it to screen buffer DECB ; reduce remaining-word count BNE @LOOP ; loop while words remain

When you were done copying the row, you needed to advance the destination pointer Y so that it pointed to the starting address for the next row you would draw into the screen buffer. Since the screen buffer was 160 bytes wide and a tile was only 14 bytes wide, that meant you had to add their difference to Y:

LEAY 160-14,Y

And, just like that, you have copied a row onto the screen.

That’s one. To copy a full tile, you need to do the same thing 28 times. So, in turn, you sandwich that code within a 28-count loop.

Putting it all together, and giving names to the important numbers, you might end up with a subroutine like this:

;;; important constants

SCRW = 160 ; screen-buffer width in bytes (= 320 4-bit pixels) TILW = 14 ; background-tile width in bytes (= 28 4-bit pixels) TILH = 28 ; background-tile height in rows WOFF = SCRW - TILW ; s-b offset from end of one tile row to start of next

COPYTILE ;;; ;;; Copy a 28x28 background tile into a screen buffer. ;;; Arguments: ;;; X = starting address of background tile ;;; Y = starting address of destination in screen buffer ;;; LDA #TILH ; remaining rows <- tile height @COPYROW LDB #TILW/2 ; remaining words <- tile width in words @LOOP LDU ,X++ ; read a word (= 4 pixels) from source tile STU ,Y++ ; write it to screen buffer DECB ; reduce remaining-word count BNE @LOOP ; loop while words remain ;; LEAY WOFF,Y ; advance dst ptr to start of next dst row DECA ; reduce remaining-row count BNE @COPYROW ; loop while rows remain ;; RTS ; done! return to caller

And that code would be fine.

If you didn’t care about speed.

Caring about speed

Knowing that the game is probably going to spend most of its time running that code, you do what any good programmer would: start counting cycles. Here’s the inner loop again, with setup and finishing, annotated with cycle counts:

LDB #TILW/2 ; 2 cycles (set-up) @LOOP LDU ,X++ ; 8 STU ,Y++ ; 8 DECB ; 2 BNE @LOOP ; 3 ;; LEAY WOFF,Y ; 8 (finishing)

Looking at those counts within the loop, you’re not likely to miss that you’re burning 21 cycles to copy just 4 pixels. To copy a full row, then, works out to 2 cycles + (7 iterations) * (21 cycles/iteration) + 8 cycles = 157 cycles. Ouch.

But this isn’t your first time at the keyboard. You know what to do. Unroll that loop!

LDU ,X++ ; 8 cycles STU ,Y++ ; 8 LDU ,X++ ; 8 STU ,Y++ ; 8 LDU ,X++ ; 8 STU ,Y++ ; 8 LDU ,X++ ; 8 STU ,Y++ ; 8 LDU ,X++ ; 8 STU ,Y++ ; 8 LDU ,X++ ; 8 STU ,Y++ ; 8 LDU ,X++ ; 8 STU ,Y++ ; 8 LEAY WOFF,Y ; 8 (finishing)

Now, with the loop overhead reduced to zero – you’ve even eliminated the set-up – each row takes only 7 * (8 + 8) + 8 = 120 cycles. That’s a 30-percent speed-up. Pretty good.

And that’s where most programmers probably would have left it.

But not my friend.

He knew that those ++ operations were costly, 3 cycles apiece. And, with the loop unrolled, he also knew exactly where each word to be read or written was located with respect to X or Y. So he cleverly replaced those 3-cycle post-increments with exact offsets. They cost only 1 cycle apiece, and the 0 offset is actually free:

LDU ,X ; 5 cycles STU ,Y ; 5 LDU 2,X ; 6 STU 2,Y ; 6 LDU 4,X ; 6 STU 4,Y ; 6 LDU 6,X ; 6 STU 6,Y ; 6 LDU 8,X ; 6 STU 8,Y ; 6 LDU 10,X ; 6 STU 10,Y ; 6 LDU 12,X