Effizient sortieren im Spiel

Im Kapitel Suchen und Sortieren hast du Quicksort und Mergesort kennengelernt, die in der Regel viel schneller sind als die Verfahren aus der Einführungsphase. Im Spiel zeigt sich aber, dass „schneller“ davon abhängt, was man über die Daten weiß.

Woran es hakt

Die Bühne zeichnet ihre Figuren in der Reihenfolge, in der sie hinzugefügt wurden. Für ein Spiel von schräg oben ist das falsch. Was weiter unten steht, ist näher am Betrachter und muss vor allem anderen gezeichnet werden. Läuft der Spieler hinter einem Baum entlang, muss der Baum ihn verdecken. Läuft er davor, muss er den Baum verdecken.

Solange sich nichts bewegt, fügt man die Figuren einmal in der richtigen Reihenfolge hinzu. Sobald sie sich bewegen, ändert sich die richtige Reihenfolge, und zwar in jedem Bild.

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.

Wer steht vorn?

Im Spiel: Der Spieler läuft hinter Bäumen vorbei und vor ihnen entlang, und es sieht richtig aus.

Dahinter steckt: ein Feld aller hohen und beweglichen Figuren, das in jedem Bild nach der y-Koordinate sortiert wird. Danach kommt jede Figur der Reihe nach mit goToFrontLayer() nach vorn, die unterste zuletzt.

Die naheliegende Antwort lautet Quicksort. Sie ist hier falsch. Zwischen zwei Bildern vergeht ein Sechzigstel einer Sekunde, und in dieser Zeit überholt kaum eine Figur eine andere. Das Feld ist also fast sortiert. Sortieren durch Einfügen braucht dafür nur etwa n Vergleiche, weil kaum etwas zu verschieben ist. Quicksort braucht auch dann n · log n, und mit einem ungünstigen Pivot bei vorsortierten Daten sogar n².

for (int i = 1; i < anzahlFiguren; i++) {
   Sprite aktuell = figuren[i];
   int j = i;
   while (j > 0 && figuren[j - 1].getY() < aktuell.getY()) {
      figuren[j] = figuren[j - 1];
      j = j - 1;
   }
   figuren[j] = aktuell;
}

Lass dir zählen, wie viele Verschiebungen in jedem Bild nötig sind. Die Zahl ist fast immer 0.

Aufwand: ★★☆

MVP zum Ausprobieren: Gehe mit dem Hasen nach oben und unten an der Kiste vorbei.

In dein Spiel übertragen: Sortiere von oben nach unten und hole die unterste Figur zuletzt nach vorne.

Eine große Bestenliste

Im Spiel: Nach vielen Runden, oder für eine ganze Klasse, stehen Hunderte Ergebnisse in einer Liste, und am Ende soll man sie sortiert sehen.

Dahinter steckt: Hier sieht es anders aus. Die Ergebnisse kommen ungeordnet, es sind viele, und sortiert wird einmal. Das ist genau der Fall, für den Quicksort gebaut ist.

Aufwand: ★★☆

MVP zum Ausprobieren: Ändere die Größe des Felds oder probiere bereits sortierte Werte aus.

In dein Spiel übertragen: Sortiere die gesammelten Rundenergebnisse einmal am Ende statt in jedem Bild.

Auf welchem Platz bin ich?

Im Spiel: Nach einer Runde steht nicht nur die Zeit da, sondern auch der Platz in der Bestenliste.

Dahinter steckt: In einer sortierten Liste findet die binäre Suche die richtige Stelle mit wenigen Vergleichen, statt die ganze Liste durchzugehen.

Aufwand: ★★☆

MVP zum Ausprobieren: Probiere 18, 19, 20 und 40 als neue Zeit. Gleiche Zeiten teilen sich den Platz.

In dein Spiel übertragen: Die binäre Suche findet die erste Stelle, an der keine bessere Zeit mehr steht.

Ein Inventar nach zwei Kriterien

Im Spiel: Das Inventar ist nach Art sortiert, und innerhalb jeder Art nach Wert.

Dahinter steckt: zweimal sortieren, erst nach Wert, dann nach Art. Das klappt nur, wenn das zweite Sortieren die Reihenfolge gleicher Elemente nicht durcheinanderbringt. Ein solches Verfahren heißt stabil. Mergesort ist stabil, Quicksort nicht.

Aufwand: ★★★

MVP zum Ausprobieren: Vertausche die Eingabereihenfolge und beobachte die Werte innerhalb derselben Art.

In dein Spiel übertragen: Sortiere zuerst nach dem Nebenkriterium, dann stabil nach dem Hauptkriterium. Bei Gleichheit kommt beim Mischen links zuerst.

Nicht sortieren, wo Suchen reicht

Im Spiel: Ein Gegner greift den nächsten Verbündeten des Spielers an.

Dahinter steckt: Für den nächsten braucht man keine sortierte Rangliste aller Abstände, sondern nur das Minimum. Eine einzige Schleife genügt: n Vergleiche statt n · log n. Die beste Sortierung ist manchmal gar keine.

Aufwand: ★☆☆

MVP zum Ausprobieren: Ändere einen Abstand. Wie viele Vergleiche braucht die Suche bei sechs Einträgen?

In dein Spiel übertragen: Merke nur den Index des bisher besten Kandidaten, statt alle Kandidaten zu sortieren.

Was kostet ein Bild?

Im Spiel: Eine kleine Anzeige zeigt, wie viele Vergleiche dein Spiel im letzten Bild gemacht hat.

Dahinter steckt: ein Zähler in jeder Sortier- und Suchmethode. Probiere aus, was passiert, wenn du statt Einfügen ein anderes Verfahren nimmst, und wie sich die Zahl ändert, wenn sich zwei Figuren gerade überholen.

Aufwand: ★☆☆

MVP zum Ausprobieren: Vergleiche fast sortierte und umgekehrte Daten. Gezählt werden die tatsächlich ausgeführten Wertevergleiche.

In dein Spiel übertragen: Setze den Zähler zu Beginn jedes Bilds zurück und erhöhe ihn direkt am Vergleich.

Und ohne Spiel?

Welches Verfahren passt, entscheidet nicht die O-Notation allein, sondern das, was man über die Daten weiß.

Deine eigene Idee

Wo sortiert oder sucht dein Spiel? Wie oft, und wie viele Daten? Sind sie vorher schon fast geordnet?

Checkpoint

Im Checkpoint nach diesem Kapitel sortiert die Welt in jedem Bild Pflanzen, Gegner und Spieler nach ihrer Höhe auf der Bühne, mit Sortieren durch Einfügen. Wie du ihn lädst, steht auf der Startseite der Werkstatt.

Checkpoint: Sortieren (Online-IDE)

Weiterbauen kannst du in deiner Werkstatt.