Archive | April 2011

Prologomenon Goes Viral

Apparently, social medias like Twitter is all the rage these days. It’s been used to convey critical information in emergency situations, helped revolutions in suppressed governments, and now it’s finally time to overthrow the corrupt imperative languages that have grown fat on the labors of the working class…. Kidding – some of my best friends are imperative languages! I have however started a Twitter account in relation with the blog with the intent to a) troll imperative languages, b) post code-snippets within the character limit that accomplishes something cool. I’ve currently implemented:

All just for fun, of course. Don’t try this at home unless you’re sure you’re able to use cryptic variable/predicate names and abuse all the language features that normally allows one to write readable, concise source code.
Advertisements

An Adventure Game – Part 5

We’re rapidly approaching the end. This time we’ll implement a meta-language that makes it easier to create new games with the existing engine. Conceptually speaking we’re not adding anything new to the table, but the example game from the previous post was created in an ad-hoc manner that demanded knowledge of both Prolog/Logtalk and the engine in question. What we want is a declarative language in which it’s possible to define rooms, entities and how they should be connected. Exactly how this language is interpreted should not be the game designer’s concern. This is a scenario in which it’s best to start with the language itself, since it’s pretty much impossible to write an interpreter otherwise.

The language

We want the language to be capable of:

  • Creating entities.
  • Adding properties to existing entities.
  • Setting new values for entities. For instance, if we first create a door with the default lock we’ll probably want to change this later on.
  • Adding entities to rooms.
  • Connect two rooms with an entrance.

All these steps should be expressible within a single file. The first part might look something like (as always, I’m just making stuff up on the fly, it’s quite possible that there are simpler/better ways to accomplish this!):

begin entities.

build(room, room1, "A rather unremarkable room.\n").
build(room, room2, "...").

build(door, door, "...").

build(lock, lock).

build(key, key, "A slightly bent key.\n").

build(player, player).

end entities.

Where build(Type, Id) should be read as: build an entity of type Type and name it Id. build/3 allows us to create printable entities, where the string is the description. This suggests that we’ll need a builder-object that’s capable of constructing some default entities. Since entities consist of properties, it would be possible to only build generic entities and manually add all the interesting properties in question, but we make the job easier for the game designer if he/she can assume that some primitive objects are already available. Of course, it wouldn’t be practical to demand that all entities are created in this manner. If two entities are identical except for a few differing properties then it would be simpler to create a generic entity and add the properties manually instead of defining a new build-predicate. For example, say that our game will consist of two different kinds of fruits: magical and non-magical. If we eat the former we finish the game, if we eat the latter we increase the health of the player. This is naturally implemented by creating two different properties: fruit\_property and magic\_fruit\_property. Hence, to create two fruits – one magical and one non-magical –  we first create two generic instances and then add the defining properties.

begin entities.

build(generic_entity, apple, "An apple! \n").
build(generic_entity, banana, "A yellow banana. Hot diggity dog!\n").

end entities.

begin properties.

add_property(fruit_property, apple).
add_property(carriable_property, apple).

add_property(magic_fruit_property, banana).
add_property(carriable_property, banana).

end properties.

The Argus-eyed reader will probably realize that it would be ever better to factorize the common properties (carriable\_property) of the two fruits into a prototypical base object, and then clone this object and later add the unique properties (magic\_fruit\_property and fruit\_property).

Since the entities that have been created thus far only has the default values we now turn to the problem of sending messages, so that we’re able to change these at whim. Say that we want to tell the lock that it should use the key that we just created, and the door that it should use the lock. A first attempt might look like this:

begin relations.

action(set_key, lock, key).
action(set_lock, door, lock).

end relations.

