Archive | March 2011

An Adventure Game – Part 3

I’ve been procrastinating too much. It’s time to roll up our sleeves and get dirty with the nitty-gritty core of Bacchus-Bosch. We’re currently able to read input from the player and parse commands. Before even considering how commands should be executed we have to take a step back and make some ontological commitments. We know that the game will consists of interaction between game objects, the entities, but haven’t specified how these should be represented or how they are created. It might be tempting to simply use a set of unit clauses and statically recite everything of interest:

entity(key).
entity(room_1).
entity(room_2).
entity(door).

contains(room_1, key).
contains(room_1, door).

connected(room_1, door, room_2).
.
.
.
%And so on for the whole level.

At a first glance this might look like an acceptable solution. It wouldn’t be very hard to add e.g. properties to the entities by adding more facts, but everything breaks down in the moment when the player changes the state of the world by picking up the key. Then the key is no longer directly contained by the room and should instead be added to the inventory of the player. The quick and easy hack is to use assert/retract in order to add and remove facts according to the fluctuating state of the game world, but in the long run that’s a terrible idea. To be forced to use impure features for such an integral part of the game is either a sign that we’re using the wrong data structures or the wrong language. I’ll go with the former theory!

Let’s begin by considering a simplified problem where the game only consists of a player with the property of having health in the form of an integer: “hit points”. It should be possible to both increase and decrease this value according to events from other entities. What’s an entity? A common and simple solution is to create a class hierarchy with an abstract class in the top and concrete classes such as items and monsters in the lower layers. While there’s nothing inherently wrong with this I think we can do better, for two reasons:

  • The class hierarchy will be huge and hard to make sense of.
  • It’s not (at least not in most languages, Logtalk happens to be an exception) possible to create new classes during runtime, with the effect that behaviour can’t be modified or extended once the game has started.

An often cited design principle is to favor composition over inheritance. We want the entities to be entirely composed of smaller objects, of properties. The sum of all the properties constitute the entity – nothing more, nothing less (followers of holism should stop reading here!). It should of course be possible to both add, remove and update properties during runtime. It’s easiest to start with a basic definition of a property, which we’ll do with a prototypical object. A property should be able to:

  • Give the initial state of the property. For the health property, this might simply be a positive integer.
  • Update the entity to which the property belong. If the property doesn’t directly influence the entity, it’s left unchanged.
  • Execute an action that changes the state of the property, e.g. increasing or decreasing the health.

With these considerations the object becomes:

:- object(property).
    :- info([
        version is 1.0,
        author is 'Victor Lagerkvist',
        date is 2011/03/19,
        comment is 'A property constitutes the basic behaviours of the objects in Bacchus-Bosch.']).

    :- public(update/2).
    :- mode(update(+entity, -entity), zero_or_more).
    :- info(update/2, [
        comment is 'Update the entity to which the property belong.',
        argnames is ['Entity', 'Entity1']]).

   :- public(action/6).
    :- mode(action(+atom, +list, +entity, +state, -state, -entity), zero_or_more).
    :- info(action/6, [
        comment is 'Execute the action Name with respects to Args, State and Entity, and store the resulting new state and entity in State1 and Entity1.',
        argnames is ['Name', 'Args', 'Entity', 'State', 'Entity1', 'State1']]).

    :- public(new/1).
    :- mode(new(-term), zero_or_more).
    :- info(new/1, [
        comment is 'Unify State with the initial state of the property.',
        argnames is ['State']]).

    %% Basic definition: do nothing!
    update(E, E).

    %% Basic definition, overloaded in almost every descendant prototype.
    new(void).

:- end_object.

Exactly how these predicates should be implemented will be clearer with an example.

:- object(health_property,
    extends(property)).

    new(10).

    action(decrease_health, [], Owner, H0, Owner, H) :-
        H is H0 - 1.
    action(increase_health, [], Owner, H0, Owner, H) :-
        H is H0 + 1.

:- end_object.

Hence, the initial state for the health property is 10. To decrease the value one calls action/6 with the correct action name, an empty argument list, the owner of the property and the old state, and in return obtains the updated owner and new state with the fifth and sixth parameters. If a property doesn’t support a specific action it’ll simply fail. Let’s see how update/2 can be used together with the health property. It should be called in each tick of the game. For example: the health should be decreased if the player is poisoned or have somehow been ignited. Such a property won’t support any actions and only overload the definition of update/2 from property.

