Hallo,
ich habe da eine kleine Frage zum zweiten Pathfinding Tutorial, bzw Pathfinding generell.
Ich plane ein Pathfinding zu implementieren, bei welchem ich beliebige konvexe (vielleicht auch konkave) Polygone als Hindernisse habe.
Sicherlich lässt sich das dort genannte Prinzip auch hierfür erweitern, da es wie genannt auch bei UT verwendet wird.

Das Problem ist nun, dass ich beim durchlesen nicht erkennen kann, wie sichergestellt wird, dass die Akteure auch durch die Wege passen.
Ich habe mir den Code dazu noch nicht angesehen, da ich eigentlich vorhatte einen eigenen Ansatz zu implementieren, dann aber beim Nachdenken darüber an diesem Problem gescheitert bin.
Die Kollision meiner Spielfiguren wollte ich mit Kreisen lösen, damit das Ganze nicht zu kompliziert wird.

Meine Idee ist nun, das Polygon zu nehmen, zu skalieren, und zwar mit dem Radius der Spielfiguren. Dann werden die Vertices des neuen Polygons zu Nodes gemacht. So können die Figuren schonmal entlang des Polygons laufen. Man könnte nun prüfen, ob der Abstand einer dieser Nodes zu einem anderen Polygon kleiner als der Radius ist, dann wäre der Weg nicht begehbar, aber was tue ich dann? den Node einfach löschen?

Wie ließe sich sowas am besten umsetzen?

€: ich habe erstmal eine kleine demo-anwendung geschrieben, die die wege erzeugt, nun muss ich halt noch prüfen, ob meine Spieler da durch passen: http://exec-dev.de/Test2.jar Eigentlich müsste es ja reichen, zwei weitere parallele Geraden loszuschicken und die auf Schnitt zu prüfen, oder?

Vielen Dank schonmal,

mfg

Wenn du alle Knoten die von einem Startknoten aus direkt (ohne über andere Knoten zu gehen) in einer Liste speicherst, dann löschst du die Kante/Verbindung die nicht gegangen werden kann, indem du den Knoten aus der "Nachbarschaftsliste" entfernst.

Aus dem System darfst du den natürlich nicht löschen, denn unter umständen kommst du über einen Umweg ja trotzdem noch da hin.

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

Eine Nachbarschaftsliste hab ich nicht direkt, ich habe eine die Verbindungen rekursiv implementiert.
Meine Node Klasse sieht so aus:


Und so erzeuge ich nun mein Netzwerk, Prüfung der Breite scheint auch schon zu funktionieren:

Eigentlich müsste ich jetzt nur noch das Pathfinding selbst implementieren. Nur welcher Algo eignet sich dafür am besten?

mfg

Natürlich hast du eine Nachbarschaftsliste. Das ist "nodes".
Die enthält für jeden Knoten alle Nachbarn.
Wenn du jetzt feststellst, dass deine Einheiten durch einen Zwischenraum nicht durchpassen, dann löscht du die Verbindung zwischen den Nodes indem du bei beiden beteiligten Nodes, die jeweils andere aus der Nachbarschaftsliste entfernst.

Falls du unterschiedlich dicke Einheiten hast, ist die Sache nicht so einfach. Eventuell kannst du ja in der Nodesliste keine direkten Nodes speichern sondern verbindungsdaten. Da steht dann drinnen, wo der Weg hingeht (zielnode), wie breit er ist und eventuell noch wie hoch die Kosten sind ihn zu gehen. So könntest du z.B. auch wege über unwegsames Gelände simulieren. Da sind dann die Kosten einfach höher.

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

Naja ich mache es ja jetzt so, dass ich vorm erzeugen der Verbindungen bereits prüfe, ob Hindernisse existieren, somit muss ich auch keine Verbindungen löschen. Leider gibt es im Tutorial keine Beschreibung dazu, wie die eigentliche Wegfindungsroutine implementiert wurde.

Welches Pathfinding Tutorial meinst du? Wir haben 2. Das erste beschreibt den A* Algorithmus.

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

Ich meinte eigentlich das zweite. Das erste beginnt mit den Worten: Da dachte ich mir, dass das für meine Zwecke wohl nicht das richtige ist. Aber soweit ich weiß ist der A* universell einsetzbar, nur so wirklich verstehen tut man den (sofern es sich um A* handelt wie du sagst) durch das Tutorial nicht. Vor allem wenn man ihn auf ein anderes Problem übertragen möchte.

mfg

Naja, der A* ist eigentlich ein ganz simpler Algorithmus. Er arbeitet mit einer Heuristik, also einer Abschätzung der noch kommenden Kosten.

Wenn wir mal einen "Vorgänger" vom A* betrachten, nämlich einer Kostenbasierten Wegsuche, dann funktioniert die ja nach dem Prinzip:

1.Nehme alle Nachbarn des aktuellen Knotens
2.Addiere die Kosten bis zum aktuellen knoten mit den Kosten die nötig sind den Nachbarn zu erreichen und sortiere den Nachbarknoten in eine Liste der entdeckten Knoten ein. Kleinste Kosten zuerst.
3.Nehme den nächsten Knoten aus der liste als aktuellen Knoten.

Kosten können z.B. die Wegstrecke sein, Aber auch abstractere Sachen z.B. die Wegdauer oder Aufwand einen Weg zu gehen.

Wenn du den obigen Ansatz verfolgst, läufst du die "schnellsten"/"günstigsten" Wege zuerst ab. Das kann aber sinnlos sein, wenn die Wege z.B. vom Ziel weg zeigen. Wir wollen ja zum Ziel hin. Und hier setzt die Heuristik von A* ein.
Die Heuristik schätzt nämlich ab, wie weit ein Knoten mindestens vom Ziel entfernt ist. (Wichtig: Eine gültige Heuristik DARF NIE die tatsächliche Entfernung überschätzen, nur unterschätzen.)
Die einfachste Heuristik ist die Berechnung des Luftlinienabstands per Satz des Pythagoras.

Wenn wir nun den obigen algorithmus zum A* ausbauen wollen, addierst du das Ergebnis der Heuristik auf den Wert von Punkt 2 mit auf. Der Rest bleibt gleich.

A* funktioniert auch auf "nicht gerasterten" Flächen. Du musst du irgend eine Möglichkeit haben den Abstand zum ziel zu bestimmen. Wenn du nur einzelne Knoten in deinem Level liegen hast, die kein quadratisches Netz bilden, dann geht das trotzdem, wenn du die 2D Koordinaten der Knoten zum Berechnen der Heuristik verwendest.

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

Vielen Dank, das war die bisher verständlichste Erklärung die ich gelesen hab ich werde mal schauen ob ich das umsetzen kann.

€: Ich hab die Beschreibung von Wikipedia.de verwendet und konnte damit meinen A* zum Laufen bringen


mfg