All identifiers here refer to the entities that have already been created. This won’t work however, due to a subtle semantic difference between how locks and doors work. A door has a lock, it consists of a lock. Therefore it’s correct to send the lock entity as an argument to set\_lock. A lock on the other hand doesn’t consist of a key. It only needs to know what key will unlock it, hence it’s not correct to send the whole key entity as argument. We only need one part of the key entity, its identity, in this case. To be able to differentiate between these cases we’ll introduce the notation that a term preceded by a dollar sign ($) will be sent as-is, instead of sending the entity corresponding to the identity. The previous attempt should hence be rewritten as:

begin relations.

action(set_key, lock, $ key).
action(set_lock, door, lock).

end relations.

The file will be interpreted from top to bottom, so if we added a property in the preceding block we’re able to change it here. The next step is to connect rooms. Strictly speaking this relation is not necessary since we’re already able to send messages to entities, but including it as a primitive in the language will make it much easier to use. The syntax is:

begin relations.
.
.
.
connect(room1, room2, door).

end relations.

The full example game in all its glory would be written as:

begin entities.

build(room, room1, "A rather unremarkable room.\n").
build(room, room2, "A room almost identical to the previous one. What on earth is going on!?\n").
build(door, door, "A wooden door with a small and rusty lock.\n").
build(lock, lock).
build(key, key, "A slightly bent key.\n").
build(generic_entity, apple, "An apple! \n").
build(generic_entity, banana, "A yellow banana. Hot diggity dog!\n").
build(player, player).

end entities.

begin properties.

add_property(fruit_property, apple).
add_property(carriable_property, apple).

add_property(magic_fruit_property, banana).
add_property(carriable_property, banana).

end properties.

begin relations.

action(set_key, lock, $ key).
action(set_lock, door, lock).

action(set_state, door, $ closed).

action(add_item, room1, apple).
action(add_item, room1, key).

action(add_item, room2, banana).

action(set_location, player, $ room1).

connect(room1, room2, door).

end relations.

A substantial improvement in readability compared to the previous efforts!

Parsing

Another boring, dry entry on parsing? Fear not, because I have a trick up my sleeve -there was a reason why the syntax of the meta-language was a spitting image of Prolog’s all along! One way to interpret the file is to say that begin/end and the dollar sign are all operators with a single argument. Then the file is nothing but a collection of facts that can be accessed as normal and we won’t have to worry about parsing at all. A slightly more contrived but more general approach is to use what in Prolog-nomenclature is known as term expansion. This is usually the preferred approach to handle embedded languages and is somewhat similar to macros in Lisp. The basic idea is simple: instead of taking a term at face-value we expand it according to a user-defined rule. What’s the point? Basically we don’t have to type as much. For example, let’s say that we have a database consisting of rule/3 facts, where the first argument is an atom, the second a list and the third an integer denoting the length of the list.


rule(a, [], 0).

rule(b, [a], 1).

Furthermore assume that we don’t want to calculate the length of the second argument at run-time. There’s nothing inherently wrong with this approach, but manually entering the length of the list is a drag and quite error-prone. It would be better if we could simply write:


rule(a, []).

rule(b, [a]).

And tell the Prolog system that these facts should be construed as rule/3 facts with an additional third argument which contains the length of the list. Fortunately this can easily be realized with the built-in predicate term\_expansion/2. The first argument of term\_expansion is the term that shall be expanded. The second argument is the expanded term. A suitable definition for the previous example is:

term_expansion((rule(Head, Body)), rule(Head, Body, Length)) :-
    length(Body, Length).

Great success! We don’t have to concern ourselves with how or when this predicate is called, just that it will eventually be called when the file is loaded. Like all powerful language constructs it’s easy to abuse the term expansion mechanism and create unreadable code. We could for instance expand A :- B to B :- A if we were in a facetious mood (don’t do it, OK?). Fortunately the Logtalk support is a bit more sane than in most Prolog systems. Instead of defining term\_expansion/2 rules in the same file as the rules that shall be expanded, they’re encapsulated in a special expansion object. This object is later used as a hook in logtalk\_load/2 to make sure that the effect is localized to a given file. In summary, there’s two steps involved:

  • Define the term\_expansion/2 rules in an expansion object (which must implement the expanding protocol).
  • Load the file (the script file in our case) with the expansion object.

