Bedlam

Boulderdash was one of my favourite games growing up, and it has been my go-to game to implement on a new platform, with its tile-based rendering, smooth scrolling and game arena update rules.

I've released an up-to-date version of this game as Rocks Off, with professionally produced artwork and music, and a full game editor.

I first wrote this in assembly language on MS-DOS on a 486 at 25MHz, which is just about performant enough for full-screen redraws on every frame.

The game

You control a character who, for whatever reason, is in a mine and has to dig through earth collecting diamonds and dealing with rocks that fall. There are also monsters, which follow around the edge of any open space and explode on contact.

The game is tile-based and takes place on a 64x64 grid. Each different entity has its own rules for how it acts: the diamonds and the rocks fall, and the monsters follow around the edges of the empty space, with the action ticking along at around 18 moves per second.

	Entity	What it does
	Man	You. Arrow keys move you through earth and empty space, and Ctrl with an arrow clears the square next to you without moving.
	Earth	Dig through it. It holds everything up, so digging underneath a rock is risky.
	Diamond	Collect them for points. Each level needs a certain number. They fall and roll like rocks.
	Rock	Falls into empty space and rolls off other rocks, diamonds and walls. A falling rock will crush you. You can push one sideways into an empty space.
	Bat	Flies round the edges of open space. Touch it and it explodes, which kills you but leaves diamonds behind. Drop a rock on it for the diamonds without the danger.
	Spirit	Follows the edges the other way round. It explodes when it touches you too, but leaves nothing behind.
	Wall	Stops everything, but explosions break through it.
	Solid wall	Can't be broken, so it makes the edges of each level.
	Explosion	Clears the 3x3 squares around it, except solid walls and the door.
	Start	Where you appear at the beginning of a level, after a short countdown.
	Door	The exit, which comes alive once you have collected enough diamonds. You can't go through it yet in this version.
	Magic wall	Not working yet in this version.
	Mould	Not growing yet in this version, but monsters explode next to it.

Sprites

The sprites are packed into a single 320x200 image, drawn in Deluxe Paint:

The sheet holds 128 sprites in 16 columns of 8, so sprite n is in column n/8, row n mod 8. Colour 0 is transparent.

Levels

The levels are spread across two 320x200 images: they're up to 64x64, so we can fit eight in each. Each level is a picture with one pixel per square, drawn in Deluxe Paint with a palette where each tile type has its own colour. The colour number of a pixel is the tile type, so drawing a level is just painting.

The colour becomes the top nybble of each arena byte, and the state is filled in when the pictures are converted (see the data import script). A table in the game code gives each level its size, its start position, its time limit, the diamonds needed and the points per diamond:

		;    A    B    C    D    E    F    G    H.
		;    I    J    K    L    M    N    O    P.
_level_width_	db  35,  58,  44,  41,  33,  64,  64,  20
		db  51,  38,  64,  32,  43,  26, 207,  42

_level_time_	db 180, 150, 210, 120, 120, 240, 240,  10
		db 150, 240,  -1, 200, 150, 120, 240, 240

_level_dias_	db  20,  36,  36,  20,   6,  24,  18,   5
		db  80,  90,  50,   9,  60,  40,  76,  33

Rendering

Each tick draws a complete frame into the back buffer in the order a painter would: background, squares, status line, and the map if right Shift is held. Then it's copied to the screen in one go.

The background is a 32x32 tile repeated across the screen. When the view scrolls by a square, the tile is rolled by one pixel in the same direction, so the background drifts slowly behind the level while the level moves sixteen pixels at a time.

The view is 20x12 squares, 320x192 pixels. Every square is drawn with its sprite's mask, which clears the pixels the sprite covers, and then the sprite's pixels are XORed into the hole. Space is drawn like any other sprite, so wherever it's clear the background shows through:

