Old School Blizzard: Sprites, Maps and Palettes

I’ve been reverse engineering two of Blizzard’s early DOS games, The Lost Vikings and Blackthorne. I’ve previously written about the virtual machine that The Lost Vikings uses for implementing game objects here and here. Blizzard has now made both The Lost Vikings and Blackthorne freely available on Battle.net. Note that Blizzard went by the name Silicon and Synapse for their early games including The Lost Vikings. Blackthorne was the first game released under the Blizzard brand.

This post is about how the sprite formats and tile engine are implemented for the games. The two games use very similar engines, with Blackthorne having a few improvements over The Lost Vikings. I’ll refer to the game engine for both games as the “Blizzard engine”.

The games store all of their data in a single pack file called DATA.DAT. The pack file is an archive which contains chunks for sprites, levels, sounds etc. Most of the chunks in the pack file are compressed using a variant of the LZSS compression algorithm.

I’ve developed a set of basic tools which can be used to view sprites, levels, etc from The Lost Vikings and Blackthorne. You can download the tools from GitHub. I’ve included the command invocations to view the various examples throughout this blog post. All of the screenshots in this post were captured using these tools.

splash

./sprite_view DATA.DAT -fraw -s -u -w344 -p 0x17b 0x17c
./level_view --blackthorne DATA.DAT 1 -h0x6e

Graphics Mode

Both games use the popular “Mode X” VGA mode. Mode X is a 256 colour, 320×240 planar graphics mode. Planar graphics means that, rather than pixels being arranged linearly as they are in the 320×200 VGA Mode 13h they are divided into a set of planes. Planar graphics were originally developed to boost graphics throughput by allowing multiple memory chips to store independent planes and deliver them in parallel. This Shikadi.net article gives a good explanation of how planar graphics work.

Mode X uses four planes. The first plane stores pixels 0, 4, 8, etc. The second stores pixels 1, 5, 9, etc. So for an 8×2 sprite rather than the pixels being stored linearly as:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

Planar Mode X stores them as:

0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15

I did most of the reverse engineering of the sprite formats by looking at the data in the pack file chunks rather than looking at the rendering code in IDA. I have a very rudimentary understanding of DOS and VGA programming and rendering code for old games tends use every optimization trick in the book and clever handcoded assembler, which is difficult (for me) to understand.

Raw Sprite Format

The first sprite format used by the games is just raw encoded planar data. Raw sprites can have any width and height that is divisible by four. Drawing raw sprites is simple:

for (plane = 0; plane < 4; plane++) {
    for (i = 0; i < (sprite_width * sprite_height) / 4; i++) {
        offset = (i * 4) + plane;
        y = offset / sprite_width;
        x = offset % sprite_width;

        pixel = *sprite++;
        dst[((dst_y + y) * dst_width) + (dst_x + x)] = pixel;
    }
}

Optionally a colour index could be chosen as an transparent colour. Raw sprites of a given width and height always have the same data size, but they are not particularly space efficient. This is especially true for the Blizzard game engine because sprites use only sixteen colours (always values 0x0 to 0xf) meaning that four bytes per pixel are wasted. The reason for using only sixteen colours per sprite is to enable some clever palette tricks which are explained later.

Unpacked/Masked Sprite Format

The second sprite format allows for transparency without sacrificing a colour index at the cost of a more complex drawing algorithm and slightly larger data size. In the tools I developed I’ve called this format “unpacked”, but it “masked” might be a better term.

In this sprite format, each set of eight pixels is preceeded by a mask byte which specifies which pixels to are to be drawn. The transparent pixels are still encoded with the value 0x0 but are skipped over when drawing. This allows the colour index 0x0 to be used as an additional colour.

The algorithm for drawing these sprites looks like this:

for (plane = 0; plane < 4; plane++) {
    x = plane;
    y = 0;
    for (i = 0; i < (sprite_width * sprite_height) / 4 / 8; i++) {
        mask = *sprite++;
        for (bit = 7; bit >= 0; bit--) {
            pixel = *sprite++;

            if (mask & (1 << bit))
                dst[((dst_y + y) * dst_width) + (dst_x + x)] = pixel;

            x += 4;
            if (x >= sprite_width) {
                y++;
                x = plane;
            }
        }
    }
}