I shan’t spell out the full details of the expansion object, but what it does is to remove the begin/end directives and create a set of entity/1 facts with the initial entities. Also, to make things easier in the script interpreter, it removes add\_property/2, action/3, connect/3 and replaces them with unary facts instead.

The builder

The builder is in charge of building game entities. As mentioned earlier it’s not strictly needed since it’s always possible to add properties manually, but it does simplify things. Here’s how a map and a room could be created:

    build(world, Id, Rooms, Player, World) :-
        Ps = [map_property-State],
        build(final_state, F),
        map_property::new([[F|Rooms], Player], State),
        entity::new(Ps, Id, World).

    build(room, Id, Description, Room) :-
        Ps = [container_property - State1,
              printable_property - State2],
        container_property::new([], State1),
        printable_property::new([Description], State2),
        entity::new(Ps, Id, Room).

Interpreting

We have a description of the game and want to transform it into an entity that has the map\_property. Strictly speaking this is not an interpreter, but rather a compiler from the script language to the entity language. The most important predicate is interpret\_game/2 that takes an expanded script file as argument and produces a game world. It works by extracting the entity directives, the property directives, the relations directives and then separately interprets each one of these. Finally it extracts the rooms and the player and asks the builder to build a game world.

   interpret_game(DB, World) :-
       findall(E, DB::entity(E), Es0),
       findall(P, DB::add_property(P), Ps),
       findall(A, DB::action(A), As),
       findall(C, DB::connect(C), Cs),
       interpret_properties(Ps, Es0, Es1),
       interpret_actions(As, Es1, Es2),
       interpret_connectors(Cs, Es2, Es),
       get_rooms(Es, Rooms),
       get_player(Es, Player),
       builder::build(world, world1, Rooms, Player, World).

The interpret\_x predicates are all rather similar. They iterate through the list of commands and changes the set of entities accordingly. For brevity, let’s concentrate on interpret\_actions/3.

    interpret_actions([], Es, Es).
    interpret_actions([t(M, Id1, Id2)|As], Es0, Es) :-
        select_entity(Id1, Es0, E0, Es1),
        lookup_argument(Id2, Es0, Arg),
        entity::action(M, [Arg], E0, E),
        interpret_actions(As, [E|Es1], Es).

    lookup_argument(Id, Es, Arg) :-
        (   Id = $(Symbol) ->
            Arg = Symbol
        ;   lookup_entity(Id, Es, Arg)
        ).

The body of interpret\_actions/3 should be read as: execute action M on the entity corresponding to Id1 with the argument Id2 (remember that arguments preceded by a dollar-mark are left unchanged). Since we might need to update an entity several times, it’s re-added to the list of entities whenever it’s updated.

Putting everything together

We need to make a small change to init/0 in the game object. Instead of building a world manually it’ll take a script file as argument and ask the interpreter to interpret (compile!) it.

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

That’s pretty much it – the end of Bacchus-Bosch. As I suspected when I started the project the final game isn’t very fun. Wait, scratch that, it might be the worst game I’ve ever played, and that includes the infamous yellow car game. But it does have a magic banana, that ought to count for something. In any case it wouldn’t be hard to create more engrossing games since all the building blocks are in place. It should also be noted that the engine is hardly limited to text-based or turn-based games. In a real-time game we could for instance run the update method a fixed amount of times per second instead of waiting for player input. We could also add e.g. role playing elements by defining new properties.

I hope that this pentalogy has been at least somewhat comprehensible and coherent. What the future holds for the blog I dare not promise. Hopefully we’ll someday see the return of the magic banana!

Source code

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

An Adventure Game – Part 4

