Pfadberechnung

[theliquidwave]

Hallo.
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:

Code: Alles auswählen

class Level:
	def __init__(self):
		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:
			self.generiereSonder()
	
	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.
Kann mir jemand einen Denkanstoß geben?

Danke,
~ Chris

[BlackJack]

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.

[theliquidwave]

Hi.
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:

Code: Alles auswählen

# 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
# 
# Permission is hereby granted, free of charge, to any person obtaining
# a copy of this software and associated documentation files (the
# "Software"), to deal in the Software without restriction, including
# without limitation the rights to use, copy, modify, merge, publish,
# distribute, sublicense, and/or sell copies of the Software, and to
# permit persons to whom the Software is furnished to do so, subject to
# the following conditions:
# 
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
# IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
# CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
# TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
# 
# Retrieved from: http://en.literateprograms.org/Depth-first_search_(Python)?oldid=15001

class Vertex:
	def __init__(self, data):
		self.data = data
		self.successors = []


def depthFirstSearch(start, isGoal, result):
	if start in result:
		return False


	result.append(start)

	if isGoal(start):
		return True

	for v in start.successors:
		if depthFirstSearch(v, isGoal, result):
			return True


	# No path was found
	result.pop()
	return False


def petersenGraph():
	v = [Vertex(i) for i in xrange(50)]
	
	# von mir, das soll das 50*50 Grid in t speichern
	t = []
	i = 0
	while i < 50:
		k = 0
		while k < 50:
			t.append((i, k))
			k += 1
		i += 1
	# ab hier ist nichts mehr von mir
	
	for a, b in t:
		v[a].successors.append(v[b])

	return v


if __name__ == "__main__":
	v = petersenGraph()
	path = []
	
	# was meint die 49?
	if depthFirstSearch(v[0], (lambda v: v.data == 49), path):
		print "Found path:", [u.data for u in path]
	else:
		print "No path found"

Tut mir Leid dass ich mich so schwer tue, doch in Mathe war ich noch nie ein Ass!

~ Chris

[BlackJack]

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.

[Hyperion]

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.

Aber vielleicht habe ich auch die Frage falsch verstanden

[dannemann]

hi chrisber

schau dir doch mal diesen link an, vielleicht hilft er dir bei deiner pfadsuche:

http://www.policyalmanac.org/games/aSta ... al_de.html

[theliquidwave]

Hi.
Danke dannemann, dein Link hat mir sehr geholfen.
Natürlich auch ein Dnake an die anderen

~ Chris