The rezrov Infocom Game Interpreter

Michael Edmonson

Interactive fiction, or IF to its devotees, is a genre of text-based computer games. IF games present a virtual environment to the player, and respond to commands typed by the player. For example:

West of House 

You are standing in an open field west of a white house, 
with a boarded front door.

There is a small mailbox here.

>open mailbox

Opening the small mailbox reveals a leaflet.

IF traces its heritage to the early days of computer gaming. The first game was known simply as Adventure, or Colossal Cave, in which the player explored a mammoth underground cavern, collecting treasure and solving puzzles. Adventure caused a sensation when it arrived on the scene in the 1970's, but the game had a very limited vocabulary and could only accept simple commands. Inspired, a group of friends at MIT set about developing a new game with a vastly expanded vocabulary and the ability to understand complete sentences. This game became known as Zork, and its developers went on to form a company called Infocom.

Zork was originally developed on a DEC PDP-10 mainframe, a very expensive computer few people had access to. To bring the game to a wider audience, Zork's programmers wanted to find a way to make it run on the fledgling home computers of the time. Further complicating matters was the fact that home computers were much rarer than they are today, and there was a much wider variety of brands. To maximize the size of their market, Zork needed to run on as many of these computers as possible, and adapt to new machines as they emerged.

Infocom's solution was ingenious: they invented a design for something called the Z-machine, a virtual computer. The idea was that the functions of this machine could be emulated on different computers with a program called a ZIP, or Z-machine Interpreter Program. The Z-machine's programs--that is, the games themselves--were written in a new, compact language called the Zork Implementation Language (ZIL or Z-code for short). Because the emulated Z-machine behaved the same way on every platform, the games were 100% portable from computer to computer. The design was pared down to the point where it became possible to write ZIPs that ran on TRS-80s and Apple IIs, quite an accomplishment when you consider that the original version of Zork strained even the august PDP-10.

When a new computer was released, the programmers didn't need to touch any of the game programs; all they had to do was create a new ZIP for that platform, and it would be able to run all the games. Likewise, new games could be developed and released simultaneously for all platforms. These efficiencies allowed Infocom to nimbly adapt to the gyrations of the personal computer market in the 1980's; They released Z-machine interpreters for the TRS-80 series, Apple II and Macintosh, Atari 800/XL/XE and ST, Commodore 64 and Amiga, and the IBM PC, to name a few. This strategy also allowed all players to experience Infocom's games in exactly the same way regardless of their computer. The Z-machine concept was astonishingly ahead of its time--consider that Java, whose "write once, run anywhere" virtual machine has received so much attention, wasn't developed until more than a decade later.

Technical merits aside, what ultimately determined Infocom's success was the quality of their games, whose immersive, sharply-written style and dry wit quickly earned them a loyal following. Zork I described itself as "a game of adventure, danger, and low cunning." Infocom's heyday was in the early-to-mid 1980's, when it released a string of solid titles, but the company stumbled with a failed venture into business software and was eventually subsumed by Activision.

Resurrecting the Z-machine

The original Infocom is long gone, but the Z-machine is alive and well. A team of dedicated hackers known as the InfoTaskForce was largely responsible for reverse-engineering the Z-machine's inner workings. Various open-source Z-machine interpreters were developed and circulated. Eventually the Z-machine was understood completely enough that a formal specification for it was drawn up by Graham Nelson. Graham also developed Inform, an interactive fiction authoring system and compiler that allows new games to be written for the Z-machine architecture. Inform has a wide following, and the annual IF contest brings in many new quality Z-code games every year. Perhaps the ultimate affirmation of Inform's success came with Activision's 1997 promotional release of "Zork: The Undiscovered Underground": a game co-authored by two of Infocom's original authors (Marc Blank and Michael Berlyn), and compiled with Inform.

Enter the Camel

