Ein Entity Component System in Common Lisp

Am Beispiel eines 2D-Videogames, entwickelt am Personal Developer Day.

Wie an jedem letzten Donnerstag im Monat, haben wir natürlich auch im August unseren Personal Developer Day veranstaltet. Bei viel zu heißen 32 Grad im Schatten wurde wieder ordentlich getüftelt. Dieses Mal stellen wir euch das Projekt „mex“ vor. Ein Videospiel aus der Feder unseres Entwicklers Michael. Gesteuert wird ein kleines Raumschiff, das durch die Weiten des Universums fliegt und auf seinem Weg zahlreichen Asteroiden ausweichen muss. Umgesetzt wurde dieses Projekt mit Hilfe eines Entity Component Systems und der Sprache Common Lisp.

Was ist ein Entity Component System?

Bei einem Computerspiel hat man immer mit einer Menge von Objekten zu tun: Spieler, Zombie, Drache, etc. Es wird dann oft versucht, diese Objekte in Klassenhierarchien abzubilden, die aber ‒ ab einer gewissen Spielgröße ‒ sehr unübersichtlich werden können. Außerdem will man dem Spieler viele Gameplay-Variationen bieten und daher schnell Gegner-Typen ändern, neue Gegner-Typen erschaffen, neues Verhalten implementieren, etc.

Klassischerweise würde man diesen Code so oder ähnlich vorfinden:

class Player {
  physics,
  graphics,
  health,
  controllable,
  weapon,
}

class Enemy {
  physics,
  graphics,
  health,
  damage,
  xp,
}

inklusive Methoden, welche die verschiedenen Komponenten für verschiedene Klassen verarbeiten. Diese Methoden müssen natürlich auch die verschiedenen Klassen kennen, was z.B. zu enger Kopplung zwischen dem Spieler und dem Gegner führen kann. Natürlich könnte man gemeinsame Daten und Verhalten in eine abstrakte Oberklasse extrahieren, aber es gibt noch eine andere Lösung.

Man extrahiert die einzelnen Komponenten einer Klasse in eigene Klassen, auch wenn es am Ende nur Klassen mit einem Attribut sind, z.B:

class Position { x: int, y: int }
class Health { value: int, }
class Damage { min: int, max int, }
class Physics { velocity: Vec2, gravity: float, }
class Graphics { image: Image, visible: boolean, }

Der eigentliche Spieler ist jetzt nur ein Container, welcher Komponenten enthält. Genauso jedes andere Objekt im Spiel: z.B. Pfeil, Pferd, Kiste, etc.

const horse = createEntity().add(Position { x: 200, y: 300 })
                            .add(Health { value: 8 })
                            ...
                            .build()

Jetzt haben wir zwar statt 20 Klassen 150 Komponenten (Components), die aber dynamisch zu neuen Spielobjekten (Entities) zusammengewürfelt werden können. Fehlen nur noch die Systeme.

In den Systemen steckt die eigentliche Spiellogik, also die Beschreibung der Interaktion zwischen Entities:

defsystem MoveSystem for (pos: Position, phy: Physics) {
  pos.x += phy.velocity.x
  pos.y += phy.velocity.y
}

Das System „MoveSystem“ wird in einer Iteration des Spiels für alle Entities ausgeführt, die sowohl eine Position- als auch eine Physics-Komponente haben.

Was haben wir also durch eine solchen Architektur gewonnen?

• Komponenten tragen nur Daten, sonst nichts.
  • Sie können auch alle am selben Ort liegen, anstatt über mehrere Klassen verteilt.
• Komponenten wissen idealerweise nichts voneinander.
• Systeme interessieren sich nur für die Komponenten eines Entities, nicht für die Entities selbst.
  • Dem MoveSystem ist es egal, ob er die Bewegung eines Gegners, Spielers, Pferds, Pfeils berechnet.
• Es ist sehr einfach, neue Entities zu erschaffen.
  • Einfach die gewünschten Komponenten zusammenbauen und die Systeme/die Logik greift automatisch.

„mex“ ist noch ein sehr einfaches Spiel, in dem die theoretischen Vorteile eines Entity Component Systems erprobt werden. Die Architektur ist jedoch nicht das einzig Experimentelle. Michael hat sich dieses Projekt auch vorgenommen, um die Sprache „Common Lisp“ zu evaluieren.

Funktionen sind nicht das Ende