:- object(on_fire_property,
    extends(property)).

    update(E0, E) :-
        entity::action(decrease_health, [], E0, E).

:- end_object.

Since update/2 takes an entity as argument, the on_fire property simply asks this entity to decrease its health. Now we have to decide how to represent entities and how to delegate action messages. As mentioned earlier an entity is simply the sum of its properties, hence we can simply represent it as a list that contains properties and their states. The formal definition reads:

  • [] is an entity.
  • [P|Ps] is an entity if Ps is an entity and P is a tuple of the form: N - S, where N is the name of a property and S is a state of that property.

Continuing on our example, [health\_property - 10] is an entity. If we decide to have some fun and for a moment indulge ourselves with arson, [health\_property - 10, on\_fire\_property - void] is also an entity. A few basic definitions remain before we can actually do anything with these entities. First we need a predicate update/2 that iterates through the list of properties that constitute the entity and calls update/2 for every property.

update(E0, E) :-
    update(E0, E0, E).

update(E, [], E).
update(E0, [P|Ps], E) :-
    P = Name - _,
    Name::update(E0, E1),
    update(E1, Ps, E).

The effect is that each property is updated with respect to the current state of the entity. Next up is action/4. It takes the name of the action that shall be performed, its arguments, the entity in question and returns the updated entity if the action could be performed or simply fails otherwise. Since an entity can’t perform any actions it has no choice but to try to delegate the action to its properties.

action(A, Args, E0, E) :-
    %% Select a property from the list such that the action A can
    %% be performed with the arguments Args.
    list::select(P, E0, E1),
    P = PropertyName - State,
    PropertyName::action(A, Args, E1, State, E2, State1),
    %% Add the property with the updated state to E2.
    P1 = PropertyName - State1,
    E = [P1|E2].

As seen from the code action/4 uses select/3 to find the first property that supports the operation. If there’s more than one potential property it will simply choose the first one but leave choice point for the others. If we put it together into one massive object we get:

:- object(entity).

    :- info([
        version is 1.0,
        author is 'Victor Lagerkvist',
        date is 2011/03/20,
        comment is 'The entity operations of Bacchus-Bosch.']).

    :- public(update/2).
    :- public(action/4).
    :- public(get_property/2).
    :- public(select_property/3).

    update(E0, E) :-
        %% As before.

    action(A, Args, E0, E) :-
        %% As before.

    get_property(E, P) :-
        list::member(P, E).

    select_property(P, E, E1) :-
        list::select(P, E, E1).

This is more or less the basic building blocks, the engine, but of course quite a lot of work remains before we have an actual game in our hands. For the remainder of the post we shall implement enough properties so that it’s possible to construct a room with some entities in it. A room is an entity that contains other entities. We can model this as a property, namely the property of being a container. This property at least has to support the following operations:

  • Being able to update the state of its children, i.e. overload update/2 from its parent.
  • Add and remove items with actions.

For simplicity the data structure is going to be a list of entities. This makes it almost trivial to write the actions.

:- object(container_property,
    extends(property)).

    new([]).

    update(E0, E) :-
        entity::select_property(container_property-Items, E0, E1),
        update_children(Items, Items1),
        E = [container_property-Items1|E1].

    update_children([], []).
    update_children([E|Es], [E1|E1s]) :-
        entity::update(E, E1),
        update_children(Es, E1s).

    action(add_item, [E], Owner, Items, Owner, [E|Items]).

    action(remove_item, [E], Owner, Items, Owner, Items1) :-
        list::select(E, Items, Items1).
:- end_object.

Then we of course need a door. Doors are awesome: you can walk through them, open them, close them, lock them – the only limit is the imagination! Our particular door will only have one property though, that of being openable. But it’s only possible to open a door if it happens to be unlocked, hence the openable property in turn depends on whether or not the lock can be unlocked with the key in question. For simplicity we’re going to assume that the player uses the key every time he/she wishes to open the door, but extending these properties so that the lock has an internal state would not be terribly difficult.