Z-code interpreters exist for almost every platform imaginable. Two of the most widely-used interpreters, zip and frotz, are written in C and have been ported to everything from mainframes to PalmPilots. One thing I've always thought was rather a shame about the available crop of interpreters was the way they've tended to fragment around different platforms' user-interface models. For example, xzip is a derivative of the character-based zip interpreter, adapted to the graphical X Window System. Likewise, the character-based frotz interpreter begat a port to Windows called winfrotz. Z-code interpreters have also been written in Java; unfortunately, when it comes to cross-platform compatibility, Java's user-interface classes are finicky and unstable--just ask anyone who's tried to reason with the AWT on different JVMs.

I decided to write a Z-code interpreter in pure Perl, so the games could be played anywhere Perl could be used. Moreover, I wanted the program to be able to adapt itself to the variety of I/O models available on different systems, so you could play the games on anything from a basic character display to a fancy graphical window. I decided to name it rezrov after a magic spell from Infocom's classic game Enchanter. In the game, the spell means "open even locked or enchanted objects," and I figured Z-code program files qualified as both. I remember playing Enchanter and thinking I was really clever for using the spell to circumvent a puzzle involving a jeweled egg:

>take egg then examine it 

Taken.

This ornamented egg is both beautiful and complex. The 
egg itself is mother-of-pearl, but decorated with delicate 
gold traceries inlaid with jewels and other precious metals. 
On the surface are a lapis handle, an emerald knob, a silver 
slide, a golden crank, and a diamond-studded button carefully 
and unobtrusively imbedded in the decorations. These various 
protuberances are likely to be connected with some machinery 
inside.

The beautiful, ornamented egg is closed.

>learn rezrov then rezrov egg 

Using your best study habits, you learn the rezrov spell.

The egg seems to come to life and each piece slides 
effortlessly in the correct pattern. The egg opens, 
revealing a shredded scroll inside, nestled among a 
profusion of shredders, knives, and other sharp instruments,
cunningly connected to the knobs, buttons, etc. on the 
outside.

Oops.

What's it do?

rezrov is a Z-code interpreter. An interpreter's job is to fetch the instructions, or "opcodes", that form a program and execute them; that's exactly what Perl itself does under the hood. Interpreters spend most of their time in a loop:

• Retrieve the next opcode
• Perform the task specified by the opcode
• Repeat

Each opcode performs a single, basic logical operation. The Z-machine has opcodes for reading from and writing to memory, manipulating variables, performing mathematical operations, reading input from the keyboard, displaying output on the screen, and changing the control flow of the program. Z-machine opcodes can be thought of as small subroutines or functions, which may accept arguments ("operands") and return results. It is the execution of many combinations of opcodes in series which form the programs, and thus the games. This basic process is echoed at many levels inside your computer, both in hardware and software, from your CPU on up through your operating system and applications.

So, rezrov emulates the workings of a virtual computer, and the Z-code games are programs that run in this computer. But where and what are the programs? For every computer, Infocom supplied an interpreter program and a data file: on MS-DOS systems, you would usually find an executable file for the interpreter (for example, zork1.com) and a large data file (zork1.dat). This data file, called the story file, is the actual Z-code program. It is completely portable between systems--you can extract the story file from an Apple II diskette and play it on a PC with a PC interpreter. Neat, huh?

On the home computers of yore, the games were usually too large to fit into memory all at once; for example, the Zork I story file is about 94K, while a typical PC had only 64K of RAM. To cope, Z-code interpreters swapped small chunks or "pages" of data from the diskette in and out of memory as they were needed by the game. This may have been the first use of virtual memory on a microcomputer--yet another revolutionary feature of the Z-machine design.

The Joy of vec()

Most Z-code interpreters still use these paging schemes to minimize memory consumption. My feeling is that life is too short, especially since loading the entire game image into memory is such a breeze with Perl:

open(GAME, $filename) || die 
      "can't open $filename: $!\n";

binmode GAME;

my $size = -s $filename;

read(GAME, $story_bytes, $size);

This loads the entire story file into a variable called $story_bytes. The Z-machine's memory is basically a fixed-length array of 8-bit bytes; while 16-bit words are used for certain operations, virtually everything in memory is indexed by a byte offset. So, my first instinct was to simply convert the data into an array of bytes:

