Editorial note: I enjoy poking around the innards of old computer games. I think it’s interesting to learn how the things worked, especially since they often had to cope with formidable resource restrictions. This is one of an occasional series of articles on things I found while looking through assembly code.
Hacker
Hacker is a 1985-vintage computer game; Wikipedia offers a good overview of it. A large part of its gameplay is given over to navigating through a maze-like system of tunnels. Hacker uses a simple look-up table to represent this maze, which I thought was a particularly elegant solution.
The analysis which follows is based upon a particular (PC) version of the game. The MD5 of the executable is:
- a75940020c4d18e353203a2211ffca74
Tunnel System
Hacker does not display the tunnel system in its entirety; you can only discover the portion of it near your current location, and instead see a world map like this:
The hidden tunnel complex looks like this – green cells represent locations from which you may access a city, and red cells represent ‘prohibited’ areas, which are supposed to end the game:
The tunnel system overlays on the world map like this:
(Notice anything odd?)
Data Structure
Hacker stores this maze as a 600 byte array. This array is stored at file offset 9330H in my version of the game. Here is the data structure, in its entirety:
01 00 09 0C 0C 0C 0C 0C 0C 0C 0C 0C 0C 0C 0C 0C 05 00 09 0C 05 00 09 0C 0C 0C 0C 0C 0C 0C 0C 0C 0C 0C 0C 0C 0D 0C 05 00
03 00 03 00 00 00 00 00 00 00 00 00 00 00 00 00 03 00 03 00 03 00 03 00 00 00 00 00 00 00 00 00 00 00 00 00 03 00 03 00
03 00 03 00 08 0C 0C 0C 0C 0C 0C 0C 0C 0C 0C 0C 0E 0C 0E 0C 0E 0C 56 00 09 0C 05 00 09 0C 0C 9C 0C 0C 05 00 03 00 03 00
03 00 03 00 03 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 03 00 03 00 C3 00 00 00 00 00 03 00 03 00 03 00
03 00 0A 7C 0D 0C 0C 6C 05 00 09 0C 0C 0C 05 00 09 AC 04 00 08 BC 0C 0C 06 00 03 00 0B 0C 0D 0C 15 00 03 38 07 00 03 00
03 00 00 00 03 00 00 00 03 00 03 00 00 00 03 00 03 00 00 00 00 00 00 00 00 00 03 00 03 00 03 00 03 00 03 00 03 00 03 00
03 00 00 00 03 00 00 00 0A 0C 0E 0C 0C 0C 0E 0C 0E 0C 0C 0C 0D 0C 0C 0C 0C 0C 0E 0C 06 00 03 00 03 00 0B 2C 06 00 0B 44
03 00 00 00 03 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 03 00 00 00 00 00 00 00 00 00 03 00 03 00 03 00 00 00 03 00
0B 0C 0C 0C 07 00 09 0C 0C 0C 05 0C 09 0C 0C 0C 05 00 00 00 03 00 89 0C 0C 0C 0C 0C 0C 0C 06 00 03 00 03 00 09 0C 06 00
03 00 00 00 03 00 03 00 00 00 03 00 03 00 00 00 03 00 00 00 03 00 03 00 00 00 00 00 00 00 00 00 03 00 03 00 03 00 00 00
03 00 09 0C 0F 0C 0F FC FC 0C 0E 0C 0F 0C 0C 0C 0F 0C 0C 0C 07 00 03 00 09 0C 0D 0C 0C 0C 04 00 03 00 03 00 03 00 01 00
03 00 03 00 03 00 F3 00 00 00 00 00 03 00 00 00 03 00 00 00 03 00 03 00 03 00 03 00 00 00 00 00 03 00 03 00 03 00 03 00
03 00 0A 0C 07 00 0A 0C 0C 0C 04 00 0A 0C 05 00 0A 0C 0C 0C 06 00 03 00 0A 0C 0E 0C 0C 0C 0C 0C 06 00 03 00 03 00 03 00
03 00 00 00 03 00 00 00 00 00 00 00 00 00 03 00 00 00 00 00 00 00 03 00 00 00 00 00 00 00 00 00 00 00 03 00 03 00 03 00
0A 0C 0C 0C 0E 0C 0C 0C 0C 0C FC 0C 04 00 0A 0C 0C 0C 0C 0C 0C 0C 0E 0C 0C 0C 0C 0C 0C 0C 0C 0C 0C 0C 06 00 0A 0C 06 00 The maze is laid out as a 40×15 grid of cells, and each cell is stored as a single byte. The grid is stored by row, with the topmost row first, and each row is stored left-to-right. The low nibble of each byte represents connectivity, and the high nibble describes special properties of the cell. These tables summarize the meaning of the low and high nibbles:
| Bit Set | Allows travel: |
|---|---|
| 0 (1) | South |
| 1 (2) | North |
| 2 (4) | West |
| 3 (8) | East |
| High nibble | Cell type |
| 0 | Ordinary cell |
| 1-12 | City cell |
| 15 | Prohibited cell |
City cells allow access to a particular city – which city depends on the specific value of the high nibble. Prohibited cells are supposed to trigger the end of the game if the player enters them at any time.
This data structure has several nice features:
- Compact. 600 bytes is a reasonable budget for a world map.
- Fast. One look-up can answer all questions about a location.
- Simple. This data structure is easy to create, edit, and understand.
Errata
An examination of the world map yields one major and one minor surprise. Cell [28, 3] (taking the origin to be [0, 0] in the upper-left-hand corner) is marked as a city cell – for city 12, to be precise. No city appears at this location on the world map. If we go to that location, however, we will find a secret (underwater) city. It’s a bit of an anti-egg, however, as the goods you can purchase there won’t be accepted by any other agent, and you have no cash to waste. In other words, if you buy anything, you will lose the game.
Another oddity is that the cell at [11, 8] permits travel to its east and west, but the cell to its west at [10, 8] does not permit travel to the east, and the cell to its east at [12, 8] does not permit travel to the west. The cell is therefore inaccessible, and serves only to demonstrate a peculiar consequence of using a digraph for your world map.
If we dig into the game’s machine code, we will find a small bug; the movement code only checks for player entry into prohibited cells on the player’s 2nd and subsequent moves, and on the player’s final move. For instance, if you stop in cell [6, 10] and move 2 cells to the south, you will skip right over the prohibited cell at [6, 11]. This doesn’t gain you anything, but it is interesting. Note that this trick doesn’t work if there are two adjacent prohibited cells, as there are at [7, 10] and [8, 10]. Since it would gain you something if you could hop over the prohibited cells on the Y=10 row (saving you valuable late-game moves), I suspect the prohibited cells were doubled up specifically to work around this bug.
