Home » Tutorials » Programmierkonzepte » Wege aus dem Labyrinth

Wege aus dem Labyrinth

2. Wie orientieren wir uns in einem Labyrinth?

Wie man sich im Labyrinth orientiert, ist Temperamentssache. Der eine saust wild drauflos ? und rennt sich am Ende aus lauter Verzweiflung den Kopf ein, weil er den Ausgang doch nicht gefunden hat; und der andere macht alles mit Überlegung und kommt nach erfolgreicher Suche am Ausgangstor an, um das „ansehnliche Erinnerungsgeschenk“ in Empfang zu nehmen.
Wir wollen es mit Überlegung machen und ein System, einen Algorithmus entwickeln, der uns gut durch den Irrgarten aus Hecken und Sträuchern zum Ausgang bringt.

  • Prinzipiell kann man von einem Feld des Labyrinths aus in vier Richtungen weiterlaufen: nach rechts oder nach unten oder nach links oder nach oben.
    Diese Feststellung bringt uns zu einem ersten Merksatz:
    Ausgehend von der aktuellen Position wollen wir eine bestimmte Reihenfolge für unsere Schritte festlegen: zuerst nach rechts, dann nach unten, dann nach links und schließlich nach oben.
    Noch mal: Rechts ? Unten ? Links ? Oben: UND NICHT ANDERS!
  • Es darf nur dann weitergelaufen werden, wenn mit dem nächsten Schritt ein freies Feld betreten wird und dieses Feld kein Ausgang ist. Sollte der nächste Schritt aber an einer Wand enden, dann kann es sehr hart werden (und wer jetzt weiterlaufen will, kann es ruhig tun).
    Daraus folgt der zweite Merksatz:
    Der nächste Schritt gemäß unserer festgelegten Reihenfolge darf nur ausgeführt werden, wenn das zu betretende Feld weder ein Wandfeld noch ein Ausgangsfeld ist.
  • Um nicht zwischen zwei Nachbarfeldern hin und her springen zu müssen, gilt als nächste Festlegung, formuliert in unserem dritten Merksatz:
    Bereits besuchte Felder dürfen nicht noch einmal besucht werden.
  • Um unseren dritten Merksatz im Algorithmus wirksam werden zu lassen, folgt jetzt der vierte Merksatz:
    Wir markieren jedes besuchte freie Feld und behandeln markierte Felder wie Wandfelder (Achtung! Kopf einziehen).
  • Um unseren Algorithmus auch nach unserem vierten Merksatz weiter fehlerfrei ablaufen zu lassen, folgt der fünfte und letzte Merksatz:
    Wenn ein Wegelement nach allen vier Richtungen abgearbeitet ist, ganz gleich ob ein Ausgang gefunden wurde oder nicht, muss die Markierung gelöscht werden.
    Da durch den Algorithmus alle Wegeelemente besucht werden, wären sonst beim Auffinden eines Ausgangs auch die Wege markiert, die nicht zum Ziel führen.

Ohne den Algorithmus jetzt hier darstellen zu wollen, soll uns das kleine Programm WegeDemo.exe (ohne Quellcode, der Code wird später erarbeitet!) Lust darauf machen, den Weg durch das Labyrinth danach selber zu entdecken. Das Programm findet sich in den Beispieldateien am Ende.

2 Gedanken zu „Wege aus dem Labyrinth“

Kommentare sind geschlossen.