Schifffahrten auf Grafikbasis berechnen (?)

Hallo alle zusammen,

ich arbeite derzeit an der Umsetzung der Spielkarte meines Browsergames. Das ganze soll wie z.B. bei Patrizier funktionieren. Das Schiff bzw. der Konvoi befindet sich auf einem Fleck der Seekarte oder in einer Stadt (in dem Fall auf der Position der Stadt). Nun klickt der Spieler auf einen Fleck auf der Karte. Nun muss das Script erkennen ob es sich um eine befahrbare Position handelt (also Wasser).

So, die Umsetzung habe habe ich im ersten Versuch so angestellt: Neben der detailreichen Karte die der Spieler sieht habe ich auch eine Schwarz-Weiße Karte dieser erstellt, wobei weiße Pixel Wasser darstellen und schwarze Pixel nicht befahrbare Stellen. Mit PHP lese ich den RGB Wert dieses Pixels aus und erkenne anhand der Farbe ob man dahin fahren kann.

So, da aber zwischen Startpunkt und Zielpunkt ein nicht befahrbarer Pixel liegen kann, also ein Schiff z.B. nicht "durch" Inseln fahren kann, muss das Script nun jeden Pixel überprüfen bis zum Ziel.

Wie bekomme ich sowas als PHP Script hin? Gibt es dafür schon Umsetzungen, oder kennt jemand eine sinnvoller Methode mit dem gleichen Ergebnis?

Würde mich wirklich sehr über Hilfe freuen, da dies die letzte "Große" Etappe vor dem Start meiner Alpha Version sein wird und ich kaum die ersten Meinungen zu meinem Spiel erwarten kann :)

Danke im vorraus!

Hallöchen, 

Für so Wegfindung nehm ich meistens denn A*-Algorithmus, näheres hier:

http://de.wikipedia.org/wiki/A*-Algorithmus

Einfach schnell und effizient :p

lg sense

Vielen Dank, das werd ich mir mal genauer anschauen ;)

Alles über die Pixel zu berechnen ist extrem aufwändig und wenn das viele Spieler machen wird schnell eine Grenze gesetzt. A* ist schon das richtige Stichwort, dennoch kann das ganz auch durch simplere Techniken performanter sowie einfacher gestaltet werden: Caching häufig benutzter Routen, Speicherung von Schlüsselpunkten mitsamt Weg (der Gesamtweg setzt sich dann zusammen aus möglichen Verbindungen der Schlüsselpunkte) e.t.c. Du wirst einen Kompromiss zwischen dem "besten" Weg und der Performance finden müssen. Dieser Link ist zwar für Flash und tile-basierte Spiele aber vielleicht hilft's dir weiter: http://tonypa.pri.ee/tbw/tut22.html (Die Links innerhalb des Artikels sind es wert aufgerufen zu werden)

Vielleicht hilft dir ja folgendes script

http://www.jtgraphic.net/2009/08/pathfinding-php/

Original von anachronist

Vielleicht hilft dir ja folgendes script

http://www.jtgraphic.net/2009/08/pathfinding-php/

Wow keine Ahnung was dieses Script sein soll, A* ist es jedenfalls nicht. Und die berechnete Route ist alles andere als brauchbar. Außerdem ist der Algorithmus rekursiv und unbrauchbar bei großen Karten. Also wenn das jemand übernimmt: Vorsicht....

> http://www.jtgraphic.net/projects/pathfind.php

Sieht nicht wirklich optimal aus.

Gestern stand ich vor dem gleichen Problem. A* ist prinzipiell bei "Freiform"-Karten (quasi Karten, die nicht in eine Representation von Knoten oder einem Gitter darstellbar sind) nicht so gut, weil das Ergebnis nur aus Achsenparallelen und Diagonalen besteht.

Abhilfe schafft hier ein sogenannter "Any Angle Path Planning" Algorithmus, wie zum Beispiel Theta* http://aigamedev.com/open/tutorials/theta-star-any-angle-paths/  ... Funktioniert klasse :)