Hi,
für die, die mich nicht kennen, ich bin Coolcat von DelphiDev.de. Wir sind quasi euer deutsches DirectX-Äquivalent.
Ich habe mir heute morgen mal euer Pathfinding2-Tutorial mal kurz angeschaut und habe einige Verbesserungsvorschläge:

Aus den berechneten Wegpunkten sollte man meiner Meinung nach keinen Baum erzeugen, sondern die Daten als Graph (vom Prinzip ein Baum mit Zykeln) speichern.
Zusätzlich wird jeder Kante (Verbinung zw. Wegpunkten) ein sog. "Kantengewicht" zugeordnet, im einfachsten Fall einfach nur die Länge. Man könnte aber z.B. auch die Bodenbeschaffenheit (z.B. unebenes Gelände) mit einberechnen. Der Algorithmus soll später eine Kante mit kleinem Gewicht "lieber" wählen, als eine Kante mit großem Gewicht.
(Achtung: Kantengewichte dürfen nicht negativ sein, führt zu Endlosschleifen später im Algo)

Den Graph könnte man dann z.B. mit dem Dijkstra-Algorithmus durchlaufen. Dieser ist recht schnell, insbesondere wenn die Anzahl der Kanten gering ist.
Infos zum Algo gibts z.B. hier:
http://de.wikipedia.org/wiki/Dijkstras_Algorithmus oder
http://www-i8.informatik.rwth-aachen.de ... -pfade.pdf (ab Seite 19)
(jedoch sind beide Erklärungen nicht so toll, in dem PDF ist aber wenigstens ein Beispiel)
Für alle die den A*-Algorithmus kennen: A* ist eine Verbesserung des Dijkstra.

Wenn man dann schon nur noch mit einem Wegpunktnetz (Graph) arbeitet, könnte man dann das ganze auch noch problemlos auf drei Dimensionen erweitern.
Zusätzlich wäre es möglich ohne das "Felder"-Raster zu arbeiten. Nachteil wäre dabei dann allerdings, dass das erstellen des Netzes möglicherweise nicht mehr ganz so einfach funktioniert.

mfg,
Coolcat

_________________
Yeah!

Hehe... Also dass ich mit "Ihr" angesprochen werde, hätte ich dann doch auch nicht erwartet ^^

Mit Graphen an sich hab' ich mich noch nie wirklich befasst. Daher sucht man diese auch im Tutorial vergeblich. Als Einleitung schrieb ich dort ja bereits, dass ich mir das alles selbst ausgedacht habe. Von daher wird man auch keine praxiserprobten Lösungen wie A* oder vergleichbares finden

Aber ich werde mich definitiv mal näher mit den Graphen beschäftigen und wer weiß... Vielleicht gibt's ja dann eines Tages noch ein Tutorial zum Thema Pathfinding

Abschließend noch: Vielen Dank für das Feedback

_________________
"Für kein Tier wird so viel gearbeitet wie für die Katz'."

Also Graphen sind echt ganz einfach. Wer das Prinzip von Bäumen verstanden hat, wird mit Graphen keine Probleme haben.
Ich selbst habe mich überings auch noch nicht wirklich mit Pathfinding beschäftigt, sondern nur eine Vorlesung Datenstrukturen&Algorithmen gehört. Dijkstra gehört da quasi zum Standard, wie auch Quicksort, etc.


In meinem ganzen Post steht nicht ein einziges mal "ihr" drin.....nur zweimal "euer".
Ich meinte auch "euch" als DelphiGL-Community.

Coolcat

_________________
Yeah!

Zu Weihnachten hab ich ein Tut hier veröffentlich. Ursprünglich wollte ich Graphentheorie als Thema wählen. Aber als ich dann angefangen hab loszuschreiben, viel mir auf, dass ich das TI Skript abtippe. Da hab ichs lieber sein lassen. Irgendwie ist es schwer Leute für Graphen zu begeistern. Wenn man sich aber erstmal damit beschäftigt hat, merkt man was man alles damit machen kann. (Man denke nur an Fluss-Netzwerke. Ohne Graphen sicherlich ein Hinderniss)

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Google


Also ich finde es schonmal schön, dass auch auf anderen Seiten hierher (und zu dem Tutorial) verlinkt wird, aber etwas verwirrt bin ich von deiner anonymen Ansprache dennoch... Du nennst stets Phobeus oder die Community hier im Zusammenhang mit dem Tutorial...
Aber du darfst mich ruhig beim Namen nennen Ich beiße nicht

Gruß,
Frase

_________________
"Für kein Tier wird so viel gearbeitet wie für die Katz'."