And yet again I display exceptional prowess in the (un)holy art of procrastination. This time I blame lack of coffee, Sweden’s gloomy weather and the Illuminati. This post will concern two of the three remaining obstacles. First we’re going to add enough properties so that we can create a map consisting of a few rooms together with some entities. Second, we’re going to translate the parsed commands from the user into a suitable set of action commands and execute them with respect to the game world and its entities. As always it’s best to start with a use-case scenario and extrapolate some requirements.

> look

You see a small, rusty key and a door.

> pick up the key and open the door.

> go through the door.

This room is almost identical to the previous one. How eerie. You see a banana and a door.

> eat the door.

no.

> eat the banana

no.

> take the banana and eat it.

Congratulations! You solved mystery of the missing banana!

Let’s don our declarative thinking cap. This particular game consists of two rooms and a player. The player starts in the first room, picks up the key, unlocks the door and enters the second room where he/she in a moment of absolute intellectual clarity manages to deduce that the only way to beat the game is to eat the banana. Just like in real life. We can summarize the requirements as:

  • The player must be able to move from one location to another.
  • The player must be able to reference entities by their names.
  • The door must be linked to the second room.
  • The key must be able to lock/unlock the door.
  • The banana must have the property that the game stops when the player eats it.

Fortunately we can already handle some of these. The most fundamental requirement is that of referencing entities. Since each entity is just a list of properties we’re currently unable to distinguish them in any sensible way. The most obvious solution is to add another property, identity\_property, which describes the property of having an identity. For example, the door in the scenario would be represented by the list:

[openable\_property-State_1, printable\_property-State_2, ..., identity\_property-State_n]

For simplicity the state of identity\_property is just going to be an atom, e.g. door. In a real implementation it would of course be preferable to use a more complex data structure so that entities can be referenced by attributes as well, e.g. “wooden door”, but the basic idea is the same. Of course, just because this is a nice, declarative solution doesn’t mean that it’s good. To quote Richard O’Keefe from The Craft of Prolog:

The nasty thing about declarative programming is that some clear specifications make incredibly bad programs.

It’s not to hard to see that storing the identity of an entity as a property is hopelessly inefficient. To find an entity in a container we have to iterate through the whole container and check whether or not every element satisfies the identity property in question. Ouch. It would be a much better idea to demand that all entities have an identity and then store the container as a tree where nodes are entities ordered by their identities. Of course, it doesn’t mean that I’m going to use this solution just because it’s better! Sometimes it’s enough to be aware that something is a potential bottleneck and fix it if/when it becomes a real problem. Or buy a faster computer.

Next up is the problem of the game world. We shall introduce a new property by the name map\_property and stipulate that it consists of a list of rooms and a player. Why not add the player as an item in the current room instead? Just for simplicity; it’s slightly easier to move the player from room to room if we don’t have to explicitly remove him/her from the first room and add him/her to the new one. Since we have removed the player from the rooms we’re going to need another property, that of having a position/being movable, so that it’s always possible to find the current room.

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

    new(identity_property-_).

    action(move, [New], Owner, _, Owner, New).

    action(get_location, [Room], Owner, Room, Owner, Room).
:- end_object.

The state of movable\_property is simply an identity property. When someone issues the move command the current location is changed. Exactly how this works should become clearer later on. For now, let’s concentrate on implementing map\_property. Its state will be a tuple of a list of rooms and the player, and it’ll have commands to add/remove rooms, get the current room, update the rooms and so on.

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

    new([]-[]).

    update(E0, E) :-
        entity::update_property(map_property, E0, Rooms0-P0, Rooms-P, E),
        entity::update(P0, P),
        update_rooms(Rooms0, Rooms).

    update_rooms([], []).
    update_rooms([R0|R0s], [R|Rs]) :-
        entity::update(R0, R),
        update_rooms(R0s, Rs).

    action(add_rooms, [Rooms1], Owner, Rooms2-P, Owner, Rooms-P) :-
        ...

    action(get_room, [Property, R], Owner, Rooms-P, Owner, Rooms-P) :-
        ...

    action(select_room, [Property, R], Owner, Rooms-P, Owner, Rooms1-P) :-
        ...

    action(print, [], Owner, Rooms-P, Owner, Rooms-P) :-
        action(current_room, [Room], Owner, Rooms-P, _, _),
        entity::action(print, [], Room, _).

    action(current_room, [Current], Owner, Rooms-P, Owner, Rooms-P) :-
        entity::action(get_location, [Id], P, _),
        list::member(Current, Rooms),
        entity::get_property(Current, Id).

    action(get_player, [P], Owner, Rooms-P, Owner, Rooms-P).

