Attack of the Space Cats (Jam version)

Contents

Preamble / Nostalgia

Cover of 'Teach Yourself Game Programming in 21 Days'

I started learning game dev when I was a kid, thanks to a book called "Teach Yourself Game Programming in 21 Days" by Andre LaMothe. It focused on C programming in DOS, with the VGA card's mode 13h.

In hindsight, mode 13h was a great graphics mode for learning: unlike many graphics modes on other systems at the time, it presents a linear framebuffer - the screen appears as a 320x200 array of pixels. Setting an element to a value sets the colour of that pixel. Lovely!

I discovered the book in the closing years of DOS' reign, as games were switching to SVGA, and just before Windows 95 (and WinG / DirectX) came along and changed everything. Pretty soon I got a book on DirectX 3.0 (can't remember the title.. it was orange) and forgot all about mode 13h.

Cover of 'Teach Yourself Game Programming in 21 Days'

In the years since I would reminisce about DOS, and wonder about "mode X" - a mysterious, arcane graphics mode I never learned about that was purported to be somehow faster than mode 13h. Then last year I heard about the DOSember game jam and thought it was a perfect opportunity to do some nostalgic research...

Initial Ideas

X-files logo

I can clearly remember all the DOS games I made as a kid. There was a pacman clone that I didn't think was very good, so I called it 'Kakman' (in my defence, I was 13.) There was an X-Files-inspired pipemania clone called 'Chicken Spay Mania' (I was 13) which had an elaborate plot about helping a mutant, fire-breathing chicken escape through the sewers to avoid an inexplicably-hatchet-wielding FBI agent (the chicken couldn't breathe fire until its bile-o-meter was high enough, and the FBI man wanted to prevent it breeding. I was 13.)

Apogee logo

The last game was one I never finished. It was a side-scrolling shooter: ship at the left, parallax starfield behind, waves of enemies from the right. A good base for a jam game, I thought!

