ZORK

English Version

L'un des premiers jeux vidéos auquel j'ai joué s'appelait: Scott Adams Adventureland. Enfin du moins d'après les traces que j'ai pu retrouver sur Internet. Il accompagnait l'ordinateur que mon père avait acheté aux tout premiers temps de l'informatique individuelle, un temps aussi ancien que la deuxième guerre mondiale l'était pour moi à l'époque. Ce jeu était une variation sur Zork, un jeu minimaliste inventé au MIT. Vraiment minimaliste... Il n'y avait pas d'image, juste du texte et on se baladait dans le jeu en écrivant des commandes en anglais dont la majorité renvoyait un message sibyllin du style: "je n'ai pas compris ce que vous dites". Pire, ma connaissance de l'anglais à l'époque était on ne peut plus rudimentaire et je passais plus de temps dans le dictionnaire à chercher du vocabulaire qu'à jouer. Du moins au début...

Pourtant, Scott Adams Adventureland en dépit de sa forme archaïque, a peut-être influencé de façon inconsciente mes centres d'intérêts: j'ai en effet passé une bonne partie de ma carrière à écrire des logiciels de Traitement Automatique des Langues.

Comme quoi le sadisme des concepteurs de jeux vidéos peut avoir des effets terrifiants par la suite. On ne le dira jamais assez. S'il en fallait une preuve supplémentaire, il suffit d'examiner le statut étrange de ce jeu dans la culture Geek: Sheldon par exemple joue à Zork dans l'un des épisodes de la saison 4 de Big Bang Theory. Il y perd vite, très vite son sang froid...

Tout cela pour vous dire que la mécanique de ce jeu offre une occasion unique d'introduire certains des aspects les plus intéressants de la programmation fonctionnelle...

Et évidemment, les exemples seront illustrés avec du code LispE...

Le code du jeu est dans le répertoire: examples/patterns/minizork_fr.lisp

Jouer

Pour examiner le code et jouer, vous pouvez lancer:

lispe -e minizork_fr.lisp

Vous pouvez même débogguer le jeu directement en plaçant des "breakpoints" avec ctrl-b. Il suffit ensuite d'exécuter le code avec: Ctrl-X d pour entrer dans le déboggueur.

Plateau de jeu

Le jeu consiste en une grille de 3x3 dans laquelle on peut se déplacer. Chaque case est associée à une description dans le dictionnaire: castlemap.

(setq castlemap {
      "1:1":"Vous vous tenez devant une porte."
      "1:2":"..."
      "1:0":"..."
      "2:1":"..."
      "0:0":"..."
      "0:2":"..."
      "2:0":"..."
      "2:2":"..."
   }
)

A chaque déplacement dans la grille, le jeu affiche la description correspondante. Il existe une multitude de dictionnaires et de listes pour enregistrer les objets présents dans les cases, les dangers qui guettent le voyageur ou bien encore les directions valides pour aller d'un point à un autre.

; Les objets présents dans les différentes cases

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

Le plateau de jeu se résume donc à quelques descriptions textuelles que l'on exploitera à chaque déplacement dans la grille.

Evaluation différée (lazy evaluation)

Notons enfin un aspect amusant sur la déclaration d'un dictionnaire. Il s'agit d'un cas intéressant d'évaluation différée. En effet, LispE ne crée pas un dictionnaire quand il rencontre une définition statique mais la suite d'ordre pour le construire...

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

; est compilé sous la forme suivante:

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

• key utilisé sans argument renvoie un dictionnaire
• key d k renvoie nil ou la valeur enregistrée pour la clef k dans le dictionnaire d
• key d k v enregistre la valeur v dans le dictionnaire d avec la clef k, puis renvoie d

De cette façon, la création du dictionnaire est uniquement effectuée à l'appel, lorsque le besoin se fait sentir. En fait, les "{}" ne sont que du sirop syntaxique pour rendre les dictionnaires plus simples à manipuler, les appels imbriqués de key ayant la fâcheuse tendance de devenir rapidement illisible...

Les commandes

Il est clair que la description ci-dessus n'a rien de bien original. Sur une échelle de bâillement (EB) de 1 à 10, on approche les 7 sans problème.

C'est là que la programmation fonctionnelle montre le bout de son nez...

En effet, nous voulons pouvoir analyser des ordres tels que va à l'ouest ou prend une pierre et ce de la façon la plus simple et la plus contrôlée possible.

Nous allons faire reposer l'ensemble des actions sur l'utilisation conjointe des Types de Données et des fonctions à motif, avec un soupçon de fonctions de haut niveau.

La saisie

La saisie est effectuée via la fonction input qui renvoie la chaine tapée au clavier. Le résultat est enregistrée dans la variable dialog ( EB=6).

