Differences

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

--- efinf:blcks2017:labyrinth [2018/03/30 10:13]
Ivo Blöchliger [Graphen-Such-Algorithmen]
+++ efinf:blcks2017:labyrinth [2018/04/24 15:21] (current)
Ivo Blöchliger [Alternative Baum-Generierung]
@@ Line 38: / Line 38: @@
+Je nachdem, wie die Todo-Liste gehandhabt wird, erhält an verschiedene Algorithmen:
+  * Wird immer der zuletzt eingefügte Knoten entfernt, erhält man die Tiefensuche (Depthfirst search). D.h. man geht erst soweit in die Tiefe wie möglich.
+  * Werden die Knoten in der Reihenfolge entfernt, in der sie eingefügt wurden, erhält man die Breitensuche (Breadhfirst search). D.h. man besucht die Knoten in der Reihenfolge ihrer Entfernung vom Startknoten aus (gemessen in Anzahl Kanten).
+  * Die Knoten nach einem Kriterium ausgewählt. Wählt man z.B. den nächsten Knoten bezüglich seiner Distanz zum Startknoten aus, erhält man Dijkstras Algorithmus zur Bestimmung des kürzesten Weges (Voraussetzung sind positive Kantenlängen). Addiert man dazu zusätzlich eine unterschätzende Distanz zum Zielknoten, erhält man den $A^\star$-Algorithmus.
+Diese Algorithmen werden z.B. auch von Webcrawlern verwendet und finden (in massiv effizienteren Formen) in Navigationsgeräten anwendung.
+==== Anwendung zu Generierung eines Labyrinths ====
+Wird kein Zielknoten festegelegt, erzeugt obiger Algorithmus exakt einen Weg vom Startknoten zu jedem anderen Knoten, d.h. ein Baum. Wird der nächste Knoten "zufällig" aus der Todo-Liste ausgewählt, entsteht ein "zufälliger" Baum und damit ein zufälliges Labyrinth.
+Damit ansprechende Labyrinthe entstehen, darf nicht jeder Knoten sofort vollständig abgearbeitet werden, sondern nur ein Weg. Danach wird der Knoten wieder in die Todo-Liste eingefügt.
+Der Zufall kann so gesteuert werden, dass "ansprechende" Labyrinthe entstehen.
+===== Alternative Baum-Generierung =====
+  - Start mit $n$ Knoten, keine Kanten.
+  - Wiederhole $n-1$ mal:
+    - Man wählt zwei Knoten $u$, $v$ aus, die nicht in der gleichen zusammenhängenden Komponente sind.
+    - Man verbindet $u$, $v$ mit einer Kante
+===== Python Code =====
+<code python laby.py>
+import random
+class Laby:
+    # directions, trigonometric
+    VECS=[[1,0], [0,1], [-1,0], [0,-1]];
+    def __init__(self, width, height):
+        self.width = width
+        self.height = height
+        # Gibt für jede Koordinate an, ob nach links und nach unten gegangen werden kann.
+        # Z.B. self.canGo[3,4,0] ist True, wenn von 3,4 auf 4,4 gegangen werden kann
+        # self.canGo[3,4,1] ist False, wenn nicht von 3,4 auf 3,5 gegangen werden kann.
+        self.canGo = [[[False, False] for y in range(self.height)] for x in range(self.width)]
+        # Mark enthaelt ein String der Laenge 1, der bei der Ausgabe mit ausgegeben wird.
+        self.mark = [[" " for y in range(self.height)] for x in range(self.width)]
+    def clearMarks(self):
+        for y in range(self.height):
+            for x in range(self.width):
+                self.mark[x][y]=" "
+    # c ist ein Koordinatenpaar
+    def onBoard(self,c):
+        return c[0]>=0 and c[0]<self.width and c[1]>=0 and c[1]<self.height
+    def move(self, c,d):
+        return (c[0]+Laby.VECS[d][0], c[1]+Laby.VECS[d][1])
+    # c ist ein Koordinatenpaar,
+    # gibt True zurueck, wenn von c in Richtung d gegangen werden kann.
+    def edge(self, c, d):
+        if self.onBoard(c) and self.onBoard(self.move(c,d)):
+            if d>1:
+                c = self.move(c,d)
+                d-=2
+            return self.canGo[c[0]][c[1]][d]
+        return False
+    def setEdge(self, c,d, value=True):
+         if self.onBoard(c) and self.onBoard(self.move(c,d)):
+            if d>1:
+                c = self.move(c,d)
+                d-=2
+            self.canGo[c[0]][c[1]][d] = value
+    def __str__(self):
+        res = "+" + ("---+"*self.width)+"\n"
+        for y in range(self.height):
+            line1 = "|"
+            line2 = "+"
+            for x in range(self.width):
+                line1 += " "+self.mark[x][y]+" "
+                line1 += " " if self.edge((x,y),0) else "|"
+                line2 += "   +" if self.edge((x,y),1) else "---+"
+            res+=line1+"\n"+line2+"\n"
+        return res
+# Nur wenn Datei dekt ausgefuehrt wird:
+if __name__== "__main__":
+    l = Laby(12,12);
+    print(l)
+</code>