:- end_object.

It’s not necessary to study the details of this particular implementation, but some of the predicates demand an explanation. update/2 uses update\_property/5 in entity to update map\_property with the state obtained by updating the list of rooms and the player. To put it more simply: it just calls update/2 on the rooms and the player. The print command extracts the current room and prints it (it would not be very interesting to print anything else). The current\_room command gets the current location of the player and then uses member/2 to find the room with that particular identity.

Then there are doors. To have a text-game without lots of doors would simply be madness. Given the representation of the game world, each door must contain the identity of the area which it leads to. It just stores the identity, not the area itself (since all areas are stored in the map\_property). We shall store this identity in entrance\_property:

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

    new(identity_property-_).

    action(get_location, [Location], Owner, Location, Owner, Location).
:- end_object.

So when we create a door we plug in an entrance\_property with a suitable identity of a room.

Translating commands to entity actions

Before we begin the translation process we’re going to define some useful action commands in container\_property and map\_property. The most frequently used action will be that of extracting  an entity according to some property (e.g. the identity), perform some state-changing operation and then adding it anew. This procedure is necessary since we don’t have explicit state: whenever we extract an entity we get a copy of it, and changes to this copy won’t affect the original. For this purpose we’re going to define two additional action commands in container\_property and map\_property that takes three arguments:

  • P – the property of the entity that shall be updated.
  • Old – will be unified with the old entity.
  • New – the new entity.
:- object(container_property,
    extends(property)).

     .
     .
     . % As before.

    action(update_item, [P, Old, New], Owner, Items, Owner, [New|Items1]) :-
        list::select(Old, Items, Items1),
        entity::get_property(Old, P).

    .
    .
    . % As before.
:- end_object.

The neat thing about this definition is that we can extract an entity with Old and simply pass a variable as New, and unify this variable to the updated entity later on. The definition in map\_property is similar, but works for the player and the current room.

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

    .
    .
    . % As before.

    action(update_current_room, [Current0, Current],
           Owner, Rooms-P, Owner, [Current|Rooms1]-P) :-
        entity::action(get_location, [Id], P, _),
        list::select(Current0, Rooms, Rooms1),
        entity::get_property(Current0, Id).

    action(update_player, [P0, P], Owner, Rooms-P0, Owner, Rooms-P).

    .
    .
    . % As before.

:- end_object.

Now we can finally begin with the translation process. Since we know that the input from the user will be a list of commands (remember that conjunctions are allowed) we will execute them one by one and thread the state of the game world.

eval_commands([], World, World).
eval_commands([C|Cs], World0, World) :-
    write('The command is: '), write(C), nl,
    eval_command(C, World0, World1),
    eval_commands(Cs, World1, World).

Each eval\_command/3 rule changes the state of World0 to World1 according to the command in question. The simplest one is the look-command with no arguments, that just prints the current room:

    eval_command(look-[], World, World) :-
        entity::action(current_room, [Room], World, _),
        write('You see: '), nl,
        entity::action(print_children, [], Room, _).

It asks the game world for its current room and then issues the print\_children command. The take-command is slightly more convoluted. It takes an identity as argument, tries to find the entity in question and asks the player to pick it up.

