The NandTier SeriesPart 10 of 12

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.

9 min readGraphicsPPUVideo
In this article
  1. What are we trying to do?
  2. The idea
  3. The registers
  4. Drawing a line
  5. Driving it from C
  6. The right moment: vertical blank
  7. Conclusion

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

text terminalUART bytes, on topsprites64 · any pixel positionbackgroundtiles from the name tablebackdroppalette entry 0the screen256 × 240, shown at 2×colour 0 is see-through,so lower layers show
The PPU stacks four layers into one picture.

The PPU's header lays out the whole memory map:

hw/video/nt_ppu.vlines 8–21
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

hw/video/nt_ppu.vlines 26–36
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 words

CTRL 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:

hw/video/nt_ppu.vlines 37–40
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.

InteractiveFlip the 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:

fw/sdk/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:

fw/sdk/ngame.clines 87–101
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.

0001100000122100012332101233332112333321012332100012210000011000one tile: 8 × 8 pixels, 4 bits eachrow 3 in CHR memory, one 32-bit word:0x12333321pixel 0 is the lowest 4 bitsthe numbers are palette entries,so one tile can be any 15 colours
A tile is eight words. Each number is a palette entry; 0 is transparent.
InteractivePaint a tile and read the CHR words it becomes, exactly what ng_begin writes to the PPU.

Putting a tile on the background is one write to the name table:

fw/sdk/ngame.clines 139–142
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:

fw/sdk/ngame.clines 144–149
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:

fw/sdk/ngame.clines 228–237
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:

fw/sdk/ngame.clines 109–123
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:

a game's main loop
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}
InteractiveVideo memory recorded from the real games, in 3D: the tile map, the sprite table and the palettes stacked into the picture, sprites moving frame by frame.

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.