text: Pfadberechnung - Das deutsche Python-Forum
  Pfadberechnung
  Samstag 25. Oktober 2008, 00:32
  Ich beschäftige mich schon länger mit Python Spieleprogrammierung mit PyGame. Funktioniert auch gut.
  Ein Spiel habe ich jetzt fast fertig. Bei dem Spiel wird ein Grid (ich nenne es mal so) von 50x50 15px großen Feldern erstellt. Und in diesem Grid sollte es halt einen Weg geben der von einem Startpunkt zu einem Zielpunkt führt.
  Bis jetzt habe ich das alles mit TXT Dateien gelöst, d.H. ich musste jedes Level selbst per Hand erstellen, wollte nun aber noch einbauen, dass dies automatisch erstellt wird, allerdings weiß ich nicht sorecht, wo ich anfangen soll.
  Hier ist die Basisklasse:
  self.generiereSonder()
  self.generierePfad()
  def generiereSonder(self):
  self.start = (random.randint(1, 49), random.randint(1, 49))
  self.ziel = (random.randint(1, 49, random.randint(1, 49))
  if self.start == self.ziel:
  def generierePfad(self):
  self.pfad = []
  Nun dachte ich mir, dass ich in die pfad-Liste alle Einträge (also Position in Form von (X, Y)) eintrage, die ein Wegstück darstellen. Wie kann ich diese Wegstücke nun berechnen? Startpunkt sollte halt die start-Variable sein, Endpunkt die ziel-Variable. Ich will es weitgehend selber machen, weiß aber wie gesagt gar nicht wo ich da anfangen muss.
  Samstag 25. Oktober 2008, 00:50
  Einfachste Lösung wäre es wohl eine rekursive Tiefensuche zu machen und sich den Weg zu merken. Erste Verbesserung wäre "branch and bound", das heisst wenn man einen Weg gefunden hat und dessen Kosten, also die Länge kennt, braucht man bei der weiteren Suche Wege die Länger als der bisher beste Weg sind, nicht mehr weiter verfolgen.
  Falls das zu langsam sein sollte, ist der A*-Algorithmus der nächste Schritt.
  Samstag 25. Oktober 2008, 01:27
  Danke, das ist doch ein Ansatz.
  Ich habe aber irgendwie noch nicht so recht verstanden, wie ich den Tiefsuche-Algorithmus benutze. Habe diesen Snippet im Netz gefunden:
  # Copyright (c) 2008 the authors listed at the following URL, and/or
  # the authors of referenced articles or incorporated external code:
  # http://en.literateprograms.org/Depth-first_search_(Python)?action=history&offset=20081013235803
  # Retrieved from: http://en.literateprograms.org/Depth-first_search_(Python)?oldid=15001
  def petersenGraph():
  v = [Vertex(i) for i in xrange(50)]
  # von mir, das soll das 50*50 Grid in t speichern
  while k < 50:
  t.append((i, k))
  # ab hier ist nichts mehr von mir
  for a, b in t:
  v = petersenGraph()
  # was meint die 49?
  if depthFirstSearch(v[0], (lambda v: v.data == 49), path):
  print "Found path:", [u.data for u in path]
  Tut mir Leid dass ich mich so schwer tue, doch in Mathe war ich noch nie ein Ass!
  Samstag 25. Oktober 2008, 08:45
  Die deutsche Wikipedia hat einen Artikel über Tiefensuche.
  Du solltest den Code selber schreiben und nicht irgendwelchen aus dem Netz anpassen. Der Grundlegende Algorithmus ist relativ abstrakt und die konkrete Implementierung hängt von den Datenstrukturen ab, auf denen operiert wird.
  Allerdings sollte ich so spät am Abend wohl nichts mehr schreiben, denn besser wäre wohl der Algorithmus von Dijkstra.
  Der ist auch wieder recht allgemein gehalten und muss auf die konkreten Datenstrukturen angepasst werden. Der Graph ist bei Dir ja zum Beispiel wahrscheinlich implizit in der Spielkarte enthalten. Die Spielfelder sind die Knoten und es existieren Kanten zwischen allen benachbarten Feldern, falls das jeweilige Zielfeld betretbar ist. Kantengewicht ist im simpelsten Fall immer 1 und die Distanzen entsprächen dann einfach der Anzahl der Schritte zwischen den Feldern.
  Ich würde ihn allgemein implementieren, d.h. mit einer Knotenklasse, die die nötigen Eigenschaften besitzt und dann eine Knotenklasse implementieren, die eine Referenz auf die Karte hat und ihre eigene Position kennt. Sofern die Karte als Abbildung von Koordinaten auf Spielfelder implementiert ist.
  Samstag 25. Oktober 2008, 15:20
  Wobei mir noch nicht ganz klar ist, wie man die Tiefensuche mit einem Level-Generator kombiniert? Einfach per Zufall Felder blockieren und dann suchen ob noch ein Weg existiert klingt für mich wenig gelungen.
  Vielleicht verstehe ich den Fragesteller auch nicht, aber wenn er das Level eh generieren möchte, würde ich doch eher zu Beginn einen Weg festlegen und dann das Level drum herum generieren lassen.