lehrkraefte:blc:informatik:efi-2023:laby [https://fginfo.ksbg.ch Fachgruppe Informatik der KSBG]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Labyrinthe lösen und erzeugen ======
<code txt>
+---+---+---+---+---+---+
|   |           |       |
+   +   +   +   +---+   +
|   |   |   |           |
+   +   +---+---+---+   +
|   |       |       |   |
+   +   +---+   +   +   +
|               |   |   |
+   +---+   +---+---+   +
|   |               |   |
+---+   +   +---+---+   +
|       |           |   |
+---+---+---+---+---+---+
</code>


In einem Raster sollen Labyrinthe gelöst und erzeugt werden.

Zur Verfügung steht eine Klasse, die eine zeilenweise ASCII-Art Darstellung des Labyrinths enthält und manipulieren kann.

  * ''l = Laby(5,8)'': Erzeugt ein leeres Raster der Grösse 5x8 (alle Verbindungen geschlossen).
  * ''l.w'' und ''l.h'' sind die Breite und Höhe des Rasters (Anzahl Zellen).
  * Zellinhalte können gesetzt und abgefragt werden: ''l.setMark(x,y,c)'' und ''l.getMark(x,y)''. Default-Inhalt ist ein Leerschlag.
  * Die vier Richtungen sind definiert: ''l.dirs'', von 0 bis 3, trigonometrisch von 0˚ bis 270˚.
  * Verbindungen können gesetzt und abgefragt werden: ''l.canGo(x,y,d)'' und ''l.setGo(x,y,d,True/False)''
  * Hilfsfunktion ''a,b = l.move(x,y,d)'' liefert die verschobenen Koordinaten von ''(x,y)'' in Richtung ''d''.
  * Hilfsfunktion ''l.on(x,y)'' liefert ''True'',  wenn ''(x,y)'' im Raster.
  * ''l.neu()'' generiert ein leeres Raster mit allen Verbindungen geschlossen.
  * ''l.load(datei)'', ''l.save(datei)'', tut was man vermutet.

{{lehrkraefte:blc:informatik:efi-2023:laby.zip|Python-Code}}

{{lehrkraefte:blc:informatik:efi-2023:labs.zip|Weitere Labyrinthe}}


===== Aufgaben =====
  * Es soll der (einzig existierende) Weg von der linken oberen Zelle (0,0) zur Zelle unten rechts (l.w-1, l.h-1) gefunden werden.
    * Überlegen Sie sich dazu erste einen Algorithmus auf Papier. Nutzen Sie dazu die Möglichkeit, Zellen markieren zu können.
    * Programmieren Sie Ihren Algorithmus. Markieren Sie den Weg
      * Markierung entweder mit 'X', oder optional die Richtung angeben, in der die Zelle verlassen werden muss, mit '>', 'v',  '<', '^'.
  * Überlegen Sie sich, wie ein Labyrinth generiert werden könnte und programmieren Sie einen solchen Generator.
  * Wie zufällig ist ihr generiertes Labyrinth? Könnten alle möglichen Labyrinthe von Ihrem Algorithmus erzeugt werden? Sind die einzelnen Labyrinthe gleich wahrscheinlich?