Egyptian room

This looks like an Egyptian tomb. A stair ascends to the west. The solid-gold coffin used for the burial of Ramses II is here.

> take the coffin

Your load is too heavy.

> drop the sword

Dropped.

> take the coffin

Taken.

> go west
> go south


All right, we know that object have variably-sized properties, Boolean attributes, a parent, child and sibling, and a name. We’re going to ignore the properties and attributes for now, and decode the rest. The object table is laid out in memory like this:

  • The address of the object table is in the word beginning at byte 10 in the story header.
  • The object table begins with either 31 or 63 default values for properties. Each is two bytes.
  • After that, the object tree proper begins. Every tree entry is of the same size:
    • 32 (or 48) bits of attributes
    • the parent object number (1 or 2 bytes)
    • the sibling object number (1 or 2 bytes)
    • the child object number (1 or 2 bytes)
    • the address of a block of data containing the name and the properties

So let’s do it. Code for this episode can be found at https://github.com/ericlippert/flathead/tree/blog7

We need some wrapper types so that the compiler can catch my bugs:

type object_base = Object_base of int
type property_defaults_table = Property_defaults_table of int
type object_tree_base = Object_tree_base of int
type object_number = Object of int
type object_address = Object_address of int
type property_header_address = Property_header of int

We need to fetch the base out of the story:

let object_table_base story =
  let object_table_base_offset = Word_address 10 in
  Object_base (read_word story object_table_base_offset)

How big the default properties block is depends on the version number:

let default_property_table_size story =
  if Story.v3_or_lower (Story.version story) then 31 else 63

let default_property_table_entry_size = 2

let tree_base story =
  let (Object_base base) = Story.object_table_base story in
  let table_size = default_property_table_size story in
  Object_tree_base (base + default_property_table_entry_size * table_size)

And how big every entry is depends on the version; version 3 has 4 bytes of attributes, 3 bytes of parent, sibling, child, and 2 bytes of property header address. Version 4 has 6, 6 and 2 respectively.

let entry_size story =
  if Story.v3_or_lower (Story.version story) then 9 else 14

Given an object number, what is the address of the object table entry?

let address story (Object obj) =
  let (Object_tree_base tree_base) = tree_base story in
  let entry_size = entry_size story in
  Object_address (tree_base + (obj - 1) * entry_size)

Given an object number, what is the parent object number?

let parent story obj =
  let (Object_address addr) = address story obj in
  if Story.v3_or_lower (Story.version story) then
    Object (Story.read_byte story (Byte_address (addr + 4)))
  else
    Object (Story.read_word story (Word_address (addr + 6)))

I’m going to skip over the sibling and child; they are obvious given how we got the parent.

The last two bytes are an address of a block of properties.

let property_header_address story obj =
  let object_property_offset =
    if Story.v3_or_lower (Story.version story) then 7 else 12 in
  let (Object_address addr) = address story obj in
  Property_header (Story.read_word story (Word_address (addr + object_property_offset)))

We’ll decode the rest of the property data later; it’s complicated. But the first thing in the property data block is a byte containing the length (in words, not bytes or zchars!) of the zstring-encoded name which follows. This is so that interpreter writers can simply skip right past the name and get to the property data. Personally I would have solved this problem by putting the address of a string here rather than the string itself, but that’s not what they did.

The length is permitted to be zero, in which case the object does not have a name and there is no string data at all. To call this out I’ll return “<unnamed>”.

let name story n =
  let (Property_header addr) = property_header_address story n in
  let length = Story.read_byte story (Byte_address addr) in
  if length = 0 then "<unnamed>"
  else Zstring.read story (Zstring (addr + 1))

All right, we have done what we set out to do. Let’s display that table. We can just do what we did last time: turn each one into a string with a little helper method, and then use my accumulator loop function to loop from object one through…

Wait a moment, how many objects are there?

The story does not contain any count of how many valid objects there are. And why should it? The authors of the game know how many there are, and its not like an interpreter ever needs to loop over all the objects. However, we can guess. In practice, every story file has the property header for the properties of object 1 immediately following the last object entry. There is of course no requirement that the property block for any object be anywhere, but this convention is consistently followed so let’s take advantage of it:

let count story =
  let (Object_tree_base table_start) = tree_base story in
  let (Property_header table_end) = property_header_address story (Object 1) in
  let size = entry_size story in
  (table_end - table_start) / size

And now we can display our object table. (Valid object numbers are from 1 to count, so we abort the loop when we get to count + 1.)

let display_object_table story =
  let count = count story in
  let to_string i =
    let current = Object i in
    let (Object parent) = parent story current in
    let (Object sibling) = sibling story current in
    let (Object child) = child story current in
    let name = name story current in
    Printf.sprintf "%02x: %02x %02x %02x %s\n"
      i parent sibling child name in
  accumulate_strings_loop to_string 1 (count + 1) 

And we can call this in our main routine:

let table = Object.display_object_table story in
  Printf.printf "%s\n" table

to get the object table:

01: 24 93 00 forest
02: 1b 77 5f Up a Tree
03: 24 b3 00 water
04: 2d 5a 00 pair of hands
05: 1b 2e 00 Inside the Barrow
06: a1 98 00 control panel
07: 1b a5 29 Dome Room
08: 37 00 00 torch
09: ac 32 00 jade figurine
0a: 44 00 00 lunch
0b: 1b 57 70 Round Room
0c: a1 00 00 matchbook
0d: 2d 6d 00 brave adventurer
0e: 1b 49 00 Maze
0f: 1b 72 00 Canyon View
10: 88 00 00 parchment map
11: 8c 4b 00 pair of candles
...

Which is great, but clearly these are in no particular order and it is very difficult to see the tree structure here.

Next time on FAIC: we’ll re-organize that into a tree.

Advertisements

6 thoughts on “Egyptian room

  1. I think it may not be the best solution to let the name function return a special string if the object is unnamend.
    In F# I would have the fuction return a Option value, either Some string or None. (Has OCaml a build in Option or Maybe type?).
    The display code then should decide what to display in the case of None. Taht separates the domain logic from the display logic
    Thank you for your blog, It is ón of my favorite regular readings. .

    • Yes, OCaml has an option type built in, and it uses Some and None constructors as you describe.

      I considered using an option type here; I think it’s a reasonable choice. As you say, the caller can then decide what the default value should be, if any.

  2. I just want to say I’m tremendously enjoying this series, including the little snippets of adventure at the start, the excellent explanations, and most notably the frequent posting schedule. Thanks a lot Eric; I’m looking forward to the next one!

  3. Pingback: The Morning Brew - Chris Alcock » The Morning Brew #2044

  4. Pingback: Altar | Fabulous adventures in coding

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s