From here it was a case of dreaming up a 'shopping list' of all the things I loved about games from that period. Essentially I wanted to create an homage to late-stage DOS shareware, with such things as:

  • prerendered 3D sprites (they were cool and futuristic! Do not mention Rise of the Robots)
  • screen after screen of overwrought sci-fi pulp story ('The year is 4222. The Empire of The Zagrablabs holds dominion over all the known galaxies. Ruthless Emperor Harman Kardon rules with an iron fist... page 1/41')
  • voice samples (to prove the sound effects aren't MIDI!)
  • "Don't forget to register"

Setup

Since my experience with PCs as a kid largely skipped the 16-bit era I chose to target the 386 as a baseline. I cross-compiled to DOS using DJGPP, which had the added benefit of coming with the DOS extender CWSDPMI (allowing access to memory beyond the 640k 'conventional memory' barrier.)

I'd recently read about MikMod on usebox.net, and the thought of playing MODs really appealed. Its additional support for sound effects convinced me - using it would save a lot of time.

An unquantised sprite sheet for the saucer cat enemy

My process for making sprites started in Blender. I'd export an animation as a series of PNGs, then have ImageMagick combine them into a spritesheet and quantise the resulting image to a 256-colour PCX. I knew I'd be quantising multiple sprites to the same palette, so I needed a fixed palette to use for everything. With no better idea what to do I chose to use Quake's palette. I would come to regret this decision multiple times, usually when I wanted a bright green colour.

I wrote a little test program to render the sprite in mode 13h, before looking into mode X. Initially I assumed I'd need to write blitting routines in assembly (LaMothe had done this in his book), but I found DJGPP could be coaxed into outputting performant-enough instructions by using memcpy with a literal size, as mentioned here. But more on that later!

Mode X

In mode 13h the first entry in the framebuffer 'array' refers to the top-left pixel. In mode X the framebuffer is split into 4 planes, so the first entry refers to the row of 4 pixels starting at the top-left. The same address refers to 4 different pixels! You have to set the VGA's 'write mask' to specify which of the 4 pixels you're referring to - but because it's a mask, you can write up to 4 pixels at the same time.

Memory layout in mode 13h

Memory layout in mode X


But there's more! Mode X also supports hardware scrolling. The idea that IBM provided special circuitry to accelerate games seemed briefly incredible to me, until I found out it was never intended for games - it was intended for text mode, it just works for graphics in mode X as an accident of the spec. VGA cards have 256k of memory, but mode 13h's framebuffer is limited to around 64k of that (representing the screen.) Mode X can access all 256k - its framebuffer is a virtual screen much larger than the actual screen. You can set the 'start address' - the offset into video memory of the 'window' you'd like to display on the screen - allowing you to scroll 'for free', instead of having to redraw the entire screen.

Video of scrolling demo running on a laptop

Memory arrangement

You can arrange the 256k how you like (2x2 screens, 1x4, or 4x1) by setting the VGA's Offset register. You can read more on that, and everything else about VGA hardware, at the FreeVGA project.

Informed by all the above, I put together a little test featuring a scrolling picture of my cat Dora, with a somewhat cat-like sprite spinning around in the foreground. (It also featured MOD music pulled from Cannon Fodder but I've omitted that here for fairly obvious reasons. "War.. has never been so much fun...")

Change of Plan

Seeing the demo scrolling in both directions made the idea of a horizontal shooter seem... limited somehow. I started to wonder if maybe the game should be a 'Lunar Lander'-type affair, moving through tight caves, trying to land carefully without blowing up.

At the same time I'd found there was a ton of public domain MOD music available - much of it on ModArchive. Once I found the track "May is 4 Her" by Drozerix I knew it had to be in the game. But it was waaaay too fast for a 'Lunar Lander'-style game. So the game couldn't be that! To do justice to this fantastic track I'd need to make a fast action game: a ship zooming in all directions through caves, blowing baddies into bits at every turn.

First Technical Decisions

Sprites & Masking

As I added more sprites, performance quickly tanked. I was setting the write plane before drawing each pixel, as it was the (naively) straightforward way of doing things. But setting the write plane has a cost: each set requires two bytes be sent to the VGA card, so where a 32x32 sprite in mode 13h requires 32x32 == 1024 bytes to be sent down the bus, in mode X, you'd send the same 1024 pixels, plus 2 bytes per pixel - an additional 32x32x2 == 2048... meaning mode 13h would run 3x faster than the naive approach in mode X!

This set the shape of the renderer going forward: all image data would be stored by plane, and the renderer would perform operations in plane order, to minimise write plane switches. But even in the perfect scenario, where you only need to send 4 plane switches, you're still sending 32x32 + 4x2 == 1032 bytes - you must send more data under mode X, which necessarily means sprite blitting is very slightly slower. Unless you're compensating in other areas... like with hardware scrolling? I felt like if I couldn't figure out a way to take advantage of hardware scrolling, the game might actually be better off written in mode 13h.

I wanted to use memcpy for blitting too, because the rep movsl instruction it produced would be way faster than a for loop - but to handle transparent sprites I'd need to support masking. So on load, a mask of each sprite was created (0 where the pixel was transparent, 255 where it wasn't), then drawing looked like this:

  1. Read the background from video memory where you're intending to draw the sprite (using memcpy)
  2. Loop over the sprite, 32 bits at a time, masking together the background and sprite
    • compositeData = (backgroundData & ~maskData) | (spriteData & maskData)
  3. Memcpy the result to the screen

Sprite masking process

It almost seems counterintuitive, but it turns out 2 block copies and a short loop is still a fair bit faster than looping over each pixel individually.

Double Buffers & Latched Writes

If I was making this game in mode 13h, the rendering would be pretty straightforward: render the tiles for the player's current offset, then all the sprites, onto an offscreen buffer. Then copy the entire offscreen buffer to the video card. Repeat for each subsequent frame. Because all the background tiles move every frame (if the player is moving) we can't erase the sprites and draw them in their new positions (i.e. using 'dirty rectangles') - we have no choice but to redraw the entire screen, every frame.

Backbuffer operation in mode 13h - backbuffer stored in system RAM

I thought I should be able to do better in mode X. Hardware scrolling seemed like it had to be the answer, but I couldn't figure out how to apply it to this game. The tiles were 16x16 so, leaving some space for the HUD at the bottom of the screen, that meant a 'screen' was 320x160. We have 256k of video memory, so we could scroll around inside a little over 4 screens' worth of tiles - which isn't a lot. I also couldn't see how I could use a double buffer and hardware scrolling at the same time... and it wasn't clear how I'd draw the HUD - it needed to stay static while the world scrolled 'underneath' it.

Having 256k of video memory meant I could move the backbuffer onto the VGA card at least. That gives the advantage of not having to copy the backbuffer to video memory to 'swap buffers', instead we just update the VGA's scroll offset to point at the newly-rendered buffer. It didn't seem like the best use of hardware scrolling, since we still had to draw the frame from scratch every time, but it was better than nothing.

Backbuffer operation in mode X - backbuffer stored in video RAM

Cover of Michael Abrash's Graphics Programming Black Book: Special Edition

One evening, staring at Abrash's Black Book until I went cross-eyed, I discovered latched writes. These allow for a limited, but accelerated, form of VRAM-to-VRAM copy: using latched writes you can write 4 pixels for the price of reading 1 plus writing 1 - as long as you're reading and writing to and from a 4-pixel boundary. Abrash explains it better, but the short version is: when you read 1 pixel in mode X, a side-effect of the read is that all 4 pixels at that offset are read into the VGA's 'latches.' You can then set the VGA's write mode to 'latches only', and tell it to write a zero to another location in memory. The VGA will then ignore the zero you sent, and write the contents of all 4 latches to that location instead. Bizarre, but it works.

A plan started to form: I'd store the tileset offscreen in video memory, and use latched writes to copy the tiles to my offscreen buffer, also stored in video memory. The offscreen buffer will be at the left edge of memory, and it'll be one tile wider than the screen - this way I can use hardware scrolling to scroll up to the width of one tile. I rewrote the tile renderer to preprocess the visible tiles, making a list of target tile positions per tile index - so I had a list of all the 'left wall' tiles, and another list of all the 'top-right corner' tiles, for example. Then, having set the VGA's write mode to latches only, I could loop over each used tile in the tileset, and read 1 pixel from the source tile, and do a single write to each of the target tile positions to draw 4 pixels each time. There's some overhead there of course, but overall this is a lot faster than I could achieve with mode 13h.

Judgement From The Future

Writing this description nearly a year after I wrote the code, it makes me think: why did I redraw the tiles every frame? Since I was hardware scrolling up to the width of one tile, could I not just redraw the tiles when I advanced the tile and reset the scroll? It took me a while to work out why not - the HUD is the problem: it prevents hardware scrolling vertically. When scrolling vertically I'd have to redraw the HUD as well as the newly-exposed section of tiles. In short, it could be optimised, but it would be fiddly. At least, given the understanding of the VGA I had at the time (more on this in the next blog post!)

Video memory layout showing front and back buffer and tileset

Redrawing the tiles every frame came with an unexpected benefit: since you're redrawing them anyway, it doesn't cost more to animate them. So all pickups (the diamonds and other power-ups) could be rendered as tiles, meaning their cost was absorbed into the tile renderer, instead of as sprites, where they'd be much more expensive.

Final note on scrolling

There are actually two values to adjust to set the scroll on the VGA. You might have noticed that because one address offset refers to 4 pixels (all 4 planes), increasing the scroll offset by a byte will make it jump right by 4 pixels. To get smooth scrolling you also need to set the VGA's "PEL panning" register (a 'PEL' is weird IBM-speak for what everyone else calls a 'pixel'.) The VGA card determines which pixel in memory is the top-left of the screen using the offset to determine the byte, and the PEL panning value to determine the plane.

3D modelling, 90s-style

Cyril McClelland, laughing unintelligently

Though I found the idea of presenting the player with huge reams of turgid sci-fi prose really funny, when it came down to it I wasn't sure I could pull off the irony of it - I was worried people would think it was meant to be taken seriously. On top of that, I wanted to have the story unfold between levels, and interspersing a fast, action game with a deliberately slow text crawl seemed a bit inappropriate - so I decided to do cutscenes instead.

The hero: Terry Bullets


I briefly looked into doing fullscreen animation; a 386 can manage the blits fast enough, if the frames are loaded from disk, but without a video codec you just can't fit many frames in memory. No time to make a codec in a jam, so I shelved the idea. Instead, I'd just do text dialogues with character portraits. And I could make the portraits using 90s-era modelling tools - specifically: metaballs. Metaballs are an intuitive, if very limited, way of making blobby, curved surfaces, so I had a go using them to model McClelland's head (above.) Turns out rendering to a 64x64 square hides a lot of rough edges, and implies a level of detail that isn't actually there! The end result is.. well, fairly terrible. But it's... appropriately terrible? More importantly, it was also tremendous fun to make!

Colonel Fuzzy Bum, as seen in Blender, and as seen in game

It hertz to run at 30

As the jam submission date grew nearer, it became apparent that while the game ran happily at 60fps on a 486 or Pentium, it struggled to manage 30fps on a 386.

I added a 'low detail' mode, which reduced the number of nuts and bolts spawned when an enemy exploded, and switched off the player's exhaust particle trail.

I'd read about 'adaptive tile refresh', Carmack's optimisation for Commander Keen, and while my tiles were too small to use it directly it did give me an idea: I made a low-detail tileset, by making the solid block wall tile a 16x16 square of solid grey, and reducing the detail of the other wall tiles to match. I also removed all the background wall objects (resistors etc.), replacing them with the solid tile in code. This meant a good portion of the screen was now made up of solid grey tiles, all of which I could blit way faster (because I only needed to load grey into the latches once, then write 16x16/4 == 64 pixels per tile.)

Adaptive tile refresh

Keen used hardware scrolling in a similar way to Space Cats, just to move up to the distance of one tile, before resetting the scroll and redrawing the tiles, shifted along one. But in Keen, the background tiles are mostly large areas of a single colour, there are very few 'detail tiles' - this meant instead of redrawing all the tiles, Keen only needed to redraw those few tiles that weren't a solid colour (and the tiles adjacent.) More info on wikipedia.

I wrote a diagnostic that executed on first run that measured how long it took to render several thousand black pixels, and if the result was high enough, would switch on low detail mode automatically.

All the above helped, but there were still moments when the frame rate would dip below 30fps. In the end I decided there was little more I could do to optimise the rendering, so I needed to focus on the next most expensive thing: MOD music. Mixing the 4 audio channels of a MOD in realtime was a fairly big ask of a 386. I absolutely did not want to remove the music entirely - the whole game design had been inspired by it! So in the end I compromised and added an 'in-game music quality: low/high' setting in the menu. 'Low' meant only 2 of the 4 channels played, enough to get the melody, and half the cost of all 4 channels. I forgave myself in the knowledge practically nobody would be playing on an actual 386, and the autodetection code would make sure everyone else got the full 4 channels!

The End

I released the game in time for DOSember on November 30th, and a post-jam update a month later. I enjoyed the process of making a DOS game so much, I kept working on it... and I still am! The 'registered version', with more levels, more weapons, more enemies, and more ludicrous story will be out in time for DOSember this year: December 1st 2026. And it runs at 60fps on a 386, with music!

I'll be writing another post about the changes I made for the 'registered version' (a complete rewrite of the renderer... which led to a near-complete rewrite of the whole game!) at a later date. In the meantime: play the jam version here!