Im Spiel: kommt man da überhaupt hin?
Optional. Diese Seite ist ein Zusatzangebot am Ende des Kapitels. Sie führt nichts Neues ein, und weder der Rückblick noch die späteren Kapitel setzen sie voraus.
Sie setzt Im Spiel: das Level als Gitter fort. Das Level steht dort als Plan aus Zeichen – jetzt kommen Mauern dazu, und damit ein Problem, das man von Hand nicht mehr lösen kann.
Scratch for Java in fünf Minuten
Diese Seite macht einen Entwurf mit der Grafikbibliothek Scratch for Java sichtbar. Du musst sie nicht kennen – hier steht alles, was du dafür brauchst. Geladen wird sie über libraries="scratch"; import-Zeilen gibt es nicht.
| Begriff | Was er bedeutet |
|---|---|
Stage |
die Bühne, 480 × 360 Pixel. Der Punkt (0, 0) liegt in der Mitte, die y-Achse zeigt nach oben. Man schreibt eine eigene Klasse, die von Stage erbt. |
Sprite |
eine Figur auf der Bühne. Auch dafür schreibt man eigene Klassen, die von Sprite erben. |
addCostume("coin_gold") |
gibt einer Figur ihr Bild. Die Bibliothek bringt über 1700 fertige Kostüme mit. |
this.add(objekt) |
fügt eine Figur oder einen Text der Bühne hinzu. Was nicht hinzugefügt wurde, sieht man nicht. |
run() |
wird für jedes Objekt etwa 60-mal pro Sekunde aufgerufen. Alles Fortlaufende steht hier drin. |
getTouchingSprite(Muenze.class) |
liefert das berührte Objekt oder null, wenn gerade keins berührt wird. Das null muss man immer abfragen. |
Dazu isKeyPressed(KeyCode.RIGHT) für die Tastatur, changeX(4) zum Bewegen, remove() zum Entfernen und new Text(text, x, y, breite) mit showText(...) für die Anzeige.
Zum Nachlesen: Die erste Grafik erklärt Bühne und Koordinatensystem, Eigene Sprites die eigenen Figurenklassen mit run(). Alle Methoden auf einen Blick: Referenz.
Woran es hakt
Ein Level mit Mauern hat ein Problem, das ein Level ohne Mauern nicht hat: Man kann Gegenstände an Stellen legen, an die niemand hinkommt.
Bei elf mal sechs Feldern sieht man das noch mit dem Auge. Bei vierzig mal dreißig nicht mehr – und spätestens wenn das Level zufällig erzeugt wird, ist Hinsehen überhaupt keine Antwort mehr. Das Programm muss die Frage selbst beantworten können:
Welche Felder kann der Spieler von seinem Startfeld aus erreichen?
Die Idee: von innen nach außen
Die Frage sieht schwer aus, weil sie nach dem ganzen Level fragt. Sie wird leicht, wenn man sie für ein einziges Feld stellt:
Ein Feld ist erreichbar, wenn ich darauf stehe – und dann sind auch alle Nachbarfelder erreichbar, die keine Mauer sind.
Das ist schon der ganze Algorithmus. Er beschreibt sich selbst mit sich selbst: Rekursion.
Vier Fragen muss man beantworten, bevor man weitergeht – das sind die Basisfälle:
- Liegt das Feld außerhalb des Levels? Dann nichts tun.
- Ist es eine Mauer? Dann nichts tun.
- War ich hier schon? Dann nichts tun.
- Sonst: Feld markieren und in alle vier Richtungen weitermachen.
Der dritte Basisfall ist der wichtigste, und man übersieht ihn beim ersten Versuch fast immer.
Ohne ihn geht das Verfahren von A nach B, von B zurück nach A, von A wieder nach B – unendlich oft. Der Aufrufstapel aus 3.1 wächst dabei, bis nichts mehr geht.
Ein Basisfall muss nicht das Ende des Wegs sein. Er kann auch heißen: „Hier war ich schon, hier ist nichts mehr zu holen."
Das Verfahren im Level
Die Klasse Zelle aus der vorigen Seite ist wieder dabei: Sie hält die Geometrie des Gitters an einer Stelle und sorgt vor allem dafür, dass jede Figur genau in eine Zelle passt. Ohne das rechnet markiere über ein Gitter, in dem die Figuren gar nicht liegen – der Hase wäre bei setSize(40) doppelt so hoch wie eine Zelle.
Unten läuft es. Die Mauern sind Kisten, und alles, was der Spieler nicht erreichen kann, ist rot eingefärbt. Lauf umher und überzeuge dich: Die roten Gegenstände bekommst du nicht.
Warum das kein Umweg ist
Man könnte einwenden: Man sieht doch, dass die Münze eingemauert ist. Für dieses Level stimmt das. Aber derselbe Algorithmus beantwortet ohne eine Zeile Änderung auch die Fragen, die man nicht sieht:
- Ist dieses zufällig erzeugte Level überhaupt lösbar?
- Wie groß ist der Bereich, in dem der Spieler eingeschlossen ist?
- Welche Felder muss ich freiräumen, damit alles erreichbar wird?
Aufgabe 1: den Algorithmus verstehen
a) Nimm den dritten Basisfall heraus – die Zeile mit erreichbar[pZeile][pSpalte]. Sage vorher voraus, was passiert, und begründe es mit dem Aufrufstapel. Probiere es erst danach aus.
b) Wie tief wird die Rekursion bei diesem Level höchstens? Gib eine obere Schranke an, die für jedes Level aus Zeilen und Spalten gilt.
c) Ändere die Reihenfolge der vier Aufrufe am Ende. Ändert sich das Ergebnis? Ändert sich die Reihenfolge, in der markiert wird?
d) Erweitere das Verfahren auf acht Richtungen, sodass man auch diagonal gehen kann. Wie viele unerreichbare Gegenstände bleiben dann?
Aufgabe 2: den Algorithmus benutzen
a) Schreibe istLoesbar(): Liefert true, wenn jeder Gegenstand auf einem erreichbaren Feld liegt.
b) Erzeuge das Level zufällig: Setze mit einer Wahrscheinlichkeit von etwa 25 % eine Mauer und verteile danach fünf Münzen auf freie Felder. Prüfe mit istLoesbar() und erzeuge so lange neu, bis es passt.
c) Beurteile dieses Vorgehen. Was passiert bei 60 % Mauern?
Und ohne Spiel?
| Im Spiel | Woanders derselbe Algorithmus |
|---|---|
| erreichbare Felder markieren | Farbeimer in einem Malprogramm |
| eingemauerte Münze finden | zusammenhängende Gebiete auf einer Landkarte |
| „war ich hier schon?" | besuchte Knoten bei der Tiefensuche im Graphen |
| Basisfall am Rand des Feldes | Abbruch am Rand jedes rekursiven Durchlaufs |
Das Verfahren heißt Flutfüllung, und wenn du in Kapitel 5 Graphen durchläufst, wirst du es wiedererkennen: Dasselbe Vorgehen, nur heißen die Felder dort Knoten und die Nachbarn Kanten.