In den meisten Programmiersprachen ist die höchste Abstraktionsstufe die Funktion. Stößt man auf Code, der an verschiedenen Stellen in ähnlicher Form auftritt, versucht man diesen in eine Funktion zu extrahieren. Anstatt die Kollisionsberechnung (~30 Zeilen) an vier Stellen im Code zu kopieren, ruft man eine Funktion auf. Soweit so gut.

Was aber, wenn die Syntax der Sprache einem dabei im Weg steht?

Beispiel: In Common Lisp erwartet die Funktion setf zwei Parameter: eine Variable und einen Wert, den dieser Variable zugewiesen werden soll. Anstatt Variablen lassen sich jedoch auch ganz anderen Dingen Werte zuweisen, z.B. den Einträgen einer Hashmap, den Attributen eines Objekts etc.

(setf x 2) ; funktioniert. x ist eine Variable.
(setf (get-x (position-xy position-component)) 2) ; funktioniert auch.

; Hmmm. Das zweite setf ist doch sehr unübersichtlich.
; Benutzen wir eine lokale Variable:

; let weist x temporär den Wert von (get-x ...) zu.
(let ((x (get-x (position-xy position-component))))
  ;; x beinhaltet eine Zahl, nicht den Ausdruck 'get-x'
  (setf x 2)) ; funktioniert nicht. 'setf NUMBER NUMBER' ist nicht definiert.

Eine Funktion hilft hier nicht weiter. Wenn wir einer Funktion den get-x Ausdruck übergeben, wird er wieder ausgewertet. Wir wollen eine Funktion, die lokalen Variablen einen Ausdruck zuweist, der nicht ausgewertet wird.

Immer, wenn man sich in einer solchen Situation befindet, braucht man ein neues syntaktisches Konstrukt. Etwas, was die Programmiersprache noch nicht hat, etwas, was sich nicht mit den Mitteln der Sprache (Funktionen, Klassen, etc.) ausdrücken lässt. In Programmiersprachen ohne Macros muss man mit den Unzulänglichkeiten der Sprache leben oder auf eine neue Sprachversion warten. Common Lisp ist keine solche Sprache.

Ein Macro ist eine Funktion, die ihre Argumente nicht auswertet und Programmcode zurückgibt.

