Lineare Datenstrukturen im Spiel

Im Kapitel Lineare Datenstrukturen hast du drei Strukturen kennengelernt, die Dinge in einer Reihe speichern. Sie unterscheiden sich nur darin, welches Element als Nächstes an die Reihe kommt. Genau diese Frage stellt ein Spiel ständig.

Die Leitfrage für dein Spiel: Wer kommt als Nächstes dran?

das zuerst Eingereihte: eine Warteschlange, FIFO
das zuletzt Aufgelegte: ein Stapel, LIFO
ein Beliebiges, oder alle der Reihe nach: eine Liste

Du kommst in der Übungsstunde nach jeder Struktur hierher – erst nach der Schlange, dann nach dem Stapel, dann nach der Liste. Bau jedes Mal eine Mechanik mit der Struktur ein, die ihr gerade besprochen habt. Zu jeder Struktur gibt es ein ausführlich erklärtes Beispiel mit lauffähigem Code.

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 mit einer Schlange

Meldungen der Reihe nach

Im Spiel: Meldungen wie „Autsch!“ oder „Ein Leben mehr!“ erscheinen nacheinander, keine überschreibt die vorige.

Dahinter steckt: eine Queue<String>. Wer etwas sagen will, reiht sich hinten ein. run() zeigt die vorderste Meldung zwei Sekunden lang und nimmt dann die nächste. Ausführlich erklärt im Beispiel Meldungen der Reihe nach.

Aufwand: ★☆☆

MVP zum Ausprobieren: Drücke mehrfach Leertaste. Jede Meldung bleibt zwei Sekunden stehen.

In dein Spiel übertragen: Reihe Ereignisse mit enqueue ein und verwalte nur für die gerade angezeigte Meldung eine Restzeit.

Gegnerwellen

Im Spiel: Ist ein Raum leer, kommt die nächste Welle. Zuerst drei Schleime, dann zwei Fledermäuse, dann alles zusammen.

Dahinter steckt: eine Schlange aus Wellen, zum Beispiel als Zeichenketten "GGG", "VV", "GGVV". Was zuerst eingeplant wurde, kommt zuerst.

Aufwand: ★★☆

MVP zum Ausprobieren: Leertaste besiegt die aktuelle Welle. Danach erscheint die nächste.

In dein Spiel übertragen: Starte die nächste Welle, sobald dein Spiel keine Gegner der aktuellen Welle mehr findet.

Befehle vorausplanen

Im Spiel: Erst plant man mit den Pfeiltasten eine Folge von Schritten, dann läuft die Figur sie Schritt für Schritt ab. Ein Rätselspiel.

Dahinter steckt: eine Schlange von Richtungen. Das Planen reiht ein, das Ablaufen nimmt vorne heraus.

Aufwand: ★★☆

MVP zum Ausprobieren: Plane mit den Pfeiltasten. Leertaste startet die Ausführung mit zwei Schritten pro Sekunde.

In dein Spiel übertragen: Trenne das Einreihen der Befehle vom zeitgesteuerten Abarbeiten.

Snake

Im Spiel: Eine Schlange aus Körperteilen kriecht über das Raster. Frisst sie etwas, wird sie länger.

Dahinter steckt: passenderweise eine Warteschlange. Bei jedem Schritt kommt vorne ein neues Körperteil dazu, hinten fällt eins weg. Nach dem Fressen fällt hinten einmal nichts weg.

Aufwand: ★★★

MVP zum Ausprobieren: Steuere mit den Pfeiltasten zur Münze. Beim Fressen bleibt das Schwanzende einen Schritt länger liegen.

In dein Spiel übertragen: Die Queue beginnt beim Schwanz. Neue Kopfsegmente kommen mit enqueue ans Ende.

Wer ist am Zug?

Im Spiel: ein rundenbasierter Kampf. Spieler und Gegner handeln abwechselnd in fester Reihenfolge.

Dahinter steckt: eine Schlange der Kämpfenden. Wer an der Reihe war, wird vorne herausgenommen und hinten wieder eingereiht.

Aufwand: ★★☆

MVP zum Ausprobieren: Leertaste führt jeweils einen Zug aus.

In dein Spiel übertragen: Nimm den Handelnden vorne heraus und reihe ihn nach seinem Zug hinten wieder ein.

Mechaniken mit einem Stapel

Die Spur zurück

