Ramblings

05 Sep, 2008

A “grue”some look at Statemachine and Treetop

Posted by: Matt Williams In: games| gotchas| ruby

In this blog entry, dear reader, we examine the statemachine and treetop gems via an old standby, a Zork imitation. And, despite the title, you won’t find a grue.

$ ruby adventure.rb
This is the beginning. Like all tales, there's a beginning, a middle and an
end....

Paths lead n.

What do you want to do?
n

This is a path in the forest, it looks fairly well travelled.  You see a
clearing to the east

Paths lead w, n, e, s.

What do you want to do?
e

This is a clearing.  You can actually see the sky here.  Compared to the deep
dark forest, it seems a relief. A path can be seen to the west.

Paths lead w, n, e, s.

You see the following: letter.

What do you want to do?
get letter

Ok, you pick up the letter.

What do you want to do?
w

This is a path in the forest, it looks fairly well travelled.  You see a
clearing to the east

Paths lead w, n, e, s.

What do you want to do?
w

You're lost in the depths of the forest.  You're not sure where you are, nor how
to get out of there.

Paths lead w, n, e, s.

What do you want to do?
quit

Statemachine is used for creating, as you no doubt have guessed, statemachines. Treetop is a parser generator. A zork-like game is a fairly useful simple example of how to use both.

Statemachine

Let’s start with a state diagramme:

Basically we have three states: Begin, Main, and Done. We can transition from one state to another in a variety of ways, as shown by the arrows. The text with the transition shows the events which can trigger the transition. Statemachine uses two basic types of statements to describe these state changes (what follows is simplified from the actual code):

    def setup_machine
      @machine = Statemachine.build do
        trans :start, :begin, :main, :enter
        state :main do
          event :move, :main, :move
          on_entry :check_if_transition_needed
        end
        context AdventureContext.new()
      end
      @machine.context.statemachine = @machine
    end

trans is used to move from one state to another upon the receipt of an event. Thus,
trans :start, :begin, :main, :enter can be interpreted as “From the start state, transition to the main state when you receive a begin event. In so doing, invoke the enter method.”
Likewise, the block starting with state :main contains code which handles events, as well as invoking a method (check_if_transition_needed) on entrance of the state. event :move, :main, :move may be read as “Within the context of the main state, when a move event is received, transition to main, invoking the move method.”

The check_if_transition_needed is something of a hack — without it setting the state within a state transition wasn’t working properly (so we couldn’t go to the “done” state and exit).

The invoked methods are performed by the object which is declared to be the context — namely an instance of AdventureContext. The last line, @machine.context.statemachine = @machine, allows our context to interract with the statemachine.

Grammar

I’ve chosen to use treetop for my grammar. Let’s take a look at the grammar:

grammar Adventure
 
# The commands fall in these categories
   rule command
     describe_inside / describe / help / move / quit / take / put / inventory
   end
 
 # nodes must always be parenthesized to be associated with a block
  rule help
    ("help" / "help" space name) {
     def eval(statemachine)
       statemachine.send(:help)
     end
    }
  end
 
  # This is a convenience method; to declare what a name is
  rule name
    ([A-Z] [a-z]*) / [a-z]+
  end
 
  # Likewise, this declares spaces -- it makes the grammar easier to read
  rule space
    ' '+
  end
 
  # This one's a little complex; we can match two forms
  rule take
   ((take_verb space item take_from) / (take_verb space item) ) {
     def eval(statemachine)
        if (self.respond_to? :take_from)
           statemachine.send(:take_from, item.text_value, take_from.container.text_value)
        else
           statemachine.send(:take, item.text_value)
        end
     end
   }
  end
 
  rule take_from
    space out space container
  end
 
  # This one's a little complex; we can match two forms
  rule put
   ((put_verb space item put_into) / (put_verb space item) ) {
     def eval(statemachine)
        if (self.respond_to? :put_into)
           statemachine.send(:put_into, item.text_value, put_into.container.text_value)
        else
           statemachine.send(:put, item.text_value)
        end
     end
   }
  end
 
  rule put_into
    space into space container
  end
 
  rule inventory
   ( "inventory" / "i" ) {
      def eval(statemachine = nil)
          statemachine.send(:inventory)
      end
   }
  end
 
  rule describe_verb
    "describe" / "look" / "examine"
  end
 
  rule something
   space "at"? space* name
  end
 
  rule describe_inside
    describe_verb space into space name {
      def eval(statemachine = nil)
        statemachine.send(:look, name.text_value, true)
      end
    }
  end
 
  rule describe
   ( (describe_verb something) / (describe_verb) ) {
       def eval(statemachine = nil)
          thing = (self.respond_to? :something) ? something.name.text_value : nil
          statemachine.send(:look, thing)
       end
     }
  end
 
  rule quit
     "quit" {
        def eval(statemachine)
          statemachine.send(:quit)
      end
     }
   end
 
  rule move
    (direction / "go" space direction / "move" space direction) {
      def eval(statemachine)
        direction ||= text_value.downcase
        statemachine.move(direction)
      end
    }
  end
 
  rule direction
    ( 'north' / 'south' / 'east' / 'west' / [nsew] ) {
      def eval(statemachine)
        statemachine.move(text_value.downcase)
      end
    }
  end
 
  rule out
    "from" / ("out" space "of") / "out"
  end
 
  rule item
    name
  end
 
  rule container
   name
  end
 
  # Below the order is very important -- it matches the first thing
  # so in needs to come last, otherwise it can't match
  # 'into' or 'inside'
  rule into
    "into" / "inside" / "in"
  end
 
  rule take_verb
    "take" / "get"
  end
 
  rule put_verb
    "put" / "place" / "drop"
  end
 
