Altar

Standing by the temple’s altar, you can see a small hole in the floor which leads into darkness. The rest of the temple is north of here.
On the two ends of the altar are burning candles.
On the altar is a large black book, open to page 569.

> go down

You haven’t a prayer of getting the coffin down there.

> pray


This is getting exciting. Last time we managed to spit out the object tree, but in a manner that was quite difficult to read. Let’s fix that.

Code for this episode can be found here: https://github.com/ericlippert/flathead/tree/blog8

And oh my goodness, we have been programming in a purely functional style in OCaml for weeks now and have yet to see so much as a single list! Lists are traditionally the data structure you use for nigh everything in functional languages, starting from Lisp on down. Let’s look at how lists are represented in OCaml first, and then we’ll reorganize that tree structure.

Lists are recursively defined, as you might imagine. The empty list is a list, and is notated []. There are two ways to notate non-empty lists. You can either notate a list as “here’s the head, an element, and here’s the tail, a list”:

1 :: []

That would be the list with one element at the head, and an empty tail. Since that is a list, it can be the tail of another list:

3 :: 1 :: []

That list has two elements. 3 is at the head, and 1 :: [] is the tail.

Since this syntax is somewhat bulky for large lists there is a sugar:

[ 3; 1 ]

is another syntax for the same list.

Lists work extremely well with pattern matching because both of these syntaxes may be used as a pattern. We’ll see plenty of examples of that in later episodes. For now we’ll stick with just plain list construction.

The first thing I’m going to need is a list of every “root” object — that is, all the objects where the parent is the invalid object.

let roots story =
  let rec aux obj acc =
    let current = Object obj in
    if current = invalid_object then
      acc
    else if (parent story current) = invalid_object then
      aux (obj - 1) (current :: acc)
    else
      aux (obj - 1) acc in
  aux (count story) []

All right, once again we are using this auxilliary function as a looper, but this time instead of passing in an empty string as the accumulator, we pass in an empty list to start with. Objects are numbered from 1 to count, so we start with count and loop until we get down to zero. Every time through the loop we ask “is the current object parentless?” If it is then we recurse, having prepended the root object to our accumulation. If not, then we recurse without prepending.

Though this time we are doing two recursions, we are still tail recursive here because for both, the recursion is the last thing the function does. And for that matter we could easily have rewritten it to use one recursion:

    else 
      let new_acc = 
        if (parent story current) = invalid_object then current :: acc 
        else acc in
      aux (obj - 1) new_acc in

Whatever; doesn’t matter to me. Point is that we recursively construct a list containing all the root objects.

Now suppose we have a root object, any root object. How are we going to print that as a tree?

  let rec aux acc indent obj =
    if obj = invalid_object then
      acc
    else
      let name = name story obj in
      let child = child story obj in
      let sibling = sibling story obj in
      let object_text = Printf.sprintf "%s%s\n" indent name in
      let with_object = acc ^ object_text in
      let new_indent = "    " ^ indent in
      let with_children = aux with_object new_indent child in
      aux with_children indent sibling in
  let to_string obj =
    aux "" "" obj in

What’s our strategy here? We solve the problem recursively. Every recursive solution has the same form: if you can solve the problem without recursion do so, otherwise reduce it to one or more smaller problems, solve each recursively, and then combine the solutions. This is no different.

The base case is: if we are trying to print out an invalid object then just produce the accumulated state.

If not, then we have two smaller problems to solve. First, accumulate the printed tree for all my children, indented more. Next, accumulate the printed tree for all my siblings, indented the same as me.

So we can produce such a string for any object, but we want to produce such a string for all the roots. How can we do that? This seems very similar to the problem I’ve already solved: doing so for a sequence of integers that map to strings. Now I want to do it for a list of objects that map to strings.

The standard library for lists has a powerful function called fold_left that will seem very familiar if you’ve been paying attention to how my string accumulator works. A fold operation takes a list, an accumulation value, and a function that maps an element of the list and an accumulation onto a new accumulation. It then applies that function in turn to every element of the list. For example:

let accumulate_strings to_string items =
  let folder text item =
    text ^ (to_string item) in
  List.fold_left folder "" items

Here I have another little helper method. As with my looping string accumulator, it takes a to_string function, but this function does not (necessarily) take an integer. Rather, it takes an element of the list of items I’ve given, and produces some value.

We then define another little nested helper function that takes text – the accumulated state – and an item from the list. It produces a new accumulated state by turning that item into a string, and concatenating the result onto the accumulation.

That little function is then passed to fold_left, which starts with an empty string and calls the folder on every item in the list. So what happens is, the folder calls to_string on every element of the list, and concatenates up all the strings as it goes.

Putting it all together, we have

let display_object_tree story =
  let rec aux acc indent obj =
    if obj = invalid_object then
      acc
    else
      let name = name story obj in
      let child = child story obj in
      let sibling = sibling story obj in
      let object_text = Printf.sprintf "%s%s\n" indent name in
      let with_object = acc ^ object_text in
      let new_indent = "    " ^ indent in
      let with_children = aux with_object new_indent child in
      aux with_children indent sibling in
  let to_string obj =
    aux "" "" obj in
  accumulate_strings to_string (roots story)

Isn’t that lovely? And now we can call it:

let tree = Object.display_object_tree story in
  Printf.printf "%s\n" tree

and see the entire object tree laid out for us:

...
    Altar
        altar
            pair of candles
            black book
    Egyptian Room
        gold coffin
            sceptre
    Temple
        prayer
        brass bell
        pedestal
            torch
    Dome Room
        wooden railing
...

Holy goodness, there is a sceptre in the coffin! That might come in handy.

Next time on FAIC: We’ve decoded the dictionary and the object table, which are the primary data structures of the story file. (I am not counting the parsing tables because those are entirely the business of the game developer; I probably will not decode the parsing tables in this series, but we’ll see.) Let’s get on to the real heart of the matter and start looking at code.

Advertisements

3 thoughts on “Altar

  1. Pingback: Egyptian room | Fabulous adventures in coding

  2. Pingback: The Morning Brew - Chris Alcock » The Morning Brew #2046

  3. Pingback: Forest edge | 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