:- object(openable_property,
    extends(property)).

    new(closed-[lock_property- Lock]) :-
        lock_property::new(Lock).

    action(open, Key, Owner, closed-Lock, Owner, open-Lock) :-
        entity::action(unlock, Key, Lock, _).
    action(close, [], Owner, _-Lock, Owner, closed-Lock).

:- end_object.

The action/6 command should be read as: change the state of the door from closed to open if the key can unlock the lock. To complete the door we of course need to define the lock and key properties.

 :- object(key_property,
    extends(property)).

    %% The default key.
    new(key).

:- end_object.

:- object(lock_property,
    extends(property)).

    %% The (default) key that opens the lock.
    new(key).

    valid_key(E, Key) :-
        entity::get_property(E, key_property-Key).

    action(lock, [Entity], Owner, Key, Owner, Key) :-
        valid_key(Entity, Key).
    action(unlock, [Entity], Owner, Key, Owner, Key) :-
        valid_key(Entity, Key).

:- end_object.

The two actions specifies that the entity can lock or unlock the lock if it has the property of being a key with the correct state. Note that the entity in question doesn’t just have to be a key, it can still support other properties as long as the key property is fulfilled.

We’re now able to create a room with a door and a key. What remains is the player. For the moment that’s just an entity that has the property of having health, which we defined earlier, and that of having an inventory. The Argus-eyed reader will probably realize that having an inventory is quite similar to that of being a container. The only difference is that the player can only pick up items that are carriable, so instead of defining everything from the ground up we’re going to inherit some definitions from container\_property. What happened to the principle of favoring composition over inheritance? Bah!

:- object(inventory_property,
    extends(container_property)).

    valid_item(E) :-
        entity::get_property(E, carriable_property-_).

    action(add_item, [E], Owner, Items, Owner, [E|Items]) :-
        valid_item(E).

    action(drop_item, [E], Owner, Items, Owner, Items1) :-
        valid_item(E), % This shouldn't be necessary since only valid item are added in the first place.
        list::select(E, Items, Items1).

:- end_object.

:- object(carriable_property,
    extends(property)).

    %% Perhaps not the most interesting property in the game.

:- end_object.

It should be noted that I haven’t actually tested most of these properties, but it should/could work! So do we now have a functional but simplistic game? Not really. We have the basic entities, but there’s a quite glaring omission: everything is invisible since nothing can be printed. For a text game this is a distinct disadvantage! The simplest solution is to add another property, that of being printable, where the state is the string that shall be displayed.

:- object(printable_property,
    extends(property)).

    new(Description) :-
        list::valid(Description).

    action(print, [], Owner, Description, Owner, Description) :-
        format(Description).
:- end_object.

But since we also want the possibility to print items in a container, e.g. a room, we’re going to define an additional action in container\_property.

:- object(container_property,
    extends(property)).

    new([]).
    .
    . % As before.
    .

    action(print_children, Args, Owner, Items, Owner, Items) :-
        % Print all children that are printable.
        meta::include([E] >>
                       (entity::action(print, Args, E, _)),
                      Items,
                      _).
:- end_object.

Putting everything together

Let’s use the properties and construct some entities. The test program is going to build a room and then print its description together with its children.

    init :-
        write('Welcome to Bacchus-Bosch!'), nl,
        build_test_room(Room),
        entity::action(print, [], Room, Room1),
        write('You see: '), nl,
        entity::action(print_children, [], Room1, _Room).

Building the room and its components is not hard, just a bit tedious.

    build_test_room(Room) :-
        build_test_door(Door),
        build_test_player(Player),
        build_test_key(Key),
        Room0 = [container_property - State1, printable_property - State2],
        container_property::new(State1),
        room_description(State2),
        entity::action(add_item, [Door], Room0, Room1),
        entity::action(add_item, [Player], Room1, Room2),
        entity::action(add_item, [Key], Room2, Room).
    build_test_door(Door) :-
        Door = [openable_property-State1, printable_property-State2],
        openable_property::new(State1),
        door_description(State2).

    build_test_key(Key) :-
         Key = [key_property-State1, printable_property-State2],
         key_property::new(State1),
         key_description(State2).

    build_test_player(Player) :-
        Player = [inventory_property-State1, health_property-State2],
        inventory_property::new(State1),
        health_property::new(State2).

