Problem mit einer Abfrage

[gourmet]

Hallo Leute,

ich bastel grad an einer Pathfinding lightversion.
Mir geht es darum, herauszufinden welche Koordinaten zwischen dem Startpunkt und Zielpunkt liegen,
damit ich die Datenbank abfragen kann, ob das Gebiet für diese Aktion geeignet ist.
d.h. mit Gebiet meine ich Wasser, Land usw. und Aktion Spieler verlegt sein Schiff von a nach b und
dabei sollte das Schiff natürlich nicht über Land fahren.
Horizontal und vertikal ist kein Problem nur wenn die Zellen diagonal auseinanderliegen gibt es Probleme.

Hier mal ein kleines Beispiel meines Problems:

s = Startpunkt
z = Zielpunkt
# = angezeigte Koordinaten

start-y = 1
start-x = 1
ziel-y = 5
ziel-x = 2

1 2 3 4 5 X
01|s|_|_|_|_|
02|#|_|_|_|_|
03|#|_|_|_|_|
04|#|_|_|_|_|
05|_|z|_|_|_|
Y

start-y = 1
start-x = 1
ziel-y = 5
ziel_x = 3

1 2 3 4 5 X
01|s|_|_|_|_|
02|_|#|_|_|_|
03|_|#|_|_|_|
04|_|#|_|_|_|
05|_|_|z|_|_|
Y

^^Bis hierhin läuft alles wunderbar.

start-y = 1
start-x = 1
ziel-y = 5
ziel_x = 4

1 2 3 4 5 X
01|s|_|_|_|_|
02|_|#|#|_|_|
03|_|#|#|_|_|
04|_|#|#|_|_|
05|_|_|z|_|_|
Y

^^Hier werden mir "2" Wege angezeigt

Der Code dazu

    //diagonal unten rechts
    IF($start_y < $ziel_y AND $start_x < $ziel_x) {
    $weg_x = $start_x +1;
    $weg_y = $start_y +1;
        if($weg_y == $ziel_y) { $weg_y = $start_y; }
        if($weg_x == $ziel_x AND $weg_y != $start_y) { $weg_x = $start_x; }
        for($a = $weg_y; $a < $ziel_y; $a++) {
            for($b = $weg_x; $b < $ziel_x; $b++) {
            echo "Koords: Y-".$a." X-".$b;
            }
        }
    } 

Kann mir jemand helfen oder einen Tip geben?

[onemorenerd]

Du ermittelst in diesem Schritt alle direkten Wege vom Start zum Ziel. Im nächsten Schritt wirst du in der DB nachsehen, welche der Kacheln auf den Wegen überhaupt für Schiffe befahrbar sind.
Dabei stellst du vielleicht fest, dass die direkten Wege alle über Land führen. Das heißt aber nicht, dass es keinen Seeweg gibt. Eventuell muß man nur einen kleinen Umweg fahren ...

http://theory.stanford.edu/~amitp/GameProgramming/

[gourmet]

@onemorenerd

Mit Pathfinding u.a. A* habe ich mich auch schon ein wenig beschäftigt,
habe aber nur Lösungen in sämtlichen Scriptsprachen, außer php gefunden.

Da die Wegfindung unter Umständen den Server stark belastet und/oder
es sei in php nicht möglich, habe ich mich nicht weiter damit beschäftigt.
Der Link den du mir gepostest hast scheint interessant zu sein
und ich werde mir das nochmal genau angucken.

[tontechniker]

A* ist für PHP kein Problem und lässt sich problemlos auch ohne Grundlage in PHP implementieren.

[gourmet]

Ich habe mich nun ausgiebig mit dem Thema A* beschäftigt und habe mal angefangen zu basteln

Codeausschnitt:

WHILE($go == TRUE) {
$open[] = array_pop($open_list);
    foreach($open as $O) {
        foreach($suche as $next) {
        $y = $O[0] + $next[0];
        $x = $O[1] + $next[1];
            IF($y != 0 AND $x != 0) {
            $weg = array($y,$x,0);
            
                IF(!in_array($weg, $open_list)) {
                $open_list[] = $weg;
                    foreach($open_list as $key=> $val) {
                        IF($open_list[$key][2] == 0) {
                        $open_list[$key][2] = weg($val[0], $val[1], $ziel[0], $ziel[1]);
                        }
                        rsort($open_list,2); //Hier wird das Array leider nicht so sortiert wie ich erhofft hatte
                    }
                }
                    IF($weg == $ziel) {
                    //echo "Ziel erreicht";
                    $go = FALSE;
                    }
            }
        }
    }
} 

Ich möchte nun die offene Liste nach kürzesten Weg absteigend sortieren.
d.h. der letzte Wert soll der kürzeste sein.
ich möchte den Wert dann dazu benutzen ihn in die geschlossene Liste einzutragen und
bei der erneuten Suche wieder als Startwert zu nutzen.

Aufbau des Arrays open_list
ARRAY_open_list[0]_ARRAY[0]=X[1]=Y[2]=WEG