Algorithmus für Wegfindung im Karosystem

[maexle1894]

Hallo PHP-Gemeinde,
ich will in mein Online-RPG eine intelligente Wegfindung einbauen. Dazu habe ich mir verschiedene Algorithmen angeschaut (First-Depth usw.), aber leider komme ich nicht weiter. Hier meine bisherige Argumentation :

Ich habe beispielsweise einen Player (in allen Grafiken der rote Punkt) und einen Zielpunkt (immer der grüne Punkt).

Da ich mich auf dem Karo nur rechts/links oder hoch/runter bewegen kann, ist es egal, ob ich diagonal laufe, oder im rechtwinkligen Dreieck [GRAFIK1].

Deshalb habe ich mir einen eigentlich ganz einfachen Algorithmus ausgedacht :

Der Suchweg beginnt in einer "richtigen Richtung" (im Fall von [GRAFIK1] entweder rechts oder unten). Sobald der Suchweg eine Koordinate von meinem Zielpunkt erreicht hat, wechselt er die Richtung (zum Zielpunkt hin).

Das funktioniert einwandfrei, solange nichts dazwischen ist *gg*.

Im Falle einer Kollision wird die Richtung in die andere "richtige Richtung" geändert. [GRAFIK2] Sollte auch das nicht zum Erfolg führen, geht der Suchweg einen Schritt in eine Richtung, die frei ist, und immer so weiter [GRAFIK3].

Im Falle von [GRAFIK4] geht das aber schief. Hier habe ich mir überlegt, evntl. eine Sackgassenfunktion zu schreiben, oder so Ultra-Schall-mäßig...

Und ab da setzt es bei mir aus. Hat vielleicht von euch schon mal jemand sowas in dieser Art geschrieben?

Die Felder, die begehbar sind, werden auf einer Access_Grafik als weißes Pixel dargestellt. Vielleicht kann man das Problem ja auch grafisch lösen?

Alles nur annähernd verwandte kann mir weiterhelfen. Vielen Dank schon mal im Vorraus.

Grüße

 

[hpvw]

Ein Algorithmus für eine solche Suche ist A*.
Google findet etliche Erklärungen dazu.
Desweiteren hilft die Suche nach kürzeste Wege Algorithmen.
In jedem Fall solltest Du die möglichen Wege in Deinem "Karo" als Graph abbilden, damit Du mit den Algorithmen darin suchen kannst.
Schwierig wird es an dem Punkt, wo Du nicht von voller Vorraussicht ausgehen willst. Da müsstest Du Dir in Deinem Graph überlegen, wie du das abbildest. eine Möglichkeit wäre von jedem Randpunkt des sichtbaren Bereichs die direkte Entfernung zum Ziel zu bestimmen, eine andere wäre, das ganze mit ein bisschen Zufall zu paaren. Bist Du am Ende des sichtbaren Bereichs angelangt müsstest Du den Algoritmhus erneut starten und den Bereich um die Sichtweite erweitern.

Gruß hpvw