Beschreibung:

Die PathFinderLib unterstüzt zwei Typen der Wegfindung:
- die Wegsuche in einer Rasterbasierenden Karte (GridPathFinder, z.b. eine Bitmap bei der schwarze Pixel Hindernisse darstellen und weiße passierbar sind)
- die Wegsuche in einem Rasterlosen System mit Knotenpunkten die untereinander verbunden sind (GridlessPathFinder)
- die Wegsuche in einem Rasterlosen System bei dem Knotenpunkte durch Wege (Tracks) verbunden sind

Es handelt sich hierbei um eine Verbesserte und Erweiterte Version der PathFinder-Klasse aus diesm Thread. Ebenfalls beiliegend ist der SourceCode in Form der Projektmappe sowie ein kleines Demo-Programm.

Update Version 1.1 (28.02.12) Informationen
Update Version 1.1.1 (12.03.12) Informationen

Screenshots:






Verwendete Programmiersprache:
Visual Basic .NET (IDE: VB 2008 Express)

Systemanforderungen:
.NET Framework 2.0

Download:
PathFinder v1.0 Komplettpaket (Demo, Source, etc)(250KB)
PathFinder v1.1 Komplettpaket (Demo, Source, etc)(310KB)
PathFinder v1.1.1 Komplettpaket (Demo, Source, etc)(350KB)<-- NEU!


Lizenz/Weitergabe:
Freeware und OpenSource
Bei Verwendung in einem Projekt würde ich mich über Namensnennung freuen!

Ich glaube das könnte für einige Leute hier hilfreich sein.
Wird dort der A*-Algorithmus verwendet?

Hi!
Also im GridLess-Modus wird eher der Dijkstra-Algorithmus verwendet (habe das ganze selbst programmiert, von dahher können leichte Abwandlungen vorkommen). Der Grid-Modus verwendet eigentlich das gleiche Prinzip wie der GridLess-Modus ist nur optimierter im Bezug auf das Raster: Es gibt keine Einzelnen Knoten die verweise auf Nachbarn haben da die Nachbarn per Koordinate bestimmt werden können. Ist also schwer zu sagen was genau da verwendet wird - auf jeden Fall kein reines A* da mein Algorithmus die Knoten nicht nach "führt wahrscheinlich am schnellsten zum ziel" bewertet und untersucht.

Bitte mehr in dieser Richtung.

Also das die Lib so schnell Freunde findet hätte ich nicht erwartet - Danke für Euer Interesse!

Ich gehe mal davon aus, das die meisten in Frage kommenden Nutzer dieser Lib ein Spiel im RPG-Stil programmieren möchten. Dafür bietet sich der GridPathFinder gut an - das auf kurzen Wegstrecken auch ausreichend schnell. Wie man in dem "Ur-Thread" nachlesen kann benötigt der damalige Alorithmus für die Wegfindung quer über die gesamte Pokemon-Map 100-200ms Rechenzeit - wie es bei der PathfinderLib aussieht weiß ich nicht, ich vermute ähnlich. Es ist auch relativ egal da ich auf etwas ganz anderes hinaus will:
Anstatt schwermotorisch den kompletten Weg auf einmal zu finden kann man den Kuchen auch in Stücke teilen und performancetechnisch optimieren. Hier mal eine Grafik die das verdeutlichen soll:


Annahme: Man will von Dorf2 zu Dorf4 gehen - oder von Dorf1 zu Dorf4. Der Unterschied? Im groben nur der Weg zwischen den beiden Startdörfern zu Dorf5 - der Rest ist identisch. Man sieht, dass das hier vorarbeit geleistet werden kann indem man die Entfernungen zwischen den Einzelnen Dörfern im voraus berechnet und abspeichert. So kann man den GridlessPathFinder nutzen um die grobe Route zu planen. Man könnte (wenn die Strecken extrem lang sind) auch den Detail-Pfad der mittels GridPathFinder berechnet wurde speichern und benutzen. So muss eigentlich nur der Pfad zwischen Jetzt-Position und Pfadbeginn des nächstgelegenen Dorfes berechnet werden - sinngemäß das gleiche für die Zielposition.

So lassen sich während des Spiels aussetzter und lags beheben - und warum gibt es wohl ladescreens? xD Doch nicht etwa zum Vorberechnen der Wege^^

Wenn man nun soetwas realisieren will muss die "Knotenpunkt-Klasse" für den GridLesspathFinder so erstellt werden, dass sie nicht die Dörfer repräsentiert sondern die Wege zwischen ihnen! Wer an dieser Stelle scheitert möge dann aber ein neues Thema erstellen mit verweis auf diesen Thread^^

