JCAP Log #8: Video Part 3
Knowing how to vomit pixels to a screen is only one side of the video generation coin. Equally important is how that data gets on the wire in the first place. At a glance it wouldn't appear to be a problem at all: you have pixel data, so just iterate through it and push it to the video generator, refreshing every 1/60th of a second. Right? Let's find out.
The most obvious and straightforward method of storing video data is the bitmap: a contiguous region of memory with sequentially stored 1:1 sections of pixel data.
Basic Bitmapping Schema
Just generate the bitmap between frames, then spit it out; easy to store, easy to index, easy to output. Decision made! Now let's just set aside some RAM to store it! So: (640 x 480 pixels) x 1 byte per pixel = 307,200 bytes, or 300 kB! That's 1000% the size of our available hub RAM, which also has to contain game and system code as well as all the other graphics resources! The only workaround would be attaching some external SRAM, which would have to be a slow serial connection due to the requisite address and data pins and would greatly increase physical complexity and unit cost of the final board, among other drawbacks and constraints. This precludes the use of pure bitmapping to manage our graphics.
Fortunately, the solution to this problem goes back to the first arcade games in the mid 1970s. The basic concept is that a lot of the graphics in early 2D arcade and console games were repetitive; platforms and other environment features were built from the same smaller elements to generate more complex structures. Thus, a basic form of compression could be used to generate the game graphics from a palette of these frequently used elements.
Zelda Tile Map
The underlying concept of the tile-mapped system is basically splitting the screen into fewer discrete areas of pixels, called tiles, and referencing those areas to a palette which represents the visual details of the tiles themselves. The screen area can feasibly be broken down into any dimensioned tiles, but the most common are 8x8 and 16x16 pixels. This means that a screen size of 640x480 broken down into 8x8 tiles will turn into a 80x60 tile screen, represented by a 80x60 tile map. Each tile can then be pointed at a tile in the tile palette which is rendered in that position by the graphics engine. This introduces the first major components of the tile map system: the tile map, tile palette map, and tile color palette map.
Tile Mapping Example
By referencing fewer screen locations (i.e. tiles) with repetitive reference data (i.e. tile palettes and color palettes) we drastically reduce our graphics resources memory footprint. If we represent each tile in the tile map by one 16-bit word, and use 1 byte to index the tile palette and 1 byte to index the color palette, we can address 2^8 or 256 tiles in the tile palette and the same for the color palette while only using 60x80x2≈9.5kB of memory for the tile map (not taking into account the size of the palettes yet). That's not bad compared to bitmapping, considering a major element of tile mapping is using fewer tile elements repetitively to build more complex graphics. We'll actually decrease this footprint by a further factor of 4 by using upscaling in the next log.
Tile Map Entry
For the entries in the tile palette map, each tile's pixels are represented by 4 bits, meaning that each pixel can be colored by 2^4=16 possible colors. This results in tile palette map entries that are (for 8x8 pixel tiles) 8x8x4=256 bits, or 32 bytes each. The colors for each pixel are determined by taking the tile color palette index from the tile map entry and addressing that palette using the color index specified by the pixel in the tile palette map. For example, the top left tile of the screen could have a tile palette index of 2 and a color palette index of 5. To render this tile, the graphics engine will look at the 3rd palette in the tile palette map (hey are zero-indexed), then iterate through the 4-bit pixels in the palette. It will use each 4-bit pixel entry to choose one of 16 colors from the 6th color palette in the color palette map. These will be the colors displayed on the screen.
Tile Color Palette Map Example (using 4 instead of 16 colors per palette)
That's a lot of indirection, somewhat convoluted, and requires a lot of processing in real time. But the amount of memory we save is more than worth the effort. Assuming we need all 256 color palettes (extremely unlikely), all 256 tile palettes (very unlikely), and a single tile map, we would still only be consuming less than 15 kB of memory!
Tiles are great at reducing our memory footprint while still giving us a large amount of flexibility, but they come with their own constraints. The most obvious is that tiles can only be defined on the 8x8 pixel grid boundary. So you can't, for example, have a tile half in one tile map entry and half in another. This means that any dynamicism of tiles you want to implement have to be in units of 8 pixels horizontally or vertically, making for choppy movement. You can work around this by having multiple tiles in the tile palette map representing intermediate states of the tile transitioning between cells of the tile map, but the game logic to implement this can become dense and the amount of tile palette entries commensurately so. Enter sprites.
Example Sprite Map
A sprite is a visual graphic element that is unbound by the tile map grid, i.e. it can be located at any discrete pixel coordinates. It also allows for effects such as transparency, mirroring, scaling, and more. Sprites can move freely around the game area and are usually used for player characters, enemies, and environmental elements which require more complex animation. The implementation of sprites is almost identical to that of tiles, with a palette of sprites and a palette of sprite colors (in some cases, the tile's palettes and colors are used for sprites as well). The only difference is how the positions and behavior of the sprites are defined. Instead of a tile map, we use a sprite attribute table (SAT).
Example Sprite Attribute Table
The SAT is simply an array of LONG-sized (32-bit) entries, each entry representing one sprite. Each entry contains information on the sprite palette, sprite color palette, position, mirroring attributes, and others. During display, the graphics system iterates through the SAT and renders each sprite based on its attributes. Characteristics such as z-indexing (what sprites are in front of others) can be defined using bits of the SAT or can simply be based on the order the sprites appear in the table. Besides the effects such as mirroring and determining visibility, the sprites are ultimately processed in the exact same way as the tiles.
The sprite and tile system is a classic, tried and true method for supporting robust graphics while minimizing memory overhead. While constraints are introduced by the paradigm, they are necessary and relatively insignificant compared to the results yielded. Leveraging this system, we'll be able to hit the optimum 640x480 resolution target without blowing out our hub RAM. The only thing left to do is implement it.