- Behandelt einen Ansatz, die Kernmechaniken eines Spiels nicht mit Funktionen, Klassen oder Zustandsvariablen, sondern mit logischen Relationen und Prädikaten zu entwerfen
- Warum Prolog fremder wirkte als LISP, lag weniger an der Syntax als daran, dass Datenstrukturen und Algorithmen über mathematische Relationen gedacht werden
- Wenn man Zeilen relationaler Datenbanken, Ein- und Ausgänge digitaler Schaltungen und Spielobjekte jeweils als n-stellige Relationen betrachtet, verbinden sich Prologs deklaratives Modell und datengetriebenes Design
- Grafik, Audio, Physik und einfache I/O vollständig in Prolog umzusetzen ist schwierig, für Gameplay-Mechaniken gibt es jedoch Potenzial
- Teil 1 beschreibt auf Basis von world und actor, wie Tags und Beziehungen zwischen actors mit Prolog-Prädikaten ausgedrückt werden; zeitliche Veränderungen und die Game Loop bleiben dem nächsten Teil vorbehalten
Die Fragestellung hinter dem Einsatz von Prolog für Spielmechaniken
- LISP und Prolog gehören zu anderen Programmierparadigmen als gängige objektorientierte Sprachen wie C# oder Java
- LISP ist stark in funktionaler Programmierung und metasprachlichen Mustern, Prolog gilt als repräsentative Sprache des Logikprogrammierens
- An LISP ließ sich dank Konzepten wie Lambda-Ausdrücken und Higher-Order Functions aus C# sowie einem Hintergrund in Elektrotechnik und Signalverarbeitung leichter herangehen als erwartet
- Bei Prolog bestand die eigentliche Hürde dagegen trotz der einfach wirkenden Syntax darin, Datenstrukturen und Algorithmen als mathematische Relationen zu behandeln
- Prologs Ansatz berührt sich mit verschiedenen ingenieurwissenschaftlichen Modellen
- Jede Zeile einer relationalen Datenbank kann in der Prolog-Syntax als n-stelliges Prädikat verstanden werden
- Das Ein-/Ausgabeverhalten digitaler Schaltungskomponenten lässt sich als n-stellige Relation aus Eingangs- und Ausgangsports modellieren
- Auch Objekte wie Hardwarebausteine oder reine Daten im Speicher können im Logikprogrammieren als Relationen definiert werden
- So wie man in der funktionalen Programmierung Objekte als Funktionen betrachten kann, kann man sie in der Logikprogrammierung als Relationen betrachten
Kernmechaniken von Spielen und deklaratives Design
- Logikprogrammierung kann dazu genutzt werden, komplexe Systeme wie die zentralen Gameplay-Mechaniken eines Videospiels zu entwerfen und zu implementieren
- Ein komplettes Spiel in Prolog umzusetzen, ist für normale Spieleentwickler eine große Herausforderung, sofern es nicht rein experimentell gemeint ist
- Nicht alle Bestandteile eines Spiels passen gut zu Prolog
- einfache I/O-Module
- Grafikmodule
- Audiomodule
- Physikmodule
- Das Ziel ist daher eher die Kernmechanik als das gesamte Spiel
- Wenn ein Gameplay-System als Menge deklarativer Aussagen aufgebaut wird, kann es gegenüber einem imperativen System robuster und modularer sein und freier von verwirrenden Edge Cases wie Race Conditions
- In dieser Methodik muss das System ausschließlich mit logischen Relationen und Prädikaten entworfen werden
- keine Funktionen
- keine structs
- keine Klassen
- keine Interfaces
- keine Zustandsvariablen
Das Modell aus World und Actor
- Der Kern Prolog-basierter Spielprogrammierung liegt darin, Relationen als primitivste Bausteine zu verwenden, ähnlich wie Widerstände, Transistoren, Kondensatoren und Induktivitäten in elektrischen Schaltungen
- Ein Spiel wird grob in world und actor unterteilt
- world ist die Szene, in der alles geschieht
- actor ist ein Objekt, das zur world gehört
- actor bezeichnet eine einzelne Entität mit Namen und Eigenschaften, etwa player, enemy, obstacle oder item
- actors können miteinander oder mit sich selbst interagieren, wobei verschiedene Ereignisse entstehen
- Gameplay lässt sich als Kette solcher Ereignisse verstehen
- In diesem Modell enthält world mehrere actors, und jeder actor besitzt seinen eigenen Zustand und sein eigenes Verhalten
Tags als unäre Prädikate ausdrücken
- Jeder actor wird über einen eindeutigen Namen identifiziert
- Im Beispiel stehen
actor1 und actor2 für den ersten und zweiten actor
- Tags sind Schlüsselwörter, die an einen actor angeheftet werden und angeben, was dieser actor ist
bread(actor1). und bread(actor2). bedeuten, dass sowohl actor1 als auch actor2 Brot sind
bread(actor1).
bread(actor2).
- In Prolog ist
bread eine unäre Relation, und bread(actor1) sowie bread(actor2) sind einzelne Instanzen dieser Relation
- Ein actor kann mehrere Tags besitzen
- Wenn jedes Brot
flammable und decomposable sein soll, ist das manuelle Anbringen dieser Tags an jedem actor umständlich und fehleranfällig
- Mit Horn-Klauseln gilt automatisch: Wenn
bread(X) wahr ist, dann sind auch flammable(X) und decomposable(X) wahr
flammable(X) :- bread(X).
decomposable(X) :- bread(X).
- Diese Horn-Klauseln funktionieren wie Konfigurationsdaten des Spiels
- ähnlich wie Eigenschaftsdefinitionen für character type, skill type oder mission type in technischen Designdokumenten oder Tabellen
- die Struktur bedeutet, dass der Type-Specifier
bread die Eigenschaften flammable und decomposable umfasst
- In einer Unity-Analogie ist das ähnlich, als würde man dem
Bread-Prefab die Komponenten Flammable und Decomposable hinzufügen
- In einer objektorientierten Umgebung entspricht es ungefähr einer
Bread-Klasse, die die Interfaces IFlammable und IDecomposable implementiert
- In diesem Kontext übernehmen Prologs Horn-Klauseln die Rolle einer Datentypdefinition
Benutzerdefinierte Tags für einzelne actors
- Unabhängig von vordefinierten Tags lassen sich auch nur für bestimmte actors benutzerdefinierte Tags vergeben
- Im Beispiel braucht das zweite Brot
actor2 das Tag enchanted, weil ein Zauberer es verzaubert hat
enchanted(actor2).
flammable und decomposable sind Eigenschaften, die zu jedem Brot gehörenenchanted ist eine Eigenschaft, die nur dem besonders verzauberten Brot zukommt
Beziehungen zwischen actors als binäre Prädikate ausdrücken
- Ein Gameplay-System muss nicht nur Eigenschaften einzelner actors ausdrücken, sondern auch Beziehungen zwischen actors
- Beispiele für solche Beziehungen sind:
- In einem Ökosystem jagt ein predator seine prey, und prey flieht vor predator
- In einer Dating-Simulation versucht ein Mann, mit einer Frau zu flirten, und die Frau weist ihn ab
- In einem Social Simulator wie The Sims sind Menschen miteinander befreundet, verfeindet oder irgendwo dazwischen
- Im Schach schlägt ein bishop einen rook diagonal, und ein rook schlägt einen bishop orthogonal
- So wie unäre Prädikate in Prolog die Eigenschaften eines einzelnen actors ausdrücken, können binäre Prädikate Beziehungen zwischen zwei actors darstellen
- Mit Horn-Klauseln lassen sich solche Beziehungen dynamisch aus den benötigten Bedingungen ableiten
Beispiele für canEat und canSpoil
- Wenn
actor3 ein Mensch ist und Menschen Brot essen können, lässt sich die Beziehung definieren: „Wenn X human und Y bread ist, kann X Y essen“
human(actor3).
canEat(X, Y) :- human(X), bread(Y).
- Hier ist
canEat(X, Y) eine Relation, die zwischen X und Y gilt
- Wenn
actor4 ein fungus ist und Brot decomposable ist, kann fungus einen decomposable actor verderben
fungus(actor4).
canSpoil(X, Y) :- fungus(X), decomposable(Y).
canSpoil(X, Y) ist die Relation „Wenn X fungus und Y decomposable ist, kann X Y verderben“decomposable(Y) kann dabei zuvor per Horn-Klausel aus bread(Y) abgeleitet werden
Das offene Problem: zeitliche Veränderung und Game Loop
- Die bisherigen Beispiele drücken Eigenschaften und Beziehungen von actors aus, sind aber alle statisch
- Ein Spiel ist keine starre Landschaft; mit der Zeit müssen sich actors bewegen und miteinander interagieren
- Allein mit Prologs deklarativem Charakter scheint sich das Problem sich verändernder Eigenschaften über die Zeit nicht leicht lösen zu lassen
- Wie sich eine Game Loop in Prolog konzeptualisieren lässt, wird in Teil 2 fortgesetzt
1 Kommentare
Hacker-News-Meinungen
Normalerweise bewerte ich Artikel, die nur einen Teil 1 haben und dann aufhören, eher niedrig, aber bei diesem hier sind tatsächlich Folgeteile weiter erschienen
https://thingspool.net/morsels/page-11.html (Teil 2)
https://thingspool.net/morsels/page-12.html (Teil 3)
https://thingspool.net/morsels/page-13.html (Teil 4)
https://thingspool.net/morsels/page-14.html (Teil 5)
Und es geht weiter
Ich denke, man könnte diese Techniken in die Spieleprogrammierung mit Rust übernehmen
Im Spieldesign von Breath of the Wild gibt es das Konzept einer Chemie-Engine. Übliche Game Engines haben eine Physik-Engine, die berechnet, wie Objekte in Bezug auf Bewegung miteinander interagieren; eine Chemie-Engine behandelt dagegen, wie Materialien in einem alchemistischen Sinn miteinander interagieren.
Sie berechnet wie eine regelbasierte Engine die Wechselwirkungen verschiedener Stoffe, wodurch überraschende Interaktionen entstehen, etwa dass ein Pfeil Feuer fangen kann, weil er aus Holz ist.
YouTube-Link: https://www.youtube.com/watch?v=QyMsF31NdNc&t=2354s
Regelbasierte Elemente in Spielen sind normalerweise vergleichsweise einfach und müssen nicht allgemein einsetzbar sein, daher werden sie offenbar von Hand programmiert. Als ich den Entwickler von Baba is You fragte, ob er eine Datalog-Engine implementiert habe, sagte er ebenfalls nein; bei Breath of the Wild dürfte es ähnlich sein.
Trotzdem denke ich oft, dass solche Chemie-Engines für schnelles Experimentieren am besten in logischen Sprachen wie Prolog oder Datalog implementiert würden. Auch SQL wurde genutzt, um die Flexibilität von Abfragen zu behalten, und am Ende genau so ausgeliefert; früher gab es wohl viele Beschwerden, SQL-Abfragen seien langsam, aber die Flexibilität war nützlich genug, dass enorme Zeit investiert wurde, um sie schnell zu machen. Heute denkt fast niemand mehr: „Ich könnte imperativen Code schreiben, der schneller ist als diese Abfrage.“
Unter den Spielen, die ich bisher gespielt habe, ist es ziemlich interessant.
https://store.steampowered.com/app/881100/Noita/
https://www.youtube.com/watch?v=prXuyMCgbTc
MUDs dürften wahrscheinlich ähnlich sein.
Was Grafikspiele heute als Innovation versuchen, gab es in Textspielen schon vor 40 Jahren, insbesondere in Interactive Fiction. Noch deutlicher wurde das weniger in den frühen Infocom-Titeln als in der Renaissance hervorragender Amateurspiele der 90er wie Curses, Jigsaw, Anchorhead, Devours sowie Spider and Web; ebenso in Roguelikes wie NetHack/Slash'EM, CDDA: Bright Nights und in Online-MUDs, die nicht nur Fantasy, sondern auch Cyberpunk- oder SF-Settings mit ungewöhnlichen Materialien und Interaktionen behandelten.
Auch die besten Game Designer wie Warren Spector dürften Free-Software-Spiele, Indie-Spiele und schräge Spiele gespielt und daraus neue Gameplay-Ideen übernommen haben.
Die NetHack-Anspielung im ursprünglichen Deus Ex war meiner Ansicht nach nicht bloß ein Easter Egg, sondern vermutlich eine Hommage an emergentes Gameplay, das von NetHack inspiriert war.
Die Stärke von Deus Ex lag nicht in der Grafik oder im Worldbuilding, sondern darin, was man im Spiel tun konnte, und darin, die lineare Struktur von FPS aufzubrechen und es zugleich zugänglicher zu machen als System Shock 1 und 2. Bei System Shock gab es Schwächen beim Balancing des Schwierigkeitsgrads und beim Feinschliff des Gameplays. Ähnlich gilt das für Arx Fatalis (heute Libertatis) und Ultima Underworld.
Aus einfachen Regeln entsteht wirklich viel interessante Komplexität.
Es gibt nicht nur die Lösungsalgorithmen, die von allgemeinen logischen/relationalen Sprachen implementiert werden; je allgemeiner sie sind, desto ineffizienter können sie für Probleme sein, die eine Game Engine effizient lösen muss. Erweitert man umgekehrt eine logische Sprache nativ um solche Funktionen, muss man vereinfachende Annahmen brechen oder die Auswertungsreihenfolge ändern, wodurch es schwerer wird, die Sprache einfach und effizient zu implementieren.
Beispielsweise wollte ich logische Relationen zusammen mit linearen Constraints verwenden. Etwa
A <= (B-10.0) .OR. B <= (A-10.0), um die Mittelpunktpositionen zweier Spielobjekte mit Breite 10.0 so zu beschränken, dass sich ihre Ränder nicht überlappen, ohne sich darum zu kümmern, welches vorne liegt. Mit solchen Aussagen könnte man Szenen oder komplexe Spielobjekte qualitativ aufbauen, und ein linearer Constraint-Solver könnte die exakten Koordinaten auswählen.Das Problem ist, dass das Lösen eines linearen Constraints wie
f(A) <= g(B)alle damit verbundenen Variablen beeinflussen kann. Da A oder B auch Constraints mit C, D, E und F haben können, kann die sofortige Ausführung beim Auswählen der linken oder rechten Seite des logischen Ausdrucksprop(X) .OR. prop(Y)andere bereits festgelegte Aussagen ungültig machen.Daher ist es besser,
<=für lineare Variablen nicht als Test mit booleschem Ergebnis zu interpretieren, sondern als Anweisung,f(A) <= g(B)einem globalen Speicher für lineare Constraints hinzuzufügen und später einen Solver über die gesamte Matrix linearer Variablen laufen zu lassen.Dann entstehen Designfragen: Woher weiß die Sprache, wann das Hinzufügen von Constraints abgeschlossen ist und es Zeit zum Lösen ist, und was passiert mit logischen Klauseln, bei denen man tatsächlich Werte testen und keine Constraints setzen darf? Der Kernpunkt ist jedoch, dass man im Kontext einer Game Engine sowohl beim Lösen linearer Constraints als auch bei logischer Programmierung mehr Kontrolle darüber braucht, wann lange Berechnungen ausgeführt werden und wie lange sie laufen dürfen.
Mit anderen Worten: Selbst wenn man Erweiterungen aus Sicht einer logischen Sprache so entwirft, dass sie gut funktionieren, bleibt aus Sicht des äußeren Systems das Problem, dass die Suchzeit zum Lösen eines Teils des logischen Programms plötzlich explodieren kann und es für Programmierer nicht immer vorhersehbar ist, wann und wo das geschieht. In diesem Sinn muss von Hand geschriebener imperativer Code nicht einmal schneller sein; selbst wenn er langsamer ist, genügt Vorhersagbarkeit.
In der Praxis muss man auch nicht unbedingt alles selbst schreiben. Entscheidend ist, ob die Regel-Engine ein Solver ist, den imperativer Spielcode von außen antreiben und unterbrechen kann, oder ob das gesamte Spiel innerhalb des Solvers, also innerhalb der relationalen Sprache, läuft. Es ist faszinierend, sich vorzustellen, was möglich wäre, wenn das ganze Spiel relational wäre; um diese Technik auf ein ganzes Spiel anzuwenden, bräuchte man jedoch einen magischen relationalen Solver, den es in Wirklichkeit nicht gibt.
Interessant ist, dass diese Einführung in die Spieleprogrammierung mit Prolog direkt zu Actionspielen übergeht. Sie behandelt Aspekte wie Echtzeit, Zeitachsen, 3D, ECS und Events.
Üblicherweise beginnen Einführungen in die Spieleentwicklung mit Prolog bei Adventure-Spielen, insbesondere klassischen Text-Adventures. Labyrinthe und Inventar-Rätsel passen nämlich direkt zu Prologs Fakten und Regeln sowie zu DSLs.
Auch Kartenspiele oder Brettspiele lassen sich mit Prolog sehr bequem als Regeln ausdrücken, und ähnlich wie Prolog-Planer in Robotik, Logistik, Finanzwesen und Industrie kann man einfache kombinatorische, universelle Spielgegner fast mühelos erweitern.
Als ich einen KI-Kurs besucht habe, war das Erste, was wir gelernt haben, Prolog, und als Aufgabe mussten wir alle ein Spiel im adventure/colossal cave-Stil schreiben. Prolog passte gut zu dieser Aufgabe, und die Vielfalt der einfachen Spiele, die im Kurs entstanden, war erstaunlich.
Ich wünschte, wir hätten alle Spiele der anderen Studierenden gesammelt. Wir behandelten das nur ein paar Wochen und gingen dann zu anderen Themen wie CLIPS und Lisp über.
In meiner Aufgabe habe ich Bureaucratic Maze [1] gebaut, und auch das war in Prolog ziemlich intuitiv.
[1]. http://logicmazes.com/bureau/index.htm
In Inform6 wird es dagegen dank der objektorientierten Ansätze im Spieldesign und der Art, wie Beziehungen zwischen Objekten im Spiel direkt behandelt werden, etwa über die ZMachine, so viel einfacher, dass es fast trivial wird.
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:1Ich habe die 12 Beiträge überflogen, und als Einstieg in die Verwendung von Prolog sehen sie gut aus, aber es scheint mir noch etwas weit hergeholt, das mit Spieleprogrammierung in Verbindung zu bringen.
Vielleicht entwickelt sich das später noch weiter, aber bis Lektion 12 ging es größtenteils darum, einige objektorientierte Konzepte in Prolog zu modellieren.
Vielleicht habe ich etwas übersehen, aber Benutzerinteraktion, die wie eine Voraussetzung für ein Spiel wirkt, wurde bisher noch nicht behandelt. Es gab einen kurzen Abschnitt zur Nachrichtenübermittlung, vielleicht war das damit gemeint.
In einem ähnlichen Zusammenhang habe ich mit Vergnügen ein Buch über logische Programmierung für Spieleprogrammierung gelesen, das statt Prolog CLIPS verwendet.
Adventures in Rule-Based Programming: A CLIPS Tutorial https://a.co/d/7wVOcZp
https://www.clipsrules.net/
Programmierbücher sind auf Kindle oft miserabel, aber auf einem Fire-Tablet könnte es okay sein.
Es gibt eine interessante Überschneidung zwischen der Sichtweise, Spielzustand als Menge von Fakten und Beziehungen zu betrachten (Prolog), und dem Kern von ECS: „Das ist eine Datenbank“[1].
Persönlich experimentiere ich mit Datascript als Datenbank für Spielzustand, aber es ist noch zu früh, um zu beurteilen, ob das erfolgreich ist. Es gefällt mir zu sehen, dass sich die Ideen dieses Tutorials 1:1 auf diese Perspektive abbilden lassen.
Ich bin mir noch nicht sicher, ob eine knappere Regeldefinition möglich ist als das, was ich gerade geschrieben habe. In den Stanford-Papers kann man Regeln wie
(<= (column ?n ?x) ...)schreiben, während in Datascript viel mehr begleitende Arbeit nötig wird, um Daten herumzuschieben.Ich weiß nicht, ob das an Grenzen von Datascript/Datomic Datalog liegt oder daran, dass mir das Verständnis fehlt.
Mich würde interessieren, wie du an Experimente herangehst. Falls es Arbeiten gibt, die du teilen kannst, oder wenn du Ratschläge zu meinem aktuellen Ansatz hast, wäre ich sehr interessiert.
[1]: https://www.cs.uic.edu/~hinrichs/papers/love2006general.pdf
Für Spiele mit viel Logik, zum Beispiel Städtebausimulationen, ist das ein frischer Ansatz, um Probleme mit Zustandsmaschinen zu behandeln. Ich hatte nie daran gedacht, Prolog auf diese Weise einzusetzen.
In Diskussionen über Kausalität und Relativität scheint man damit wirklich großartige Dinge tun zu können. Zum Beispiel könnte man bei der Erzeugung einer zufälligen Begegnung mit einem NPC eine Ereignishistorie dieses NPC erstellen, die eine Kausalkette enthält, die der Spieler in der Vergangenheit angestoßen hat.
Da alles eine Beziehung ist und es die Tatsache gibt, dass der NPC jetzt existiert, sowie den Verlauf aller beobachteten Weltzustände und Handlungen, kann man rückwärts nachverfolgen und dem NPC eine vollständig konsistente Vergangenheit geben, ohne sie im Voraus simulieren zu müssen.
Ich hatte nie darüber nachgedacht, dass das verbreitete Actor-World-/Entity-Trait-Modell gut zur relationalen Arbeitsweise von Prolog passt.
Allerdings sind auch vorhersehbare und effiziente Laufzeiten wichtig. Prolog neigt normalerweise dazu, Begriffe abzugleichen und dabei brute-force zu suchen, um eine Anfrage zu erfüllen. Ich habe die Serie noch nicht vollständig gelesen, frage mich aber, ob sie dieses Problem behandelt.
Meine erste Vermutung wäre, dass man bekannte Constraints über die Lösung in einer Art „Typdeklaration“ notiert.