Direkte Wegsuche

[STARGÅTE]

Vorwort
Nach vielen schlaflosen Nächten habe ich es nun geschafft
eine funktionsfähige direkte Wegsuche zu programmieren.
Derzeit biete ich euch nur eine Demo-Anwendung,
bei der ihr selber Start und Ziel verschieben könnt
und Mauern setzen könnt.
Dies dient dazu mehr Ergebnisse zu sammeln,
sodass ihr mit BUGs oder nicht ganz richtig berechnete Wege
zeigen könnte (ScreenShot mit F12)
Später werde ich dann den Quellcode freigeben,
sodass ihr es in Spielen verwenden könnt.


Infos
- Wegsuche ist Thread-basierend (behintert während der Suche nicht das Hauptprogramm)

Vorteile
- Felderlose Wegsuche
- freies Setzen von Mauern und Start/Ziel-Punkt im Zahlenbereich FLOATs
- Enorm schnelle Wegfindung bei riesigen Karten
- genaue "umfahrung" von unregelmäßigen Mauern

Nachteile
- schneller Anstieg der Berechungszeit bei ungünstiger Mauerlage


ScreenShot


PathFind.zip - Quellcode von Demo, PathFind und Includes

PathFind - Demo Nur als Anwendung

Inhalt:
PathFind-Demo.pb ; Beispiel für die Anwendung
PathFind.pbi ; Haupt-Include für das Wegfinden
Math.pbi, Vector2D.pbi und Line2D.pbi ; Diese sind für die PathFind.pbi notwenig, weil ich das nicht alles mit in die PathFind quetschen wollte. Logischerweise sind dabei auch unbenutze Proceduren dabei, diese gelten hiermit als mit "veröffendlicht"
Mouse.pbi ; ist noch für die Demo notwenig.

Meine Code sind immer etwas "knapp" Kommentiert, bitte nicht übel nehmen

Zur Frage:"Wie sieht denn deine Thread-Arbeitsverteilung aus ?"

Mit einer Procedure wird halt ein Thread gestartet:
CreateThread(@FindPathThread(), *PathTree)
dieser Thread arbeitet nun (völlig unabhängig von außen)
Wenn der Weg gefunden ist, endet der Thread und ExaminePath wird 1 und man kann die Wegpunkt auslesen.
Wenn man nun während der Wegsuche n neue Linie setzt wird die aktuelle wegfindung gekillt, dass das so hart sein muss, kann dabei jeder selber entscheiden ich habe halt FreePath eingebaut.

Schauts euch einfach an.
PS: sobalt auch nur ein Byte geändert wird, verfällt die Rückgabegarantie
... kleiner witz ^^

Noch n kleiner AnwendungsHinweis:
Falls jemand diese Wegfindung bei "normalen" Quadratischen oder Rechteckigen Gebäuden anwenden will, dann braucht man dort nicht 4 Seitenwände, sondern ein Kreuz aus den Diagonalen erfüllt auch den Zweg und man braucht nur 50% der Wände.
Natürlich muss man dann noch verhindern das jemand das Ziel IN DAS Gebäude setzt.

[AND51]

Cool, funktioniert in einem ersten Schnelltest tadellos. Habe auf Anhieb nichts erwähnenswertes gefunden.
Sogar unmögliche Positionierungen werden erkannt und mit "Das Ziel ist unerreichbar" entsprechend kommentiert. Toll!

Vielleicht kannst du noch die Funktion "Alternativweg" einbauen. Denn wenn dieser Algorithmus in einem Strategiespiel eingesetzt und die markierten Einheiten immer denselben Weg nehmen würden, wäre das schon ein bisschen langweilig. Eventuell kannst du ja einen Parameter einbauen, der eine Varianz erlaubt (nicht den kürzesten Weg, sondern den kürzesten Weg mit ein paar weitläufigeren Umrundungen der Mauern, damit eine Kolonne Einheiten nicht stumpf hintereinander herläuft, sondern in lockerer Formation). Oder, was auch super wäre, wie bei einem Navigationsgerät, die Möglichkeit, komplett andere Routen, also Alternativpfade zu finden.

[dige]

Nach ca. 20 Linien ist es plötzlich gecrasht ... ohne weitere Infos. Kannst Du mal bitte eine Version mit der OnError Lib hochladen?

[RSBasic]

@SG
Hi,

echt sehr gut gemacht, das ist einfach klasse

Aber wenn zum Schluss das Ziel nicht mehr erreichbar ist, dann bekomme ich leider eine Fehlermeldung:


\\Edit:
Ich habe mal was ausprobiert, aber ich verstehe nicht, wieso das Zeil unerreichbar ist?
Da ist doch viel Platz

[STARGÅTE]

Nach ca. 20 Linien ist es plötzlich gecrasht ... ohne weitere Infos. Kannst Du mal bitte eine Version mit der OnError Lib hochladen?

Jo kann ich machen, aber was soll ich dennn alles ausgeben lassen ?
Reicht das hier:

Code: Alles auswählen

Procedure ErrorHandler() 
 MessageRequester("Fehler", GetErrorDescription()) 
 End  
EndProcedure 

OnErrorGosub(@ErrorHandler())

@RSBasic
Das das Ziel dort unerreichbar war, könnte damit zusammen hängen das du an manchen stellen "ausgebessert" hast.
Es könnte sein (habs noch nicht probiert) das er bei den Wegsuche in eine "mini"-Sackgasse gekommen ist, aus der er jedoch nicht mehr raus kommt.
Wei das möglich ist weiß ich jedoch nicht.

Ich werde als Update eine hinreichende Fehlerauflistung geben lassen....

[hörmi]

hab auch was gefunden...vll kannst ja was damit anfangen

[Kiffi]

@STARGÅTE: Immer wieder klasse, was Du da bastelst
Das sieht für mich als Laie ziemlich beeindruckend aus.

Wollt ich nur mal so gesacht ham ... Kiffi

[X0r]

Respekt!
Muss mich damit auch mal irgendwann beschäftigen.

[STARGÅTE]

Hinweis

Das kling jetzt vielleicht etwas blöd, aber ich habe die Berechungen noch mal komplett auf den Kopf gestellt und versuche nun das ganze zu minimieren (sowohl Zeit, als auch Speicher)

Deswegen kann es noch n bisschen dauern ...

[Thorium]

Cool, kann es sein das der auf dem gleichen Prinzip basiert, was ich mir auch mal ausgedacht hatte? Siehe hier.
Sieht mir so aus. Wenn ja, sehr schön das mal in aktion sehen zu können. Ich hatte es damals nie programmiert, nur konzeptioniert und wegen Schwächen bei Tilewertigkeit nicht umgesetzt.