The string descriptions are simply given as facts.

    room_description("A rather unremarkable room.\n").
    door_description("A wooden door with a small and rusty lock.\n").
    key_description("A slightly bent key.\n").

When running the test program we get the following output:

Welcome to Bacchus-Bosch!
A rather unremarkable room.
You see:
A slightly bent key.
A wooden door with a small and rusty lock.
true

Only three major obstacles remain before we have a game in our hands:

  • More properties.
  • Conjoin the parsed commands with the game world so that it’s possible for the user to interact with entities. It shouldn’t be too hard to see that commands will be executed by sending action commands to the entities in question.
  • Abstract the creation of game objects, e.g. with the help of an embedded language.

Which will be the topics of the next post. Stay tuned!

Source code

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

An Adventure Game – Part 2

When we left off last time we were able to read input from the player and tag the atoms with their word classes. This time we’ll use this information to analyze what the input means with two different techniques: pronominal anaphora resolution and chunk-based parsing. Don’t worry about the technical names – I’m way to lazy to do something that would actually be strenuous, so the presented solutions won’t be that hard to grasp. Let’s have a look at some typical user input and some potential answers:

> look

You are in a dimly lit room. A banana hangs from the ceiling in a thin, plastic wire.

> look at the banana

It’s a typical banana. Yellow, crooked and utterly delicious. Mmm.

> eat it

The banana is out of reach.

> grab the banana and eat it

Not even your long, hairy ape-arms are enough to bridge the vast gap.

> fling feces around the room

I’m sorry. I don’t know what ‘fling’ means.

All these sentences have something in common: they are imperative in nature and somehow either changes the state of the game world or inspects it. We’ll make the basic assumption that every command can be described as a tuple, C-Args, where C is an atom and Args is a list of tags. The “look”-command from the example can be represented as:

command(look, [entity]).
command(look, []).

Since a banana is an entity, the sentence “look at the banana” can be parsed as a look-command with “banana” as argument. It can also be parsed simply as “look”, with no argument at all, but the first interpretation is preferable. There is however one problem that we must tackle before the parsing can take place: what does “it” mean? That depends on the context and is the subject of pronominal resolution.

Pronominal resolution

Just like everything else in natural language processing, resolving pronouns is quite challenging in the general case. Fortunately we’re dealing with a rather restricted subset of English. When a pronoun such as “it” is used we can make the assumption that it’s just a shorthand for a previously identified entity. The task then becomes to replace all occurrences of a pronoun with the corresponding entity before the parsing. Let’s have a look at a few examples:

> take the banana and eat it

Here the pronoun refers to the banana, i.e. the sentence should be replaced by “take the banana and eat the banana”.

> look at the ceiling and take the banana and eat it

Here the pronoun probably refers to the banana, but it could possibly also refer to the first entity: the ceiling. Since we always want the possibility to backtrack and try alternative solutions in case the first one fails later on, it’s a good idea to make the predicate non-deterministic. Assuming that we’re given a list of tagged atoms, a simple algorithm may look as follows:

  • If the list of tagged atoms is non-empty, inspect the first element.
  • If it’s not a pronoun, ignore it and continue with the rest of the list.
  • If it’s a pronoun, replace the pronoun with the corresponding entity, where the candidates of possible entities are the tagged atoms that occur to the left of the pronoun in the sentence.

Putting this into code is straightforward. The predicate will have three arguments: the list of tagged atoms, the tagged atoms that have been processed so far and the result.

    resolve_pronouns(ATs, Xs) :-
        resolve_pronouns(ATs, [], Xs).

    resolve_pronouns([], _, []).
    resolve_pronouns([A-T|Xs], Pre, [Y|Ys]) :-
        (   T = pronoun ->
            resolve_pronoun(A, Pre, Y),
            resolve_pronouns(Xs, Pre, Ys)
        ;   Y = A-T,
            resolve_pronouns(Xs, [Y|Pre], Ys)
        ).

