- Présente une approche qui consiste à concevoir les mécanismes centraux d’un jeu sous forme de relations logiques et de prédicats, plutôt qu’avec des fonctions, des classes ou des variables d’état
- Si Prolog paraît plus déroutant que LISP, c’est parce qu’il traite les structures de données et les algorithmes autour de relations mathématiques, plus que pour une question de syntaxe
- En considérant les lignes d’une base de données relationnelle, les entrées/sorties d’un circuit numérique et les objets de jeu comme des relations n-aires, on relie le modèle déclaratif de Prolog à une conception pilotée par les données
- Il est difficile d’implémenter en Prolog les graphismes, l’audio, la physique ou même de simples E/S, mais il peut s’appliquer aux mécanismes de gameplay
- La partie 1 exprime les relations entre tags et acteurs sous forme de prédicats Prolog, à partir des notions de world et d’actor ; l’évolution dans le temps et la boucle de jeu sont laissées à l’épisode suivant
Le questionnement autour de l’application de Prolog aux mécanismes de jeu
- LISP et Prolog appartiennent à des paradigmes de programmation différents des langages orientés objet courants comme C# ou Java
- LISP est puissant pour la programmation fonctionnelle et les motifs méta-linguistiques, tandis que Prolog est considéré comme le langage emblématique de la programmation logique
- LISP s’est révélé plus facile d’accès que prévu grâce à des notions comme les expressions lambda et les fonctions d’ordre supérieur de C#, ainsi qu’à un bagage en génie électrique et traitement du signal
- À l’inverse, même si la syntaxe de Prolog paraît simple, sa manière de traiter les structures de données et les algorithmes comme des relations mathématiques a constitué une difficulté majeure
- L’approche de Prolog rejoint plusieurs modèles d’ingénierie
- Chaque ligne d’une base de données relationnelle peut être vue, dans la syntaxe de Prolog, comme un prédicat n-aire
- Le comportement d’entrée/sortie des composants d’un circuit numérique peut être implémenté comme une relation n-aire combinant ports d’entrée et de sortie
- Des objets comme des morceaux de matériel ou des données pures en mémoire peuvent également être définis comme des relations en programmation logique
- De même qu’en programmation fonctionnelle on peut voir les objets comme des fonctions, en programmation logique on peut voir les objets comme des relations
Mécanismes centraux du jeu et conception déclarative
- La programmation logique peut servir à concevoir et implémenter des systèmes complexes, comme les mécanismes centraux de gameplay d’un jeu vidéo
- Implémenter un jeu entier en Prolog représente un grand défi pour un développeur de jeux classique, sauf dans un but expérimental
- Tous les composants d’un jeu ne se prêtent pas bien à Prolog
- Modules d’E/S simples
- Modules graphiques
- Modules audio
- Modules de physique
- Le périmètre d’application se situe plutôt du côté des mécanismes centraux que du jeu entier
- Composer un système de gameplay comme un ensemble d’énoncés déclaratifs peut le rendre plus robuste et modulaire qu’un système impératif, et le libérer davantage de cas limites déroutants comme les race conditions
- Dans cette méthodologie, le système doit être conçu uniquement avec des relations logiques et des prédicats
- Pas de fonctions
- Pas de struct
- Pas de class
- Pas d’interface
- Pas de variables d’état
Modèle World et Actor
- Le cœur de la programmation de jeux basée sur Prolog consiste à utiliser les relations comme briques les plus primitives, à la manière des résistances, transistors, condensateurs et inductances d’un circuit électrique
- Un jeu se divise globalement en world et actor
- Le world est la scène où tout se passe
- Un actor est un objet appartenant au world
- Un actor désigne une entité individuelle dotée d’un nom et de propriétés, comme un player, un enemy, un obstacle ou un item
- Les actors peuvent interagir entre eux ou avec eux-mêmes, et divers événements se produisent au cours de ce processus
- Le gameplay peut être vu comme une chaîne de ces événements
- Dans ce modèle, le world contient plusieurs actors, et chaque actor possède son propre état et ses propres comportements
Représenter les tags par des prédicats unaires
- Chaque actor est identifié par un nom unique
- Dans l’exemple,
actor1 et actor2 désignent le premier et le deuxième actor
- Un tag est un mot-clé attaché à un actor et indique ce qu’est cet actor
bread(actor1). et bread(actor2). signifient que actor1 et actor2 sont tous deux du pain
bread(actor1).
bread(actor2).
- En Prolog,
bread est une relation unaire, et bread(actor1) et bread(actor2) sont des instances individuelles de cette relation
- Un actor peut avoir plusieurs tags
- Si tous les pains doivent être
flammable et decomposable, ajouter manuellement ces tags à chaque actor est fastidieux et sujet aux erreurs
- Avec une clause de Horn, lorsque
bread(X) est vrai, flammable(X) et decomposable(X) deviennent automatiquement vrais
flammable(X) :- bread(X).
decomposable(X) :- bread(X).
- Ces clauses de Horn se comportent comme des données de configuration du jeu
- Elles ressemblent aux définitions de propriétés de character type, skill type ou mission type que l’on trouve dans un document de conception technique ou une feuille de calcul
- Il s’agit d’une structure où le type-specifier
bread inclut les propriétés flammable et decomposable
- Par analogie avec Unity, cela revient à placer les composants
Flammable et Decomposable dans un prefab Bread
- Dans un environnement orienté objet, c’est similaire à une classe
Bread qui implémente les interfaces IFlammable et IDecomposable
- Dans ce contexte, les clauses de Horn de Prolog jouent le rôle de définitions de types de données
Tags personnalisés attachés à un actor individuel
- Indépendamment des tags prédéfinis, on peut ajouter un tag personnalisé à un actor particulier
- Dans l’exemple, un sorcier ayant jeté un sort sur le deuxième pain,
actor2, il faut un tag enchanted
enchanted(actor2).
flammable et decomposable sont des propriétés appartenant à tous les painsenchanted est une propriété attachée uniquement au pain spécial qui a été enchanté
Représenter les relations entre actors par des prédicats binaires
- Un système de gameplay doit exprimer non seulement les caractéristiques des actors individuels, mais aussi les relations entre actors
- Voici des exemples de relations
- Dans un écosystème, un predator poursuit une prey, et la prey fuit le predator
- Dans un dating simulator, un homme essaie de flirt avec une femme, qui le repousse
- Dans un social simulator comme The Sims, les personnes sont amies, ennemies ou quelque part entre les deux
- Aux échecs, un bishop prend un rook en diagonale, et un rook prend un bishop orthogonalement
- En Prolog, tout comme un prédicat unaire représente la caractéristique d’un actor, un prédicat binaire peut représenter une relation entre deux actors
- Avec des clauses de Horn, on peut déduire dynamiquement des relations à partir de l’ensemble des conditions nécessaires
Exemples canEat et canSpoil
- Si
actor3 est un humain et qu’un humain peut manger du pain, on peut définir la relation “si X est human et Y est bread, alors X peut manger Y”
human(actor3).
canEat(X, Y) :- human(X), bread(Y).
- Ici,
canEat(X, Y) est une relation qui s’établit entre X et Y
- Si
actor4 est un fungus et que le pain est decomposable, alors un fungus peut spoil un actor decomposable
fungus(actor4).
canSpoil(X, Y) :- fungus(X), decomposable(Y).
canSpoil(X, Y) est la relation “si X est fungus et Y est decomposable, alors X peut spoil Y”decomposable(Y) peut être déduit de bread(Y) par la clause de Horn précédente
Problème restant : évolution dans le temps et boucle de jeu
- Les exemples jusqu’ici expriment les caractéristiques et les relations des actors, mais ils sont tous statiques
- Un jeu n’est pas un décor figé : les actors doivent se déplacer et interagir au fil du temps
- La seule nature déclarative de Prolog ne semble pas résoudre facilement le problème des caractéristiques qui changent avec le temps
- La manière de conceptualiser la boucle de jeu en Prolog est abordée dans la partie 2
1 commentaires
Avis sur Hacker News
D’habitude, je vois d’un mauvais œil les articles qui n’ont qu’une Partie 1 et s’arrêtent là, mais ici il y a bien des suites qui continuent de paraître
https://thingspool.net/morsels/page-11.html (partie 2)
https://thingspool.net/morsels/page-12.html (partie 3)
https://thingspool.net/morsels/page-13.html (partie 4)
https://thingspool.net/morsels/page-14.html (partie 5)
Et ça continue
Il semble possible d’appliquer ces techniques à la programmation de jeux en Rust
Dans la conception de Breath of the Wild, il y a le concept de moteur chimique. En général, un moteur de jeu dispose d’un moteur physique qui calcule comment les objets interagissent du point de vue du mouvement ; le moteur chimique, lui, traite la manière dont les matériaux interagissent au sens alchimique.
Il calcule les interactions entre différentes substances comme un moteur à règles, ce qui produit des interactions surprenantes, par exemple le fait qu’une flèche puisse prendre feu parce qu’elle est en bois.
Lien YouTube : https://www.youtube.com/watch?v=QyMsF31NdNc&t=2354s
Les éléments fondés sur des règles dans les jeux sont généralement relativement simples et n’ont pas besoin d’être généralistes, donc ils semblent codés à la main. Quand on a demandé au créateur de Baba is You s’il avait implémenté un moteur Datalog, il a aussi répondu que non, et j’imagine que Breath of the Wild est similaire.
Malgré tout, je pense souvent qu’un tel moteur chimique serait idéalement implémenté dans un langage logique comme Prolog ou Datalog pour permettre des expérimentations rapides. SQL aussi a été utilisé pour conserver la flexibilité des requêtes, puis a fini par être déployé tel quel ; autrefois, on se plaignait sûrement beaucoup de la lenteur des requêtes SQL, mais cette flexibilité était suffisamment utile pour qu’on consacre énormément de temps à les rendre rapides. Aujourd’hui, presque plus personne ne se dit : « je peux écrire moi-même du code impératif plus rapide que cette requête ».
C’est l’un des jeux les plus intéressants auxquels j’aie joué jusqu’ici.
https://store.steampowered.com/app/881100/Noita/
https://www.youtube.com/watch?v=prXuyMCgbTc
Les MUD sont sans doute similaires.
Ce que les jeux graphiques essaient de faire de manière innovante, les jeux textuels le faisaient déjà il y a 40 ans, en particulier la fiction interactive. C’était encore plus marqué non pas dans les premiers titres d’Infocom, mais dans la renaissance des excellents jeux amateurs des années 90 comme Curses, Jigsaw, Anchorhead, Devours, Spider and Web ; de même avec les roguelikes comme NetHack/Slash'EM, CDDA: Bright Nights, et les MUD en ligne qui mettaient en scène des matériaux et interactions étranges dans des univers non seulement fantasy, mais aussi cyberpunk ou SF.
Les meilleurs créateurs de jeux, comme Warren Spector, ont probablement joué à des jeux libres, indépendants et bizarres, et y ont puisé de nouvelles idées de gameplay.
À mon avis, la mention de NetHack dans le Deus Ex original n’était pas un simple easter egg, mais probablement un hommage au gameplay émergent inspiré par NetHack.
La force de Deus Ex n’était ni ses graphismes ni son univers, mais ce qu’il permettait de faire dans le jeu ; il brisait la structure linéaire des FPS tout en restant plus accessible que System Shock 1 et 2. System Shock avait en partie échoué sur l’équilibrage de la difficulté et la finition du gameplay. Arx Fatalis (aujourd’hui Libertatis) et Ultima Underworld sont du même ordre.
Des règles simples font émerger beaucoup de complexité vraiment intéressante.
Les algorithmes de résolution implémentés par les langages logiques/relationnels généralistes ne sont pas les seuls possibles, et plus ils sont généralistes, plus ils peuvent être inefficaces pour les problèmes qu’un moteur de jeu doit résoudre efficacement. À l’inverse, si l’on étend nativement un langage logique avec de telles fonctionnalités, il peut devenir difficile de garder le langage simple et efficace à implémenter, parce qu’il faut casser certaines hypothèses de simplification ou modifier l’ordre d’évaluation.
Par exemple, je voulais combiner relations logiques et contraintes linéaires. Une expression comme
A <= (B-10.0) .OR. B <= (A-10.0)permettrait de contraindre la position centrale de deux objets de jeu de largeur 10.0 afin que leurs bords ne se chevauchent pas, sans se soucier de savoir lequel est devant. Avec ce type d’énoncé, on pourrait construire qualitativement une scène ou des objets de jeu complexes, puis laisser un solveur de contraintes linéaires choisir les coordonnées exactes.Le problème est que résoudre une contrainte linéaire comme
f(A) <= g(B)peut affecter toutes les variables concernées. Comme A ou B peuvent aussi avoir des contraintes avec C, D, E et F, exécuter immédiatement le choix du membre gauche ou droit de l’expression logiqueprop(X) .OR. prop(Y)peut invalider d’autres propositions déjà fixées.Il vaut donc mieux interpréter le
<=des variables linéaires non pas comme un test produisant un résultat booléen, mais comme une instruction qui ajoutef(A) <= g(B)à un magasin global de contraintes linéaires, puis exécuter plus tard le solveur sur l’ensemble de la matrice de variables linéaires.Cela soulève alors des questions de conception : comment le langage sait-il quand l’ajout de contraintes est terminé et qu’il est temps de résoudre ? Que faire des clauses logiques où il faut réellement tester une valeur, et non ajouter une contrainte ? Mais l’idée centrale est que, dans le contexte d’un moteur de jeu, il faut davantage contrôler quand lancer les longs calculs, et combien de temps les laisser tourner, aussi bien pour la résolution de contraintes linéaires que pour la programmation logique.
Autrement dit, même si l’on conçoit bien une extension du point de vue du langage logique, du point de vue du système externe il reste le problème que le temps de recherche nécessaire pour résoudre une partie du programme logique peut soudainement exploser, et qu’il est difficile pour le programmeur de toujours prévoir quand et où cela se produira. En ce sens, le code impératif écrit à la main n’a même pas besoin d’être plus rapide : il suffit qu’il soit prévisible, même s’il est plus lent.
En réalité, il n’est pas non plus nécessaire de tout écrire soi-même. Le point essentiel est de savoir si le moteur de règles est un solveur piloté et préempté de l’extérieur par le code impératif du jeu, ou si le jeu entier s’exécute dans le solveur, c’est-à-dire dans le langage relationnel. Imaginer ce qu’un jeu entièrement relationnel permettrait de faire est séduisant, mais utiliser cette technologie pour tout un jeu nécessiterait un solveur relationnel magique qui n’existe pas vraiment.
C’est une introduction à la programmation de jeux en Prolog, et il est intéressant qu’elle aille directement vers les jeux d’action. Elle aborde les aspects temps réel, chronologie, 3D, ECS et événements.
En général, les introductions au développement de jeux en Prolog commencent par les jeux d’aventure, en particulier les aventures textuelles classiques. Les labyrinthes et les énigmes d’inventaire correspondent directement aux faits et règles de Prolog, ainsi qu’aux DSL.
Les jeux de cartes ou de plateau permettent aussi d’exprimer très facilement les règles en Prolog, et l’on peut presque aisément étendre un adversaire de jeu généraliste combinatoire de base, d’une manière proche des planificateurs Prolog utilisés en robotique, logistique, finance, industrie, etc.
Quand j’ai suivi un cours d’IA, la première chose que nous avons apprise était Prolog, et pour le devoir nous devions tous écrire un jeu de style adventure/colossal cave. Prolog convenait bien à cette tâche, et la diversité des petits jeux créés pendant le cours était surprenante.
Je me suis dit que cela aurait été bien de conserver tous les jeux réalisés par les autres étudiants. Nous n’y avons consacré que quelques semaines avant de passer à d’autres sujets comme CLIPS et Lisp.
Pour mon devoir, j’avais créé Bureaucratic Maze [1], ce qui était aussi assez intuitif en Prolog.
[1]. http://logicmazes.com/bureau/index.htm
Mais avec Inform6, grâce à l’orientation objet appliquée à la conception du jeu et à la façon de manipuler directement les relations entre les objets du jeu, comme avec la ZMachine, la difficulté chute fortement et cela devient presque trivial.
http://logicmazes.com/alice.html
alice.html:353 Uncaught TypeError: Cannot read properties of undefined (reading 'play')at playSound (alice.html:353:30)at finalize2 (alice.html:347:1)at :1:1J’ai parcouru les 12 articles, et cela semble être une bonne introduction à l’utilisation de Prolog, mais il me paraît encore difficile de dire que cela relève de la programmation de jeux.
Cela pourra peut-être évoluer plus tard, mais jusqu’à la leçon 12, il s’agissait surtout de modéliser quelques concepts orientés objet en Prolog.
J’ai peut-être manqué quelque chose, mais les interactions utilisateur, qui semblent être un prérequis pour un jeu, n’ont pas encore été abordées. Il y avait un court passage sur l’envoi de messages, donc c’est peut-être ce qui était visé.
Dans un registre similaire, j’ai lu avec plaisir un livre de programmation logique appliquée à la programmation de jeux qui utilise CLIPS au lieu de Prolog.
Adventures in Rule-Based Programming: A CLIPS Tutorial https://a.co/d/7wVOcZp
https://www.clipsrules.net/
Les livres de programmation sont souvent très mauvais sur Kindle, mais sur une tablette Fire cela peut être acceptable.
Il y a un recoupement intéressant entre la vision de l’état du jeu comme un ensemble de faits et de relations (Prolog) et l’idée centrale de l’ECS : « c’est une base de données »[1].
Personnellement, j’expérimente Datascript comme base de données d’état de jeu, mais il est encore trop tôt pour juger si cela fonctionne. C’est appréciable de voir les idées de ce tutoriel se mapper 1:1 avec cette perspective.
Je ne suis pas encore sûr qu’il soit impossible de définir les règles plus simplement que ce que j’ai écrit pour l’instant. Dans l’article de Stanford, on peut écrire des règles comme
(<= (column ?n ?x) ...), alors qu’avec Datascript il faut beaucoup plus de travail périphérique pour déplacer les données.Je ne sais pas si c’est dû aux limites du Datalog de Datascript/Datomic, ou simplement à mon manque de compréhension.
Je serais curieux de savoir comment tu abordes tes expérimentations. Si tu as des travaux à partager, ou des conseils sur ma manière de faire actuelle, cela m’intéresse beaucoup.
[1]: https://www.cs.uic.edu/~hinrichs/papers/love2006general.pdf
C’est une approche rafraîchissante pour traiter les problèmes de machines à états dans les jeux riches en logique, par exemple les simulations urbaines. Je n’avais jamais envisagé d’utiliser Prolog de cette façon.
On dirait qu’on peut faire des choses vraiment formidables avec les discussions sur la causalité et la relativité. Par exemple, en générant une rencontre aléatoire avec un PNJ, on pourrait créer l’historique des événements de ce PNJ en y incluant une chaîne causale initiée par le joueur dans le passé.
Comme tout est relation, et puisqu’il y a le fait que le PNJ existe maintenant ainsi que l’historique de tous les états du monde et actions observés, on peut remonter à rebours sans simulation préalable et donner au PNJ un passé entièrement cohérent.
Je n’avais jamais pensé que le modèle courant actor-world/entity-trait s’accordait bien avec l’approche relationnelle de Prolog.
Cela dit, un temps d’exécution prévisible et efficace compte aussi. Prolog a généralement tendance à faire une recherche brute en unifiant des termes pour satisfaire une requête. Je n’ai pas encore lu toute la série, mais je me demande si elle traite ce problème.
Ma première intuition serait qu’on décrive les contraintes connues sur les solutions sous une forme proche d’une sorte de « déclaration de type ».