The various collectible items in The Lost Vikings are 16×16 unpacked/masked sprites. They can be viewed with:

./sprite_view DATA.DAT -l2 -funpacked -w16 -h16 0x12f

tlv_items

Packed 32×32 Sprites

The final sprite format is only used in The Lost Vikings and is optimized for drawing 32×32 sprites. Like the unpacked/masked format each set of pixels is preceeded by a mask byte indicating which pixels to draw. However the packed format does not store the transparent pixels and packs two pixels into each byte since only sixteen colours are used. If the number of pixels to be drawn is odd, then the final half byte is zero.

This format is more space efficient the other two formats, but has a more complex drawing algorithm and variable length sprites. Pack file chunks which contain packed format sprites start with a header of 16-bit values indicating the starting offset of each sprite.

The algorithm for drawing the packed sprites is as follows:

for (plane = 0; plane < 4; plane++) {
    for (y = 0; y < 32; y++) {
        num_pixels = 0;
        mask = *sprite++;
        for (bit = 7; bit >= 0; bit--) {
            if (mask & (1 << bit)) {
                pixel = *sprite;
                if (num_pixels & 1)
                    sprite++;
                else
                    pixel >>= 4;
                pixel &= 0xf;

                x = ((7 - bit) * 4) + plane;
                dst[((dst_y + y) * dst_width) + (dst_x + x)] = pixel;

                num_pixels++;
            }
        }
        if (num_pixels & 1)
            sprite++;
    }
}

While writing this blog post I found this sprite in the header for The Lost Vikings second level which uses the packed 32×32 format, however I don’t remember ever seeing it in the game. Does anybody know if it is a secret or an unused leftover asset? View it with:

./sprite_view DATA.DAT -l2 -fpacked32 0xec -b0x10

tlv_secret_guy

Why Multiple Sprite Formats?

This is a question I can’t fully answer. I am by no means an expert in the intricacies of optimized VGA programming. It’s possible that the different formats are used to improve rendering speed for sprites that need to be updated frequently vs infrequently. Tiles for the maps are always raw format. The raw format is also used for some HUD (head-up dislay) sprites. Sprites using the packed 32×32 format including the vikings and many enemies. The unpacked sprite format is used for some less animated enemies like the gun turret, and other objects like switches and elevators.

Blackthorne doesn’t appear to use the 32×32 packed format at all, probably due to the fact that many of Blackthorne’s sprites are larger than 32×32. Most of the highly animated sprites use the raw format. Blackthorne does not have scrolling levels (it is screen to screen like the original Prince of Persia), which will make rendering quicker.

One thing I don’t yet fully understand is how the Blizzard engine knows which sprite format and size to draw for each object. There is some information in the level headers which corresponds to this, but it isn’t enough to be able to draw all objects correctly. I suspect that parts of the rendering information are managed by the virtual machine.

Sprite Layouts

As mentioned previously, Blackthorne uses larger sprites than The Lost Vikings. Although an algorithm for rendering arbitrarily sized raw sprites can be written, the Blizzard engine takes a different approach. Larger sprites are rendered by composing multiple smaller sprites in a fixed layout. For example, the titular Blackthorne character uses 32×48 sprites, which consist of two 16×16 sprites for the head, and a single 32×32 sprite for the body:

bt_layout_guy

Note that the background colour used here is actually the index 0 colour for the Blackthorne sprites, which is used as the transparent colour in game. You can view the full set of the Blackthorne player sprites with:

./sprite_view --blackthorne DATA.DAT -fraw -w32 -h48 -l2 -b0x80 0x42

It possible that this approach was taken because Blizzard already had written optimized rendering loops for 16×16 and 32×32 sprites, making it faster to draw large sprites as set of smaller sprites rather than one large sprite.

Tilemap Levels

Both The Lost Vikings and Blackthorne are use tilemap levels with 16×16 tiles (though I think the art in both games does a really good job of making it look like this isn’t the case). The sprites used for the tiles are actually 8×8. Each tile has a structure, which I called a “prefab”, that details how a set of 8×8 sprites from a 16×16 tile. Each component piece can be vertically and/or horizontally flipped, allowing the component tiles to be reused.