Im Spiel: Mit der Taste R läuft die Figur ihre eigene Spur rückwärts, Schritt für Schritt.

Dahinter steckt: ein Stack<Platz>. Alle 15 Bilder kommt die aktuelle Position oben drauf. R nimmt den obersten Platz und setzt die Figur dorthin. Der zuletzt besuchte Platz muss als Erstes zurückkommen.

private void geheZurueck() {
   if (!spur.isEmpty()) {
      Platz p = spur.top();
      spur.pop();
      held.setPosition(p.getX(), p.getY());
   }
}

Warum speichert der Stapel Plätze und nicht einfach den Spieler? Überlege, worauf ein Verweis auf den Spieler zeigen würde.

Aufwand: ★★☆

MVP zum Ausprobieren: Pfeiltasten gehen einen Schritt. R nimmt den letzten Schritt zurück.

In dein Spiel übertragen: Speichere neue Platz-Objekte mit alten Koordinaten, keine Verweise auf die bewegte Figur.

Kisten schieben und zurücknehmen

Im Spiel: Kisten lassen sich schieben, und eine Taste nimmt den letzten Schiebezug zurück, dann den davor.

Dahinter steckt: ein Stapel von Zügen. Ausführlich erklärt im Beispiel Kisten schieben und zurücknehmen.

Aufwand: ★★★

MVP zum Ausprobieren: Rechts schiebt die Kiste. R nimmt einen Schiebezug zurück.

In dein Spiel übertragen: Speichere pro Zug die alten Positionen aller betroffenen Objekte.

Räume und Menüs

Im Spiel: Durch eine Tür geht es in ein Haus, im Haus in den Keller. Jeder Ausgang führt in den Raum davor. Genauso bei Menüs: Escape führt eine Ebene zurück.

Dahinter steckt: ein Stapel der besuchten Räume. Betreten heißt push, Verlassen heißt pop.

Aufwand: ★★☆

MVP zum Ausprobieren: Leertaste öffnet eine weitere Ebene. Escape führt zurück.

In dein Spiel übertragen: Speichere beim Betreten die bisherige Ansicht auf dem Stapel und hole sie beim Zurückgehen herunter.

Ein Kartenstapel

Im Spiel: Man zieht Karten mit Zaubersprüchen oder Ereignissen von einem gemischten Stapel. Benutzte Karten kommen auf einen Ablagestapel.

Dahinter steckt: zwei Stapel. Ist der Nachziehstapel leer, wird der Ablagestapel gemischt und wird zum neuen Nachziehstapel.

Aufwand: ★★☆

MVP zum Ausprobieren: Ziehe mit Leertaste mehrfach. Nach drei Karten wird der Ablagestapel neu gemischt.

In dein Spiel übertragen: Benutze zwei Stapel; zum Mischen kannst du die Ablage vorübergehend in ein Feld legen.

Mechaniken mit einer Liste

Ein Inventar mit Auswahl

Im Spiel: Aufgehobene Dinge stehen in einer Reihe am unteren Rand. Eins ist ausgewählt, eine Taste wählt das nächste, eine andere benutzt es.

Dahinter steckt: eine List, deren aktuelles Element die Auswahl ist. Ausführlich erklärt im Beispiel Ein Inventar.

Aufwand: ★★☆

MVP zum Ausprobieren: N wählt den nächsten Gegenstand, Leertaste benutzt und entfernt ihn.

In dein Spiel übertragen: Das aktuelle Listenelement ist die Auswahl. Nach dem Entfernen zeigt die Liste auf den Nachfolger.

Eine Patrouille

Im Spiel: Eine Wache läuft eine feste Runde über mehrere Wegpunkte, immer wieder.

Dahinter steckt: eine Liste von Plätzen. Das aktuelle Element ist das nächste Ziel. Ist es erreicht, geht es mit next() weiter, und am Ende mit toFirst() wieder von vorn.

Aufwand: ★★☆

MVP zum Ausprobieren: Beobachte die Runde und ergänze einen fünften Wegpunkt.

In dein Spiel übertragen: Das aktuelle Listenelement ist das Ziel. Nach dem letzten Wegpunkt beginnt die Runde wieder vorne.

Was ist noch offen?

Im Spiel: Die Anzeige nennt die Gegenstände, die in diesem Level noch fehlen.