blit_loop:
    ;  AND mask.
  mov eax, [si+32000]
  mov ebx, [si+32004]
  and es: [di], eax
  and es: [di+4], ebx
  mov eax, [si+32008]
  mov ebx, [si+32012]
  and es: [di+8], eax
  and es: [di+12], ebx
    ;  XOR mask.
  mov eax, [si]
  mov ebx, [si+4]
  xor es: [di], eax
  xor es: [di+4], ebx
  mov eax, [si+8]
  mov ebx, [si+12]
  xor es: [di+8], eax
  xor es: [di+12], ebx

  add si, 16
  add di, 320
  loop blit_loop

The bottom eight rows hold the status line: points per diamond, diamonds still needed, the score and the time. When you're dead or out of time it flashes with GAME OVER or TIME OUT. Right Shift draws the whole 64x64 level as dots in the bottom right corner.

The view follows the man with some slack. It doesn't move while he's in the middle of the screen, and when he gets near an edge it picks a new target and scrolls towards it one square per tick.

When the frame is finished, it waits for the vertical retrace and copies all 64,000 bytes to the screen at once, so there's no tearing and nothing half-drawn is ever seen:

  mov dx, 3DAh
update_vrt:
  in al, dx
  test al, 8
  jz update_vrt

  ...

  mov ds, _scr_seg
  mov es, _graph_seg
  xor esi, esi
  xor edi, edi
  mov ecx, 16000
  cld
  rep movsd

The dissolve at the start and end of each go uses the same drawing code. When a game starts, the 240 squares of the view are given a shuffled order, and during the dissolve a square shows the level only if its place in that order is below a counter that goes up by five each tick. Everything else shows a flashing block.

Sprites and levels

Each sprite sits at nx256 in the sprite segment. At load time a mask is built for every sprite, with FFh where the sprite is clear and 0 where it isn't, which is what the drawing code ANDs with.

The game never works out which sprite to draw. A 256-byte table maps every possible arena byte (see The arena) straight to a sprite number, so drawing a square is one lookup:

_sprite_table	dd 01010100h,01010101h,01010101h,01010101h	;  Space.
		dd 0B0A0908h,0F0E0D0Ch,0B0A0908h,0F0E0D0Ch	;  Earth.
		dd 40404040h,40404040H,40404040h,40404040h	;  Diamond.
		dd 4B4B4B4Bh,4F4E4D4Ch,4F4E4D4Ch,4F4E4D4Ch	;  Newdia.
		dd 10101010h,10101010h,10101010h,10101010h	;  Bat.

Animation is done by changing the table rather than the level. Each tick, a routine called game_rotate steps the diamond row through sprites 40h to 4Ah, and the bat, spirit, magic wall and rotating-solid rows through their eight frames. Every diamond in the level sparkles at once, and the level itself never has to be touched.

The view is a 20x12 window onto the 64x64 arena. The level's size from its settings table, with its minimum x and y, stops the view scrolling past the edges of the level, so the unused part of the arena around a smaller level is never shown.

The player character

The man only has six standing frames:

50h is him facing you, 51h to 53h turn his head right round, and 54h and 55h move a foot. What makes him look alive is the order they're played in, which is a list of bytes in the code, one per tick:

_game_man_anim	db 36 dup (50h), 51h, 52h, 53h, 52h, 51h
		db 4 dup (50h, 50h, 54h, 54h), 9 dup (55h)
		db 6 dup (50h), 4 dup (55h)
		db 4 dup (50h, 50h, 54h, 54h), 51h, 52h, 53h, 52h, 51h, 50h
		db -1

That's two seconds of standing still, a look round, some foot tapping, and another look round, about five and a half seconds in all. Each tick game_rotate takes the next byte and writes it into the sprite table at F0h, the entry for a standing man, and when it reaches -1 it goes back to the start:

  mov bx, _game_man_frame
  mov al, cs: [bx]
  inc bx
  cmp al, -1
  jne game_rotate_manok
  mov bx, offset cs: _game_man_anim
  mov al, cs: [bx]
game_rotate_manok:
  mov _game_man_frame, bx
  mov byte ptr _sprite_table[0F0h], al

Every time he moves, the pointer is put back to the start of the list, so he only starts fidgeting after two seconds of being left alone.

