Bäume und Graphen im Spiel

Im Kapitel Nichtlineare Datenstrukturen hast du Strukturen kennengelernt, die sich verzweigen. Spiele verzweigen sich überall: Ein Gegner entscheidet sich, ein Gespräch nimmt verschiedene Wendungen, eine Welt besteht aus Orten, die auf verschiedenen Wegen verbunden sind.

Woran es hakt

So sieht die Entscheidung eines Gegners aus, wenn man sie direkt hinschreibt:

if (this.distanceToSprite(ziel) < 160) {
   // verfolgen
} else {
   if (abstandZumPosten > 4) {
      // zurück zum Posten
   } else {
      // warten
   }
}

Das funktioniert. Aber wer einem zweiten Gegner ein anderes Verhalten geben will, kopiert die ganze Klasse und ändert die Verschachtelung. Dabei ist diese Verschachtelung bereits ein Baum, man sieht ihn nur nicht:

flowchart TD
    A{"Spieler nah?"} -->|ja| B["verfolgen"]
    A -->|nein| C{"weit vom Posten?"}
    C -->|ja| D["zurück zum Posten"]
    C -->|nein| E["warten"]

Die MVPs sind kleine, eigenständig lauffähige Beispiele. Starte ein Beispiel mit ▶ und klicke für die Tastensteuerung in seine Ausgabe. Im Reiter Beispiel.java steht die jeweilige Idee. Falls ein Reiter Baukasten.java dabei ist, enthält er vorbereitete Hilfen für Figuren, Texte und Steuerung. Probiere zuerst die angegebene Änderung aus und übertrage dann die Idee in deine Werkstatt.

Mechaniken

Such dir mindestens eine aus. Du darfst sie verändern, kombinieren oder dir etwas ganz anderes ausdenken.

Ein Gegner, der sich entscheidet

Im Spiel: Eine Wache steht an ihrem Posten. Kommt der Spieler nah, verfolgt sie ihn. Ist er weg, kehrt sie zurück. Über ihrem Kopf steht, was sie gerade tut.

Dahinter steckt: ein Entscheidungsbaum als BinaryTree<String>. Innere Knoten tragen Fragen, Blätter tragen Handlungen. Links geht es bei ja weiter, rechts bei nein. Die Auswertung läuft von der Wurzel bis zu einem Blatt.

BinaryTree<String> verfolgen = new BinaryTree<String>("verfolgen");
BinaryTree<String> zurueck = new BinaryTree<String>("zurück zum Posten");
BinaryTree<String> warten = new BinaryTree<String>("warten");
BinaryTree<String> weg = new BinaryTree<String>("weit vom Posten?", zurueck, warten);
entscheidung = new BinaryTree<String>("Spieler nah?", verfolgen, weg);

private String entscheide() {
   BinaryTree<String> knoten = entscheidung;
   while (!knoten.getLeftTree().isEmpty()) {
      if (this.beantworte(knoten.getContent())) {
         knoten = knoten.getLeftTree();
      } else {
         knoten = knoten.getRightTree();
      }
   }
   return knoten.getContent();
}

Der Gewinn: Eine zweite Wache mit anderem Baum verhält sich anders, bei gleichem Programmcode.

Aufwand: ★★☆

MVP zum Ausprobieren: Steuere den Hasen zur Wache und entferne dich wieder. Die Wache nennt ihre Entscheidung.

In dein Spiel übertragen: Halte Fragen und Handlungen im Baum getrennt von dessen Auswertung.

Ein Gespräch mit Abzweigungen

Im Spiel: Eine Figur stellt Fragen. Je nach Antwort, J oder N, geht das Gespräch anders weiter und endet mit einem Geschenk, einem Auftrag oder einer Abfuhr.

Dahinter steckt: derselbe Aufbau wie beim Entscheidungsbaum. Nur beantwortet nicht das Programm die Fragen, sondern der Mensch an der Tastatur. Jeder Tastendruck geht einen Knoten tiefer.