Dahinter steckt: eine Liste, die beim Aufbau gefüllt und beim Einsammeln verkleinert wird. Zum Anzeigen läuft man sie mit toFirst(), hasAccess() und next() durch. In der NRW-Fassung von Scratch for Java liefert auch this.find(Muenze.class) eine solche Liste.

Aufwand: ★☆☆

MVP zum Ausprobieren: Leertaste sammelt jeweils den ersten noch fehlenden Gegenstand.

In dein Spiel übertragen: Entferne beim echten Einsammeln den passenden Eintrag und baue die Anzeige aus den verbleibenden Einträgen.

Ein Questlog

Im Spiel: Figuren geben Aufträge. Eine Liste zeigt die offenen, erledigte verschwinden, neue kommen an beliebiger Stelle dazu.

Dahinter steckt: eine Liste von Aufträgen. Anders als bei Schlange und Stapel wird auch in der Mitte entfernt.

Aufwand: ★★☆

MVP zum Ausprobieren: N wählt einen Auftrag, Leertaste erledigt ihn. A fügt einen Auftrag vor der Auswahl ein.

In dein Spiel übertragen: Benutze insert und remove an der aktuellen Stelle, statt die Liste nur vorne oder hinten zu verändern.

Mehrere Zauber gleichzeitig

Im Spiel: Die Figur ist gerade schnell und unverwundbar und leicht vergiftet. Jeder Effekt läuft zu einer anderen Zeit ab, oben steht eine Liste der aktiven.

Dahinter steckt: eine List<Effekt>. Jeder Effekt kennt seine Restzeit. In jedem Bild läuft run() die Liste mit toFirst(), hasAccess() und next() durch, zieht Zeit ab und entfernt abgelaufene Effekte mit remove(), auch mitten aus der Liste. Ein neuer Zauber kommt mit append dazu. Wer Effekt als abstrakte Klasse baut, lässt jeden Effekt selbst entscheiden, was er tut.

Aufwand: ★★★

MVP zum Ausprobieren: Leertaste startet drei verschieden lange Effekte. Beobachte, wie Einträge aus der Mitte verschwinden.

In dein Spiel übertragen: Nach remove steht der Zeiger bereits beim Nachfolger. Rufe dort kein zusätzliches next auf.

Ein Gespräch der Reihe nach

Im Spiel: Eine Figur erzählt eine kleine Geschichte in mehreren Sätzen. Jeder steht ein paar Sekunden in ihrer Sprechblase, dann kommt der nächste.

Dahinter steckt: eine Schlange von Sätzen, wie bei den Meldungen, nur mit say(…) statt einer Textzeile.

Aufwand: ★☆☆

MVP zum Ausprobieren: Starte und lies die drei aufeinanderfolgenden Sprechblasen.

In dein Spiel übertragen: Lege die Sätze beim Gesprächsbeginn in eine Schlange und entnimm sie zeitgesteuert.

Und ohne Spiel?

Im Spiel	Dieselbe Struktur woanders
Meldungen, Wellen der Reihe nach	Druckaufträge, Warteschlange an der Kasse, Nachrichten im Postfach
Spur zurück, Schritt für Schritt	Rückgängig im Textprogramm, Zurück-Knopf im Browser, Aufrufstapel
Inventar, offene Gegenstände	Warenkorb, Teilnehmerliste, alle Nachrichten eines Chats

Wer in der Klausur entscheiden muss, welche Struktur passt, stellt genau eine Frage: Wer kommt als Nächstes dran, der Erste, der Letzte oder alle der Reihe nach?

Deine eigene Idee

Wo in deinem Spiel wartet etwas darauf, behandelt zu werden? Wo soll etwas rückgängig gemacht werden? Wo gibt es eine veränderliche Sammlung, aus der du auswählst?

Fürs Tagebuch: Begründe für jede Struktur, die du eingebaut hast, warum es diese ist. Beschreibe für eine davon genau, was im Spiel passieren würde, wenn du stattdessen eine der anderen beiden genommen hättest.

Checkpoint

Im Checkpoint nach diesem Kapitel stellen sich Meldungen in einer Schlange an, und ein Stapel merkt sich die Spur des Spielers, die man mit R zurückgehen kann. Wie du ihn lädst, steht auf der Startseite der Werkstatt.

Checkpoint: Lineare Datenstrukturen (Online-IDE)

Weiterbauen kannst du in deiner Werkstatt.