For example in the full tileset for first level of The Lost Vikings you can see several tiles like the ladders which have mirrored versions, but also a number of tiles which reuse a single corner piece like the riveted blue panels.

tlv_level1_tileset.png

You can view this tileset with:

./tileset_view DATA.DAT 1

The pack file contains a chunk for each tileset describing the prefabs. Each prefab is 8-bytes long, with each tile encoded as a 16-bit value. For each 16-bit value, the sprite index is encoded as 10-bit value, with the remaining 6 bits used for flags. The flags indicate if the sprite is horizontally and/or vertically flipped, and whether this component of the tile is foreground or background. Encoding a foreground/background bit into the prefabs allows the Blizzard engine to use a single tile map to render both layers.

Blackthone extends the engine the prefabs in two ways. First the three unused flag bits are used as a colour base. The Lost Vikings only allocates 16 colours for all the map tiles. By adding the colour base bits Blackthorne is able to use 128 colours for the tiles, though each individual component sprite of the tiles is still limited to 16 colours.

Blackthorne also adds an additional background map layer. This allows the game to have more detailed backgrounds and skies against the jagged foreground tiles. For simplicitly I’ll refer to the secondary background layer as the sky layer, and the main tilemap as the foreground and background layers. The sky layer does not use the foreground/background flag bits, so can be considered as a single
layer.

The following image shows how the tilemap for the first level of Blackthorne is composited:

bt_level.png

You can view this with (note the level number 3 is used, because levels 1 and 2 are the intro cutscene and practice stage):

./level_view --blackthorne DATA.DAT 3

There are some interesting things to note here:

  • Some parts of the sky layer are completely obscured by the foreground layers. This might be due to Blizzard’s development process or tools.
  • The waterfalls are partially drawn on the sky layer and partially on the background. For example, in the bottom right corner, the base of the waterfall is drawn on the sky layer. This is because there is a rock covering the waterfall in the foreground layer. Because of the shape of the rock, this cannot be drawn on using a single map with correct foreground/background handling.
  • There are some areas of the map the appear to be missing. For example the waterfall in the upper middle abruptly ends. This is because Blackthorne uses static rooms instead of scrolling. The empty areas of the map are never visible when playing the game. On some levels this is quite wasteful as entire screens are unused. Blizzard probably chose to implement the screens on a single tilemap even though the game doesn’t scroll so that they could reuse existing code from The Lost Vikings engine.

Everything is a Level

One clever trick Blizzard has used is that almost everything in the game, splash screens, cutscenes, menus, is a level. This undoubtedly saved on development time. Because all the hard work of implementing code for game levels with animation and moving objects is already done, it makes sense to reuse that same code to handle cutscenes and menus. I believe the game engine also uses the virtual machine (see my previous blog post) to implement animation in the cutscene levels. One notable exception to this is The Lost Vikings splash screen at the beginning of this blog, which is encoded as a large, uncompressed raw sprite.

For example, when the game starts up a number of splash screens are shown. Two of these are encoded into a single level (as two rooms). The left of the image below shows the tileset for the level, while the right hand side shows the level itself. In the game, the silhoutte is shown first (which glows, more on this later). The Blackthorne logo is displayed above the main menu.

bt_splash.png

I’m not sure why there are two copies of the Blackthorne logo tiles. Note that they are slighly different colourisation. The TM is black and inside the logo in the top set, and white and outside the logo in the bottom set for example. The tileset may be reused for a different splash screen at the end of the game?

You can view the tileset and level for this splash screen with:

./tileset_view --blackthorne DATA.DAT 1 -c 0x6e 
./level_view --blackthorne DATA.DAT 1 -h0x6e

Palette Management

Earlier I talked about how sprites only use sixteen colours each, always encoding the values as 0x0 – 0xf. This is used to allow each level to define its own palette while allowing sprites to be reused across levels.

In The Lost Vikings there are several worlds including a space world, prehistoric world, and a wacky candy world. Each has its own colour scheme and enemies. The player controlled vikings only use two sixteen colour palette sets (Olaf and Baleog share a green and yellow colour scheme, Erik has a red and blue scheme). The HUD uses another sixteen colour set, and one is also used for items such as keys and health pickups that are used in all of the worlds. This leaves a sizable portion of the 256 colour palette to be defined by the level. Most of the levels load an 128 colour base palette, followed by a set of eight 16 colour palettes.