@story_bytes = unpack("C*", 
      $story_bytes);

This was easy to do, but it came at a significant cost. Because each byte is converted to an individual scalar variable, much more memory is consumed. Consider the following program:

#!/usr/bin/perl -w

use strict;
use Benchmark;

my $filename = shift || die "specify filename\n";
my $b1 = new Benchmark();

my $story_bytes;
open(GAME, $filename) || die "can't open $filename: $!\n";
binmode GAME;
my $size = -s $filename || die "no file";
read(GAME, $story_bytes, $size);

if (@ARGV) {
    print "Creating array with unpack\n";
    my @story_bytes = unpack "C*", $story_bytes;
} else {
   print "Not converting data to array\n";

}

my $td = timediff(new Benchmark(), $b1);
printf "%s\n", timestr($td);
print "Sleeping...\n";
sleep 10000;

This program reads a file into memory, and if a second argument is provided, it converts that file into an array of bytes. Finally, it prints the time elapsed as recorded by the Benchmark module, and sleeps (to allow the user to check the size of the process in memory).

I ran this program on the 94 kilobyte zork1.dat on my Pentium 133 running Linux. It completed almost instantaneously, and the Perl process consumed 1.9 megabytes of memory. When it converted the data into an array of bytes, the process consumed 6.5 megs of memory, and took almost a half-second to finish. This discrepancy became even more pronounced with the 256K trinity.dat: the first version consumed 2 megabytes of memory and still finished virtually instantaneously, while the array of bytes consumed almost 14 megabytes of memory and took more than 1.3 seconds to complete. While Perl's typeless scalar variables are very convenient to use, the overhead they impose becomes apparent in large arrays like this.

Happily, there's a way out: the undersung vec() function. vec() lets you treat a variable as an array of unsigned integers where you get to specify the number of bits of storage to allocate for each entry. This is great for arrays of fixed-size data: 8-bit bytes, 16-bit words, etc. There are some restrictions: The elements of a vec() array can only be unsigned integers, and the number of bits of storage must be a power of two from 1 to 32. But for my purposes, vec() was perfect: I could grab all the data with a single read() command, my program would start up quickly because I could avoid converting the data into a huge array, and I would save a lot of memory as well.

The vec() function takes three arguments: the name of the variable to hold the data, the index in the array you want to reference, and the number of bits used for each entry in the array. Here are two object methods from rezrov that use vec() to access single bytes in $story_bytes:

sub get_byte_at {
    # get the 8-bit byte at the specified storyfile offset.
    return vec($story_bytes, $_[1], 8);
}

sub set_byte_at {
    # set the 8-bit byte at the specified storyfile
    # offset to the given value.
    vec($story_bytes, $_[1], 8) = $_[2];
}

This initial excitement aside, much of the guts of rezrov's interpreter aren't particularly interesting. Most of the opcodes are fairly straightforward subroutines; the trickiest part was just making sure the bits came from and wound up in the right place. The basic nuts and bolts of Z-code interpreters are considered a solved problem these days; Graham Nelson wrote "If your system isn't supported, adapting the C source code for one of the main interpreters is only a trial of patience, not of strength."

Tinkering with the Z-machine

>read dusty book

The first page of the book was the table of contents. 
Only two chapter names can be read: The Legend of the Unseen 
Terror and The Legend of the Great Implementers.

>read legend of the implementers

This legend, written in an ancient tongue, speaks of the
creation of the world. A more absurd account can hardly
be imagined. The universe, it seems, was created by
"Implementers" who directed the running of great engines.
These engines produced this world and others, strange and
wondrous, as a test or puzzle for others of their kind.
It goes on to state that these beings stand ready to aid
those entrapped within their creation. The great magician-
philosopher Helfax notes that a creation of this kind is
morally and logically indefensible and discards the theory
as "colossal claptrap and kludgery."

--Enchanter, 1983