Walking works the same way with a second entry. While an arrow is held his byte is F1h instead of F0h, and the F1h entry steps through one of two short lists, depending on the last way he went left or right:

_move_man_left	db 58h, 59h, 5Ah, 5Bh, 5Ch, 5Dh, 5Bh, 5Ah, 59h, -1
_move_man_right	db 60h, 61h, 62h, 63h, 64h, 65h, 64h, 63h, 62h, -1

Going up or down keeps whichever cycle he was last using, so he carries on facing the way he was going. There is no vertical running animation: we just use either the left or right running when moving vertically.

The game loop

The game moves on one tick at a time, 18.2 times a second, driven by the timer interrupt. Each tick does the same things in the same order:

1. Every eighteenth tick, a second comes off the level's time limit.
2. The rules are run for every square of the level.
3. The frame is rendered into the back buffer.
4. If the last diamond needed has just been collected, the frame is filled with white for a flash.
5. The status line is drawn, or GAME OVER or TIME OUT if the man has gone, when Space starts the go again.
6. If right Shift is held, the map is drawn on top.
7. After the vertical retrace, the frame is copied to the screen.

Game state

Everything the game changes as it runs is in a handful of variables, from which routine the timer is running down to the arena and the sprites:

All the _level_ variables are copied from the per-level table each time a go starts, so the time and the diamond count start afresh. There's also a _pause byte, which nothing uses yet.

The arena

The arena is a 64x64 grid packed into 4,096 bytes, with each byte representing one tile on the map. In each byte the top 4 bits are which entity it is, and the bottom 4 bits are an entity-dependent state:

	Entity	Top nybble	State bits
	space	0	unused
	earth	1	which of 8 earth sprites, picked at random
	diamond	2	bit 3: falling
	newdia	3	animation step, before it becomes a diamond
	bat	4	the direction it's facing, 0 to 3
	spirit	5	the direction it's facing, 0 to 3
	rock	6	bits 0-2: which rock sprite, bit 3: falling
	wall	7	0-7 a plain wall, 8-15 a decorated one
	magic	8	unused
	bang	9	bits 0-1: animation step, Ch: becomes the man
	mould	A	unused
	solid	B	unused
	door	C	animation step, once the level is done
	rsolid	D	unused, it's animated through the sprite table
	start	E	countdown, 0 to 15
	man	F	0 standing, 1 walking

The grid is always 64 bytes a row, so the squares around offset s are s-1, s+1, s-64 and s+64, and moving something is just copying a byte from one offset to another. Most levels don't use the whole area.

Each level is played from a copy. When a level starts, its 4,096 bytes are copied out of the level data into the arena, so starting again always starts from the original.

The rules

Each tile type has one rule, run once per tick for every square of that type:

	Type	Rule
	space, earth, wall	nothing
	diamond, rock	fall into space below, slip sideways off rocks, diamonds, walls and mould
	newdia	turn into a diamond
	bat	keep the wall on the left, explode into diamonds next to the man or mould
	spirit	keep the wall on the right, explode next to the man or mould
	bang	count 0 to 3, then turn into space
	start	count 16 ticks, then explode into the man
	door	animate once every diamond needed has been collected
	man	move with the arrow keys
	magic, mould	nothing yet
	solid, rsolid	nothing, and they survive explosions

Each tick, game_move walks the level once, left to right and top to bottom, and jumps to the rule for whatever type is in each square. The type is just the top nybble, so the dispatch is a chain of compares:

  mov al, _level[si]

  cmp al, 10h
  jb move_space_
  cmp al, 20h
  jb move_earth_
  cmp al, 30h
  jb move_diamond_

  ...

Scanning from the top has a catch. A rock that falls moves into the row below, which the scan hasn't reached yet, so without care it would be moved again and fall the whole height of the screen in one tick. Scanning from the bottom up would fix that for falling, but not for a bat moving down or right. So there's a second 64x64 array, _level_flags, cleared at the start of each tick, and anything that moves marks the square it moved into. The scan skips marked squares, so everything moves at most once per tick whichever way it goes.

