TileMap — Internals

Introduction

TileMap is a playable game map, supporting selected ZX Spectrum games.

Each game room runs as a separate Spectrum emulation, with the display output from each joined together to give the appearance of a single large game map. The game state is synchronised as the player moves around the map.

Game Map

Every room in the game has a number, which is used internally by the game to reference that location. The values are game-specific, but still a unique reference we can use to distinguish between rooms. Arranging the rooms with common exits touching each other forms the overall game map that TileMap aims to display.

If the game map is arranged in a rectangular grid, it’s usually possible to determine its position in the map from the room number, using a simple formula. This isn’t possible for irregular maps, which must be extracted from the game data or determined empirically, then stored in a look-up table. Online maps can also be a great help in determining the count and position of rooms in unfamiliar games.

The currently supported games use a mix of map types:

Room Control

To display every room in the map we need to control the room number used by the game code. To see how we can do this it helps to understand how a typical game changes rooms as you move between them during gameplay:

  1. Detect the main character is close to a screen edge.
  2. Look up the neighbouring room number for that edge.
  3. Prepare and draw the new room.
  4. Continue the main game main loop.

If we intercept the game at step 3 and change the room number it has decided on, it’s possible to move to a different room, even looping back into the same room. This is the key trick behind how TileMap works.

Locating the room change (step 3 above) in the game code requires a bit of reverse-engineering. If you’re lucky someone has already disassembled the game, providing clues to the game logic. Though in most cases it’ll need to be done from scratch using the debugger in a Spectrum emulator.

For a simple example I’ll use the Jet Set Willy disassembly created by Richard Dymond using his Skoolkit utility. Here’s the start of the room initialisation code at address 0x8912:

8912  LD A,($8420)    Pick up the current room number from 8420
8915  OR $C0          Point HL at the first byte of the room definition
8917  LD H,A
8918  LD L,$00
891A  LD DE,$8000     Copy the room definition into the game status buffer at 8000
891D  LD BC,$0100
8920  LDIR

The room number is read into the A register from location 0x8420. This is used to calculate the address of the new room data, which is copied to another buffer at the start of the initilisation process. Setting a breakpoint at location 0x8912 in an emulator and changing the contents of memory location 0x8420 allows manual control of the new room number. You could also break at 0x8915 and change just A, but this may cause problems if any other code later reads from 0x8420. It’s best to keep the stored room number consistent with the changed register value.

Starting a new game also sets the same room number location, before passing through the room initialisation code above:

87EA  LD A,$21        Initialise the current room number at 8420 to 0x21 (The Bathroom)
87EC  LD ($8420),A

Code Hooks

Using this room changing technique requires catching code execution at specific points during the emulation. The simplest approach to this is to check the Program Counter value before every instruction. This was deemed to be too slow, as checking a list of hooks was more expensive than the implementation of many CPU instructions in the core.

To solve this I used a more invasive technique, which changes the instruction at the breakpoint address. This is similar to what modern system debuggers do, where the breakpoint location is patched with a single-byte software interrupt that the debugger handles. This approach has no overhead for normal code execution, with a cost only when the hook instruction is executed.

For maximum flexibility we also need the hook to be a single byte instruction, so we can hook the shortest instructions without modifying the instruction following it. However, the base Z80 instruction set is fully defined with no spare opcodes values for us to use. Fortunately, the instruction set patterns include some useless LD r,r instructions that are unlikely to be used by real programs. Even if they are used, they can be made to behave normally (a 4-tstate NOP) if there a hook wasn’t installed at that location. I chose the LD H,H instruction (0x64), and modified the CPU core to call a function when it was executed.

For safety we can also check the hook points contains the expected opcode byte before we patch them. This gives a reasonable guarantee that the game code is compatible with the hook, without being overly strict. This leaves the door open for games with modified data, or unrelated code changes (cheat pokes or game fixes).

The hook modifies a Z80 instruction so it’s no longer performing its original operation. To fix this the TileMap hook handler unpatches the location, single-steps, then re-patches before calling the final hook handler. This avoids the need to implement the missing instruction functionality in each handler (which used to be the case!). The only restriction is that the single-step must have changed PC, so the hook isn’t re-executed immediately. This rule is enforced at runtime, and prevents block instructions such as LDIR being used as a hook target.