One of the most entertaining things about writing rezrov was adding features that putter around under the hood of the Z-machine while it's running. I found fertile ground for these experiments in the Z-machine's object table. The object table is a block of memory containing information about every significant object in the game. Every room, every item that can be picked up or otherwise interacted with, even the player: each is represented by an entry in the object table. Entries contain, among other things, a short description of the object, and pointers to a parent, a sibling, and a child object. Thus the object table describes a tree whose branches connect the items in the game. For example, take Zork I's kitchen, which the game describes like so:

>look 

Kitchen 

You are in the kitchen of the white house. A table seems
to have been used recently for the preparation of food. A
passage leads to the west and a dark staircase can be
seen leading upward. A dark chimney leads down and to the
east is a small window which is open.

A bottle is sitting on the table.
The glass bottle contains:
	A quantity of water There is a brown sack here.
The brown sack contains:
	A lunch
	A clove of garlic 

This scene is represented in the object table like this:

Kitchen (203)
|----kitchen table (204)
| |----brown sack (224)
| | |----lunch (225)
| | |----clove of garlic (189)
| |
| |----glass bottle (236)
| | |----quantity of water (237)

Here the Kitchen room object (object #203), has a child, the kitchen table (#204). The table has a child, a brown sack (#224). The sack has a child, the lunch (#225), which itself has a sibling, the clove of garlic (#189). Likewise the sack has a sibling, the glass bottle (#236), which has a child, the quantity of water (#237).

The Z-machine has a set of opcodes which manipulate the entries in this table; the games execute these opcodes to make changes to their environment. I added a feature to rezrov, activated by the -snoop-obj command-line switch, which prints a message whenever an object is moved from one location to another. It prints out the name of the object being moved and the name of its new parent so you can watch what's happening. Using this feature you can see the name Infocom assigned to the "player" object in a number of their early games:

West of House
You are standing in an open field west of a white house,
with a boarded front door.
There is a small mailbox here.

>north [Move "cretin" to "North of House"]
North of House
You are facing the north side of a white house. There is
no door here, and all the windows are boarded up. To the
north a narrow path winds through the trees.

Later games changed this to the more diplomatic "yourself".

Once I had implemented all the opcodes necessary to manipulate the object table, the temptation to make changes to it in mid-game proved irresistible. This led to the creation of a few new verbs which rezrov intercepts without the game's knowledge, enabled by the -cheat command-line option: teleport, bamf, and pilfer, among others.

Teleport

This command moves the player to any room in the game. Since the player and the locations in the game are all simply entries in the object table, teleporting the player is simply a matter of modifying the player's object so that it becomes the child of the room to be moved to. The code for the teleport() subroutine is shown in Listing 1.

teleport() uses several objects to do its dirty work:

• $story is a reference to StoryFile.pm, a package that contains most of the Z-machine's data and opcodes, and manages communication with the user interface.
• $zo is a reference to ZObject.pm; ZObject instances represent individual objects in the object table. ZObject's methods provide access to the object's data and allow the caller to navigate its parent/child relationships.
• $object_cache is a reference to ZObjectCache, which manages a pool of ZObject references. It also tries to guess which objects represent rooms and which represent items, providing a find() method to search this information.

The subroutine takes as a parameter the name of the location the player wants to move to. Using ZObjectCache, it then looks to see if the player has specified a unique location name. If this is so, the insert_obj() method of StoryFile is called. insert_obj() implements the opcode responsible for making one object the child of another object. It's called in the ordinary course of games to move the player from room to room: With each move, the player's object is unlinked from its old "parent" room object and made a "child" of the new room object. By doing this ourselves, we can teleport from one place to another.

But most of the code in this subroutine is for handling special cases:

• If you specify the name of an item in the game rather than a room, it tries to determine what room the object is in by walking up the object's parent/child hierarchy so it can take you there.
• If you specify an ambiguous location or item name, it will print a message listing the alternatives and ask which you mean.
• If it can't figure out where you mean to go, it will assume you are a tourist and suggest visiting a randomly chosen location in the game instead.

After teleport() is called, rezrov temporarily disables the output of the game until the next prompt. This prevents the player from seeing the game's confused complaint that it didn't understand the teleport command: Remember, even though rezrov understands what to do, the underlying game program has no idea what that means. rezrov also steals the player's next turn to submit a look command on their behalf. The player sees only the final result, which looks something like this:

>teleport kitchen
You are momentarily dizzy, and then...
Kitchen
You are in the kitchen of the white house. A table seems
to have been used recently for the preparation of food. A
passage leads to the west and a dark staircase can be
seen leading upward. A dark chimney leads down and to the
east is a small window which is slightly ajar.
On the table is an elongated brown sack, smelling of 
hot peppers. A bottle is sitting on the table.
The glass bottle contains:
  A quantity of water 

This effectively modifies the behavior of the game without the player noticing that anything unusual has happened.

This technique is also used at the very beginning of the game to try to guess its title. rezrov steals the user's first turn to submit a version command to the game. version is a traditional command that prints out the name of the game and its revision information. rezrov extracts the title from the game's redirected output and uses it to set the title of the window. Usually version doesn't even cost the player an official turn, so no one's the wiser. If the user interface can't support setting the window's title or the word version isn't in the game's dictionary, rezrov skips the attempt entirely.

Teleport

This command moves the player to any room in the game. Since the player and the locations in the game are all simply entries in the object table, teleporting the player is simply a matter of modifying the player's object so that it becomes the child of the room to be moved to. The code for the teleport() subroutine is shown in Listing 1.

teleport() uses several objects to do its dirty work:

• $story is a reference to StoryFile.pm, a package that contains most of the Z-machine's data and opcodes, and manages communication with the user interface.
• $zo is a reference to ZObject.pm; ZObject instances represent individual objects in the object table. ZObject's methods provide access to the object's data and allow the caller to navigate its parent/child relationships.
• $object_cache is a reference to ZObjectCache, which manages a pool of ZObject references. It also tries to guess which objects represent rooms and which represent items, providing a find() method to search this information.

The subroutine takes as a parameter the name of the location the player wants to move to. Using ZObjectCache, it then looks to see if the player has specified a unique location name. If this is so, the insert_obj() method of StoryFile is called. insert_obj() implements the opcode responsible for making one object the child of another object. It's called in the ordinary course of games to move the player from room to room: With each move, the player's object is unlinked from its old "parent" room object and made a "child" of the new room object. By doing this ourselves, we can teleport from one place to another.

But most of the code in this subroutine is for handling special cases:

• If you specify the name of an item in the game rather than a room, it tries to determine what room the object is in by walking up the object's parent/child hierarchy so it can take you there.
• If you specify an ambiguous location or item name, it will print a message listing the alternatives and ask which you mean.
• If it can't figure out where you mean to go, it will assume you are a tourist and suggest visiting a randomly chosen location in the game instead.

After teleport() is called, rezrov temporarily disables the output of the game until the next prompt. This prevents the player from seeing the game's confused complaint that it didn't understand the teleport command: Remember, even though rezrov understands what to do, the underlying game program has no idea what that means. rezrov also steals the player's next turn to submit a look command on their behalf. The player sees only the final result, which looks something like this:

>teleport kitchen
You are momentarily dizzy, and then...
Kitchen
You are in the kitchen of the white house. A table seems
to have been used recently for the preparation of food. A
passage leads to the west and a dark staircase can be
seen leading upward. A dark chimney leads down and to the
east is a small window which is slightly ajar.
On the table is an elongated brown sack, smelling of hot 
peppers. A bottle is sitting on the table.
The glass bottle contains:
  A quantity of water 

This effectively modifies the behavior of the game without the player noticing that anything unusual has happened.

This technique is also used at the very beginning of the game to try to guess its title. rezrov steals the user's first turn to submit a version command to the game. version is a traditional command that prints out the name of the game and its revision information. rezrov extracts the title from the game's redirected output and uses it to set the title of the window. Usually version doesn't even cost the player an official turn, so no one's the wiser. If the user interface can't support setting the window's title or the word version isn't in the game's dictionary, rezrov skips the attempt entirely.

Bamf

bamf is sort of the inverse of teleport: it unlinks an object from the object tree, effectively making it disappear from the game. This is convenient for moving monsters or other troublesome objects out of your way:

The Troll Room
This is a small room with passages to the east and south
and a forbidding hole leading west. Bloodstains and deep
scratches (perhaps made by an axe) mar the walls.
A nasty-looking troll, brandishing a bloody axe, blocks
all passages out of the room.
Your sword has begun to glow very brightly.

>wait
Time passes...
The axe sweeps past as you jump aside.

>bamf troll
The troll disappears with a pop.

>look
The Troll Room
This is a small room with passages to the east and south
and a forbidding hole leading west. Bloodstains and deep
scratches (perhaps made by an axe) mar the walls.
Your sword is no longer glowing.

Pilfer

pilfer is a practical implementation of two of the cardinal rules of adventure gaming:

1. Anything that is not nailed down is mine.
2. Anything that I can pry loose is not nailed down.

pilfer moves the object you specify to your current location, by making the object a child of your current room's object (rezrov knows which object represents the current room by tracking the player's movements). It then steals a turn from the player to submit a take command to move the object into the player's inventory. In this fashion any "takeable" item can be moved from anywhere in the game into your hot little hands; any object that can't actually be picked up will simply remain in the player's current location.

