ZORK

Version française

One of the first video games I played was called Scott Adams Adventureland. At least according to what I could glean on the Internet. It was delivered with the computer that my father had bought in the very first days of personal computing, a time as old as World War II was for me at the time. This game was a variation on Zork, a minimalist game invented at MIT. Truly minimalist... There was no image, just text, and you walked around the game writing commands in English, the majority of which sent back cryptic messages like: "I don't understand". Worse, my knowledge of English at the time was rudimentary and I spent more time in the dictionary looking up vocabulary than playing. At least in the beginning...

However, Scott Adams Adventureland, despite its archaic form, may have unconsciously influenced my interests: I spent a good part of my career writing Natural Language Processing (NLP) software.

The sadism of video game designers can have terrifying effects afterwards. We can never say it enough. If further proof were needed, one need only look at the strange status of this game in geek culture: Sheldon, for example, plays Zork in one of the episodes of season 4 of Big Bang Theory. He quickly loses his temper, very quickly...

However, the mechanics of this game offers a unique opportunity to introduce some of the most interesting aspects of functional programming...

And of course, the examples will be illustrated with LispE code...

The game code is in the directory: examples/patterns/minizork_en.lisp

Play

To examine the code and play, you can launch:

lispe -e minizork_en.lisp

You can even debug the game directly by placing "breakpoints" with ctrl-b. Then just execute the code with: Ctrl-X d to enter the debugger.

Game board

The game consists of a 3x3 grid in which you can move around. Each square is associated with a description in the dictionary: castlemap.

(setq castlemap {
      "1:1":"You stand in front of a gate."
      "1:2":"..."
      "1:0":"..."
      "2:1":"..."
      "0:0":"..."
      "0:2":"..."
      "2:0":"..."
      "2:2":"..."
   }
)

Each time you move in the grid, the game displays the corresponding description. There are a multitude of dictionaries and lists to record the objects present in the boxes, the dangers that await the traveler or the valid directions to go from one point to another.

; The objects present in the different boxes

(setq objects {
      "1:1": 'stone
      ...
   }
)

The game board is therefore limited to a few text descriptions that will be used for each move in the grid.

Lazy Evaluation

Finally, let's note that dictionary declaration is an interesting case of lazy evaluation. Indeed, LispE does not create a dictionary when it encounters a static definition but the sequence of commands to build it .

(defun test(s) (setq s {1:x "a": "b"}))

; is compiled in the following form:

(defun test(s) (setq s (key (key) 1 x) "a" "b"))

• key used without argument returns a dictionary
• key d k returns nil or the value stored for key k in dictionary d.
• key d k v initializes the dictionary d with the key k and the value v and returns d.

In this way, the dictionary is only created on call, when the need arises. In fact, the "{}" are only syntactic sugar to make dictionaries easier to handle, as nested calls of key have the unfortunate tendency to quickly become unreadable .

Commands

It is clear that the above description is not very original. On a Yawn Scale (YS) of 1 to 10, we approach 7 without any problem. Indeed, the difficulty is to analyze a command such as: go west and to deduce that it is a direction. In the same way, we also want to be able to say: take the stone and deduce that it is a matter of picking up an object on the ground.

This is where Functional Programming shows the tip of its nose...

We are going to base all actions on the joint use of Data Types and Pattern Matching Functions, with a hint of map and filter.

Input

Input is done via the input function which returns the string typed on the keyboard. The result is stored in the variable dialog ( YS=6).

The following code is a more subtle one... (YS=3)

   (setq dialog (+ (upper (at dialog 0)) (lower (extract dialog 1 (size dialog)))))
   (setq commands (map (\(x) (select (key synonyms x) x)) (split dialog " ")))
   ; we transform each of our strings into atoms, for match sake
   ; we remove useless words: the, a etc...
   (setq commands (filter (\(x) (not (key stopwords x))) (map 'atom commands))))

The first line takes our command: get the stone to turn it into: Get the stone. In other words, we put the string in lowercase and we put the first letter in uppercase.

The dialogue is then cut along spaces. We then check for each word if there is a synonym. The word Get has a synonym (see the synonyms dictionary in the code) which turns out to be the word Take.

Our sentence becomes a list of strings: ("Take" "the" "stone")

The last line transforms this string list into a list of atoms, from which useless words (stopwords) are removed.

Note the combination of filter and map which allows in two lines of code to replace words by their synonyms, to transform each of them into an atom and to remove those that are considered redundant. Finally, note the use of (\(x)...) which is a more compact way of writing (lambda(x)...).

Our sentence is now a list of atoms: (Take stone).

maybe

maybe is an instruction that could make you think of a try/catch (YS=5). The instructions are executed in sequence, if one of them triggers an error, then the last line is executed:

   (maybe
      (println (action commands))
      (println (random_choice 1 msgs 10))
   )

Remember that commands is a list of atoms which in this context will be evaluated as a data type. If this evaluation fails, we will display a random message from the list of error messages.

And there begins the elegance of pattern programming...

Data Types

The following description is found at the beginning of the code (YS=2):

(data
   [Move atom_]
   [Break atom_ atom_]
   [Open atom_ atom_]
   [Kill atom_ atom_]
   [Take atom_]
   [Drop atom_]
)

These are the valid actions in the game... Note that the previous work consists in matching these definitions with the text that the player has written. The synonyms and empty word filters have no other objective than to establish this correspondence.

Moreover, we can then benefit from an intrinsic verification of the user declarations... If the sentence contains one word too many or too few, the system can immediately return an error message based on these declarations.

Thus, maybe takes all its meaning. If the sentence does not correspond to one of the statements allowed here, an error message is immediately returned.

Pattern Functions

But for the mechanics to be complete, one element is missing. We have shown how an utterance can be transformed into a data structure.

We will now show how this structure can be exploited to our advantage (YS=1).

For this, we will use defpat, the pattern function operator.

Each data type is then associated with a function whose name is action.

(defpat action ([Take x] ) ...)

; We can obviously define in advance the atoms we are looking for.
; direction = north, south, west, east
(defpat action ([Move 'north] ) ...)
(defpat action ([Move 'south] ) ...)
(defpat action ([Move 'west] ) ...)
(defpat action ([Move 'east] ) ...)

Thus, the (action commands) call consists in choosing the function that corresponds to the data structure obtained after processing the player's command.

If commands is not a valid data type, a first error message will be returned and caught by maybe.

Otherwise LispE will execute the function corresponding to this data type.

Independence

It is important to note that the granularity of these different functions can vary depending on whether one wants to have a general or very fine-grain definition of the arguments. It is therefore quite simple to enrich the game mechanics with additional functions, and this in a rather robust way. Indeed, the alternative is to place cascades of if in your functions, which can eventually have uncontrollable side effects, especially if you want to test many particular combinations of values. Unless, of course, you want to offer your code as a sacrifice to the Great Spaghetti Monster.

Thus, adding new Data Types and thus new Pattern Functions is done completely independently from the rest of the code, which ensures a form of stability that a cascade of if or switch can hardly offer, especially if they are at the heart of the game mechanics.

A well-oiled machine

As can be seen, this code benefits from a joint use of data structures and pattern functions. Thus, syntax checking is covered by the simple declaration of data structures. As for execution, it consists in providing an action function that takes these data structures as arguments.

You can then enrich the story as you wish...