Putting the text in 'text adventures'

Decoding text so it can be displayed on-screen is something the Z-machine has to do a lot of. Let's see how it's done:

Firstly, text in a z-machine story file is stored in an encoded format where every two bytes represents three five-bit 'z-characters', each with values of 0-31. These z-characters are decoded into ZSCII characters, a character encoding scheme similar to ASCII. The algorithm used to convert z-characters to ZSCII varies somewhat in Z-machine versions 1 through 3, making it awkward to implement cleanly using an inheritance model like I have chosen.

First we convert the encoded text into z-characters.


protected ImmutableStack<byte> EncodedTextToZCharacters(ref int address)
{
  ushort character;
  ImmutableStack<byte> characters = null;
  var storyLength = this.StoryLength;
  do
  {
    if (address >= storyLength)
    {
      this.FrontEnd.ErrorNotification(ErrorCondition.InvalidAddress, "Encoded text does not end before the end of memory.");
      break;
    }

    character = this.Memory.ReadWord(address);
    characters = characters.Add((byte)(character >> 10 & 31));
    characters = characters.Add((byte)(character >> 5 & 31));
    characters = characters.Add((byte)(character & 31));
    address += 2;
  }
  while ((character & 32768) == 0);
  return characters.Reverse();
}

You may notice that three five-bit values per two bytes leaves one bit unused, this bit is set to mark the end of the text as no other length indicator is given. Once we have our z-characters, we can convert them to ZSCII. The common parts of the algorithm use the following method which in turn calls a virtual method by the same name containing the version specific differences.

protected ImmutableStack<Zscii> ZCharactersToZscii(bool calledRecursively, ImmutableStack<byte> zcharacters)
{
  byte lockedAlphabet = 0;
  byte nextAlphabet = 0;
  ImmutableStack<Zscii> zsciiText = null;
  while (zcharacters != null)
  {
    var currentAlphabet = nextAlphabet;
    nextAlphabet = lockedAlphabet;
    var zcharacter = zcharacters.Top;
    zcharacters = zcharacters.Tail;
    this.ZCharactersToZscii(calledRecursively, zcharacter, currentAlphabet, ref nextAlphabet, ref lockedAlphabet, ref zcharacters, ref zsciiText);
  }
  return zsciiText.Reverse();
}

This method loops through all the z-characters, building up the zscii text as it goes. Alphabet values range from 0 to 2 and affect the meaning of an individual z-character. Initially the alphabet is zero but can be shifted for a single character (changing nextAlphabet) or shift-locked (changing lockedAlphabet). The calledRecursively parameter is used in version 2 and above as we'll see in a bit. Next we'll see the actual decoding as it is done in version 1.

protected virtual void ZCharactersToZscii(bool calledRecursively, byte zcharacter, byte currentAlphabet, ref byte nextAlphabet, ref byte lockedAlphabet, ref ImmutableStack<byte> zcharacters, ref ImmutableStack<Zscii> zsciiText)
{
  switch (zcharacter)
  {
    case 0:
    zsciiText = zsciiText.Add(Zscii.Space);
    break;
    case 1:
    zsciiText = zsciiText.Add(Zscii.NewLine);
    break;
    case 2:
    case 3:
    nextAlphabet = (byte)((lockedAlphabet + zcharacter - 1) % 3);
    break;
    case 4:
    case 5:
    nextAlphabet = lockedAlphabet = (byte)((lockedAlphabet + zcharacter) % 3);
    break;
    default:
    if (zcharacter == 6 && currentAlphabet == 2)
    {
      if (zcharacters.Count() > 1)
      {
        zsciiText = zsciiText.Add((Zscii)((zcharacters.Top * 32) + zcharacters.Tail.Top));
        zcharacters = zcharacters.Tail.Tail;
      }
      else
      {
        zcharacters = null;
      }

      break;
    }

    zsciiText = zsciiText.Add(this.GetZsciiAlphabetCharacter((byte)((currentAlphabet * 26) + zcharacter - 6)));
    break;
    }
  }

  return zsciiText.Reverse();
}

As you can see, z-characters 0 and 1 are translated to 'space' and 'newline' respectively. Values 2 and 3 are single character alphabet shifts while 4 and 5 are shift locks. With a single exception, all other values are converted to zscii by subtracting 6 and adding 26 times the current alphabet number. The exception to this is the z-character 6 when the current alphabet is 2, which represents an escape sequence. In this case the zscii value is determined by the next two z-characters and is calculated as 32 times the first z-character plus the second. Next is version 2, which adds a new feature called abbreviations.

protected override void ZCharactersToZscii(bool calledRecursively, byte zcharacter, byte currentAlphabet, ref byte nextAlphabet, ref byte lockedAlphabet, ref ImmutableStack<byte> zcharacters, ref ImmutableStack<Zscii> zsciiText)
{
  if (zcharacter == 1)
  {
    this.AppendAbbreviation(zcharacter, calledRecursively, ref zcharacters, ref zsciiText);
    return;
  }

  base.ZCharactersToZscii(calledRecursively, zcharacter, currentAlphabet, ref nextAlphabet, ref lockedAlphabet, ref zcharacters, ref zsciiText);
}