end

All grammars start with the keyword grammar and the word which follows is the name used for the parser’s class. So, grammar Adventure creates an AdventureParser class. Within the grammar block exist a series of rules. Personally, I think that they’re easier to understand than BNF.

One interesting piece that caused me some grief — the rules are order dependant. If you have a rule that can match “in” or “inside”, “inside” has to come before “in” — otherwise it will error when you try to parse “inside”. However, in debugging parsers, irb is very helpful:

$ irb
&gt;&gt; require 'rubygems'
=&gt; true
&gt;&gt; require 'treetop'
=&gt; true
&gt;&gt; Treetop.load('adventure')
=&gt; AdventureParser
&gt;&gt; p = AdventureParser.new
=&gt; #
&gt;&gt; p.parse "look outside backpack" #this should fail
=&gt; nil
&gt;&gt; p.failure_reason
=&gt; "Expected one of  , into, inside, in, at at line 1, column 6 (byte 6) after "
&gt;&gt; p.parse "look inside backpack"
=&gt; SyntaxNode+DescribeInside1+DescribeInside0 offset=0, "look inside backpack" (describe_verb,space,eval,name,into):
  SyntaxNode offset=0, "look"
  SyntaxNode offset=4, " ":
    SyntaxNode offset=4, " "
  SyntaxNode offset=5, "inside"
  SyntaxNode offset=11, " ":
    SyntaxNode offset=11, " "
  SyntaxNode offset=12, "backpack":
    SyntaxNode offset=12, "b"
    SyntaxNode offset=13, "a"
    SyntaxNode offset=14, "c"
    SyntaxNode offset=15, "k"
    SyntaxNode offset=16, "p"
    SyntaxNode offset=17, "a"
    SyntaxNode offset=18, "c"
    SyntaxNode offset=19, "k"
&gt;&gt;

There are other methods to use for finding failures, but failure_reason is very helpful most of the time. However, if there’s an issue with grammar, such as “in” coming before “inside” it has issues.

Locations and Items

I have chosen to set up my map within a yaml file. It’s split into two pieces — the first defines the locations and the second the items and their properties. In order to keep my yaml file as dry as possible, I’m only including things that are “special” about a location or an item — things which differ from the defaults.

Locations have the following properties:

Property	Default	Description
name (inferred)	“”	Location’s name
description	“”	Description of the location
paths	[]	Paths away from the current location
items	[]	Items which are contained in this location
transition	nil	Any transitions which might occur from moving to this location — these include victory or failure conditions.

So a location might look like this in the yaml file:

---
locations:
  start:
    description: "This is the beginning. Like all tales, there's a beginning, a middle and an end...."
    paths:
      n: forest_path

Items have the following properties:

Property	Default	Description
name (inferred)	“”	The name of the item
description	“”,	The description
take	true,	Can the item be taken?
container	false,	Can the item hold other items?
droppable	true	Can the item be dropped?

So an item might look like this:

---
items:
  letter:
    description: "It's an old letter.  It is addressed and has an uncancelled stamp."

The Source

Finally we have our source code. It’s pretty straightforward, so I’ll not talk about it here, but if anyone has questions, please comment.

Running the Code

First off, be sure you’ve installed the treetop and statemachine gems. You can do so via:

sudo gem install statemachine
sudo gem install treetop

From there you can download the files and unarchive them into a directory. adventure1.tgz

Then run it via

ruby adventure.rb

Where to go from here?

Well, there’s a few things to add…. Save and restore for one. Scoring for another. Combat, if you wanted as well. But as a demonstration of statemachine and treetop, I think this does a pretty good job.

EDIT: Fixed an error in adventure.rb