Suchen und Sortieren im Spiel
Im Kapitel Algorithmen: Suchen und Sortieren hast du gelernt, wie man in einem Feld etwas findet und wie man es ordnet. Spiele suchen und sortieren ständig: Welcher Gegner ist am nächsten? Welche Zeit war die beste? In welcher Reihenfolge stehen die Sachen im Rucksack?
Die Leitfragen für dein Spiel:
- Wo muss dein Spiel unter vielen Dingen eins finden, das am nächsten, das stärkste oder das mit einem bestimmten Namen?
- Wo soll etwas geordnet angezeigt werden?
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.
Neue Runde
Im Spiel: Nach dem Ende startet die Leertaste eine neue Runde: alle Münzen zurück, Zeit und Leben voll, Figur an den Start.
Dahinter steckt: noch kein Suchen oder Sortieren, aber die Voraussetzung für die Bestenliste. whenKeyPressed der Welt reagiert auf die Leertaste. this.remove(Muenze.class) nimmt alle übrigen Münzen von der Bühne, dann legt eine Methode sie neu aus dem Plan.
public void whenKeyPressed(KeyCode pTaste) {
if (pTaste == KeyCode.SPACE && !laeuft) {
this.neueRunde();
}
}
Aufwand: ★★☆
MVP zum Ausprobieren: Sammle dreimal mit Leertaste. Erst danach startet die nächste Leertaste neu.
In dein Spiel übertragen: Setze in neueRunde alle veränderlichen Werte zurück und erzeuge entfernte Sammelobjekte neu.
Eine Bestenliste
Im Spiel: Rechts oben stehen die fünf schnellsten Zeiten, die beste zuerst.
Dahinter steckt: ein Feld, das immer sortiert bleibt. Kommt eine neue Zeit dazu, rücken alle langsameren eine Stelle nach hinten, und die neue kommt in die Lücke. Das ist genau ein Schritt von Sortieren durch Einfügen.
private double[] bestzeiten = new double[5];
private int anzahlBestzeiten = 0;
int i = anzahlBestzeiten;
while (i > 0 && bestzeiten[i - 1] > pSekunden) {
bestzeiten[i] = bestzeiten[i - 1];
i = i - 1;
}
bestzeiten[i] = pSekunden;
Was passiert, wenn die Liste voll ist und eine sechste Zeit kommt? Im Checkpoint siehst du eine Lösung.
Aufwand: ★★☆
MVP zum Ausprobieren: Starte die vorbereiteten sechs Einträge. Welche Zeit fällt aus der Top 5?
In dein Spiel übertragen: Rufe eintragen am Ende jeder Runde mit der gemessenen Spielzeit auf.
Ein Kompass
Im Spiel: Ein Pfeil oder ein Text zeigt die Richtung zur nächsten Münze.
Dahinter steckt: eine lineare Suche nach dem kleinsten Abstand. Dafür müssen die Münzen in einem Feld Muenze[] liegen. Bereits eingesammelte überspringst du. Ob eine Münze noch auf der Bühne ist, verrät dir m.getStage() != null.
Aufwand: ★★★
MVP zum Ausprobieren: Bewege dich mit den Pfeiltasten. Die Textzeile zeigt die Richtung zur nächsten noch vorhandenen Münze.
In dein Spiel übertragen: Merke eingesammelte Münzen zusätzlich mit null im Feld, damit entfernte Sprites nicht weiter abgefragt werden.
Der nächste Gegner greift an
Im Spiel: Von mehreren Gegnern wird nur der nächste aktiv und läuft auf dich zu, die anderen bleiben stehen.
Dahinter steckt: dieselbe Suche nach dem kleinsten Abstand, diesmal in einem Feld von Gegnern. Der gefundene Gegner bekommt Tempo, alle anderen Tempo 0.
Aufwand: ★★★
MVP zum Ausprobieren: Laufe mit den Pfeiltasten herum. Nur die jeweils nächste Kiste bewegt sich.
In dein Spiel übertragen: Suche zunächst den Index des nächsten Gegners; bewege anschließend nur diesen.
Ein sortierter Rucksack
Im Spiel: Eingesammelte Gegenstände stehen am unteren Rand, alphabetisch oder nach Wert geordnet.
Dahinter steckt: ein Feld von Namen und ein Sortierverfahren deiner Wahl. Zum Vergleichen von Zeichenketten gibt es a.compareTo(b). Das Ergebnis ist negativ, wenn a im Alphabet vor b kommt.
Aufwand: ★★☆
MVP zum Ausprobieren: Ergänze einen Namen im Feld und beobachte die alphabetische Ausgabe.
In dein Spiel übertragen: Sortiere die gespeicherten Namen beim Einsammeln oder beim Öffnen des Inventars.
Wie schnell ist schnell genug?
Im Spiel: nichts zu sehen, solange alles gut geht.
Dahinter steckt: run() läuft 60-mal in der Sekunde. Sortierst du darin in jedem Bild ein Feld, zählt jeder Vergleich. Wie viele Vergleiche braucht Bubblesort für 10, für 100, für 1000 Einträge? Lies dazu Wie schnell ist das? und überlege, wann es in einem Spiel eng würde.
Aufwand: ★☆☆
MVP zum Ausprobieren: Vergleiche die gemessenen Vergleiche für 10, 100 und 1000 Werte.
In dein Spiel übertragen: Zähle Arbeitsschritte deiner echten Sortiermethode und multipliziere mit den Aufrufen pro Sekunde.
Deine eigene Idee
Wo sucht oder ordnet dein Spiel etwas? Vielleicht eine Rangliste von Monstern nach Stärke, ein Laden, der das billigste Angebot findet, oder ein Schatz, der immer an der Stelle liegt, die am weitesten vom Start entfernt ist.
Fürs Tagebuch: Welches Such- oder Sortierverfahren steckt in deinem Spiel? Begründe, warum es hier passt. Schätze ab, wie viele Vergleiche es höchstens braucht, und wie oft es läuft: einmal pro Runde oder 60-mal in der Sekunde?
Checkpoint
Im Checkpoint nach diesem Kapitel startet die Leertaste nach dem Ende eine neue Runde, und eine Bestenliste hält die fünf schnellsten Zeiten sortiert. Wie du ihn lädst, steht auf der Startseite der Werkstatt.
Checkpoint: Suchen und Sortieren (Online-IDE)
Weiterbauen kannst du in deiner Werkstatt.