Z-character 1 is no longer a newline, but instead represents an abbreviation decoded in the following method.

protected void AppendAbbreviation(byte zcharacter, bool calledRecursively, ref ImmutableStack<byte> zcharacters, ref ImmutableStack<Zscii> zsciiText)
{
  if (calledRecursively)
  {
    this.FrontEnd.ErrorNotification(ErrorCondition.NestedAbbreviation, "Nested abbreviation detected.");
    return;
  }

  if (zcharacters != null)
  {
    var abbreviationNumber = ((zcharacter - 1) * 32) + zcharacters.Top;
    zcharacters = zcharacters.Tail;
    var abbreviationsTableAddress = this.Memory.ReadWord(24);
    var abbreviationAddress = 2 * this.Memory.ReadWord(abbreviationsTableAddress + (2 * abbreviationNumber));
    var abbreviation = this.ZCharactersToZscii(true, this.EncodedTextToZCharacters(ref abbreviationAddress));
    foreach (var zsciiCharacter in abbreviation.Enumerable())
    {
      zsciiText = zsciiText.Add(zsciiCharacter);
    }
  }
}

An abbreviation is essentially just another encoded string which needs to be decoded separately and appended to the text we've decoded so far. After looking up the location of the text we end up calling our first method recursively (remember that parameter?) The calledRecursively parameter allows us to detect the situation where an abbreviation contains another abbreviation, which is illegal according to the Z-machine standard and could potentially lead to an endless loop otherwise. Lastly, version three expands the number of possible abbreviations and alters the behavior of alphabet shifts.

protected override void ZCharactersToZscii(bool calledRecursively, byte zcharacter, byte currentAlphabet, ref byte nextAlphabet, ref byte lockedAlphabet, ref ImmutableStack<byte> zcharacters, ref ImmutableStack<Zscii> zsciiText)
{
  switch (zcharacter)
  {
    case 1:
    case 2:
    case 3:
    this.AppendAbbreviation(zcharacter, calledRecursively, ref zcharacters, ref zsciiText);
    break;
    case 4:
    case 5:
    if (currentAlphabet == 0)
    {
      nextAlphabet = (byte)(zcharacter % 3);
      break;
    }

    nextAlphabet = lockedAlphabet = (byte)(currentAlphabet - ((zcharacter - currentAlphabet) % 3));
    break;
    default:
    base.ZCharactersToZscii(calledRecursively, zcharacter, currentAlphabet, ref nextAlphabet, ref lockedAlphabet, ref zcharacters, ref zsciiText);
    break;
  }
}

This implementation allows shift locks in version 3 caused by consecutive single shifts, although the 1.1 standard disallows it. Many (all?) of Infocom's version 3 and later interpreters did this which is the reason I included it.

That's it. The resulting ZSCII is mostly ready to be displayed. I say mostly because some ZSCII values fall in what is called the 'extra characters' range, outside the standard ASCII printable characters and used primarily to display accented characters and the like. These are easily converted to unicode via a simple lookup.

Design decisions

This post is long overdue and was originally going to feature my code for playing sounds in the Z-machine. That will have to wait however as I've recently been making some significant changes to my Z-machine library and the sound code faces some significant rewriting.

Supporting all eight Z-machine versions in one codebase is an interesting challenge. Back when I first started this project, I had one class which encompassed every version. It was filled with hundreds of if/else statements and switches which directed behavior based on the machine version. This worked well enough, but was a mess to look at and maintain. After some time I decided to use an inheritance model to separate the behavior of each version. This helped me clean up the code as well as fix a few bugs which were hidden before.

One thing that became clear to me as I refactored my code was that my original design, in the interest of typing less code, had actually created a sort of hybrid machine where capabilities of later versions are actually available to earlier ones. An interpreter can get away with this sort of design by relying on the fact that earlier games will not try to use these capabilities, as I mentioned during my last post. Indeed, I think this approach is fairly common among Z-machine interpreters. While this is fine from a practical point of view of running games. I've recently come to the conclusion that it is poor from a code-as-documentation standpoint. If we had to reverse engineer existing interpreters to reproduce the Z-machine standards document, a hybrid machine would give us a badly distorted picture. Theoretically, it could also encourage the development of games that use capabilities not properly belonging to a given version. Because of this I've decided to adopt a more strict interpretation of the specification and make the appropriate changes to my library.

Moving to an inheritance model has helped me improve my code a lot, but it hasn't all been a cure all. There are a few methods, namely converting between Z-characters and ZSCII which don't lend themselves easily to inheritance. Key pieces of the algorithms change between versions, which makes it difficult to implement them as virtual/override methods and leads to blocks of repeated code. This is the exception however, and the overall improvement in the code has been substantial.

I still have some refactoring to do to implement my latest design changes, but I hope to make my source code available soon.