Like teleport, pilfer uses the context information of the object table to respond appropriately. If you pilfer something from another location, you may hear a distant rumble of thunder. Pilfering an item that's already in your inventory results in the sensation of invisible hands rummaging through your possessions. Pilfering things that are contained inside of other things produces special effects, and attempting to pilfer yourself results in ridicule. Various random messages keep things interesting.

Oh well, to be honest, the ray only has evil
applications...you know, my wife will be happy,
she's hated this whole death ray thing from day
one.
                            - Professor John Frink

Besides its obvious nefarious uses, the pilfer command raises the possibility of revealing Easter eggs in old Infocom games. I remember a maddening puzzle from the game Planetfall, involving a room that you could enter, but not see anything in. There was a lantern in the game, but it was located in a lab full of deadly radiation. You could enter the room and take the lamp, but would die of radiation poisoning in a few moves, just out of reach of where you needed it. In this way the player's natural curiosity was denied even if they sacrificed their life to get a peek. And as it turned out, you didn't need to see inside that room to finish the game. In fact, as pilfering the lamp and entering the room reveals, you were never meant to:

Transportation Supply
You have just located a serious bug.

Planetfall contains a number of these red herrings, and closes with a truly sadistic flourish: Your robotic companion Floyd rushes up, hands you several seemingly-critical items missing from the game, and tells you "maybe we can use these in the sequel."