Aufwand: ★★☆

MVP zum Ausprobieren: Antworte mit J oder N. R beginnt das Gespräch erneut.

In dein Spiel übertragen: Der aktuelle Knoten ist der Gesprächszustand. An einem Blatt ist das Gespräch beendet.

Ein Monsterlexikon

Im Spiel: Ein Buch, in dem man jedes Monster nachschlagen kann, das man schon getroffen hat, alphabetisch sortiert.

Dahinter steckt: ein binärer Suchbaum. Ein Eintrag implementiert ComparableContent und vergleicht nach dem Namen. Die Ausgabe in alphabetischer Reihenfolge liefert ein Inorder-Durchlauf.

Aufwand: ★★★

MVP zum Ausprobieren: Ergänze ein Monster und ändere den gesuchten Namen.

In dein Spiel übertragen: Vergleiche Einträge über ComparableContent und gib den Suchbaum mit Inorder alphabetisch aus.

Ein Fähigkeitenbaum

Im Spiel: Mit gesammelten Punkten schaltet man Fähigkeiten frei. Eine Fähigkeit geht erst, wenn die darüber schon freigeschaltet ist: erst „schneller laufen“, dann „rennen“ oder „springen“.

Dahinter steckt: ein Baum, in dem jeder Knoten eine Fähigkeit ist. Freischalten darf man nur Kinder von freigeschalteten Knoten.

Aufwand: ★★☆

MVP zum Ausprobieren: Leertaste kauft die aktuelle Fähigkeit. Danach geht J zum linken und N zum rechten Kind. R führt zur Wurzel.

In dein Spiel übertragen: Erlaube den Abstieg nur über freigeschaltete Eltern und ziehe die Kosten genau einmal ab.

Eine Weltkarte mit Wegen

Im Spiel: Mehrere Räume, durch Türen verbunden. Nicht jeder Raum ist mit jedem verbunden, und manche Wege sind länger.

Dahinter steckt: ein Graph mit den Abiturklassen Graph, Vertex und Edge. Räume sind Knoten, Türen sind Kanten, die Länge des Wegs ist das Gewicht. Jeder Raum kann eine eigene Bühne sein, wie bei Räume als eigene Bühnen in Objektorientierung im Spiel; der Graph sagt dann, welche Bühne hinter welcher Tür liegt. Ob jeder Raum erreichbar ist, beantwortet eine Tiefensuche, im Prinzip dieselbe wie die Flutfüllung aus dem Kapitel über Rekursion. Die Klassen findest du in der Referenz.

(Nur Leistungskurs.)

Aufwand: ★★★

MVP zum Ausprobieren: Entferne eine Kante. Welche Orte sind vom Dorf aus noch erreichbar?

In dein Spiel übertragen: Benutze Knoten für Räume und gewichtete Kanten für Verbindungen. Tiefensuche prüft Erreichbarkeit, nicht den kürzesten Weg.

Und ohne Spiel?

Entscheidungsbäume sind eines der ältesten Verfahren des maschinellen Lernens. Dort wird der Baum nicht von Hand gebaut, sondern aus Daten erzeugt. Die Auswertung bleibt genau die, die hier in zehn Zeilen steht.

Deine eigene Idee

Wo verzweigt sich etwas in deinem Spiel? Wo würdest du gern nach einem Namen nachschlagen? Was ist auf mehreren Wegen verbunden?

Checkpoint

Im Checkpoint nach diesem Kapitel steht oben rechts eine Wache. Sie entscheidet mit einem Entscheidungsbaum, ob sie den Spieler verfolgt, zu ihrem Posten zurückkehrt oder wartet, und sagt es. Wie du den Checkpoint lädst, steht auf der Startseite der Werkstatt.

Checkpoint: Bäume (Online-IDE)

Weiterbauen kannst du in deiner Werkstatt.