Dans le premier article de cette série, je vous ai montré comment les utiliser les relations dans ink. On a pu voir comme faire et défaire des relations avec relate()
et unrelate()
et comment interroger le système avec isRelated()
et whatIs()
mais on n’a absolument pas regardé comment ça marche « à l’intérieur ». Et moi, j’aime bien savoir comment les choses sont faites.
Ainsi, dans cet article, nous verrons :
- le fonctionnement du cœur du système
- une étude détaillée du code que vous pourrez survoler ou lire attentivement selon votre intérêt
J’avais également « promis » de donner quelques exemples de choses intéressantes pour vos jeux à construire par dessus ce système ainsi qu’une traduction en français du système, mais cet article est déjà suffisamment long, ça sera pour la partie 3 !
Cet article est plutôt technique, en particulier la section « Étude du code d’inkle« . Elle s’adresse a priori à des personnes utilisant déjà le langage ink. Je vais détailler comment ce code spécifique fonctionne mais je ne ferai pas de rappels sur les bases telles que les variables, les listes ou les fonctions.
Fonctionnement
Comment faire pour enregistrer l’information « X est en relation avec Y via R » ? Il faut qu’on mette ces 3 éléments ensemble dans une structure de données. Dans la plupart des langages informatiques, on pourrait les mettre dans un tableau [X, R, Y]
, un objet ou un tuple. Avec ink, on est très limité. Il n’y a qu’une seule structure de données, la LIST.
LIST Personnes = Alice, Bernard, Charlie
LIST Relations = Aime
// On peut regrouper ces éléments dans une variable de type LIST
VAR relation = (Alice, Aime, Bernard)
Si vous avez lu notre article sur les listes, vous savez qu’on ne peut pas avoir plusieurs fois un même élément dans une liste. On ne pourra donc pas stocker une relation du type (Alice, Aime, Alice)
.
Ce n’est pas le seul problème : une liste n’a pas vraiment d’ordre, donc (Bernard, Aime, Alice
) c’est la même chose que (Alice, Aime, Bernard)
, ce qui est problématique.
Et le pire reste à venir : on a besoin de stocker plusieurs relations, on ne sait pas combien, ça va dépendre de ce que fait le joueur. On ne peut donc pas mettre chaque relation dans sa variable. Il faudrait pouvoir les mettre dans un tableau, que nous n’avons pas dans ink.
La LIST, seule structure de données d’ink, ne fait pas l’affaire… Alors, on est coincé ? Et bien non, chez inkle, ils ont réalisé qu’il y a dans ink un système qui permet de stocker ces triplets, dans l’ordre qu’on veut, et autant qu’on veut. Ce système, c’est…
… les chaînes de caractères. Voyez plutôt :
LIST Personnes = Alice, Bernard, Charlie
LIST Relations = Aime
VAR data = "Alice,Aime,Bernard/Bernard,Aime,Alice/"
Et voilà, on peut stocker nos relations ! Bon je dois vous avouer qu’on n’est pas sorti des ronces car :
- on stocke la chaîne
"Alice"
et pas l’itemAlice
- on ne peut pas séparer une chaîne en plus petites pour extraire les relations (on ferait
data.split("/")
dans d’autres langages par exemple) - on ne peut pas supprimer un morceau d’une chaîne, seulement en ajouter, ce qui est gênant pour supprimer une relation
On ne peut faire que deux choses avec les chaînes, et on va tout faire avec ça :
- ajouter une chaîne au bout d’une autre avec
+=
- vérifier si une chaîne en contient une autre avec
has
(ou l’opérateur équivalent :?
)
Voici un exemple simplifié à l’extrême du fonctionnement de relate()
et isRelated()
:
LIST Personnes = Alice, Bernard, Charlie
LIST Relations = Aime
VAR data = ""
~ relate(Alice, Aime, Bernard)
~ relate(Charlie, Aime, Charlie)
~ isRelated(Alice, Aime, Bernard) // true
~ isRelated(Bernard, Aime, Alice) // false
~ isRelated(Charlie, Aime, Charlie) // true
== function relate(X, R, Y)
// On ajoute le triplet à notre "base de données" data.
~ data += "{X},{R},{Y}/"
== function isRelated(X, R, Y)
// Si on trouve la chaîne "X,R,Y/" dans data, c'est que les éléments sont en relation.
~ return data has "{X},{R},{Y}/"
Ça ne nous dit pas comment nous allons gérer unrelate()
et whatIs()
, mais pour ça, il est temps de plonger dans le véritable code d’inkle.
Étude du code d’inkle
Qu’est-ce qui justifie qu’on passe de deux fonctions d’une ligne chacune à un code de 150 lignes ? Avec 150 lignes, on peut :
- vérifier la validité des arguments passés aux fonctions (en déclarant au préalable quel type de
LIST
est en relation avec quel autre type) - mettre en relation plusieurs items d’un coup au lieu d’appeler
relate()
de nombreuses fois - faire des requêtes du type « Qui aime Alice ? » ou du type « Qui Alice aime ? »
- supprimer des relations
1 – Validation
Si dans notre jeu il peut y avoir une relation, par exemple, entre un objet et un propriétaire, ce serait bien d’éviter d’inverser la relation par erreur avec relate(VéloToutTerrain, Possède, John)
ou bien de carrément s’emmêler les pinceaux et écrire relate(Jill, Possède, Chapitre3)
. Ça peut paraitre simple d’éviter ces erreurs, mais quand votre code devient complexe et que vous manipulez des variables, relate(obj, Possède, interlocuteur)
saute peut-être moins aux yeux.
Le système de relations expose une fonction relate()
, qui appelle validate()
et si ça passe, appelle une fonction interne _relate()
. Comme _relate()
est récursif (on le verra juste après), ça permet de faire la vérification une seule fois.
=== function relate(x1, rel, x2)
{ not validate(x1, x2, rel):
~ return ()
}
~ _relate(x1, x2, rel)
La fonction validate()
appelle une fonction que l’on doit nous même définir dans chaque jeu. C’est relationDatabase()
et elle sert à définir pour chaque relation ce qui peut aller à gauche et à droite.
Dans la partie 1, on avait écrit :
=== function relationDatabase(relation, gauche)
{ relation:
// Ex : La relation EstEn lie des Objets (à gauche) à des Matières (à droite)
- EstEn: ~ return gauche_droite(gauche, Objets, Matières)
- Contient: ~ return gauche_droite(gauche, Objets, Objets)
- Réclame: ~ return gauche_droite(gauche, Objets, Formes)
- EstDeForme: ~ return gauche_droite(gauche, Objets, Formes)
- Possède: ~ return gauche_droite(gauche, Personnes, Objets)
- Connait: ~ return gauche_droite(gauche, Personnes, Objets)
}
// gauche_droite() est une fonction utilitaire qui sert juste à pouvoir faire tenir chaque relation sur une seule ligne
=== function gauche_droite(gauche, listeGauche, listeDroite)
{ gauche:
~ return listeGauche
- else:
~ return listeDroite
}
Pour vérifier qu’x1
est bien un membre de la liste de gauche, validate()
récupère la liste de gauche en appelant relationDatabase(rel, true)
puis teste l’appartenance avec ITEM_IS_MEMBER_OF_LIST()
. Pareil pour x2
et la liste de droite. Et si c’est pas bon, ça affiche un texte d’erreur : [ ERROR: John not a valid rhs for Possède ]. lhs
signifie left-hand side (côté gauche) et rhs
signifie right-hand side (coté droit)
=== function validate(x1, x2, rel)
{ x1 && not ITEM_IS_MEMBER_OF_LIST(x1, relationDatabase(rel, true)):
[ ERROR: {x1} not a valid lhs for {rel} ]
~ return false
}
{ x2 && not ITEM_IS_MEMBER_OF_LIST(x2, relationDatabase(rel, false)):
[ ERROR: {x2} not a valid rhs for {rel} ]
~ return false
}
~ return true
Pour tester l’appartenance à une liste, on a l’opérateur ?
qui peut aussi s’écrire has
. Et il ne faut pas oublier qu’une liste peut avoir des items activés et d’autres désactivés. ?/has
ne teste que les éléments activés. Pour détecter aussi éléments désactivés, on crée une copie de la liste où tout est activé. Par exemple :
LIST Fruits = Pomme, (Poire)
{Fruits has Pomme} // false
{Fruits has Poire} // true
{LIST_ALL(Fruits) has Pomme} // true
{LIST_ALL(Fruits) has Poire} // true
Ainsi, le code de ITEM_IS_MEMBER_OF_LIST()
tient sur une ligne :
=== function ITEM_IS_MEMBER_OF_LIST(k, list)
~ return k && LIST_ALL(list) ? k
2 – Mettre en relation
Maintenant que nos items de gauche et de droite sont bien validés, on va pouvoir entrer dans la fonction _relate()
. On va commencer par gérer le cas relate(item1, relation, item2)
puis on traitera du cas plus complexe relate(liste_d_items1, relation, liste_d_items2)
.
Si vous avez suivi depuis le début, on va avoir besoin de stocker les informations dans une chaîne de caractères :
VAR pairstore = "" // J'aurais plutôt appelé ça tripletstore 🤷🏻
Dans l’exemple du début, j’avais proposé de stocker les relations sous la forme X,R,Y/
, le code d’inkle utilise plutôt :X>R>Y;
et définit la fonction _pairString()
pour la générer :
=== function _pairString(x1, x2, rel)
~ return ":{x1}>{rel}>{x2};"
La version simplifié de _relate()
est très simple : si el1 et el2 ne sont pas déjà en relation, on ajoute leur « pairString » à la « pairstore ». On teste s’ils sont en relation avec _isRelated()
, fonction que l’on verra plus tard.
// Je reprends les noms de variables du code d'inkle, el1 = element 1
=== function _relate(el1, el2, rel)
{ not _isRelated(el1, el2, rel):
~ pairstore += _pairString(el1, el2, rel)
}
Passons au cas général où l’on met en relation directement plusieurs éléments à la fois. Ça parait simple : on boucle sur les deux listes et on met en relation les paires d’éléments. Oui. Sauf que…
ink n’a pas ce qu’on appelle dans la plupart des langages de programmation de « boucles for » :
for (el1 of list1) {
for (el2 of list2) {
// mettre en relation el1 et el2
}
}
Ça, on ne peut pas le faire avec ink.
Tout ce qui suit explique comment faire une double récursion pour remplacer la double itération que l’on ne peut pas faire. Si ça ne vous intéresse pas, vous pouvez directement passer à la suite.
Quand on doit boucler avec ink, en général on fait ça avec de la récursivité. Je ne vais pas faire un cours sur ça, c’est un concept en programmation qui déroute plus d’un étudiant mais en quelques mots : la récursivité, c’est quand une fonction s’appelle elle même.
L’exemple classique est celui du calcul de la factorielle d’un nombre. Pour rappel, la factorielle de n, c’est 1×2×3×…(n-1)×n. La clé, c’est de se rendre compte que factorielle(n) = (1×2×3×…(n-1)) × n = factorielle(n-1) × n
. On peut donc calculer factorielle(n)
en calculant d’abord factorielle(n-1)
et en multipliant le résultat par n. Et bien sûr, pour calculer factorielle(n-1)
, on va d’abord calculer factorielle(n-2)
… Et ce jusqu’à l’infini ? Mais non, surtout pas ! Il faut bien s’arrêter à un moment. Dans le cas de la factorielle, on s’arrête à 0 (factorielle(0) = 1, mais on va pas faire un cours de maths).
=== function factorielle(n)
{ n == 0:
~ return 1
- else:
~ return n * factorielle(n - 1)
}
Avec ça, vous avez les bases pour comprendre les fonctions récursives : la fonction s’appelle elle-même et il y a une condition pour s’arrêter et ne pas tourner infiniment.
On va s’en servir pour parcourir des listes avec ink. La fonction va s’occuper d’un élément puis va s’appeler elle-même avec une liste qui contient un élément de moins. La condition d’arrêt, c’est quand la liste est vide.
=== function afficher_liste(liste)
~ temp element = LIST_MIN(liste) // On prend un élément de la liste, ici le plus petit, mais on aurait pu utiliser LIST_MAX ou LIST_RANDOM
// Si on a un élement…
{ element:
// … on l'affiche…
Item : {element}
// … et on "récurse" avec une liste sans cet élément…
~ afficher_liste(liste - element)
}
// …sinon c'est la condition d'arrêt (la liste est vide) et on ne fait rien.
Dans cet exemple, je prends un élément de la liste et quand vient le moment d’appeler récursivement la fonction, je lui passe liste - element
pour fournir une copie de la liste sans l’élément, mais il y a une autre façon de faire sur laquelle vous pouvez tomber (spoiler, ça va être le cas dans quelques lignes…) : on modifie directement la liste lors de l’extraction de l’élément.
~ temp element = pop(liste)
// maintenant, la liste ne contient plus élément, il n'y aura pas besoin de faire "liste - element"
La fonction pop()
est fournie dans l’éditeur Inky, dans le menu Ink > List-handling > List: pop.
// Grâce au modifieur "ref", c'est la liste passée en argument qui est modifiée (-= x).
// Sans "ref", pop() recevrait une copie de la liste et ça ne servirait à rien de la modifier. En programmation, on parle de passage par référence ou par copie.
=== function pop(ref list)
~ temp x = LIST_MIN(list)
~ list -= x
~ return x
Armés de la récursivité et de pop()
, revenons à _relate()
et occupons nous du cas où le deuxième argument est une liste :
=== function _relate(el1, list2, rel)
// On sort un élément de la liste puis…
~ temp el2 = pop(list2)
// … si la liste n'est pas vide…
{ el2:
// … on l'ajoute à pairstore si nécessaire…
{ not _isRelated(el1, el2, rel):
~ pairstore += _pairString(el1, el2, rel)
}
// … puis on "récurse", sachant que list2 ne contient plus cet élément.
~ _relate(el1, list2, rel)
}
// Si el2 est nul, c'est que la liste est vide, on a fini la récursion
Nous sommes prêts à attaquer la dernière étape, la version qui gère aussi une liste à gauche. Appelons-la list1
, comme dans le code, et distinguons trois cas :
list1
est vide : il n’y a rien à mettre en relation, on s’arrêtelist1
contient un seul élément : on est dans le cas qu’on sait déjà gérerlist1
contient plus d’un élément : on va utiliser un deuxième niveau de récursion. On prend un élément delist1
, on appelle récursivement_relate(el1, list2, rel)
(c’est le cas que l’on maitrise) et on appelle aussi récursivement_relate(list1, list2, rel)
(avec un élément en moins danslist1
).
=== function _relate(list1, list2, rel)
{ LIST_COUNT(list1):
- 0: ~ return
- 1: ~ temp el2 = pop(list2)
{ el2:
{ not _isRelated(list1, el2, rel):
~ pairstore += _pairString(list1, el2, rel)
}
~ return _relate(list1, list2, rel)
}
~ return ()
- else:
~ temp el1 = pop(list1)
~ return _relate(el1, list2, rel) + _relate(list1, list2, rel)
}
_relate()
retourne une liste vide et le cas doublement récursif additionne les deux résultats mais ça ne sert à rien car c’est toujours une liste vide et que rien d’autre dans le code n’utilise le résultat de _relate()
. C’est probablement pour que le code soit quasi identique à un autre code que l’on verra plus loin qui fait aussi une double récursion mais retourne un résultat.
3 – Requêtes
Vous êtes toujours là ? Je parie que vous avez cliqué sur « passer à la suite »… Alors, passons à la suite ! Nous avons ajouté des relations dans notre « base de données », c’est bien. Maintenant, il faut pouvoir poser des questions à cette base.
On a vu en partie 1 que le système gère trois types de questions :
isRelated(X, Y, R)
– Est-ce que X est en relation avec Y via la relation R ?whatIs(X, R)
– Qu’est-ce qui est est en relation avec X via R ?whatIs(R, Y)
– Qu’est-ce qui est est en relation avec Y via R ?
Ou pour prendre un cas concret, avec la relation Aime qui lie des Personnes et des Fromages :
- Est-ce que Lilie aime le roquefort ?
- Quels fromages Antonin aime-t-il ?
- Qui aime la mimolette extra-vieille ?
Précision : isRelated()
ne gère qu’un élément de chaque côté à la fois mais whatIs()
peut tester des listes, par exemple whatIs(Aime, (TomeDeKaltbach, MoelleuxDuRevard))
qui nous donnera la liste des personnes qui aiment la tome et des personnes qui aiment le moelleux.
Attention, ce n’est pas la liste des personnes qui aiment à la fois la tome et le moelleux. Pour ça, il vous faut l’intersection whatIs(Aime, Tome) ^ whatIs(Aime, Moelleux)
Commençons par la première forme, car c’est la plus simple. On commence par valider les arguments et on vérifie aussi qu’on appelle la fonction avec des éléments uniques et pas des listes d’éléments. Ensuite, c’est très simple : on génère la « pairString » et on regarde si elle est dans la base. C’est tout.
=== function isRelated(x1, x2, rel)
{ validate(x1, x2, rel):
{LIST_COUNT(x1) > 1 || LIST_COUNT(x2) > 1:
[ERROR: Testing relation {rel} on non-unary lists {x1} and {x2} ]
~ return false
}
~ return _isRelated(x1, x2, rel)
}
=== function _isRelated(x1, x2, rel)
~ temp relString = _pairString(x1, x2, rel)
~ return pairstore ? relString
Pour whatIs()
, qui gère les deux autres formes de question, c’est plus compliqué. Tout d’abord, il faut distinguer les deux formes whatIs(X, R)
et whatIs(R, Y)
. On regarde lequel des deux arguments fait partie de la liste Relations
. Si c’est le deuxième, on est dans le cas whatIs(X, R)
et on appelle la fonction getRelatesTo(X, R)
, et si c’est le premier, c’est whatIs(R, Y)
et on appelle getRelatedFrom(Y, R)
. Et si aucun des deux arguments n’est une relation, c’est une erreur.
=== function whatIs(a1, a2)
{
- ITEM_IS_MEMBER_OF_LIST(a2, Relations):
~ return getRelatesTo(a1, a2)
- ITEM_IS_MEMBER_OF_LIST(a1, Relations):
~ return getRelatedFrom(a2, a1)
- else:
[ ERROR: whatIs needs a relation! ]
}
On peut parler en même temps de getRelatesTo()
et getRelatedFrom()
puisqu’elles sont symétriques. Je vais détailler la première mais vous pourrez voir que la deuxième fait la même chose en inversant gauche et droite.
getRelatesTo()
possède deux paramètres : x1
, les éléments de gauche (un seul ou une liste), et rel
, la relation. On commence donc par valider les arguments passés avec validate()
. Comme on a que des éléments de gauche et une relation, on passe une liste vide ()
à la place des éléments de droite. Retournez voir le code de validate()
et vous verrez que le test est sauté si l’argument est vide.
Ensuite, grâce à relationDatabase()
, on récupère tous les éléments de droite possibles. Enfin, on délègue le travail à _getMatchedPairs()
en lui passant :
- les éléments de gauche (
x1
), - les possibilités de droite (
searchSpace
), - la relation (
rel
) true
, pour dire qu’on est intéressé par les éléments de droite qui sont en relation avec l’élément de gauche
=== function getRelatesTo(x1, rel)
{ not validate(x1, (), rel):
~ return ()
}
~ temp searchSpace = LIST_ALL(relationDatabase(rel, false))
~ return _getMatchedPairs(x1, searchSpace, rel, false)
=== function getRelatedFrom(x2, rel)
{ not validate((), x2, rel):
~ return ()
}
~ temp searchSpace = LIST_ALL(relationDatabase(rel, true))
~ return _getMatchedPairs(searchSpace, x2, rel, true)
Nous arrivons maintenant à la dernière pièce de ce système de requêtes : _getMatchedPairs()
. C’est à la fois compliqué et simple. Compliqué parce qu’on fait une double récursion sur deux listes. Simple parce que c’est exactement ce qu’on a déjà fait tout à l’heure ! Quoi, vous aviez cliqué sur « Passer à la suite » ?
Cette fonction parcourt les deux listes avec une double récursion afin d’appeler isRelated()
pour chacune des paires. Les éléments qui correspondent sont retournés (de gauche ou de droite selon ce qui est demandé via getLhs
). Je ne repasse pas sur les détails de la récursion, c’est exactement la même structure que pour relate()
.
=== function _getMatchedPairs(list1, list2, rel, getLhs)
~ temp ret = ()
{ LIST_COUNT(list1):
- 0: ~ return ()
- 1: ~ temp el2 = pop(list2)
{ el2:
{ _isRelated(list1, el2, rel):
{ getLhs:
~ ret = list1
- else:
~ ret = el2
}
}
~ return ret + _getMatchedPairs(list1, list2, rel, getLhs)
}
~ return ()
- else:
~ temp el1 = pop(list1)
~ return _getMatchedPairs(el1, list2, rel, getLhs) + _getMatchedPairs(list1, list2, rel, getLhs)
}
4 – Supprimer une relation
Courage, nous sommes arrivés à la dernière fonctionnalité : la suppression de relations.
Appelons Xu, Ru et Yu (u = unrelate) le triplet à supprimer. Comme une relation est stockée sous la forme ":Xu>Ru>Yu;"
dans une grande chaîne, il faut pouvoir supprimer ce morceau. Avec ink, on ne peut pas extraire un morceau d’une chaîne, on ne peut pas couper une chaîne. Si on peut savoir qu’une sous-chaîne est contenue dans une chaîne, on ne peut pas savoir à quel endroit. On ne peut pas parcourir une chaîne caractère par caractère. Bref, on ne peut rien faire.
Alors comment enlever ce morceau de chaîne si c’est impossible ? Avec les gros moyens : on va entièrement reconstruire la base de données en sautant cette relation ! On va parcourir tous les types de relation, pour chacun (R) on va parcourir toutes les paires possibles (X, Y), et pour tous ces triplets (X, R, Y), on va regarder s’ils sont en relation. Si oui, on les ajoute à la nouvelle version de la base de données. Sauf s’il s’agit de (Xu, Ru, Yu).
unrelate()
elle-même ne fait pas grand chose, elle valide et délègue le travail :
=== function unrelate(x1, rel, x2)
{ validate(x1, x2, rel):
// rebuild the whole pair string
~ pairstore = _rebuildPairStringExcept(LIST_ALL(Relations), x1, x2, rel)
}
On va itérer dans tous les sens, donc vous commencez à avoir l’habitude : ça va « récurser ». D’abord dans _rebuildPairStringExcept()
, on va itérer sur tous les types de relations (LIST Relations
). La condition de sortie, c’est s’il n’y a plus de relation à traiter et les cas les plus intéressants sont :
- si on traite le type de relation qui est concerné par le
unrelate
, on demande à_validPairsIn()
de générer tous les triplets possibles sauf celui qui lie x1 à x2, et on « récurse » ; - sinon, c’est-à-dire pour toutes les autres relations, on demande aussi à
_validPairsIn()
de générer tous les triplets possibles et on « récurse ».
=== function _rebuildPairStringExcept(allRels, x1, x2, rel)
~ temp relEl = pop (allRels)
{
- not relEl:
~ return ""
- relEl == rel:
~ return _validPairsIn(LIST_ALL(relationDatabase(rel, true)), LIST_ALL(relationDatabase(rel, false)), relEl, x1, x2) + _rebuildPairStringExcept(allRels, x1, x2, rel)
- else:
~ return _validPairsIn(LIST_ALL(relationDatabase(relEl, true)), LIST_ALL(relationDatabase(relEl, false)), relEl, (), ()) + _rebuildPairStringExcept(allRels, x1, x2, rel)
}
Enfin, _validPairsIn()
est du même acabit que les autres fonctions qui itèrent sur toutes les paires. Elle est même très similaire à relate()
sauf qu’elle saute le cas qu’on veut supprimer (not1, not2
).
=== function _validPairsIn(list1, list2, rel, not1, not2)
~ temp ret = ""
{ LIST_COUNT(list1):
- 0: ~ return ()
- 1: ~ temp el2 = pop(list2)
{ el2:
{ _isRelated(list1, el2, rel) && not (not1 ? list1 && not2 ? el2):
~ ret = _pairString(list1, el2, rel)
}
~ return ret + _validPairsIn(list1, list2, rel, not1, not2)
}
~ return ""
- else:
~ temp el1 = pop(list1)
~ return _validPairsIn(el1, list2, rel, not1, not2) + _validPairsIn(list1, list2, rel, not1, not2)
}
Et voilà, c’était la dernière brique qui permet de supprimer une relation de la base de données. Ça fait beaucoup de code à exécuter pour supprimer une relation, mais dans la pratique vous allez pouvoir stocker un paquet de relations avant que ce soit problématique. Et si vous atteignez à ces limites et que vous avez des problèmes de performance, vous pourrez toujours externaliser la fonction et la réécrire en JavaScript.
Laisser un commentaire
Vous devez vous connecter pour publier un commentaire.