Universal command set

Infocom made a number of revisions to the Z-machine and their interpreters, gradually adding new features which made the games more enjoyable to play. A number of these were quality-of-life concessions for weary typists, such as short aliases for certain frequently-used words; for example, x could be entered in place of examine. There was also the oops command, which allowed you to correct the spelling of a word you had mistyped on the previous line:

Figure 1

>give lmap to troll
I don't know the word "lmap".

>oops lamp
The troll, who is not overly proud, graciously accepts the
gift and not having the most discriminating tastes,
gleefully eats it.
You are left in the dark...

use Curses;

eval 'use Tk;'
# try to load the Tk module
if ($@) {
    # there was an error
    print "Your system does not have Tk.\n";
} else {
    # loaded OK
    $w = MainWindow->new;
    print "Look, a Tk reference!: $w\n";
} 

if ($zio_type eq "tk") {
    # GUI interface
    require Rezrov::ZIO_Tk;
    $zio = new Rezrov::ZIO_Tk(%FLAGS);
} elsif ($zio_type eq "win32") {
    # windows console
    require Rezrov::ZIO_Win32;
    $zio = new Rezrov::ZIO_Win32(%FLAGS);
}

Zork I (1983, Z-machine revision 3): 652 opcodes
Trinity (1986, Z-machine revision 4): 1539 opcodes
Zork: The Undiscovered Underground
  (1997, Z-machine revision 5, Inform): 2186 opcodes

#define get_byte(offset) ((zbyte_t) datap[offset])