Previous Top Next


An adventure game's parser is the part of the code that's responsible for trying to make sense of the user's typed commands, and transforming those English instructions into operations to be performed on all the data structures described in the previous nodes, the rooms, the travel tables, and the objects.

Many games, like Infocom's Zork had sophisticated parsers able to handle fairly complicated grammar. This is not an easy thing to do. And, of course so far, nobody has managed to make a parser which is "perfect". You can generally always find a hole in them someplace, usually quite easily.

For purposes of this write-up, I'm not going to describe the world's most sophisticated parser, I'm going to keep things really simple. I will talk about some of the complications and some of the features of more complex parsers, and some things you might want to try, but real natural language processing is beyond the scope of these nodes.

Before jumping right in, it helps to take a look at some of the typical things a user might type into an adventure game.

> take lantern, matches, sword
> light lantern 
> kill troll
> inventory
> jump

These are the kinds of input that the parser in the sample code can handle, so I'll start by describing how that's done, and then move on to more complicated sentences.

There are a couple of things to notice about these "sentences.".

  • each "sentence" begins with a verb.
  • each "sentence" is followed by zero of more nouns (objects).

Believe it or not, with just that, you can get pretty far.

So one possible scheme for a simple parser would go something like this:

  1. Use (something like) the C library's "strtok" function to break up the input into "words".
  2. Look up the first word in a table of verbs.
  3. if the verb is not known, bail out and get another command.
  4. Take the remaining words to be objects. Look each one up in the object table. Make a list of the object numbers. If some word is unknown, bail out.
  5. Depending on what the verb is, call a corresponding C function, and pass it the list of object numbers. Each verb should have a function that examines the list of objects and "does the right thing".

    This is essentially what the parser in the sample code does. For each verb, the program has an instance of the following structure:

    struct verb_t {
            char *word;     /* "go", "take", etc. */
            void (*f)(void *game, int *objlist); /* C func to call */
    };
    

    The character pointer "word" is the string representation of the word, and "f" is a pointer to the C function to be called for that verb. The funciton takes a void pointer, which is used for the "game state", a structure that simply acts as a container for the object list, room list and player, that is, it is a single pointer that leads to the entire state of the game. The objlist is a pointer to an int, actually, a pointer to the zeroth element of an array of ints. This is the list of object numbers that gets passed to each "verb function".

    So what do these "verb functions" actually do, what is the "right thing" so casually mentioned in step number 5, above?

    So, first let's consider the verb "take". If someone said to you "take!", you'd probably say, "take what?". "Take" requires at least one object, the object to be "taken". So, assuming some number of objects are specified to be taken, ("take apple" for instance), what does the verb function for "take" need to do?

    Well, first it needs to check that the object is lying around someplace within reach, that is, check that it's location is the same as the player's location. Second, it needs to make sure that the object isn't something huge like the Washington Monument. Once those two conditions are satisfied, ordinarily, the object may be taken. How? By setting it's location to zero. Remember, room zero is reserved to mean the player's pocket.

    So, some really simple code for the "take" function might look something like this:

    void take(int *obj)
    {
            int *i;
    
            for (i=obj;*i!=-1;i++) /* for each object */
            {
                    if (object[*i].location != player.location) {
                            printf("%s: that isn't here.\n",
                                    object[*i].short_name);
                    } else
                    if (!object[*i].portable) {
                            printf("%s: cannot be taken.\n",
                                    object[*i].short_name);
                    } else
                    {
                            object[*i].location = 0;
                            printf("%s: Taken\n",
                                    object[*i].short_name);
                    }
            }
    }
    

    So that's it for "take". "Drop" is very easy also. Just check that the object is currently in the player's possession, (that location is zero) and change it's location to the player's current location. That's it.

    What about "go" as in "go north"? A simple trick here is to have the first ten objects in the object list correspond to the ten directions in the travel table. That way the object number can be used directly as an index into the travel table. Some simple code for "go" might look something like this:

    void go(int *obj)
    {
            int *i;
            if (*obj == -1) { /* "go" by itself */
                    printf("go which way?\n");
                    return;
            }
    
            for (i=obj;*i != -1;i++)  /* for each direction... */
            {
                    if (*i > 9) { /* go pizza? huh? nonsense. */
                            printf("I don't understand...\n");
                            return;
                    }
    
                    /* is that direction passable? */
                    if (room[player.location].tt[*i] == -1) {
                            printf("You can't go that direction.\n");
                            return;
                    }
                    /* ok, go ahead and move them. */
                    player.location = room[player.location].tt[*i];
            }
    }
    

    Another important verb for adventure games is "look". This is what it used to get the program to describe the room, what objects are around, and what directions it is possible to move from here. In pseudocode:

    1. Description: print room[player.location].description
    2. Objects: for each object i, if object[i].location = player.location print object[i].description
    3. Exits: for each i in room[player.location].tt[i], if it's not -1, print object[i].short_name

    To implement "inventory", just scan the list of objects and print out those which are in location zero.

    You should be getting the hang of this now, it's pretty simple.

    For objects which you want the parser to "know", but which don't appear anywhere in the "dungeon", set the location to some ridiculous value like MAXINT. This works for objects which are not present "yet" too. (e.g. maybe there's no "slingshot" in the game until you combine the "rubber band" with the "y-shaped stick" Just set the slingshot's location to MAXINT until the player "creates" it, then set its location to zero and send the rubber band and the stick off into MAXINT limbo.)

    Advanced parsing topics:

    The words "all" and "everything" are useful in many situations. They are very similar to the "*" wildcard character in, say, ksh. It doesn't behave the same for all verbs though. Notable, "take everything" and "drop everything" refer to different sets of objects. For "take", and most other verbs, it refers to all objects which have the same location as the player. For drop, it means all the objects with a location of zero.

    Syntax specifications:

    Consider the verb "put" in the following sentences:

    > put the peanut butter and jelly on the bread with the knife
    > put the apple and the orange on the table
    > put on the jacket
    > put out the fire
    > put together the puzzle
    

    One way to tackle this is to imagine that there are really three verbs here that all happen to be called "put", but have different "syntaxes".

    1. put (list of objects) (preposition) object (preposition) object
    2. put (list of objects) (preposition) object
    3. put (preposition) object

      When the parser sees "put", it has to consider all three alternatives and discard those which do not fit the actual input, the goal being to have exactly one syntax match the input. Then the appropriate verb function for whichever "put" matches may be called.

      Adjectives and articles:

      The articles "a", "an", and "the" and adjectives are helpful in ambiguity resolution because you know you must see a noun or a pronoun after an article prior to seeing another verb. Adjectives are also useful for distinguishing a copper coin from a gold coin.

      Pronouns: "it", and "them"

      As you're parsing the sentence, you can keep track of the last object, and last objects (plural) and these can be referred to later in the sentence with "it" and "them". There are complications however. Consider this:

      take the hammer and hit the car then drop it.
      
      Clearly "it" used with "drop" may only refer to things which you "have", and you surely do not "have" the car. Clearly you mean to drop the hammer. It's complicated.

      Conjunctions, "and", ";", ".", "then"

      These can separate sentences or objects, though a period or semicolon generally only separates sentences. They may generally be handled by just ignoring them, though they may be useful in resolving ambiguity.

      Ambiguity detection and resolution: Consider a game which contains the following objects:

      a golden ring
      a small hammer
      a large iron bell
      

      What does this sentence mean?

      Take hammer ring bell
      

      Does it mean "take the hammer ring and bell?" or does it mean "take the hammer, and ring the bell." Fron the given sentence, it is not clear, it is ambiguous. From "take the hammer ring and bell", you can see how conjunctions may be used to resolve ambiguity.

      When I implemented all of these features (many years ago), I used a state machine in the parser. Whenever I came to a word which had multiple interpretations, I forked the state machine into multiple state machines, one for each interpretation. As each state machine parsed through the sentence, it might come to a word that couldn't fit into its interpretation. When that happened, that state machine was terminated. When the end of the sentance was reached, there would normally be one state machine left in a happy (completed) state. There might be other state machines left that were uncompleted. Those were terminated. If there were multiple state machines left in a happy state, then the sentence was considered ambiguous. If there were no state machines left then the sentence was considered gibberish, or, more likely, too difficult for the parser to understand. This scheme actually worked very well.

      Well, I guess that's about it, except for the sample code.


      Previous Top Next

Log in or registerto write something here or to contact authors.