(defmacro set-let (variable ausdruck &body body)
  (let ((new-body (replace-all variable ausdruck body)))
    `(progn
       ,@new-body))

(set-let x (get-x (position-xy position-component))
  ;; x *ist* der Ausdruck (get-x ...)
  (setf x 2)) ; funktioniert

Das obige Macro würde im Körper von set-let alle Vorkommen von variable mit ausdruck 
ersetzen und das Ergebnis textuell zurückgeben.

Vor der eigentlichen Kompilierung (beim Lesevorgang) wird der Macro-Aufruf set-let durch seinen Rückgabewert ersetzt. set-let wandelt also selbst definierte Syntax in normale Common Lisp Syntax um, sodass der Compiler nur Ausdrücke zu sehen bekommt, die er auch versteht. Der obige Aufruf wird übersetzt zu:

(progn
  (setf (get-x (position-xy position-component)) 2))

progn fasst mehrere Ausdrücke und Statements in einen Ausdruck zusammen, ähnlich wie ein Block in C-ähnlichen Sprachen. Falls das set-let Macro mehrere Ausdrücke und Statements enthält, werden sie automatisch zusammengefasst, sodass der Programmierer das gleiche Verhalten von set-let bekommt, das let ebenfalls implementiert.

Was bedeutet das ganze für ein Entity Component System? Der weiter oben gezeigte Pseudocode sieht im eigentlichen Programmcode folgendermaßen aus:

(run-system (((pos 'c-position)
              (vel 'c-velocity)))
    (symbol-macrolet ((pos-x (-> pos c-position-xy gk:x))
                      (pos-y (-> pos c-position-xy gk:y)))
      (incf pos-x (c-velocity-x vel))
      (incf pos-y (c-velocity-y vel))))

symbol-macrolet ist das sprach-eigene (furchtbar benannte) Macro für set-let. Dieses System bewegt jedes Entity, das sowohl eine Position, als auch eine Geschwindigkeit hat, um den definierten Geschwindigkeits-Vektor.

run-system sieht unscheinbar aus, ist jedoch ein gewaltiges Macro. Es holt sich alle Positions- und Geschwindigkeitskomponenten für alle Entities, entfernt aus dem Ergebnis alle Entities, die nicht beide Komponenten haben und lässt dann für alle gefundenen Kombinationen den übergebenen Code laufen. Außerdem können beliebig viele Komponentenkombinationen abgefragt werden und bestimmte Entities explizit vom System ausgeschlossen werden. (Beispielsweise wird das Spielerraumschiff von dem Haupt-Rendering-System ausgeschlossen und separat gezeichnet, weil für dieses Entity spezielle Regeln gelten.)

Das Macro ist 30(!) Zeilen lang und sehr komplex. Es greift auf interne Datenstrukturen zu (Hashmaps, Arrays, Entity-Indizes), ohne dass sich der Programmierer um die Details kümmern muss. Das Ergebnis ist allerdings eine sehr angenehme Syntax.

Eine Anmerkung zur Performance von Macros: Sie kosten (fast) nichts. Die Expansion vom Macroaufruf zu Common Lisp Code geschieht noch vor der Kompilierzeit. Entsprechend ist ein Macro genauso schnell als hätte man den gesamten Code an allen Aufrufstellen per Hand geschrieben.

3D reduziert auf 2D

Die Objekte von „mex“ wurden mit Hilfe von Blender modelliert. Dafür wurde das Raumschiff, die Asteroiden und die Explosion als 3D-Modelle bzw. als Animation in Blender gebaut und anschließend von oben „fotografiert“, dadurch entsteht die 2D-Optik.

Die Explosion wurde mit dem Blender-eigenen Partikelsystem erstellt, auf dem anschließend eine Rauchsimulation 
aufgesetzt wurde. Dabei werden sogar Parameter wie Rauchdichte und Hitzeentwicklung beachtet.

Die Asteroiden wurden in drei Schritten konstruiert:

Für jeden Asteroiden wurde zunächst ein Würfel(!) erstellt. Um am Ende verschiedene Asteroiden zu erhalten, wurden die Ecken der Würfel verschoben.

Diese Würfel wurden etwa 6 mal mit dem berühmten Catmull-Clark-Algorithmus geglättet. Bei jedem Schritt wird ein Quad (also ein Polygon bestehend aus vier Vertices) in vier neue Quads unterteilt. Die Positionen der neuen Quads werden entsprechend der Positionen der alten Quads gemittelt. Anschaulich betrachtet: Wenn man einen Würfel oft genug mit dem Algorithmus glättet, erhält man eine Kugel.

Asteroiden haben viele Unebenheiten. Diese per Hand einzufügen ist sehr mühselig und zeitaufwändig. Diesen Aufwand hat man für jeden einzelnen Asteroiden. Deswegen hat Michael einen generativen Ansatz gewählt.

Displacement Mapping ist eine Technik, die ein Bild auf die Oberfläche des Meshes legt. Dieses ist am Ende jedoch nicht sichtbar. Es ist für den Computer eine Schablone, die ihm vorschreibt, wie stark die Vertices des Meshes verschoben werden sollen:

• Liegt der Vertex auf einem weißen Punkt des Bildes, wird er sehr stark nach außen gezogen.
• Liegt der Vertex auf einem schwarzen Punkt des Bildes, bleibt er an dieser Stelle.
• Je heller der Bildpunkt, desto weiter wird der Vertex nach außen gezogen.

Bilder sagen mehr als Worte:

Wie man sieht, wurden Wolkentexturen generiert und angepasst bis ein zufriedenstellendes Ergebnis zustande kam. So können sehr schnell beliebig detaillierte Flugkörper erzeugt werden.

In Computerspielen ist Displacement Mapping sehr teuer (im Vergleich zum Normal Mapping), weil ein sehr detailliertes Mesh notwendig ist: Gibt es keine Vertices, können sie auch nicht verschoben werden. In „mex“ fällt das allerdings nicht ins Gewicht, weil sämtliche Grafiken vorgerendert werden.

Alles in allem stecken in diesem unscheinbaren Asteroids-Klon jede Menge Details. Michael hatte eine Menge Spaß, sich in die Eigenheiten von Spieleprogrammierung, Common Lisp und Blender einzuarbeiten. Jeder dieser Bereiche allein kann beliebig komplex werden und wir sind daher gespannt, wozu sich „mex“ im Laufe der Zeit noch entwickeln wird. Eins wissen wir aber schon jetzt: den Asteroiden langfristig erfolgreich auszuweichen, sieht einfacher aus als es ist und macht auch schon in der derzeitigen Entwicklungsstufe sehr viel Spaß.