The per-level palettes also allow sprites to be reused with a different colour scheme. This was a popular trick in era of 8-bit colour and limited storage space. The Mortal Kombat games famously have a number of palette swapped ninja characters. The following image shows the same dinosaur sprites with the palette setting from two different levels:

tlv_dinosaur

To view the two different versions of the dinosaur sprite:

./sprite_view DATA.DAT -fpacked32 -b0xc0 -l5  0xf8
./sprite_view DATA.DAT -fpacked32 -b0xc0 -l10 0xf8

Note that the level number (-l) and base palette offset (-b) arguments are passed to the sprite viewer program. The level number is used to determine which palette chunks to load by parsing the level header chunk. The base palette index has been determined experimentally. Again, this is something I don’t fully understand in the Blizzard engine, and again I suspect that the base palette index may be specified by instructions in the object’s virtual machine program.

Palette Animations

Another popular trick from the DOS days is animating graphics by changing colours in the palette. Animating an object by redrawing the pixels is quite expensive, especially for something large than needs to be updated frequently like the background waterfalls in Blackthorne. Instead of modifying the pixels themselves it is much less expensive to modify colours in the palette, which is immediately updates all pixels of the corresponding colour. This technique is mostly useful for simple cyclical animations like waterfalls and the blinking lights in The Lost Vikings spaceship levels. As mentioned previosly, palette animations are used in Blackthorne to make the silhoutte glow in the startup splash screen.

The Blizzard engine implements palette animations in the level header. Each palette animator has a 8-bit speed value and two 8-bit colour index values. If the two indexes are not equal then the animation cycles the colour values between the two indexes. This format is good for animating things like the waterfalls and blinking lights which appear to move in a pattern.

If the two indexes are equal, then the palette animation is for a single colour and the level header specifies a list of 16-bit values for the animation. The 16-bit values each encode a colour value in RGB-555 format (meaning 5 bits per colour, so one bit wasted). The normal VGA palette, and the Blizzard engine is capable of 6 bits per colour. The palette animations lose the least significant bit by shifting each of the colour values left by one. This palette animation format is useful for animating something like a pulsing light.

You can press ‘A’ in the level viewer to show the palette animations.

Game Over

That’s all for now:

./level_view DATA.DAT 48
./level_view --blackthorne DATA.DAT 23

game_over.png

Advertisements

6 comments

    • ryiron

      Ah, I hadn’t thought of that. I don’t know much about the other DOS era platforms, and I’ve only reversed the DOS version of the games, so I don’t know if the sprite formats are the same across all platforms.

  1. inteluga

    The second logo of BlackThorne is different. Game was released as Blackhawk in some European countries.

    • ryiron

      Interesting. Good spotting. I knew about the alternative Blackhawk branding, but I didn’t notice that’s what the tiles spelled when looking at the tileset. I wonder why they included both sets of tiles in the data file. I can’t find (at a quick skim through) an alternative version of the level which displays the Blackhawk logo.

  2. Sven

    Hi Ryiron, this is an amazing article. You are like an archaeologist trying to recover lost treasures and cultural goods from an ancient kingdom, seriously.
    I have a question: I’m also currently trying to reverse engineer the Lost Vikings using my own pygame-based engine (github.com/sven1977/spygame). I’m doing this because I’m interested in reinforcement learning, meaning I would like to play around with AI algos that can solve the different levels (they are quite a hard problem still for AIs). I wasn’t able to compile your tools in Windows. I could spend some time on making this work, but would it be possible for you to provide the complete level tilesets (for each world) plus the level maps (tmx)?
    Thanks so much,
    Sven

    • ryiron

      Thanks for the kind words.

      I don’t want to provide any of the assets from the game because I don’t know what the full copyright status of them is. The tools are mostly provided for people who are curious about how the original games worked, or interested in attempting to mod the original games. I don’t know what legality of using assets from the games in new works is.

      I haven’t tried compiling the tools for Windows, but I think it should be possible without too much effort. SDL is available for Windows and I have attempted to write the code portably.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s