<?php

        class Astar

        {

            public $map;

            public $lignes;

            public $colonnes;

            public $liste_ouverte = array();

            public $liste_fermee = array();

            public $liste_chemin = array();

            public $start;

            public $end;

            

            public function __construct($map,$start,$end)

            {

                /* mise en place de la carte */

                $this->map = $map;

                $this->lignes = count($map);

                   $this->colonnes = count($map[0]);

                $tmpstart = explode("x",$start); $this->start = array('y' => $tmpstart[0], 'x' => $tmpstart[1], 'yx' => $start); unset($tmpstart);

                $tmpend = explode("x",$end); $this->end = array('y' => $tmpend[0], 'x' => $tmpend[1], 'yx' => $end); unset($tmpend);

                $this->map[$this->start['y']][$this->start['x']] = "D";

                $this->map[$this->end['y']][$this->end['x']] = "A";

                

                /* ajout du point de départ dans la liste ouvert et en tant que case courante */

                $this->liste_ouverte[$this->start['yx']] = array('node' => $this->start['yx'], 'parent' => 'n/c', 'g' => 0, 'h' => 0, 'f' => 9999);        

                $this->current = $this->start['yx'];

                

                /* boucle tant que l'arrivé n'a pas été atteinte */

                while(!isset($this->liste_fermee[$this->end['yx']]))

                {

                    $this->get_adjacent_node();

                    $this->get_next_node();

                }

                

                /* on parcours la liste fermee pour reconstituer le chemin */

                $parent = $this->end['yx'];

                while($parent!=$this->start['yx'])

                {

                    $parent = $this->liste_fermee[$parent]['parent'];

                    $this->liste_chemin[$parent] = 1;

                }    

                unset($this->liste_chemin[$this->start['yx']]);

            }



                private function get_adjacent_node()

                {

                    /* on explore les case adjacentes pour les ajouter ou non à la liste ouverte */

                    $node = explode("x",$this->current);

                    $y = $node[0];

                    $x = $node[1];

                    if($this->is_free($y-1,$x)) $this->add_node($y-1,$x,$y."x".$x); //case haut

                    if($this->is_free($y-1,$x+1,1)) $this->add_node($y-1,$x+1,$y."x".$x); //case haut droite

                    if($this->is_free($y,$x+1)) $this->add_node($y,$x+1,$y."x".$x); //case droite

                    if($this->is_free($y+1,$x+1,1)) $this->add_node($y+1,$x+1,$y."x".$x); //case bas droite

                    if($this->is_free($y+1,$x)) $this->add_node($y+1,$x,$y."x".$x); //case bas 

                    if($this->is_free($y+1,$x-1,1)) $this->add_node($y+1,$x-1,$y."x".$x); //case bas gauche

                    if($this->is_free($y,$x-1)) $this->add_node($y,$x-1,$y."x".$x); //case gauche

                    if($this->is_free($y-1,$x-1,1)) $this->add_node($y-1,$x-1,$y."x".$x); //case haut gauche

                }



                private function is_free($y,$x,$diag=null)

                {

                    /* on vérifie qu'on peut ajouter cette case dans la liste ouverte */

                    if(!isset($this->map[$y][$x])) return false; // si elle n'existe pas, impossible

                    elseif(isset($this->liste_ouverte[$y."x".$x])) return false; // si elle est déja en liste ouverte, impossible

                    elseif(isset($this->liste_fermee[$y."x".$x])) return false; // si elle est en liste fermée, impossible

                    elseif($this->map[$y][$x]==1) return false; // si c'est un mur, impossible

                    elseif(isset($this->map[$y+1][$x]) && $diag==1 && $this->map[$y+1][$x]==1) return false; // si c'est un accés en diagonale et collé à un mur, impossible

                    elseif(isset($this->map[$y-1][$x]) && $diag==1 && $this->map[$y-1][$x]==1) return false; // si c'est un accés en diagonale et collé à un mur, impossible

                    else return true;

                }

                

                private function add_node($y,$x,$parent)

                {

                    /* on calcule g,h et f pour la case et on l'ajoute à la liste ouverte */

                    $g = $this->get_g($y,$x,$parent);

                    $h = $this->get_h($y,$x);

                    $this->liste_ouverte[$y."x".$x] = array('node' => $y."x".$x, 'parent' => $parent, 'g' => $g, 'h' => $h, 'f' => $g + $h);

                }



                private function get_g($y,$x,$parent)

                {

                    /* on calcule le g de cette case en lui ajoutant celui de sa case parent */

                    $pt = explode("x",$parent);

                    $result = 0;

                    if($x==$pt[1] || $y==$pt[0]) $result += 10;

                    else  $result += 14;

                    $result += $this->liste_ouverte[$parent]['g'];

                    return $result;

                }

                

                private function get_h($y,$x)

                {

                    /* on calcule le nombre de case séparant cette case et celle d'arrivé, sans les diagonales */

                    $end = explode("x",$this->end['yx']);

                    return abs($x-$end[1])+abs($y-$end[0]);

                }

            

                private function get_next_node()

                {

                    $min = "1000"; $node = "";

                    /* on passe la case actuelle dans la liste fermée */

                    $this->liste_fermee[$this->current] = $this->liste_ouverte[$this->current];

                    /* on supprime la case actuelle de la liste ouverte */

                    unset($this->liste_ouverte[$this->current]);

                    /* on recherche la case ayant l'indice f le plus faible dans la liste ouverte */

                    foreach($this->liste_ouverte as $ouverte) { if($ouverte['f']<$min) { $node=$ouverte['node']; $min=$ouverte['f']; } }

                    $this->current = $node;

                    return $node;

                }

            

        }

?>