A*-Algorithmus in php

Dezfafara · 26. September 2011

Huhu stagetwo,

nach mind. 3 Schateln kippen hab ich hier meine erste funktionierende Version des A*-Algorithmus in php. Vielleicht kanns ja mal iwer gebrauchen.

Kritik, verbesserungs Vorschläge und änliches sind gern gesehen.

astar.class.php

Spoiler anzeigen

PHP

<?php
//==========================================================================================================================
//======= A*-Algorithmus by Dez === for more informations take a look at http://de.wikipedia.org/wiki/A*-Algorithmus =======
//==========================================================================================================================
error_reporting(E_ALL);
//Klasse point einfügen
require_once('point.class.php');
class astar
{
private $start_point; //Startknoten
private $goal_point; //Zielknoten
private $current_point; //Knoten der momentan bearbeitet wird
private $current_point_index; //ID in des momentanen Knotens in der Openlist
private $closed_list = array(); //Liste der Knoten zu denen bis jetzt ALLE Wege bekannt sind
private $open_list = array(); //Liste der Knoten zu denen EIN Weg bekannt ist
private $zx; //X-Position des Zielknotens
private $zy; //Y-Position des Zielknotens
public function __construct($sx, $sy, $zx, $zy)
{
//Start Koordinaten sx,sy + Ziel Koordinaten zx,zy
$this->zx = $zx;
$this->zy = $zy;
//Start- und Zielknoten erstellen inkl. Heuristik (hier Luftlinie)
$this->goal_point = new point($zx, $zy, 1, null, $zx, $zy);
$this->start_point = new point($sx, $sy, 0, null, $zx, $zy);
//Rahmen der Karte(10*10 Feld) in die closedlist einfügen
for($i = 0; $i <= 11; $i++)
{
array_push($this->closed_list, new point($i, 0, 99, null, $zx, $zy));
array_push($this->closed_list, new point($i, 11, 99, null, $zx, $zy));
array_push($this->closed_list, new point(0, $i, 99, null, $zx, $zy));
array_push($this->closed_list, new point(11, $i, 99, null, $zx, $zy));
}
}
private function main()
{
//Startknoten in die openlist einfügen
array_push($this->open_list, $this->start_point);
do
{
//Speichert den Knoten mit dem geringsten f-Wert in der current_point
$this->get_the_point_with_the_smallest_f();
//Prüfen ob der momentane Knoten gleich dem Zielknoten ist
if($this->current_point->get_x() == $this->goal_point->get_x() && $this->current_point->get_x() == $this->goal_point->get_x())
{
//Dem Zielknoten den momentanen Knoten als Vorgänger zuweisen
$this->goal_point->set_antecessor($this->current_point);
//Methode beenden
return true;
}
else
{
//Nachbarn des momentanen Knotens ermitteln
//hier wird direkt geprüft ob die Nachfolgeknoten bereits in der openlist bzw. in der closedlist sind
//und werden dementsprechend verarbeitet
$this->get_neighbours($this->current_point->get_x(), $this->current_point->get_y(), $this->current_point);
//der momentane Knoten wird der closedlist hinzugefügt und von der openlist gestrichen
array_push($this->closed_list, $this->current_point);
unset($this->open_list[$this->current_point_index]);
}
}while(!empty($this->open_list)); //Solange wie es Knoten in der openlist gibt
//Die openlist ist leer und das Ziel wurde nicht erreicht
return false;
}
private function get_the_point_with_the_smallest_f()
{
$this->current_point_index = 0;
$count = 0;
//openlist neu sortieren da unset() "Löcher" in der openlist hinterlässt die die foreach-Schleife zwar ignoriert
//aber der Index "current_point_index" nicht mehr passt, da die "Löcher" immer noch im Array sind.
sort($this->open_list);
//Der momentane Knoten ist der erstbeste aus der openlist
$this->current_point = $this->open_list[0];
//Die openlist durchlaufen und schauen ob es einen Knoten gibt der einen kleineren f-Wert hat als der momentane
foreach($this->open_list as $point)
{
if($point->get_f() < $this->current_point->get_f())
{
//Ist der f-Wert kleiner ist der Knoten der neue momentane Knoten, "current_point_index" enthält die Stelle
//des Knotens in der openlist
$this->current_point = $point;
$this->current_point_index = $count;
}
$count++;
}
}
private function is_in_closed_list($list_of_potential_points)
{
$count = 0;
//Für jeden möglichen Nachbarn schauen ob dieser in der closed- oder openlist enthalten ist und entsprechend behandeln
foreach($list_of_potential_points as $potential_point)
{
foreach($this->closed_list as $closed_list_point)
{
//Ist der Nachbarknoten auf der closedlist wird er als möglicher Nachbar gestrichen
if($closed_list_point->get_x() == $potential_point->get_x() && $closed_list_point->get_y() == $potential_point->get_y())
{
unset($list_of_potential_points[$count]);
break;
}
}
foreach($this->open_list as $open_list_point)
{
if($open_list_point->get_x() == $potential_point->get_x() && $open_list_point->get_y() == $potential_point->get_y())
{
//Ist der Nachbarknoten bereits auf der openlist und...
if($open_list_point->get_f() < $potential_point->get_f())
{
//.. der f-Wert größer als der in der openlist, ist der weg zu diesem Knoten länger als der alte.
//Der Knoten wird als möglicher Nachbar gestrichen
unset($list_of_potential_points[$count]);
break;
}
else
{
//.. der f-Wert kleiner als der in der openlist, ist der weg zu diesem Knoten kürzer als der alte.
//Der Knoten in der openlist bekommt nun einen neuen Vorgängerknoten mit dem entsprechendem f-Wert
//und wird als möglicher Nachbar gestrichen
$open_list_point->set_f($potential_point->get_g() + $open_list_point->get_c() + $open_list_point->get_h());
$open_list_point->set_antecessor($potential_point->get_antecessor());
unset($list_of_potential_points[$count]);
break;
}
}
}
$count++;
}
//Alle übrigen Nachbarknoten werden in die openlist geschrieben
foreach($list_of_potential_points as $potential_point)
{
array_push($this->open_list, $potential_point);
}
}
private function get_neighbours($x, $y, $antecessor)
{
$list_of_potential_points = array(); //Liste aller Nachbarn, die aber noch auf ihre Existenz in der
//closedlist überprüft werden müssen
//Über dem aktuellen Knoten
array_push($list_of_potential_points, new point($x, $y - 1, 1, $antecessor, null, $this->zx, $this->zy));
//Links neben dem aktuellen Knoten
array_push($list_of_potential_points, new point($x - 1, $y, 1, $antecessor, null, $this->zx, $this->zy));
//Rechts neben dem aktuellen Knoten
array_push($list_of_potential_points, new point($x + 1, $y, 1, $antecessor, null, $this->zx, $this->zy));
//Unter dem aktuellen Knoten
array_push($list_of_potential_points, new point($x, $y + 1, 1, $antecessor, null, $this->zx, $this->zy));
//Die Nachbarn zur Üperprüfung weitergeben.
$this->is_in_closed_list($list_of_potential_points);
}
public function show_the_way()
{
if($this->main())
{
$way = array();
do
{
array_push($way,$this->current_point);
$this->current_point = $this->current_point->get_antecessor();
}while(!is_null($this->current_point->get_antecessor()));
array_push($way,$this->current_point);
$way = array_reverse($way);
foreach($way as $point)
{
echo $point->get_x().":".$point->get_y()."<br>";
}
}
else
{
return "Sorry. I can`t get over there :(";
}
}
}
$way = new Astar(1,1,5,5);
$way->show_the_way();
?>