eval_command(take-[Id], World0, World) :-
    entity::action(update_current_room, [R0, R], World0, World1),
    entity::action(update_player, [P0, P], World1, World),
    entity::action(select_item, [identity_property-Id, Item], R0, R),
    entity::action(add_item, [Item], P0, P).

The move-command is perhaps the most complex of the bunch, but follows the same basic structure:

    eval_command(move-[Id], World0, World) :-
        entity::action(current_room, [Room], World0, _),
        entity::action(update_player, [P0, P], World0, World),
        entity::action(get_item, [identity_property-Id, Entrance],
                       Room, _),
        entity::action(open, [], Entrance, _),
        entity::action(get_location, [Location], Entrance, _),
        entity::action(move, [Location], P0, P).

It tries to find and open the entrance in the current room, asks it where it leads and finally asks the player to move to that location. The lock/unlock and open/close commands are implemented in the same way. One problem remains though: it’s possible to take the key, unlock the door, open it and go through it, but no way to actually finish the game. Just like everything else this functionality can be implemented in a number of ways. It might be tempting to somehow augment the top-loop and in every iteration check whether or not the final state have been reached, but this is needlessly complicated. Instead we’re going to introduce a special entity with only two properties, that of having the identity final\_state and that of being printable. It’s constructed as:

    build_win_screen(Screen) :-
        Screen = [printable_property - State, identity_property-final_state],
        State = "Congratulations! A winner is you!\n (No, you can't quit. Stop trying.)\n".

Then we need an object that has the effect that it asks the player to move itself to the final state whenever it is used, for instance a banana.

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

    action(dissolve, [E0, E], Owner, State, Owner, State) :-
        entity::action(move, [identity_property-final_state], E0, E).

:- end_object.

The banana entity is created by combining an identity, a printable, a carriable and a fruit property:

    build_test_banana(Banana) :-
        Banana = [fruit_property - State1, printable_property-State2,
                  identity_property-banana, carriable_property-State3],
        fruit_property::new(State1),
        banana_description(State2),
        carriable_property::new(State3).

Then we of course need an eat-command, but this is straightforward to implement. So what happens when the player eats the banana is that the current location changes to final\_state. This room doesn’t have any entities and doesn’t support any operations besides being printed, which means that the player can’t return to the rest of the game world and have completed the game.

Putting everything together

We shall use the top-loop from part 2, but with some modifications. The input will be parsed into commands that are executed with respect to the current game world. The loop then calls itself recursively with the new state and asks for new input.

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

    repl(S, History, World0) :-
        entity::update(World0, World1),
        entity::action(print, [], World1, _),
        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, World1, World) ->
            true
        ;   write('no.'), % This is Prolog after all.
            nl,
            World = World1
        ),
        write('-------------------'), nl,
        repl(S, AtomTags, World).

    eval(History, AtomTags, World, World1) :-
        nlp::resolve_pronouns(History, AtomTags, AtomTags1),
        nlp::parse_atoms(AtomTags1, _, Commands),
        eval_commands(Commands, World, World1).

Like a professional TV-chef I prepared a small test world and got the following result (with some of the debug output omitted):

Welcome to Bacchus-Bosch!
A rather unremarkable room.
> look

You see:
A slightly bent key.
A wooden door with a small and rusty lock.
——————-
A rather unremarkable room.
> open the door

no.
——————-
A rather unremarkable room.
> take the key and unlock the door with it

——————-
A rather unremarkable room.
> go through the door
——————-
A room almost identical to the previous one. What on earth is going on!?
> look

You see:
A yellow banana. Hot diggity dog!
A wooden door with a small and rusty lock.
——————-
A room almost identical to the previous one. What on earth is going on!?
> take the banana
——————-
A room almost identical to the previous one. What on earth is going on!?
> eat it
——————-
Congratulations! A winner is you!
(No, you can’t quit. Stop trying.)

The final herculean task, the creation of a script-language, is saved for the next entry!

Source code

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