resolve\_pronoun/2 is also a walk in the park. For now, we’re only going to be dealing with “it”. Other pronouns can be added in a similar manner.

    %% NAME:
    %%  resolve_pronoun(Pronoun, AtomTags, X)
    %% DESCRIPTION:
    %% True if X is an entity corresponding to the pronoun resolved
    %% with the help of AtomTags. It is the caller's responsibility to
    %% make sure that AtomTags is in the correct (possibly reversed)
    %% order.
    resolve_pronoun(it, Xs, X) :-
        X = A-entity,
        list::member(X, Xs).

Nota bene: since the words are pushed onto Pre in LIFO order, a pronoun will be resolved from right-to-left. While this algorithm is indeed very simple, it’s not particularly efficient. Due to the call to member/2 in resolve\_pronoun/2, the worst case execution time (to find one solution) for resolve\_pronouns/2 is exponential. But considering the fact that a typical sentence is just a few words long and that they rarely if ever contains more than one or two pronouns, I think we’ll survive.

One step remains. Note that “it” is used in one of the example sentences without referring to anything in that particular sentence. Instead it refers to the entity that was used in the previous sentence. The obvious yet quite flexible solution is to augment resolve\_pronouns/2 with an additional argument that holds the previous sentence. Then a pronoun can first be resolved with respect to the current sentence, but if that fails the previous sentence is tried instead.

Parsing

Natural language contains a lot of noise and variations. This makes formal methods such as context-free grammars somewhat ill-suited and cumbersome to use. One deceivingly simple solution is to ignore everything that we’re not interested in and group the good stuff into chunks. A command, e.g. “eat”, can be considered a chunk. We know that it takes one entity-argument, so after encountering the command chunk we scan the rest of the sentence for an argument chunk of the correct type. This might sound like cheating – and it kind of is – but as long as the reduced, simpler problem still yields the correct output that’s hardly of any importance.

The goal is to produce one or more commands given a list of tagged atoms (where the pronouns are resolved). Remember that commands are defined as:

        command(look, [entity]).
        command(look, []).
        command(eat, [entity]).

To allow some flexibility in the input, we’re also going to allow synonyms. These can be defined as additional facts.

    variants(look ,[look, inspect]).
    variants(eat, [eat, munch, digest]).

For every chunk of type X we’re going to write a corresponding X\_chunk predicate that has 3 arguments: the list of tagged atoms, the list that remains after this chunk is parsed, and the resulting chunk. First off is the sentence chunk.

    %% NAME:
    %%  parse_atoms(+AtomTags, -Remainder, -Commands)
    %% DESCRIPTION:
    %% True if Commands is a list of commands parsed from from the atoms and their
    %% tags in AtomTags.
    parse_atoms(ATs, Remainder, Commands) :-
        sentence_chunk(ATs, Remainder, Commands).

    %% NAME:
    %%  sentence_chunk(+AtomTags, -Remainder, -Commands)
    %% DESCRIPTION:
    %% True if Commands is a list of commands parsed from from the atoms and their
    %% tags in AtomTags. The remainder, i.e. the chunk after the
    %% sentence, is stored in Remainder (most likely just the empty list).
    sentence_chunk(ATs, Remainder, [C-Args|Cs]) :-
        command_chunk(ATs, ATs1, C),
        argument_chunk(ATs1, C, ATs2, Args),
        (   conjunction_chunk(ATs2, Remainder0, _) ->
            sentence_chunk(Remainder0, Remainder, Cs)
        ;   Cs = []
        ).

    conjunction_chunk([Conj-conjunction|ATs], ATs, Conj-conjunction).

Which shall be read as “first parse a command followed by its argument, then if the arguments are followed by a conjunction, recursively parse the rest of the list”. The command chunk is slightly more involved since we have to deal with variants of commands.

    %% NAME:
    %%  command_chunk(+AtomTags, -Remainder, -Command)
    %% DESCRIPTION:
    %% True if Command is the command parsed from the atoms and their
    %% tags in AtomTags. The remainder, i.e. the chunk after the
    %% command, is stored in Remainder.
    command_chunk(ATs, ATs1, C) :-
        %% First find a verb, i.e. a potential command.
        list::append(_, [C0-verb|ATs1], ATs),
        %% Then check whether or not the verb is a variant of a known
        %% command.
        game_logic::variants(C, Cs),
        list::member(C0, Cs).

