Darstellung des Pfades
Ein Binärbaum würde die logische Darstellung des Pfades ziemlich exakt treffen, belegt aber mit allen Möglichkeiten auch schnell (zu) viel Speicherplatz. Deshalb verwende ich ein Array der Länge N (N = Pfadlänge), z.B. im obigen Beispiel dann:
pfad = ['D', 'D', 'R'] # D: down, R: right |
Darstellung des Levels
Das Level wird in einem zweidimensionalen Array dargestellt:
level = [['FREI', 'FREI', ..., 'MIENE', 'FREI', ...], [...], ...] |
Auffinden von Sackgassen
Es gibt Kombinationen von Feldern, die eine Sackgasse darstellen und im vornherein so aufbereitet werden können, dass eine Sackgasse frühzeitig entdeckt werden kann.
Die grauen Felder sind unzugänglich, weil sie von davor liegenden Mienen abgeschirmt werden. (Es können nur Schritte nach rechts bzw. nach unten gemacht werden).
Die roten Felder sind wahre Sackgassen. Man kann sie betreten, wird aber zwangsläufig irgendwann auf eine Miene treffen.
Aus diesem Grund wird das Level im Vornherein nach grauen und roten Felder abgesucht und an diesen Stellen als unzugänglich markiert.
level = [['FREI', 'FREI', ..., 'UNZUGÄNGLICH', 'MIENE', 'FREI', ...], [...], ...] |
"Intelligente" Pfadauswahl
Im hier gezeigten Beispiel, das natürlich absichtlich zugunsten der "intelligenten" Pfadsuche ausgelegt ist, wird deutlich, dass weniger Versuche für das Finden des Pfades benötigt werden, wenn immer mit der Pfad-Kombination "alle nach rechts" begonnen wird. Ein rotes C bedeutet einen Crash in einer erkannten Sackgasse, ein rotes X bedeutet das Treten auf eine Miene. Trifft man auf ein Hindernis, versucht man es an der Stelle des Pfades mit "nach unten" und setzt den Rest des Pfades auf "nach rechts".
Allgemeines Vorgehen bei der "intelligenten" Pfadsuche:
- Es werden nicht stur alle Kombinationen von „nach rechts“ und „nach unten“ durchprobiert, sondern es wird bei alle Stellen stehen auf „nach rechts“ angefangen.
- Stößt man beim Probieren eines Pfades auf ein Hindernis (Sackgasse/Miene), wird an dieser Stelle der Pfad nach unten umgelenkt und der Rest des Pfades auf „nach rechts“ gesetzt. (Alle weiteren Kombinationen hinter der Stelle des Crashs sind ja ebenfalls nicht zielführend).
- Befindet sich an der neuen Stelle im Pfad wieder ein Hindernis, versucht man es im Pfad an der Stelle davor mit „nach unten“.
- Befindet sich der Pfad an der Stelle, die auf „nach unten“ gestellt werden soll, bereits im Status „nach unten“, wird wiederum eine Stelle nach vorne gesprungen, bis die neue Stelle den Status „nach rechts“ besitzt und auf „nach unten“ gesetzt werden kann.
- Ist der Anfang vom Pfad erreicht und steht das erste Element bereits auf „nach unten“, dann sind alle Möglichkeiten für diese Anzahl an Schritten ausgeschöpft