Things that fall

Rocks and diamonds share one routine. If the square below is empty, it falls. If it's sitting on a rock, a diamond, a wall or mould, it slips off to the right if both the square to the right and the one below that are empty, otherwise to the left. Bit 3 of the state remembers that it's falling, and only a falling rock does damage: landing on a bat turns the 3x3 squares round the bat into diamonds, and landing on a spirit or on you makes an explosion.

    ;  Is there a gap below?
  test _level[si+64], 0F0h
  jnz move_rock_nofall

  lea di, [si+64]
  jmp move_rock_move

Things that follow walls

Bats and spirits are wall followers, and their state nybble is the direction they're facing. A bat first checks to its left: if that's empty it turns and goes that way. If not, it goes forward if it can, and if it can't it turns right. That keeps a hand on the wall all the way round any shape. A spirit does the same with the directions mirrored, so it keeps the wall on its right.

_bat_dir	dw 64, 1, -64, -1, 64, 1, -64, -1

  ...

    ;  Is there anything to it's left (relative to it's direction)?
  mov di, si
  add di, _bat_dir[bx+6]
  test _level[di], 0F0h
  jnz move_bat_notleft

After moving, each one looks at its four neighbours, and if you or some mould is next to it, it goes off: a bat explodes into a 3x3 block of diamonds, a spirit into a 3x3 explosion.

You

The man can step into space, earth or a diamond, which is anything with a byte below 30h. Holding Ctrl turns the move into a grab: the square next to you becomes an explosion and you stay where you are. Collecting a diamond adds the level's points and counts one off the diamonds needed. A rock can be pushed left or right if the square beyond it is empty, but only on one tick in sixteen, so pushing feels heavy.

Explosions, the start and the door

An explosion is type 9 with its state counting 0 to 3, and then it turns to space. It's made by writing it into the 3x3 squares round a point, skipping solid walls, rsolid and the door, so the edges of a level always hold. The start square counts through its sixteen states, then turns into a special explosion, 9Ch, which becomes the man when it finishes. When the last diamond is collected the screen flashes white and the door starts to animate.

Not finished

This is version 0.7, and some rules weren't written. Magic walls and mould have sprites and colours but their routine is:

;  Characters not yet programmed.

move_magic:
move_mould:
  jmp game_move_ok

The man can't walk into the door yet either, since it's above 30h, so a level ends when the time runs out. And the new-diamond animation starts with an instruction that turns it straight into a diamond, so the rest of the routine never runs.

The intro screen

The intro has a background, a big BEDLAM made of blocks, and a sine wave:

None of it is in the .BED file. The blocks and the background were drawn in one picture, and a second C program, BEDINTRO, read it and wrote them out as assembler data, along with the sine wave:

BEDINTRO reads the 48 blocks from the 96x128 area on the left, 6 across and 8 down, and the background from the 100x100 square beside them. The second copy of the blocks on the right and the blue checks aren't read.

The background is a 100x100 picture in four shades of grey, packed four pixels to a byte, 2,500 bytes. At start-up it's unpacked into the intro segment and drawn tiled across the screen. Each frame shifts every row of it one pixel to the left, wrapping the first pixel round to the end, so it scrolls.

The title isn't a picture. It's a map of 64 columns by 9 rows, where each byte is one of 48 blocks of 16x16 pixels: straight pieces, corners, and the curves of the B and D. Twenty columns fit on the screen, and the map scrolls sideways two pixels a frame, wrapping round:

		  ;               B                          E                          D                          L                          A                          M

_intro_title	db 0, 0, 0, 0, 0, 1, 4,11,11,11,22,23,24, 0, 1, 4,11,11,11,17, 0, 0, 0, 1, 4,11,11,11,22,23,24, 0, 1, 3, 0, 0, 0, 0, 0, 0, 0, 1, 4,11,11,11,22,23,24, 0,19,20,21,23,24, 0, 0, 0, 0, 0, 0, 0, 0, 0
		db 0, 0, 0, 0, 0, 7, 9, 0, 0, 0,28,29,30, 0, 7, 9, 0, 0, 0, 0, 0, 0, 0, 7, 9, 0, 0, 0,28,29,30, 0, 7, 9, 0, 0, 0, 0, 0, 0, 0, 7, 9, 0, 0, 0,28,29,30, 0,25,26,27,29,43,22,23,24, 0, 0, 0, 0, 0, 0