Alles anzeigen

point.class.php

Spoiler anzeigen

PHP

<?php
error_reporting(E_ALL);
class point
{
private $x; //X-Position des Knotens
private $y; //Y-Position des Knotens
private $c; //Kosten dieses Feld zu Betreten
private $h; //Geschätze Kosten zum Ziel
private $f; //f-Wert dieses Knotens
private $g; //Kosten bis zum Startknoten
private $antecessor; //Vorgänger Knoten
private $zx; //X-Position des Zielknotens
private $zy; //Y-Position des Zielknotens
public function __construct($x, $y, $c, $antecessor = null, $zx, $zy)
{
//Koordinaten und Kosten dieses Punktes
$this->x = $x;
$this->y = $y;
$this->c = $c;
$this->zx = $zx;
$this->zy = $zy;
//Falls ein Vorgängerknoten übergeben wurde, diesen als selbigen eintragen
if(!is_null($antecessor))
{
$this->antecessor = $antecessor;
}
//den geschätzen Weg zum Ziel berechnen (hier Luftlinie)
$this->set_h();
//den g-Wert berechnen (Kosten von diesem Punkt bis zum Startpunkt über die Vorgängerpunkte)
$this->set_g();
//den f-Wert berechnen (falls vorhanden Kosten des Vorgängerknotens bis zum Startpunkt + Kosten dieses Knotens
//+ geschätze Kosten zum Ziel)
$this->set_f();
}
public function get_x()
{
return $this->x;
}
public function set_x($x)
{
$this->x = $x;
}
public function get_y()
{
return $this->y;
}
public function set_y($y)
{
$this->y = $y;
}
public function get_c()
{
return $this->c;
}
public function set_c($c)
{
$this->c = $c;
}
public function get_h()
{
return $this->h;
}
public function set_h()
{
$this->h = sqrt(pow(abs($this->x - $this->zx), 2) + pow(abs($this->y - $this->zy), 2));
}
public function get_f()
{
return $this->f;
}
public function set_f($f = null)
{
if(!is_null($f))
{
$this->f = $f;
}
else
{
$this->f = $this->get_g() + $this->get_c() + $this->get_h();
}
}
public function get_g()
{
return $this->c;
}
public function set_g()
{
if(is_null($this->get_antecessor()))
{
$this->g = 0;
}
else
{
$this->g += $this->antecessor->get_g();
}
}
public function get_antecessor()
{
return $this->antecessor;
}
public function set_antecessor($antecessor)
{
$this->antecessor = $antecessor;
}
}
?>

Alles anzeigen

FragSalat · 26. September 2011

sieht ja scfhonma nice aus....

obs auch wirklich den kürzsten weg zum zielknoten findet ist noch offen aber es ist sauber und könnte funzen^^

wie kams das du den algo gecodet hast?

MfG Sick^

Dezfafara · 26. September 2011

ich habs selber nur mit 2 paaren getestet also alles ohne gewähr .. aber die beiden passten

hab iwas gesucht um ein wenig oop in php zu üben.. ich weiß auch nicht ob das mit der 2ten klasse für die knoten eine resourcen arme methode ist aber für meine zwecke wars so das beste

danke für das lob an die optik

FragSalat · 26. September 2011

ja bei sonem kleinem code ist das wohl wille wie man das macht aber ehrlich gesagt weiß ich auch nicht genau wie man da ressourcen sparen kann^^

Teilen