1. Computing

Finding and Moving Nodes

By

Finding and Moving Nodes
Making a Text Adventure Game in Ruby

Finding Nodes

This article is part of the series Making Text Adventure Games in Ruby. The example code for this article can be downloaded here.

You've just dropped your keys. Or at least that's what the game told you, but what really happened is the game moved the keys node from the player node to the living room node. Virtually every interaction in an interactive fiction game involves finding a node and moving it from one place to another.

Finding nodes will become extremely important. You'll need to be able to do things like "find the node with the tag :kitchen" or "find the new batteries" and come back with a Node object of some kind.

One thing you'll notice is that with this data structure, finding nodes will be very simple. Start at the root of the tree (or any other node, such as the room the player is in) and if this is the node you're looking for then return that node. Otherwise, repeat the search on all of the child nodes. Recursion is used to iterate the trees just as in the previous article when printing the graphs.

We'll also want a find method that just knows what to do with whatever we send at it. If we send a symbol, we want to search for the node with a matching tag. If we send a string of space-separated words, we want to find a node with a matching name and attributes. This also mirrors how the find methods will be used: your definition and script code will find things by tag since you know the tag by looking at the game data, but users don't have this information, and will find things by words. Also note that since only items have describing words, the player can only really find items, so he can't accidentally pick up and carry around the living room. This Node#find method starts out as little more than a switch statement.


class Node < OpenStruct
  def find(thing)
    case thing
    when Symbol
      find_by_tag(thing)
    when String
      find_by_string(thing)
    when Node
      thing
    end
  end
end

The find_by_tag method is rather straightforward. Just walk over the tree and, if you find a node with a matching tag, return it. There isn't supposed to be more than one node with the same tag, so only the first match in the depth-first search will be returned. If no node is found, return nil.


class Node < OpenStruct
  def find_by_tag(tag)
    return self if self.tag == tag

    children.each do|c|
      res = c.find_by_tag(tag)
      return res unless res.nil?
    end

    return nil
  end
end

The find_by_string method is a little more complicated. Given a space separated list of words in a string, it must find all nodes whose name (and since it has a name, it must be an item) is included in the words. You're left with an array of nodes you must score and evaluate. To score them, we count the number of words in the input and in the adjectives for the object there are in common. Then we just sort them so the highest score is first in the list, then delete any other nodes from the list with a lower score. If you're left with one object, that's the one you're looking for. If you're left with more than one object, there aren't enough adjectives to complete the search and, since this method will be used directly by the user, tell then which items it found and their adjectives.

But first, the find_by_name method which the find_by_string method uses. It's very similar to find_by_tag, but finds all matching nodes and returns an array of them.


class Node < OpenStruct
  def find_by_name(words, nodes=[])
    words = words.split unless words.is_a?(Array)
    nodes << self if words.include?(name)

    children.each do |c|
      c.find_by_name(words, nodes)
    end

    return nodes
  end
end

And now onto the find_by_string method itself. It's a bit long, but there are comments to remind you of what's going on. The only "clever" bit is how the matches are scored. The code (words & i.words).length takes the union of two arrays (gets an array of all the elements they have in common) and gets its length. In other words, counts how many words the two lists have in common.


class Node < OpenStruct
  def find_by_string(words)
    words = words.split unless words.is_a?(Array)
    nodes = find_by_name(words)

    if nodes.empty?
      puts "I don't see that here"
      return nil
    end

    # Score the nodes by number of matching adjectives
    nodes.each do |i|
      i.search_score = (words & i.words).length
    end

    # Sort the score so that highest scores are
    # at the beginning of the list
    nodes.sort! do |a,b|
      b.search_score <=> a.search_score
    end

    # Remove any nodes with a search score less
    # than the score of the first item in the list
    nodes.delete_if do |i|
      i.search_score < nodes.first.search_score
    end

    # Interpret the results
    if nodes.length == 1
      return nodes.first
    else
      puts "Which item do you mean?"
      nodes.each do |i|
        puts " * #{i.name} (#{i.words.join(', ')})"
      end
      
      return nil
    end
  end
end

Convenience

To facilitate finding and manipulating nodes, we need to write a few convenience functions: the get_room and get_root methods. These methods traverse the tree upwards until a room or the root node is found. We'll need this to be able to refer to the root node from any point in the tree, and to refer to the room that a node is in. You might think the get_room method is silly, an item's parent node is the room, right? Why not just use the parent pointer we already have? Remember that items themselves are also nodes that can have children. The dead mouse's parent is the cat, not the living room.


class Node < OpenStruct
  def get_room
    if parent.tag == :root
      return self
    else
      return parent.get_room
    end
  end

  def get_root
    if tag == :root || parent.nil?
      return self
    else
      return parent.get_root
    end
  end
end

Hidden Items

As noted before, items can contain other items. But not all items can hold any other item. It doesn't make any sense to put the batteries in the knife, so we need some way of designating which items are containers, and can hold other items. Note that we won't be covering which items containers can and cannot hold just yet, that's covered in the scripting section.

By default, item nodes are not containers. If an item node is a container, it should set its open key to true. If the node's open key is false, it's either not a container or it's not open at the present time. This is an important point. If you try to pick up the dead mouse when it's currently inside the cat (a decidedly closed container), it just won't work (and the player's face item will now have the adjectives "scratched" and "bleeding"). A "hidden" node is any node that has a closed ancestor node. The mouse is a hidden node, so it cannot be taken by the player.


class Node < OpenStruct
  def hidden?
    if parent.tag == :root
      return false
    elsif parent.open == false
      return true
    else
      return parent.hidden?
    end
end

Moving Nodes

Moving nodes from one parent node to another parent node is, at its heart, really the only thing that matters in a text adventure game. You might think that finally taking the holy grail into your possession is a huge thing, but for the game it just changed the holy grail's parent reference to the player.

There's only one thing that stands in the way of moving a node from one parent to another: if the item is hidden (and therefor not reachable by the player), or if the destination is hidden or note open. The rest of the method is straightforward: simply remove the item from the parent's children, change the parent pointer on the item and add it to its new parent's children.

And remember that the find method can be called on any node, not just the root node. So, imagine a typical text adventure situation: take brass lantern. What this is really telling the text adventure engine is to find the player (the thing taking the brass lantern) and, from its parent node (the room the player is in) search for the brass lantern. If it found the brass lantern and it's not hidden, move it from the room (or whatever container it was in) to the player.

Also, a check parameter is included. If false, it will skip the checks for hidden items or container objects. This is here to aid scripting so it can move things around behind the scenes that wouldn't otherwise make sense to move. It has a default value of true though, so you can just ignore it for now.


class Node < OpenStruct
  def move(thing, to, check=true)
    item = find(thing)
    dest = find(to)

    return if item.nil?
    if check && item.hidden?
      puts "You can't get to that right now"
      return
    end

    return if dest.nil?
    if check && (dest.hidden? || dest.open == false)
      puts "You can't put that there"
      return
    end

    item.parent.children.delete(item)
    dest.children << item
    item.parent = dest
  end
end

Apart from the few checks at the beginning, that's just three lines of code. And probably the most important three lines of code in the entire game engine. In the next article, we'll look at implementing the player node and finally have a semi-playable game.

  1. About.com
  2. Computing
  3. Ruby
  4. Tutorials
  5. Text Adventure Games
  6. Finding and Moving Nodes

©2014 About.com. All rights reserved.