An Adventure Game – Part 1

A Prolog programmer walks into a bar:

– Can I have beer?

– No.

As promised, in this and the following posts I’ll design and implement a simple, text-driven adventure game in the spirit of Zork. I shan’t be too concerned with superfluous features and instead direct most energy towards nifty algorithms and reasonably well-designed data structures. No guarantees whatsoever will be made regarding the actual playability of the final product! Since they say that a picture is worth more than a thousand words:

Wait. That’s probably not true in the case of a text-adventure game. Crap. In any case the basic ideas involved are not too hard to grasp. The only interface against the user is text in the form of output and input. Output is as one might expect one of the easiest parts to implement since all game objects will have textual descriptions. Input is far, far worse since we’ll be dealing with natural instead of formal languages. In the general case perfect natural language processing is more or less impossible. This is why almost all successful services that make use of natural languages are based on statistical/probabilistic methods instead of strictly formal models such as context-free grammars (hybrids also exist). But of course, just because something is very hard in the general case doesn’t necessarily imply that it’s just as hard in every case. We will however be forced to make some severe restrictions regarding what kind of input we want to accept and focus on these areas.

Where to start? UML-diagrams? Activity diagrams? Of course not — we’ve already put several minutes into the project without savoring a single cup of the brown, precious liquid known to man as coffee. That’s the first step. The second step is to blankly stare into the monitor for at least a few minutes and realize that it would probably be a good idea to put on some music before the mind-numbing silence quells all remaining sanity. Good choices are Einstürzende Neubauten, Melt Banana or Programmer Art, by Yellow Bear. The fourth step is to automatically generate a nonsensical name for the project. I used a soundex-algorithm with random names as input, and after some tinkering I ended up with:

Bacchus-Bosch

No, I’ve got absolutely no idea what it means, but it rolls of the tongue nicely. Now we’re finally in a position where we might be inclined to do some real work! This is an instance where the bottom-up methodology will work nicely: start with something simple that we know that we’ll need later on and expand from there. For no particular reason I’ll start with the most fundamental parts of user input: tokenizing and part-of-speech tagging. A typical example of user input is:

open the door

go through the door

How should these sentences be construed? Well, no matter what we’ll have to start by reading them character by character from an input stream. This will result in a list of characters. We can code this in more or less the same way as in an imperative language: continue reading characters until the end of line is reached.

read_line(S, Chars) :-
    get_char(S, C),
    read_line(C, S, Chars).

read_line('\n', _, []) :- !.
read_line(C, S, [C|Chars]) :-
    read_line(S, Chars).

Where get\_char/2 takes a stream as input and returns the next character. We could in theory analyze this character list already at this stage, but for simplicity it’s better to introduce some additional pre-processing steps. Therefore we’ll take our character list and group together the characters into words instead. For example, the character list from the first example sentence would be [o,p,e,n,'\,',t,h,e,'\,',d,o,o,r],  and would result in the word list [open, the, door]. There already exists a primitive for this purpose: atom\_chars/2, so what we need to do is to go through the list and look for groups separated by whitespace and convert each group to an atom. One simple solution is to use a set of DCG-rules (for brevity some basic rules are omitted):

chars_to_list([A|As]) -->
	chars_to_atom(A),
	whitespace,
	chars_to_list(As).
chars_to_list([A]) -->
	chars_to_atom(A),
	opt_whitespace.
chars_to_atom(A) -->
	chars(Cs),
	{atom_chars(A, Cs)}.

The goal in the curly braces, atom\_chars(A, Cs), makes sure that each group is converted appropriately. This is certainly not the most efficient solution. For example: the last atom always needs to be parsed twice in chars\_to\_list//1, one time in the first rule and one time in the second. In a real compiler this might not be acceptable, but since we’re dealing with sentences of just a few words it’s A-OK.

Now we can recognize individual words, but we still don’t know what they mean, i.e. what semantic class they belong to. Are they imperative commands? Directions? Physical objects? For that we’ll use a technique that in natural language processing is known as tagging: each word will be assigned a tag corresponding to its lexical category. For example, the sentences above could be manually tagged as:

open/verb the/article door/noun

go/verb through/preposition the/article door/noun