Le code qui suit est revanche un poil plus subtile... (EB=3)

   (setq dialog (+ (upper (at dialog 0)) (deaccentuate (lower (extract dialog 1 (size dialog))))))
   (setq commands (map (\(x) (select (key synonyms x) x)) (rgx_split (rgx "{%s%p}" dialog)))
   ; Chaque chaine est transformée en un atome
   ; Nous retirons aussi les mots vides
   (setq commands (filter (\(x) (not (key stopwords x))) (map 'atom commands)))

Nous supposerons que le joueur a proposé comme ordre: ramasse la pierre.

La première ligne prend cet ordre pour le transformer en: Ramasse la pierre. Autrement dit, on met la chaine en minuscule et on met la première lettre en majuscule. Remarquons l'utilisation de deaccentuate qui remplace les voyelles accentuées par la voyelle correspondante sans accent. Cela permet d'homogénéiser la saisie du joueur...

Le dialogue est ensuite découpé le long des espaces et des ponctuations. On utilise rgx_split qui permet de découper une chaine en utilisant des expressions régulières. Ici notre expression est une disjonction entre des espaces (%s) et des ponctuations (%p). On vérifie ensuite pour chaque mot s'il existe un synonyme. Le mot Ramasse, par exemple, est ici un synonyme de Prendre (voir le dictionnaire synonyms dans le code).

Notre phrase devient une liste de chaines de caractères: ("Prendre" "la" "pierre")

La dernière ligne transforme cette liste de chaines en une liste d'atomes, dont on vire les mots vides (stopwords).

Remarquez la combinaison de filter et map qui permet en deux lignes de code de remplacer des mots par leurs synonymes, de les transformer chacun en un atome et de virer ceux que l'on juge redondant. Notez enfin, l'utilisation de (\(x)...) qui est une façon plus compacte d'écrire (lambda(x)...).

Notre phrase est désormais une liste d'atomes: (Prendre pierre).

maybe

maybe est une instruction qui pourrait faire penser à un try/catch (EB=5). On exécute en séquence les instructions, si par malheur l'une d'entre elles déclenche une erreur, on exécute alors la dernière ligne:

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

Rappelons que commands est une liste d'atomes qui dans ce contexte va être évaluée comme un type de données. Si cette évaluation échoue, nous afficherons un message aléatoire tirée de la liste des messages d'erreur.

Et là commence l'élégance de la programmation par motif...

Les Types de Données

Au début du code, on trouve la définition suivante (EB=2):

(data
   [Aller atom_]
   [Casser atom_ atom_]
   [Ouvrir atom_ atom_]
   [Tuer atom_ atom_]
   [Prendre atom_]
   [Lacher atom_]
)

Il s'agit des actions valides dans le jeu... Remarquons que le travail précédent consiste donc à projeter sur ces définitions le texte que le joueur a écrit. Les synonymes et les filtrages de mots vides n'ont d'autre objectif que d'établir cette correspondance.

De plus nous pouvons dès lors bénéficier d'une vérification intrinsèque des énoncés utilisateurs... Si la phrase contient un mot de trop ou de moins, le système pourra immédiatement renvoyer un message d'erreur sur la base même de ces déclarations.

Ainsi, le maybe prend tout son sens. Si la phrase ne correspond pas à une des déclarations autorisées ici, un message d'erreur est immédiatement renvoyé.

Fonctions à motif

Mais pour que la mécanique soit complète, il manque un élément. Nous avons montré comment un énoncé pouvait être transformé en une structure de données.

Nous allons montrer maintenant comment on peut exploiter cette structure à notre avantage (EB=1).

Pour cela, nous allons utiliser les defpat, les fonctions définies par pattern.

Chaque type de données est alors associé avec une fonction dont le nom est action.

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

; On peut évidemment définir à l'avance les atomes que l'on recherche
; direction = nord, sud, ouest, est
(defpat action ( [Aller 'nord] ) ...)
(defpat action ( [Aller 'sud] ) ...)
(defpat action ( [Aller 'ouest] ) ...)
(defpat action ( [Aller 'est] ) ...)

Ainsi, l'appel (action commands) consiste à choisir la fonction qui correspond à la structure de données obtenue après traitement de la commande du joueur.

Si commands n'est pas une structure de données valide un premier message d'erreur sera renvoyé et intercepté par maybe.

Sinon, LispE exécutera la fonction correspondant à cette structure de données.

Indépendance

Il est important de noter que la granularité de ces différentes fonctions peut varier selon que l'on veut avoir une définition générale ou très fine des arguments. Il devient dès lors très simple d'enrichir la mécanique du jeu avec des fonctions supplémentaires, et ceci de façon plutôt robuste. En effet, l'alternative est de placer des cascades de if dans vos fonctions ce qui peut avoir à terme des effets de bord incontrôlables, en particulier si vous voulez tester de nombreuses combinaisons particulières de valeurs. A moins évidemment, que ne vous désiriez offrir votre code en sacrifice au Grand Spaghetti Monster.

Ainsi, rajouter de nouveaux Types de Données et par là-même de nouvelles fonctions à motif se fait en toute indépendance du reste du code, ce qui assure une forme de stabilité qu'une cascade de if ou de switch ne peut guère offrir, surtout s'ils sont au coeur de la mécanique de jeu.

Une mécanique bien huilée

Comme on le voit, le fonctionnement de ce code repose sur une utilisation conjointe des structures de données et des fonctions à motif. Ainsi, la vérification syntaxique est couverte par la simple déclaration des structures de données. Quant à l'exécution, elle consiste à fournir une fonction action qui prend ces structures de données en argument.

Rien n'est plus simple dès lors d'enrichir l'histoire à votre gré...