Sowas ist natürlich perfekt für PaperPanzer (für den Singleplayer)!

grandios ... gerade "GridlessPathFinder" gefällt mir und ist sogar bei 90-100 nodes subjektiv gesehen sehr sehr performant (unter 1 sec)

danke

Kann es sein das das hier ein Fehler ist?



Bin mir nich sicher, aber eigendlich kommt er ja da nicht durch oder?

Sehr schöne sache ich bedanke mich dass kann immer sehr hilfreich sein....

@Flipez:
Du hast 8 Nachbarn ausgewählt, sprich es werden auch Diagonalen berücksichtigt. Wenn das nicht sein soll musst du 4 Nachbarn auswählen.

Mfg
Firestorm

Achso, alles klar. Ich konnte das mit den 4 und 8 nicht richtig zuordnen.

Hallo TE,

tolle Leistung.

Gruss

mikeb69

TE hat auch einen Namen

Ok das ist echt ma was das was hergibt. Mus man sagen

sehr gut. mehr davon

@Myrax,

ich schau nicht immer nach wer das Thema erstellt hat.
Sollte sich der TE dadurch gekränkt fühlen tut es mir Leid.

Gruss

mikeb69

War auch bloss als Scherz gemeint.

Edel!

hab mir vor kurzem mal ein 2D TD-Game in XNA vorgenommen, dafür wäre sowas z.B. perfekt. Ich machs trotzdem lieber selbst, da lernt man mehr

Aber wie schon mehrfach gesagt, Respekt an die Leistung! Seit langem mal wieder was richtig interessantes im Showroom.

Ich hatte ähnliches mit der triangulation mal erstellt.
Da waren die Erbebnisse nicht immer optimal!
Sehr gut!

Nochmal an alle: Vielen Dank für die vielen Lobenden Beiträge! Es Freut mich sehr, dass die Lib auf solches Interesse gestoßen ist - so macht das weiterentwickeln gleich doppelt Spaß. Darum gibt es jetzt die Version 1.1!

Neuerungen:

• Bugfix behebt Problem im Algorithmus des GridlessPathFinder (Auswirkung gibt es hier zu sehen)
• Überarbeitung der bestehenden Klassen (Felder zu Properties, etc)
• Neu: NodeByLocation-Klasse (war vorher im Demo-Project dabei, nun in fester bestandteil der Lib)
• Neu: NodeAsTrack-Klasse
  

NodeByLocation-KlasseDiese Klasse war schon in der Version 1.0 vorhanden - allerdings nur im Demo-Project. Nun ist sie, etwas ausgebessert, in die Lib integriert. Sie eignet sich besonders zur Wegfindung bei denen die direkte Entfernung zwischen den Knoten die Wegstrecke ist (der Abstand von Knoten1 zu Knoten2 ist die Wegstrecke).
NodeAsTrack-KlasseMan kann Sie als Erweiterung der NodeByLocation-Klasse sehen. Sie hebelt die Begrenztheit der besagten Klasse aus: Es ist Beispielsweise unmöglich ein solches Konstrukt mit der NodeByLocation-Klasse zu erstellen (versuch mal ein Dreieck mit diesen Kantenlängen zu zeichnen^^).
Dafür gibt es nun die NAT-Klasse. Sie kümmert sich um das Erstellen von Knotenpunkten (BSP: Dörfer oder Kreuzungen) und den Verbindungen (Wegstrecken => Track) zwischen ihnen. Dabei muss ein Weg nicht mehr stumpf geradlinig sein, ein Track kann den genauen Wegverlauf mittels Wegpunkten speichern und die Wegstrecke anhand der Liste von Wegpunkten berechnen. Alternativ verzichtet man auf den genauen Wegverlauf und gibt die gewünschte Entfernung zwischen den Punkten manuell an. Ein weiterer Bonus ist die WegFaktor-Eigenschaft der Track-Klasse. Es lassen sich so weitere Faktoren (z.b. die Geschwindigkeit) einbeziehen - der zeitlich gesehen schnellste Weg kann gefunden werden.

So lassen sich Situationen wie folgende berechnen:



ein Weiteres Aufgabengebiet habe ich schon in diesem Post beschrieben - das die Track-Klasse eine PointListe für den genauen Wegverlauf nutzt kommt gerade Recht: Denn der GridPathFinder liefert eine solche als Ergebnis seiner Wegfindung^^

Ich hoffe das Update wird dem ein oder anderen die Lib noch schmackhafter machen. Über Rückmeldung würde ich mich freuen!

PS: TE ist mir völlig ausreichend - auf der "Arbeit" ruft man nach mir auch nur zwei Buchstaben