Blocks are drawn whole, even when they hang off the side of the screen, and because the screen is one long run of bytes, whatever hangs off one edge wraps round onto the other. So at the end of each frame a strip ten pixels wide is cleared down each edge. That's the black border in the screenshot, and it hides the blocks sliding in and out.

Blocks 1 to 18 are square and are copied in solid. The rest have curved edges, and are drawn like sprites, with a mask. Every block casts a shadow down and to the right, and the shadow is done by adding one to the colour of each pixel underneath. The background uses colours from a ramp of greys where each step is a little darker, so adding one darkens whatever is there without any lookup.

The whole title also bobs up and down. BEDINTRO worked out a table of 157 screen offsets on a sine wave, and each frame the title is drawn starting at the next one:

for(i = 0; i < 157; i ++)
  fprintf(out, "  dw %d\n", 320*((int)(26+20*sin(2*i*M_PI/157))));

Storing the offset rather than the row means drawing the title needs no multiply: the offset is added to the start of the screen and the blocks are drawn from there.

Unlike the game, the intro doesn't run from the timer. Its loop calls the frame routine directly, and the wait for the vertical retrace before each copy to the screen paces it at the monitor's refresh rate, which is smoother than 18 frames a second. Space starts the game and Esc goes back to DOS.

The executable

The game is made up of an executable, BEDLAM.EXE, which is assembled with Turbo Assembler from the assembly source, and a data file, BEDLAM.BED, which contains the levels and the sprite sheet, along with the palette.

BEDLAM.BED, 99,072 bytes

offset    size      contents
0         768       palette: 256 colours x 3 bytes, 6-bit VGA values
768       32,768    sprites: 128 sprites of 16x16 pixels, 256 bytes each
33,536    65,536    levels: 16 levels of 64x64 bytes, 4,096 bytes each

A standalone C program, MAKEBED, converts the sprite and level images into this byte-packed data file, which the executable reads on start-up.

There is also an intro animation, with large lettering made out of a set of tiles, and the tile images and the tilemap are baked directly into the assembly source as data statements. Those statements were written out by a second C program, BEDINTRO, which is covered with the intro screen. The executable also carries the font for the status line and the table of level settings, and comes to 41,883 bytes.

Memory map

Everything lives in real-mode segments of 64k. When it starts, Bedlam shrinks its own memory block down to the size of the program with int 21h function 4Ah, and then asks DOS for 202k with function 48h. That block is cut into four pieces:

A000:0000   VGA memory, 320x200, 64,000 bytes
B800:0000   text screen, only used for the start-up log

program     code, tables, the working copy of the level (4,096 bytes),
            its moved flags (4,096 bytes) and an 8k stack

allocated block, 3280h paragraphs:
  +0k       _scr_seg      the back buffer the screen is drawn into
  +64k      _sprite_seg   sprites at 0-32,767, masks from 32,000
  +128k     _level_seg    the 16 levels as loaded from BEDLAM.BED
  +192k     _intro_seg    the intro background, 102x100 bytes

The top half of the sprite segment is scratch space. When a game starts it fills it with a transparency mask for every sprite, and the intro screen overwrites it with masks and shadows for its own graphics, so each one rebuilds it when it starts. The game's masks begin at 32,000 rather than 32,768, so they overwrite the last three sprite slots, which nothing uses.

Starting up

Before anything appears on screen, Bedlam switches to 80x50 text mode and prints a log of what it's doing: the segment it was loaded at, the size it shrank to, where each buffer went, and the old and new address of each interrupt it hooks. Then it waits for a key, so the log can be read. Esc at that point quits without changing anything.

