A* Algorithmus fast fertig in PHP implementiert
lima-city → Forum → Programmiersprachen → PHP, MySQL & .htaccess
achse
algorithmus
anzahl
array
berechnen
break
code
fehler
feld
first
funktion
helfen
heuristik
hindernis
http
koordinate
last
simulator
sortieren
start
-
Hallo,
ich habe derzeit den A* Algorithmus in PHP implementiert. Ich weiß, dass ich kein besonders überragender Programmierer bin, aber ich denke , dass es zumindest brauchbar für einige ist. In allen Tests von mir, hat der A* Algorithmus wie vorgesehen geklappt, nur bei einem nicht. Deswegen hier der Code von mir und die Frage ob jemand von euch mir sagen kann, wieso er hier nicht wie vorgesehen rechnet.
Folgendes Beispiel:
Wir haben ein Feld, dass 4 x 9 Felder groß ist. Wir wollen den Weg vom Startpunkt 4,0 (X = 4 Y = 0) zum Zielpunkt 0,2 (X = 0 Y = 2) berechnen.
$map = new astar(4,9); $map->main(4,0,0,2);
Da ich das ganze für einen Simulator baue, der aus anderen Klassen die Hindernisse einbindet und übernimmt, muss ich diesen Teil hier weglassen, da wenn andere meinen Code hier benutzen (könnt ihr ruhig), das nicht hilfreich ist, da ihr ja nicht die API Anbindung an meinen Simulator habt. Deswegen müssen wir in der __construct() Methode die Hindernisse noch schnell manuell einfügen:
// Hindernisse werden aus der Map-Klasse geholt und in die Closedlist eingefügt // Hier Hindernisse manuell einfügen, solange das noch nicht über die Construct Funktion geregelt wird array_push($this->closedlist,array("X" => 1, "Y" => 2)); array_push($this->closedlist,array("X" => 1, "Y" => 3)); array_push($this->closedlist,array("X" => 2, "Y" => 2)); array_push($this->closedlist,array("X" => 3, "Y" => 2)); array_push($this->closedlist,array("X" => 2, "Y" => 0)); array_push($this->closedlist,array("X" => 2, "Y" => 1));
Wer sich das nicht mehr im Kopf vorstellen kann, dem habe ich hier ein Bild gemalt, wie unsere Situation nun aussieht: http://www.5load.de/img_68235_lvh.gif
So. Nun seht ihr auch schon das Problem. Mit der Funktion getWay, komme ich an den mit A* berechneten Weg heran. Nun klappt das immer wie vorgesehen, allerdings in dem oben von mir konstruiertem Beispiel nicht. Da berechnet er einen Weg, der den blauen Punkten auf meinem Bild entspricht. Nämlich:
Feld 0: 4,0
Feld 1: 3,1
Feld 2: 4,2
Feld 3: 3,3
Feld 4: 2,3
Feld 5: 1,4
Feld 6: 0,3
Feld 7: 0,2
Wäre er optimal müsste es doch 4,0 - 4,1 - 4,2 heißen und nicht 3,1.
Ich habe also, wenn ich nicht falsch mitgedacht habe, irgendwo einen kleinen Fehler in der Berechnung der F Werte, wenn ich mich nicht irre. Mich wundert aber, dass nur in diesem Fall das auftritt. Andere Fälle habe ich nicht finden können. Daher die bitte an euch, ob ihr rausfindet woran genau es liegt. Denn wenn dieser Fehler (?) beseitigt ist, hätten wir einen 100%ig umgesetzten A*, den hier jeder gerne benutzen darf. Anwendungsbeispiele wären Browsergames, in denen Wege berechnet werden müssen.
Ich weiß das ganze ist nicht ganz toll geschrieben, aber so programmiere ich. Und er ist ja fast optimal. Beim letzten bisschen müsstet ihr mir nun helfen, damit er voll funktionsfähig ist. Vielen Dank. Ich hoffe ich kann einigen, die gerade an Browsergames basteln damit ein wenig helfen. Hier der Code von meinem astar:
<?php error_reporting(E_ALL); // ------------------------------------------- // V.1.0 // ------------------------------------------- // Allgemeines // G = Bisherige Wegkosten // C = Kosten Vorgängernode -> currentNode // H = Geschätzte Restkosten (Luftlinien Heuristik) // F = Gesamtkosten // VX = Bezeichnet die X-Koordinate des Vorgängernodes // VY = Bezeichnet die Y-Koordinate des Vorgängernodes // ------------------------------------------- class astar { private $x; private $y; private $openlist = array(); private $closedlist = array(); private $tx; private $ty; public function __construct($x,$y) { // $x = Anzahl Felder auf der X-Achse, $y = Anzahl Felder auf der Y-Achse $this->x = $x; $this->y = $y; // Hindernisse werden aus der Map-Klasse geholt und in die Closedlist eingefügt // Hier Hindernisse manuell einfügen, solange das noch nicht über die Construct Funktion geregelt wird array_push($this->closedlist,array("X" => 1, "Y" => 2)); array_push($this->closedlist,array("X" => 1, "Y" => 3)); array_push($this->closedlist,array("X" => 2, "Y" => 2)); array_push($this->closedlist,array("X" => 3, "Y" => 2)); array_push($this->closedlist,array("X" => 2, "Y" => 0)); array_push($this->closedlist,array("X" => 2, "Y" => 1)); } public function main($x,$y,$tx,$ty) { // Berechnet den Weg vom Start zum Zielnode // Vorbelegungen $Start = array(); $Start["X"] = $x; $Start["Y"] = $y; $Start["G"] = 0; $Start["VX"] = -1; $Start["VY"] = -1; $this->tx = $tx; $this->ty = $ty; // Ganz zu Anfang des Skriptes den Startnode in die Openlist einfügen array_push($this->openlist,$Start); do { // Die Openlist nach dem niedrigstem F-Wert sortieren usort($this->openlist,'Compare'); // Wenn der Aktuelle Node gleich dem Zielnode ist -> Weg gefunden $ActualNode = array("X" => $this->openlist[0]["X"],"Y" => $this->openlist[0]["Y"],"VX" => $this->openlist[0]["VX"],"VY" => $this->openlist[0]["VY"]); if($ActualNode["X"] == $this->tx && $ActualNode["Y"] == $this->ty) { array_push($this->closedlist,$ActualNode); $Way = $this->getWay(); return $Way; } else { // Wenn nicht, wird vom Punkt mit dem niedrigstem F-Wert weitergesucht $this->expandNode($ActualNode["X"],$ActualNode["Y"]); // Den fertig untersuchen Node auf die Closedlist setzen und aus der Openlist löschen array_push($this->closedlist,$ActualNode); unset($this->openlist[0]); } } // Bis die Openlist leer ist while(!empty($this->openlist)); // Ist die Openlist leer und es wurde nicht abgebrochen, existiert kein Weg return FALSE; } private function expandNode($x,$y) { // Expandiert den Node $i=0; $Successor = array(); $Successors = $this->getSuccessors($x,$y); foreach($Successors as $Index => $Current) { // Geht jeden Nachfolgenode einzeln durch array_push($Successor,$Current); if($i%2 != 0) { // Tritt nur jedes zweite mal in Kraft da immer erst BEIDE // Werte (X und Y Koordinate) $Successor hinzugefügt werden müssen // Überprüft, ob $Successor in der Closedlist ist $Inside = $this->inClosedList($Successor); if($Inside == TRUE) { // Wenn $Successor innerhalb der Closedlist ist, mache nichts außer $Successor zu leeren $Successor = array(); $i++; continue; } else { // F Wert von $Successor berechnen $g = 0; foreach($this->openlist as $Key) { // Holt den G Wert vom aktuellen Node if($x == $Key["X"] && $y == $Key["Y"]) { $g = $Key["G"]; break; } } switch($Index) { // Berechnet den C Wert zwischen aktuellem Node und Successor case "ol_y": $c = sqrt(2); break; case "om_y": $c = 1; break; case "or_y": $c = sqrt(2); break; case "ml_y": $c = 1; break; case "mr_y": $c = 1; break; case "ul_y": $c = sqrt(2); break; case "um_y": $c = 1; break; case "ur_y": $c = sqrt(2); break; } // Berechnet H Wert des Successors $XDifference = $Successor[0] - $this->tx; if($XDifference < 0) { $XDifference *= -1; } $YDifference = $Successor[1] - $this->ty; if($YDifference < 0) { $YDifference *= -1; } $h = sqrt($XDifference * $XDifference + $YDifference * $YDifference); // G, C und H Wert werden zum F Wert addiert $f = $g + $c + $h; $Exit = FALSE; for($n=0;$n<count($this->openlist);$n++) { if($Successor[0] == $this->openlist[$n]["X"] && $Successor[1] == $this->openlist[$n]["Y"]) { if($f > $this->openlist[$n]["F"]) { // Wenn Successor in der Openlist ist und der neue F Wert größer als // der alte F Wert ist, tue nichts $Exit = TRUE; } else { // Wenn Successor in der Openlist ist und der neue F Wert nicht größer als der // alte ist, den F Wert in der Openlist aktualisieren $this->openlist[$n]["F"] = $f; $Exit = TRUE; } break; } } if($Exit) { // Wenn der Successor bereits in der Openlist war und der F Wert falls nötig // aktualisiert wurde, $Successor leeren, $i inkrementieren und den Rest // des Schleifendurclaufes überspringen $Successor = array(); $i++; continue; } // War der Successor garnicht in der Openlist, füge ihn hinzu $NewNode = array("X" => $Successor[0],"Y" => $Successor[1],"F" => $f,"G" => ($g + $c),"VX" => $x,"VY" => $y); array_push($this->openlist,$NewNode); } // $Successor leeren, damit sich keine Werte überschneiden $Successor = array(); } $i++; } } private function getSuccessors($x,$y) { // Bestimmt alle Umgebungsnodes von $x,$y $Successors = array(); if(($x - 1 >= 0) && ($y + 1 <= $this->y)) { $Successors["ol_x"] = $x - 1; $Successors["ol_y"] = $y + 1; } if($y + 1 <= $this->y) { $Successors["om_x"] = $x; $Successors["om_y"] = $y + 1; } if(($x + 1 <= $this->x) && ($y + 1 <= $this->y)) { $Successors["or_x"] = $x + 1; $Successors["or_y"] = $y + 1; } if($x - 1 >= 0) { $Successors["ml_x"] = $x - 1; $Successors["ml_y"] = $y; } if($x + 1 <= $this->x) { $Successors["mr_x"] = $x + 1; $Successors["mr_y"] = $y; } if(($x - 1 >= 0) && ($y - 1 >= 0)) { $Successors["ul_x"] = $x - 1; $Successors["ul_y"] = $y - 1; } if($y - 1 >= 0) { $Successors["um_x"] = $x; $Successors["um_y"] = $y - 1; } if(($x + 1 <= $this->x) && ($y - 1 >= 0)) { $Successors["ur_x"] = $x + 1; $Successors["ur_y"] = $y - 1; } return $Successors; } private function inClosedlist($Successor) { // Überprüft, ob $Successor in der Closedlist vertreten ist $Inside = FALSE; for($j=0;$j<count($this->closedlist);$j++) { if($Successor[0] == $this->closedlist[$j]["X"] && $Successor[1] == $this->closedlist[$j]["Y"]) { $Inside = TRUE; } } return $Inside; } private function getWay() { // Berechnet aus $Closedlist den wirklichen Weg $Way = array(); array_push($Way,end($this->closedlist)); $Last = end($Way); do { foreach($this->closedlist as $Key) { if($Key["X"] == $Last["VX"] && $Key["Y"] == $Last["VY"]) { array_push($Way,$Key); break; } } $Last = end($Way); } while($Last["VX"] != -1 && $Last["VY"] != -1); $Way = array_reverse($Way); for($i=0;$i<count($Way);$i++) { // Debug Output - kommt später weg echo "Feld $i: " . $Way[$i]["X"] . "," . $Way[$i]["Y"] . "<br>"; } return $Way; } } function Compare($First, $Second) { // Vergleichsfunktion für das sortieren der Openlist if($First['F'] < $Second['F']) { return -1; } elseif($First['F'] > $Second['F']) { return 1; } else { return 0; } } $map = new astar(4,9); $map->main(4,0,0,2); ?>
Vielen Dank, ich hoffe ihr findet meinen Fehler . Hier noch die Wikipedia Erklärung: http://de.wikipedia.org/wiki/A_Stern Ich habe mich so gut es geht an die Namen in Wikipedia gehalten.
Yuzuke
Beitrag zuletzt geändert: 10.4.2010 22:30:09 von yuzuke -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Hi,
yuzuke schrieb:
Na dann schaun wir mal ;).
Vielen Dank, ich hoffe ihr findet meinen Fehler . Hier noch die Wikipedia Erklärung: http://de.wikipedia.org/wiki/A_Stern Ich habe mich so gut es geht an die Namen in Wikipedia gehalten.
Im Abschnitt
addierst du H zu F. Das macht keinen Sinn. H ist eigentlich nur gedacht, um die Auswahl des nächsten Knoten zu beeinflussen um die Chance zu haben, möglichst schnell die kürzeste Route zu finden. In die tatsächliche Weglänge fließt H nicht ein. Wenn Heuristik haben möchtest, müßtest du zu jedem Konten den H-Wert speichern und dann beim Sortieren der openlist bei gleichem F, den Knoten mit dem kleinsten H wählen. Die einfache Variante wäre aus dem oben genannten Code nur// Berechnet H Wert des Successors $XDifference = $Successor[0] - $this->tx; if($XDifference < 0) { $XDifference *= -1; } $YDifference = $Successor[1] - $this->ty; if($YDifference < 0) { $YDifference *= -1; } $h = sqrt($XDifference * $XDifference + $YDifference * $YDifference); // G, C und H Wert werden zum F Wert addiert $f = $g + $c + $h;
zu machen. Dass ist dann ohne Heuristik, quasi Brute-Force :)$f = $g + $c;
Ich habe es jetzt nicht bis ins letzte Detail geprüft, aber dein Beispiel funktioniert mit den beschriebenen Änderungen.
Gruß
Manni -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage