Beiträge von Dezfafara

<?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();


?>

<?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;
   }
 }


?>