Don’t fret if the part-of-speech lectures from middle school are nothing but a distant, hazy memory: it won’t become much more complicated than this. Like all other domains in natural language processing, tagging is very hard to do perfectly. Therefore we shall use a simple tagger that either looks up the tag for a word manually, or forms a decision based on the previously tagged words. First we need a small dictionary that contains words and their lexical categories. The simplest solution is to implement it as a set of word/2 facts:

:- object(game_logic).

    :- public(word/2).

    word(entity, door).
    word(entity, key).
    word(entity, banana).

    word(direction, north).
    word(direction, east).
    word(direction, south).
    word(direction, west).

    word(preposition, on).
    word(preposition, through).

    word(pronoun, he).
    word(pronoun, it).
    word(pronoun, she).

    word(verb, go).
    word(verb, take).
    word(verb, open).
    word(verb, eat).
    word(verb, use).

    word(article, a).
    word(article, an).
    word(article, the).

:- end_object.

A remark: it would be preferable to store the tuples with the arguments switched to exploit first-argument indexing, since the word is usually looked up more frequently than the lexical category. Obviously this is just a sample dictionary, but it can easily be extended once we begin working on the rest of the game. Next we’ll need a predicate that, given a word returns its lexical category as a tag. However, since we also want to be able to construct rules that takes the history into account, it will in addition to the word also need a list of the preceding words and their tags. For efficiency reason this list will be stored in reversed order. An example of such a rule is: “if the previous tag was an article, then the word must be an entity”.

    %% NAME:
    %% 	tag(+Preceding, -Word, -Tag).
    %% DESCRIPTION:
    %% 	True if Tag is the tag corresponding to Word. Preceding is used
    %% 	whenever a rule needs to look at the history in order to tag the
    %% 	word.
    tag([_-article|_], _, entity).
    tag(_, A, T) :-
        game_logic::word(T, A).

It’s easy to extend tag/3 with additional rules, but let’s leave it as it is for now. The actual tagger, tag\_atoms/2, will just go through the list of atoms and call tag/3 for each of them.

    %% NAME:
    %%  tag_atoms(+Atoms, -AtomTags).
    %% DESCRIPTION:
    %%  True if AtomTags is a list of pairs of the form Atom-Tag,
    %%  where Tag is the tag corresponding to Atom.
    tag_atoms(As, Ts) :-
        tag_atoms(As, [], Ts).

    tag_atoms([], _, []).
    tag_atoms([A|As], Pre, [A-T|Ts]) :-
        tag(Pre, A, T),
        tag_atoms(As, [A-T|Pre],Ts).
    tag_atoms([A|As], Pre, [A-unknown|Ts]) :-
        %We don't use a cut since we want the ability to try several
        %different tags if necessary.
        \+ tag(Pre, A, _),
        tag_atoms(As, [A-unknown|Pre], Ts).

Note something about tag\_atoms/3: it can return several solutions if tag/2 is non-deterministic. This is actually a good thing since natural language is inherently non-precise and ambiguous. If some other part in the game fails due to an erroneous tagging it’s always possible to backtrack and try again.

Here’s how the tagger looks in action:

-> eat the key
The input is: eat the key
The tagged input is: eat-verb the-article key-entity

-> open the door with the banana
The input is: open the door with the banana
The tagged input is: open-verb the-article door-entity with-preposition the-article banana-entity

Whether those specific commands make any sense in the finished game remains to be seen!

Summary

We’ve implemented some fundamental parts of Bacchus-Bosch and are now able to get input from the player and make sense of it by tagging it. Next we’ll concern ourselves with parsing. The goal is to construct a parse tree from the tagged input that reflects the structure of the command that the player had in mind. Stay tuned!

Source code

The source code is available at https://gist.github.com/847541.

Advertisements

4 responses to “An Adventure Game – Part 1”

  1. Jensan says :

    Really interesting article! Looking forward to the next installation in the series.

    • victorlagerkvist says :

      Why thank you, Mr Turesson! If everything goes according to the Plan the next installment will be done next week or so. There might be a correlation with the frequency of the posts and whether or not I decide to get some mulled wine for the weekend. But in what direction I don’t know!

  2. Stewart Sims says :

    I like this example, nice clean code and your writing style is easy to follow. I’m also looking forward to further posts, it’s interesting to see a Prolog development blog!

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

%d bloggers like this: