lehrkraefte:blc:informatik:efi-2023:laby

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
lehrkraefte:blc:informatik:efi-2023:laby [2024/05/16 09:04] – [Labyrinthe lösen und erzeugen] Ivo Blöchligerlehrkraefte:blc:informatik:efi-2023:laby [2024/05/16 09:20] (current) – [Labyrinthe lösen und erzeugen] Ivo Blöchliger
Line 1: Line 1:
 +====== 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?
 +