The data file is read with plain DOS calls: 768 bytes of palette, 32k of sprites, and the levels in two reads of 32k. The interrupt hooks are made with the DOS get and set vector functions:

  mov ax, 351Ch
  int 21h
  mov _int1C_off, bx
  mov _int1C_seg, es

  ...

  mov ax, 251Ch
  mov dx, offset cs: timer
  mov ds, _code_seg
  int 21h

Then it switches to mode 13h, sets the palette from the file and clears the back buffer. A letter after the program name picks the level, so BEDLAM D starts on level D. When it quits, it frees the memory, puts both vectors back and returns to text mode.

The timer interrupt

The whole game runs inside the timer interrupt. Int 1Ch is called by the BIOS 18.2 times a second, and Bedlam's handler calls whatever routine _timer_proc points at: the start of a level, a frame of play, or the dissolve at the end of a go. The main program just sits in a loop waiting for Esc.

timer:
  cmp _timer_in, 0
  jne timer_end

  mov _timer_in, 1
  push bx

  mov bx, _timer_proc
  sub cs: _random, bx
  rol cs: _random, 3
  cmp word ptr cs: [bx], 9090h
  jne timer_noproc

  call bx

  ...

timer_end:
  push _int1C_seg
  push _int1C_off
  retf

Three small things make this safe. _timer_in stops the handler running again if a frame takes longer than a tick. Every timer routine starts with two NOPs, and the handler only calls the address if it finds 9090h there. And it finishes by jumping to the original handler, by pushing its address and doing a far return, so the BIOS clock keeps time. Both handlers also stir a small random number generator each time they run.

The keyboard interrupt

The BIOS keyboard handler is replaced completely. Bedlam's int 09h handler reads the scan code from port 60h and keeps a table of 128 bytes, one per key: FFh while the key is down, 0 when it's released. It never passes the key on to the BIOS, so there's no typeahead buffer to fill up and no beep.

  in al, 60h
  xor bh, bh
  mov bl, al
  test al, 80h
  jz kbd_press

    ;  Key released.
  and bl, 7Fh
  mov _kbd_keys[bx], 0
  jmp kbd_after

kbd_press:

    ;  Key pressed.
  mov _kbd_keys[bx], -1

It's a table of which keys are held right now, not a record of presses: nothing in the game writes to it, and only a release clears a key. Each tick reads the state of the arrows, Ctrl, Space, right Shift and Esc, several can be held at once, and the man keeps moving one square a tick for as long as an arrow is down. The catch is that a key pressed and released entirely between two ticks is never seen, but a tick is 55 milliseconds, which is shorter than a normal key press.

Data import script

MAKEBED reads the images as 320x200 BMP files. It switches to mode 13h, loads each one straight into video memory so you can watch, and then reads the pixels back out in the order the game wants them, inverting each one on screen as it goes to show its progress.

The sprite sheet is read a column at a time. Each column is 16 pixels wide and 128 tall, which is eight sprites one above the other, so writing a column row by row gives eight complete sprites of 256 bytes, one after another:

for(k = 0; k < 16; k ++)
  for(j = 0; j < 128; j ++)
    for(i = 0; i < 16; i ++)
      {
        fputc(screen[j][i+k*16], out);
        screen[j][i+k*16] ^= 255;
      }

Then it reads the two level screens and writes each square as a byte, filling in the state as it goes: earth and rocks get a random variant so the ground doesn't look like wallpaper, colours above 15 become walls with a decorated sprite, and bats and spirits get a starting direction from whichever neighbour isn't empty:

if(screen[j+80*q][i+80*s] == 4)
  {
    m = 0;
    for(d = 0; d < 4; d ++)
      if (screen[j+80*q][i+80*s+bat[d]] != 0) m = d;
    m = (m+1)&3;
  };

fputc(screen[j+80*q][i+80*s]*16+m, out);

The same program writes the digits and letters for the status line out as an assembler include file, BEDIGITS.INC, which went into the game's source.

The editor

I also started writing an editor, and got as far as rendering some windows and supporting mouse movements.