Room Tiles

Each tile in the map is responsible for a single room, and knows its own identity. Rooms run in separate Spectrum emulations, but they can interact with each other if needed.

Let’s start with a simple example of two tiles, assigned room numbers 1 and 0. If we load a JSW snapshot into both and run them we get two copies of the starting room (33 = The Bathroom):

Two Tile Test

Two Tile Test

This isn’t surprising given the identical starting state and running conditions. To simplify use I’ve also patched the snapshot to auto-start the game, so it doesn’t require Enter to start the game.

Next, we add a small code hook to address 0x8912:

// Room change
Hook(mem, 0x8912, 0x3a /*LD A,(nn)*/, [&](Tile &tile)
{
    Z80_A(tile) = tile.mem[0x8420] = tile.room;
});

The 0x3a opcode is used to verify the hook target contains the expected instruction. The hook handler sets both the A register and room number memory location to the tile’s own room number.

Re-running the test now shows two different rooms, matching JSW rooms 1 (The Bridge) and 0 (The Off Licence):

Rooms 1 and 0

Rooms 1 and 0

Fleshing out the full game map just requires us to create a tile for each game room, and the hook above will ensure each tile shows the expected location. JSW uses an irregular map, so I created a table containing each room number and the grid coordinates in the full game map:

static const std::vector<SparseMapRoom> jsw_map =
{
    { 50, 9,0 },    // Watch Tower

    { 48, 6,1 },    // Nomen Luni
    { 18, 7,1 },    // On the Roof
    { 17, 8,1 },    // Up on the Battlements
    { 16, 9,1 },    // We must perform a Quirkafleeg
...

The game understands the map layout so it could be extracted from the game data, avoiding the need for this table. I hope to add that in a future release, to support modded versions of JSW with a different room layout. However, it’s non-trivial in cases where the game map isn’t planar.

Active Room

If you look closely you’ll see Miner Willy is visible in both rooms above, albeit embedded in the bridge in one! To maintain a convincing illusion the main character should only ever appear in one room — the active room. Character drawing needs to be suppressed in inactive rooms to fix this.

It’s also important that the main character only interact with elements in the active room. Touching enemies or objects in other rooms should do nothing. It won’t cause gameplay-breaking bugs, since the affected rooms will be refreshed when they’re visited, but it spoils the illusion. Main character movement must also be prevented, so it can’t fall out of the room. Even if it’s not visible, leaving the room will cause the room to be re-initialised, moving everything back to their starting positions. Travellators may also need to be disabled if the character could interact with any.

These can all be solved with additional code hooks in the right places. If the hook handler detects it’s running in in inactive room the code behaviour is adjusted to achieve the desired effect — keeping the main character invisible, inert, and immobile.

In JSW the sprite drawing and collision detection are performed by the same routine at 0x95c8, so disabling the drawing also disables the collision detection — handy! The routine at 0x8dd3 peforms character movement, including falling. In both these cases returning from the routines in inactive rooms is enough to avoid their unwanted behaviour. Other games may require changes to register values or program flow, but most can be implemented with just a few lines of code.

The final job of the active room is to handle I/O. It’s the only room to receive user input (currently keyboard), and the only room to generate sound output.

Changing Rooms

At this point we have a game that looks right, but still isn’t playable. If you walk out of a room you’ll re-appear at the opposite side of the same room. This happens because the new hook keeps the tile showing the same room, even when the game tries to change it.

To fix this we need to extend the room change hook to recognise the active tile and actually perform the room change:

// Room change
Hook(mem, 0x8912, 0x3a /*LD A,(nn)*/, [&](Tile &tile)
{
    auto new_room = Z80_A(tile);

    if (IsActiveTile(tile) && new_room != tile.room)
    {
        auto &tile_new = FindRoomTile(new_room);
        auto lock = tile_new.Lock();

        CloneTile(tile, tile_new);
        Z80_A(tile_new) = tile_new.mem[0x8420] = new_room;

        ActivateTile(tile_new);
    }

    Z80_A(tile) = tile.mem[0x8420] = tile.room;
});

The if condition checks whether we’re leaving the active room for a different room. If so we find the tile object managing the new room and copy our current tile state to it. Finally, we update its game room number (in both A and memory), and set it to be the new active room tile. The final line in the function loops the old room back to its assigned room, since the game will have changed it. Since the old room is no longer active the main character will now be hidden.

The tile lock is important to ensure we have exclusive access to it before making any changes, as the CPU emulations are run in parellel on different threads. The cloned state includes the memory contents and Z80 state, which is enough to transfer the game state to a different tile.

Moving between rooms now works correctly, but the old room appears in the new location very briefly, which is ugly. This happens because the state we cloned includes the Spectrum display memory. I initially changed CloneTile to clone starting after the display, but later found that Jet Set Willy II+ stores game state behind black-on-black attributes! A better solution was to add an enable flag for tile drawing. Drawing is turned off at the start of a room change and back on when room drawing has completed. This requires another small hook:

// Room drawing complete
Hook(mem, 0x8a3a, 0xcd /*CALL nn*/, [&](Tile &tile)
{
    tile.drawing = true;
});

Game State

Maintaining the illusion of a single running game also requires consistent game state between rooms. This must cover key game elements, such as object locations and states, but doesn’t have to include precise enemy locations in each room. It’s not necessary to keep the rooms perfectly synchronised on a frame-by-frame basis.

The active room tile maintains the master game state, which is copied to other rooms as the player moves to them. Most of the time the remaining rooms are running completely independently of each other. You can see this in JSW, where the rope positions in different rooms will slowly drift out of sync. This is easiest to see when comparing The Swimming Pool to The Cold Store, as the latter is slowed by having to draw more enemies each frame.

Sometimes data needs to be shared between rooms. This is best stored in the object managing the overall game, and will require locking protection if it could be accessed from multiple rooms. Jet Set Willy preserves the state of a room being entered, before it is overwritten by the cloned copy of the active room. Another hook catches when the new room has been initialised, to restore the original room state. This preserves the enemy and rope positions, to give a more seamless game experience when moving between rooms.

Starting a new game is another important state synchronisation point, as the game state reset should be copied to all rooms. Without this a room will not match the master game state, and may appear differently when entered. The game start should be hooked after the game has been initialised:

// Game start
Hook(mem, 0x88fc, 0x21 /*LD HL,nn*/, [&](Tile &tile)
{
    if (IsActiveTile(tile))
    {
        CloneToAllTiles(tile);

        auto &tile_start = FindRoomTile(tile.mem[START_ROOM_ADDR]);
        ActivateTile(tile_start);
    }
});

Games with random elements have the opposite problem of static state. Even if they seed their random numbers from the R register or the FRAMES system variables, the fixed snapshot and deterministic execution will result in the same number sequence every run. These games need help seeding their random number generators, which can be done after the snapshot has loaded.

Other Games

Jet Set Willy was the first supported game, which took only a weekend to get running as a proof of concept. It took a couple of weeks of refactoring to separate out the JSW-specific code, in preparation for other games. Then a couple of months (on and off) to add another 6 games, including any engine enhancements they required. A future update could support systems other than the Spectrum.

Adding new games revealed some interesting quirks, and gave the opportunity for some minor enhancements:

Dynamite Dan II

This game map is interesting because the rooms contain an overlap region on all edges: 16 pixels horizontally and 24 pixels vertically. The vertical overlap is particularly obvious at the airship dock in the first room:

Without Overlap

Without Overlap

With Overlap

With Overlap

This overlaps permits Dan to transition seamlessly between rooms horizontally, and vertically with only a small vertical jump. It’s almost as though Rod designed this just for TileMap.

The overlap also introduced a new complication for the engine, concerning which room graphics to favour at the overlap. The background of the favoured room replaced the foreground of the other, leading to black strips that sprites disappeared behind. Even favouring the active room wasn’t enough as objects in the inactive room would be clipped, and suddenly appear on room entry.

Sprites Clipped at Overlap

Sprites Clipped at Overlap

A better solution was to treat black pixels as transparent. That way any non-black pixels from either room would be seen in the overlap. In most cases overlapping non-black pixels are identical, as the graphics in the overlap match. There are some rock patterns on island 2 that are mismatched, but they’re not bad enough that it’s worth fixing them in the room data.

The airship room also raised the possibility of a game-specific enhancement. Could it move like the game pretends? The game already tracked the airship position to know where to draw the scrolling dock graphics. Hooking this code we are able to determine the airship position relative to the appropriate island, and position the room tile in the expected place on the map. This required another engine enhancement to support changing the position of a tile at runtime. You can see the airship in action on YouTube.

I’d initially hoped to track Blitzen on the map, and show him wherever he happened to be. It soon became apparent that his position was faked, and he was just made to visit periodically. For that reason it was necessary to limit his drawing to the active room, to prevent him appearing in inactive rooms — often more than one at the same time!

Dynamite Dan

Perhaps not surprisingly, this game uses the same room overlap margins as Dynamite Dan II, with the same benefits. However, there were some strange issues in a few places that needed to be investigated:

Duplicate Enemies

Duplicate Enemies

The screenshot shows two yellow and two magenta sprites below the safe, when there should be one of each colour. One pair is from the bottom of the safe room, and the other from the top of the room below. The transparent drawing change in DD2 allows them both to be visible. The game manages these as separate entities, so touching one will not remove it from the other room — something I’d never noticed before now. After looking more closely, 7 pairs of duplicate enemies were found on the map, and in each case only one set could be touched by the main character. The solution was to remove the unwanted (untouchable) entities by marking them as removed during game initialisation.

I’d hoped to track the lift and raft positions across the map, so they could always be seen. However, like Blitzen in DD2 their positions aren’t consistent. In both cases they’re kept near the player, so you don’t have to wait too long for each to re-appear. You can see this if you wait near the top of the lift shaft. The departing lift returns after about 7 seconds, but riding it down and back up takes nearly 2 minutes! For that reason both lift and raft are hidden in inactive rooms.

Jet Set Willy II+

JSW2+ has many gamplay similarities to JSW, but it doesn’t share any code. There is also no disassembly available to help with hooks.

I initially had some trouble making the main character inert in inactive rooms, so I tried a different approach. The game has a demo mode that shows the game rooms if you wait long enough at the main menu. Rooms are animated without Miner Willy, which is exactly what I needed. I transplanted the guts of the demo loop into the hook handler for the main game loop. In the active room it runs the game as normal, and in inactive rooms the demo loop runs instead.

The Cartography Room presented another opportunity for a special feature. It’s updated as you visit rooms in the map, and shows whether there are still items to be collected. The room is always visible in TileMap, so I thought it would be nice to have it update live. The implementation was as simple as cloning the active tile to The Cartography Room on each room entry, which passes the latest set of room-visited flags needed to draw the updated map.

I’d like to add seamless support to this game, but I’ve yet to isolate the data needed to be preserved the room state. The demo loop includes the routines used to animate the room content, so it should be possible to track it down from them. The lift states will need to be excluded from this as their initial positions are designed to support Miner Willy when he enters a room from above or below.

Spindizzy

This is probably the most visually striking map because of its isometric view. It also prevented a few extra challenges for TileMap.

The isometic layout makes creating the map slightly more awkward than for rectangular rooms. Fortunately, each room has the same basic 8x8 block layout, so they’re all the same size. It still means the room base is a diamond shape from a 2D point of view, which requires skewing them both vertically and horizontally to jigsaw the rooms together to form the map. This also means the rooms overlap, with the following effect:

Transparent Overlap

Transparent Overlap

Note how the the blocks appear to be transparent where the rooms touch. This was another side-effect of the transparent merging of overlapping rooms. We somehow needed transparent black for the background, but opaque black for the level blocks. I realised that the required mask could almost be created by taking a screenshot and flood-filling around the outside of the room shape. Anything filled should be transparent, everything else should be opaque. The engine was modified to support creating a mask from the room image when room drawing completed. This gives the following result:

Room Masking

Room Masking

This is pretty good, but the bottom-right edge still shows some transparent blocks. The tiles on the left have vertical gaps to separate them, which runs into the tile face. The remaining issue is caused by the flood fill leaking into these areas, leading them to be treated as transparent. It’s actually doing it on all of the base tiles, including their tile faces, but you only notice it where it overlaps another room. The easiest work-around for this is to close the gaps by editing the graphics data itself, which can be patched after loading the snapshot. Due to the shared use of some edge graphics this introduces some single pixel bumps, but they’re minor enough not to spoil the look of the game. There are still some transparency issues around jewels, due to a black outline effect, which I must return to fix sometime.

The active map area covers an immense 38x40 grid (1520 rooms in total), though only 382 of them are populated. Many of the unpopulated rooms can still be entered from the edges of regular rooms, so they need to be associated with a room tile. When the map is zoomed out these empty rooms would still be eligible to be run, but emulating 1138 empty rooms seemed like a waste. Instead, a new flag was created to mark these rooms as inactive (initially), which prevents them being run. Visiting the rooms activates them, so they become part of the normal execution pool.

Moving between rooms in the original Spindizzy is slow because 3D drawing is hard for the humble Spectrum. The screen freezes for nearly a second before the new room is revealed, which breaks the immersion when moving around the map in TileMap. To fix this the room emulation takes note of the tile.drawing flag, which is clear when a room change is in progress. It keeps running emulated frames until the room change completes, up to a maximum of 50 frames (1 second). This is enough to remove the room change delay, leading to a more pleasant gamplay experience.

Technician Ted

The attraction for adding this game was the small changes to rooms that occur after tasks are completed. Completing the first task in Ted’s Desk adds a support platform to The Silicon Slice Store, and so on. So far I’ve only managed to get the map updated when Ted leaves the room after completing each task, but it’s a start.

This is also the only game to show side-effects from room changing. Entering the final room (to complete the game) makes state changes that breaks re-entry to the previous room. This was solved by cloning back to the previous room before these breaking changes occur, so the previous room continues to function.

The map contains a lift room, allowing Ted to move between the 6 floors more easily. To ensure the lift is always available the lift room tile tracks the currently active room row. Selecting a floor number also moves the lift, of course.

Adding New Games

I’ve still got a few partially completed games to finish, including Sabre Wulf and Ant Attack. I have my eye on a few other titles, but haven’t started them.

I hope that the currently supported games serve as useful examples, tempting others into adding new titles. If you’ve ever reverse-engineered games for pokes, you’ve got what it takes. I’ve covered the general process above for a simple conversion case. Most games need about 6 hooks, totalling around 100 lines of code — a little more if it needs a room look-up table too.

Here’s a quick overview of what is usually needed:

Engine Implementation

That covers the Spectrum game side of the implementation, but haven’t said much about the underlying engine. Here’s a quick overview:

The current version is Windows-specific and requires D3D10-level graphics hardware with support structured buffers. It’s currently still using DirectInput for keyboard input and DirectSound for audio output, with Blargg’s Blip_Buffer used to manage the Spectrum beeper. It uses Manuel Sainz de Baranda y Goñi’s Z80 CPU core, which doesn’t currently support memory contention, but is very fast.

The following occurs during each 20ms loop:

The map layout is prepared in a vertex buffer, and only updated if the layout changes (including tile movements). It contains per-instance data that describes the position, size and screen index of each room in the display data buffer. The vertex shader expands these into the required vertices and texture coordinates, plus the data offset into the room data, which is passed through to the pixel shader.

The raw Spectrum display data is passed to the pixel shader in a structured buffer, where it is converted to directly to the output image. That avoids any pre-processing by the CPU, which may not scale well as the room count increases. This does means the display is a snapshot at the end of each frame, so rainbow effects won’t be visible. That’s unlikely to be problem for any suitable games.

CPU utilisation shouldn’t be a problem for most users. Even with all 512 rooms in Starquake running, my eight year old i7 CPU only reaches about 40% utilisation. Only the visible rooms are run, so at normal zoom levels the usage should be just a few percent.

GPU utilisation depends on the graphics hardware and the number of output screen pixels that contain display content. Surprisingly, zooming out to view the entire map requires less GPU effort than zooming in to view a small part of a single room! The Intel integrated graphics on an i7 6700 can drive a 3840x2160 display with around 35% GPU utilisation in fullscreen mode, and about 65% in windowed mode (due to Desktop Window Manager overhead). Anyone with even a low-end gaming card shouldn’t have any performance issues.

Questions? Please get in touch using the link below.