Note the use of append/3 to ignore everything in the list up to a verb. When parsing the arguments we scan the input and look after atoms of the correct type.

    %% NAME:
    %%  argument_chunk(+AtomTags, +Command, -Remainder, -Args)
    %% DESCRIPTION:
    %% True if Args are the arguments corresponding to the arity of
    %% Command with respect to the atoms and their tags in
    %% AtomTags. The remainder, i.e. the chunk after the last
    %% argument, is stored in Remainder.
    argument_chunk(ATs, C, ATs1, Args) :-
        game_logic::command(C, Tags),
        matches(ATs, Tags, ATs1, Args).

    %% NAME:
    %%  matches(+AtomTags, +Tags, -Remainder, -Args).
    %% DESCRIPTION:
    %%  True if the list of atoms and their corresponding tags matches
    %%  Tags, i.e. there exists a sequence of atoms, not necessarily
    %%  in a a direct linear sequence, such that their tags can be
    %%  mapped to the tags in Tags.
    matches(ATs, [], ATs, []).
    matches(ATs, [T|Ts], Remainder, [A|As]) :-
        list::append(_, [A-T|ATs1], ATs),
        matches(ATs1, Ts, Remainder, As).

That’s all the constructs that we’re going to support at the moment. Two remarks should be made before we move on:

  • The chunk predicates can be rewritten as DCGs instead since they’re essentially just threading state. I’ll leave this as an exercise to the reader!
  • argument\_chunk/4 is given the ability to ignore everything that it can’t make sense of. While this is good in many circumstances, it also has the effect that some ill-formed sentences will be incorrectly parsed. For example, consider the sentence “eat the bnana and look at the room”. Assuming that bnana is tagged as unknown, the sentence will be parsed as eat-room since room is the only entity that argument\_chunk/4 discovers. One possible solution is to restrict the argument parsing to the current clause and disallow it to continue past conjunctions.

Putting everything together

Now we’re able to dissect the meaning of the user input and extract commands from it. The next task is to actually carry out the commands and update the state of the game world, but for the moment we’re just going to print the parsed commands to verify that everything works. The steps are the following:

  • Read a line and convert it to atoms.
  • Tag the atom list.
  • Resolve the pronouns.
  • Parse the resulting list of tagged atoms.

And it’s rather easy to cobble together.

    init :-
         write('Welcome to Bacchus-Bosch!'), nl,
         current_input(S),
         repl(S, []).

    repl(S, History) :-
        write('> '),
        nlp::parse_line(S, Atoms),
        write('The input is: '),
        meta::map([X] >> (write(X), write(' ')), Atoms), nl,
        nlp::tag_atoms(Atoms, AtomTags),
        write('The tagged input is: '),
        meta::map([X] >> (write(X), write(' ')), AtomTags), nl,
        (   eval(History, AtomTags) ->
            true
        ;   write('I''m sorry, Dave. I''m afraid I can''t do that'),
            nl
        ),
        repl(S, AtomTags).

    eval(History, AtomTags) :-
        nlp::resolve_pronouns(History, AtomTags, AtomTags1),
        eval_commands(AtomTags1).

    eval_commands(AtomTags) :-
        nlp::parse_atoms(AtomTags, _, Commands),
        write('The parsed commands are: '), nl,
        meta::map([X] >> (write(X), nl), Commands).

If we feed this program with the example sentences we end up with the following dialogue:

Welcome to Bacchus-Bosch!

> look

The input is: look
The tagged input is: look-verb
The parsed commands are:
look-[]

> look at the banana

The input is: look at the banana
The tagged input is: look-verb at-preposition the-article banana-entity
The parsed commands are:
look-[banana]

> eat it

The input is: eat it
The tagged input is: eat-verb it-pronoun
The parsed commands are:
eat-[banana]

> grab the banana and eat it

The input is: grab the banana and eat it
The tagged input is: grab-verb the-article banana-entity and-conjunction eat-verb it-pronoun
The parsed commands are:
take-[banana]
eat-[banana]

> fling feces around the room

The input is: fling feces around the room
The tagged input is: fling-unknown feces-unknown around-preposition the-article room-entity
I’m sorry, Dave. I’m afraid I can’t do that

Source code

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

Due to a hefty amount of school-work (I should actually be crunching theorems in number theory right now!) part 3 will probably be delayed one or two weeks.