lehrkraefte:blc:informatik:glf25:labyrinthe:wegfindung [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.
====== Wegfindungsalgorithmen ======
Ziel ist es, dass Sie ihren Wegfindungsalgorithmus in Python übersetzen und auf verschiedenen Labyrinthen testen.


<code txt>
# aktuelle Position = Startposition
# Wiederhole:
#   Alle Nachbarfelder der aktuellen Position betrachten
#   wenn ein Nachbar mit 'Z' markiert ist:
#     Beende mit "Fertig, Weg gefunden!"
#   wenn es einen unmarkierten Nachbar nb gibt:
#     markiere aktuelle Position mit 'o'
#     aktuelle Position ist neu nb
#   sonst:
#     aktuelles Feld mit 'X' markieren
#     wenn es einen Nachbar nb mit 'o' markiert gibt:
#       aktuelles Feld ist neu nb
#     sonst:
#        Beende mit "Fertig, es gibt keinen Weg"
</code>
===== Nützliche Code Schnipsel =====
==== Labyrinth laden ====

Beispiellabyrinthe gibt es hier: {{lehrkraefte:blc:informatik:glf25:labyrinthe:labs.zip}}. Entpacken Sie die Dateien ins gleiche Verzeichnis, wo sich ihre Programme und die Klassen befinden.

**Von Datei laden**
<code python>
from laby import Laby
from zelle import Zelle

l = Laby.load("10x07-06.txt")
print(l)
</code>

**In Datei speichern**
<code python>
# l enthält eine Instanz der Klasse Laby
l.save("meineloesung.txt")
</code>

==== Start und Ziel markieren ====
<code python>
l[0,0].mark = "S"
l[l.breite-1, l.hoehe-1].mark = "Z"
</code>


==== Erreichbare Nachbarszellen ====

<code python>
aktuell = l[2,4]                    # eine Zelle des Labyrinths
for dir in range(4):                # Alle Richtungen durchgehen
    if aktuell.offen[dir]:          # Wand in die Richtung ist offen
        nb = aktuell.nachbar(dir)   # Nachbarszelle (oder None, wenn es diese nicht gibt)
        if nb!=None:                # Nur wenn es diese Zelle auch gibt (Mauern am Rand könnten auch offen sein)
            # Tu wat mit nb
            nb.mark = "X"
            aktuell = nb
            break                   # for-Schleife sofort beenden (evtl. weitere Nachbarn ignorieren)
</code>


==== Dictionary nach Markierungen ====
Idee: Für jede vorhandene Markierung um eine aktuelle Zelle generiert man eine Liste mit Zellen mit dieser Markierung, z.B.
''{'X':[a,b], '.':[c], 'S':[d]}'', .d.h. es gibt zwei Nachbarszellen a,b, die mit 'X' markiert sind, eine mit '.' und eine mit 'S'.

<code python>
nachbarn = {}   # Leerer dictionary
aktuell = l[2,4]                    # eine Zelle des Labyrinths
for dir in range(4):                # Alle Richtungen durchgehen
    if aktuell.offen[dir]:          # Wand in die Richtung ist offen
        nb = aktuell.nachbar(dir)   # Nachbarszelle (oder None, wenn es diese nicht gibt)
        if nb!=None:                # Nur wenn es diese Zelle auch gibt (Mauern am Rand könnten auch offen sein)
            if nb.mark in nachbarn: # Markierung gibt es schon
                nachbarn[nb.mark].append(nb)        # Zur List hinzufügen
            else:
                nachbarn[nb.mark] = [nb]            # Sonst neue Liste mit einem Eintrag
                
</code>
==== Testen, ob ein Dictionary einen Schlüssel hat ====
<code python>
d = {"foo":2, "bar":17}
if "foo" in d:
   print("Schlüssel foo existiert")
if not "baz" in d:
   print("Schlüssel baz existiert nicht")
</code>