Tiles and Sprites: a Picture Processor
Why games don't draw pixels, how a tile map, a sprite table and a palette describe a whole screen in a few kilobytes, and the C that drives them.
In this article
What are we trying to do?
We can send any pixel to the monitor. Now a game wants to put a world on the screen and move things around in it, sixty times a second. The obvious way is a framebuffer: memory with one entry per pixel, which the CPU draws into. Let us count. 256 × 240 pixels at 12-bit colour is 90 KiB; the whole FPGA has about 58 KiB of block RAM. And even if it fit, our CPU at 6 million instructions a second could rewrite about 100,000 pixels per second, not 60 screens.
So we do what the consoles of the 1980s did: the CPU does not draw pixels. It describes the screen in tiles and sprites, and a small graphics chip, the PPU (picture processing unit), works out every pixel while the picture is being sent.
The idea
- Tiles are 8 × 8 pixel drawings, 4 bits per pixel (16 colours). There are 256 of them, stored once.
- The name table is a grid of tile numbers: which tile goes in each 8 × 8 cell of the background. Drawing a wall across the screen is 32 writes, not 2,048 pixels.
- Sprites are tiles that float on top, at any pixel position: the player, the ball, the aliens. A table of 64 of them (the OAM) holds each one's position, tile and colours.
- Palettes turn the 16 colour numbers into real colours, so the same tile can be red in one place and blue in another.
The PPU's header lays out the whole memory map:
8// Video memory (written by the CPU, write only):9// CHR 256 tiles of 8 x 8 pixels, 4 bits per pixel. Word tile*8+row10// holds one tile row; pixel k (0 = left) is in bits 4k+3..4k.11// NAMETAB 64 x 32 tile map (two screens wide), word row*64+col:12// bits 7:0 tile, 9:8 palette, 10 flip horizontally, 11 vertically13// OAM 64 sprites, one word each:14// bits 7:0 y (top line; 240..255 is off screen), 16:8 x (9-bit15// two's complement, -256..255), 24:17 tile, 26:25 palette,16// 27 flip horizontally, 28 vertically, 29 16 x 16 (tiles t, t+1,17// t+16, t+17), 30 behind the background18// PALETTE 128 colours, 12-bit 0xRGB: 0..63 background palettes 0..3 (1619// colours each), 64..127 sprite palettes 0..3. Colour 0 of a20// tile is transparent; where every layer is transparent, entry21// 0 (the backdrop) shows.Count it up: tiles 8 KiB, name table 8 KiB, sprites 256 bytes, palettes 256 bytes. A full, scrollable game screen in about 16 KiB, all of it in block RAM inside the PPU.
The registers
26// Registers and memory, byte offsets:27// 0x0000 CTRL bit 0 background on, bit 1 sprites on, bit 2 text28// terminal overlay on (reset: 0b100)29// 0x0004 SCROLL_X bits 8:0, scroll position in the 512-pixel-wide map30// 0x0008 SCROLL_Y bits 7:0, in the 256-pixel-high map31// 0x000C SPLIT bits 7:0, first scrolled line32// 0x0010 STATUS read only: bit 0 vertical blank, bits 31:16 frame count33// 0x0400 PALETTE 128 words34// 0x0800 OAM 64 words35// 0x2000 NAMETAB 2048 words36// 0x4000 CHR 2048 wordsCTRL turns the layers on: background, sprites, and the text terminal from part 9. SCROLL_X and SCROLL_Y move the background, which is twice as wide as the screen (64 tiles), so a game can scroll smoothly by redrawing one column at a time just off screen. SPLIT keeps the top lines still, for a score bar that does not scroll with the world. STATUS is the one register the CPU reads: it says whether the beam is in vertical blanking, and counts frames.
Drawing a line
The PPU's picture is 256 × 240, shown at double size in the middle of the 640 × 480 output. That doubling is the trick that makes it possible:
37//38// Rendering: picture line n is drawn into one half of a line buffer while39// line n-1 is shown from the other half, i.e. during output lines 2n-2 and40// 2n-1 (1600 clock cycles; a line with 16 wide sprites takes about 820).Each picture line is shown on two output lines, which gives the PPU 1,600 clock cycles to build it. It draws line n into one half of a line buffer while the other half, line n−1, is on screen. For each pixel it looks up the name table entry, then the tile row, then picks the 4-bit colour; then it goes through the sprites on that line, front to back, and the first non-transparent one wins.
CTRL bits and a sprite's "behind" flag, and watch the priority between backdrop, tiles, sprites and the terminal.Driving it from C
The games use a small library, fw/sdk/ngame.c, so they talk about tiles and sprites rather than register offsets. Under it is one function per register access, from game_hal.h:
static inline void hal_ppu_write(uint32_t offset, uint32_t value){ PPU_REG(offset) = value;}Starting a game loads its tiles and palette into the PPU:
87void ng_begin(const uint32_t *chr, int tiles, const uint16_t *palette)88{89 hal_ppu_write(PPU_CTRL, 0);90 hal_ppu_write(PPU_SPLIT, 0);91 hal_ppu_write(PPU_SCROLL_X, 0);92 hal_ppu_write(PPU_SCROLL_Y, 0);93 scroll_x = scroll_y = 0;94 for (int i = 0; i < tiles * 8; i++)95 hal_ppu_write(PPU_CHR + i * 4, chr[i]);96 for (int i = 0; i < 128; i++)97 hal_ppu_write(PPU_PALETTE + i * 4, palette[i]);98 for (int i = 0; i < 64; i++)99 hal_ppu_write(PPU_OAM + i * 4, OAM_HIDDEN);100 n_sprites = shown_sprites = 0;101 ng_clear();Every tile row is one 32-bit word (eight 4-bit pixels), so a tile is eight writes. All 64 sprites start hidden: a sprite's y of 240 or more is below the picture.
ng_begin writes to the PPU.Putting a tile on the background is one write to the name table:
139void ng_tile(int col, int row, int tile, int pal)140{141 hal_ppu_write(PPU_NAMETAB + (((row & 31) << 6) + (col & 63)) * 4, tile | pal << 8);142}The entry index is row * 64 + col, and the value is the tile number with the palette in bits 9:8. A rectangle of tiles is two loops:
144void ng_fill(int col, int row, int w, int h, int tile, int pal)145{146 for (int r = row; r < row + h; r++)147 for (int c = col; c < col + w; c++)148 ng_tile(c, r, tile, pal);149}Sprites are different: a game sets them every frame (things move), so ng_sprite only collects them in an array:
228void ng_sprite(int x, int y, int tile, int pal, int flags)229{230 if (n_sprites == 64 || y <= -16 || y >= 240 || x <= -16 || x >= 256)231 return;232 if (y < 0) // the PPU cannot place a sprite above the screen233 return;234 oam[n_sprites++] = OAM_ENTRY(y, x, tile, pal, flags & NG_HFLIP ? 1 : 0,235 flags & NG_VFLIP ? 1 : 0, flags & NG_BIG ? 1 : 0,236 flags & NG_BEHIND ? 1 : 0);237}OAM_ENTRY packs position, tile, palette and the flip and size flags into the 32-bit format from the header. The array is copied to the PPU once per frame, at the right moment.
The right moment: vertical blank
If the CPU changes the sprite table while the PPU is drawing them, a sprite can be half at its old place and half at its new one: tearing. So games wait for the frame to end, then update. ng_frame() does it:
109void ng_frame(void)110{111 uint32_t busy = hal_cycles() - frame_start;112 if (busy > slowest)113 slowest = busy;114 115 uint32_t f = hal_ppu_read(PPU_STATUS) >> 16;116 while ((hal_ppu_read(PPU_STATUS) >> 16) == f)117 if (idle_fn)118 idle_fn();119 frame_start = hal_cycles();120 frames++;121 122 for (int i = 0; i < n_sprites; i++)123 hal_ppu_write(PPU_OAM + i * 4, oam[i]);It reads the frame counter from STATUS, waits until it changes (a new frame has begun), then writes all sprites. Before that it measures how many cycles the game spent on this frame, which is how we know whether a game is fast enough: a frame is about 420,000 cycles, the number from part 9.
So a game's main loop is always the same shape:
for (;;) { read the buttons move things, check collisions ng_tile(...) for whatever changed in the background ng_sprite(...) for every moving object ng_frame(); // wait for the next frame, then show the sprites}Conclusion
A tile engine turns 90 KiB of pixels into 16 KiB of description, and moves the work of drawing from the CPU to dedicated hardware that does it in step with the video. The CPU only says what changed.
We have everything a game needs now: a CPU, storage, buttons through the UART, and a screen. In the next article we read a whole game, Snake, from the title screen to game over.