path.php

  1. <?php
  2. session_start();
  3. if(!empty($_GET['del'])) 
  4.    unset($_SESSION['murs']);
  5. if(!isset($_SESSION['murs']))
  6.    $_SESSION['murs'] = array();
  7. if(!empty($_GET['case'])){
  8.    if(in_array($_GET['case'], $_SESSION['murs'])){
  9.       unset($_SESSION['murs'][$_GET['case']]);
  10.    }
  11.    else 
  12.       $_SESSION['murs'][$_GET['case']] = $_GET['case'];
  13. }
  14. ?>
  15. <style>
  16. table{
  17.    border-collapse: collapse;
  18. }
  19. td{
  20.    font-size: 10px;
  21.    padding: 5px;
  22.    border: 1px solid black;
  23. }
  24. .depart{
  25.    background-color: #55F055;
  26. }
  27. .arrive{
  28.    background-color: #F05555;
  29. }
  30. .visite{
  31.    background-color: #5555F0;
  32. }
  33. .mur
  34. {
  35.    background-color: #AAAAAA;
  36. }
  37. </style>
  38. <?php
  39. set_time_limit(10);
  40.  
  41. function print_pre($array){
  42.    echo '<pre>';
  43.    print_r($array);
  44.    echo '</pre>';
  45. }
  46.  
  47. $resolu = FALSE;
  48. $largeur = 10;
  49. $hauteur = 10;
  50. $depart = 0;
  51. $arrivee = 99;
  52. $x_arr = $arrivee % $largeur;
  53. $y_arr = floor( $arrivee / $largeur);
  54. $cout_f_glob = array();
  55. $cout_h_glob = array();
  56. $cout_g_glob = array();
  57. $cout_g_glob[$depart] = 0;
  58. $parent= array();
  59.  
  60. $murs = $_SESSION['murs'];
  61.  
  62. $coordonnees = array();
  63. $liste_ouverte = array();
  64. $liste_fermee = array();
  65.  
  66. function voisines($case){
  67.    global $largeur, $hauteur;
  68.    
  69.    if($case == 0){
  70.       $voisines = array($case+1 => 100, $case+$largeur+1 => 141, $case+$largeur => 100);
  71.    }
  72.    elseif($case == $largeur-1){ //en haut a droite
  73.       $voisines = array($case+$largeur => 100, $case+$largeur-1 => 141, $case-1 =>  100);
  74.    }
  75.    elseif($case == ($hauteur - 1)* $largeur){ //en bas a gauche
  76.       $voisines = array($case+1 => 100, $case-$largeur => 100, $case-$largeur+1 => 141);
  77.    }
  78.    elseif($case == $hauteur * $largeur - 1){ //en bas a droite
  79.       $voisines = array($case-1 =>  100, $case-$largeur-1 => 141, $case-$largeur => 100);
  80.    }
  81.    elseif($case < $largeur){ //la ligne du haut
  82.       $voisines = array($case+1 => 100, $case+$largeur+1 => 141, $case+$largeur => 100, $case+$largeur-1 => 141, $case-1 =>  100);
  83.    }
  84.    elseif($case % $largeur == 0){ //la colonne de gauche
  85.       $voisines = array($case+1 => 100, $case+$largeur+1 => 141, $case+$largeur => 100, $case-$largeur => 100, $case-$largeur+1 => 141);
  86.    }
  87.    elseif($case % $largeur == $largeur-1){ //la colonne de droite
  88.       $voisines = array($case+$largeur => 100, $case+$largeur-1 => 141, $case-1 =>  100, $case-$largeur-1 => 141, $case-$largeur => 100);
  89.    }
  90.    elseif($case > ($hauteur-1) * $largeur){ //la ligne du bas
  91.       $voisines = array($case+1 => 100, $case-1 =>  100, $case-$largeur-1 => 141, $case-$largeur => 100, $case-$largeur+1 => 141);
  92.    }
  93.    else{ //tout ce qui n'est pas sur les bords
  94.       $voisines = array($case+1 => 100, $case+$largeur+1 => 141, $case+$largeur => 100, $case+$largeur-1 => 141, $case-1 =>  100, $case-$largeur-1 => 141, $case-$largeur => 100, $case-$largeur+1 => 141);
  95.    }
  96.    return $voisines;
  97. }
  98.  
  99. function cout_h($case){
  100.    global $largeur, $hauteur, $x_arr, $y_arr, $cout_h_glob;
  101.    $x = $case % $largeur;
  102.    $y = floor( $case / $largeur);
  103.    $cout_h = 100*sqrt(pow(($x_arr-$x), 2)+pow(($y_arr-$y), 2));
  104.    //$cout_h = 10*(abs($x-$x_arr)+abs($y-$y_arr));
  105.    $cout_h_glob[$case] = $cout_h;
  106.    return $cout_h;
  107. }
  108.  
  109. $liste_ouverte[] = $depart;
  110. $case_courante = $depart;
  111.  
  112. while($case_courante != $arrivee && !empty($liste_ouverte)){
  113.  
  114.    unset($liste_ouverte[$case_courante]);
  115.    unset($cout_f_glob[$case_courante]);
  116.  
  117.    foreach(voisines($case_courante) as $case => $cout_g){
  118.       if(!in_array($case, $murs) && !in_array($case, $liste_fermee)){
  119.          if(!in_array($case, $liste_ouverte)){
  120.             $liste_ouverte[$case] = $case;
  121.             $parent[$case] = $case_courante;
  122.             $cout_g_glob[$case] = $cout_g_glob[$case_courante] + $cout_g;
  123.             $cout_f_glob[$case] = $cout_g_glob[$case] + cout_h($case);
  124.          }
  125.          elseif(in_array($case, $liste_ouverte) && $cout_g_glob[$case] > $cout_g_glob[$case_courante] + $cout_g){
  126.             $cout_g_glob[$case] = $cout_g_glob[$case_courante] + $cout_g;
  127.             $cout_f_glob[$case] = $cout_g_glob[$case] + cout_h($case);
  128.             $liste_ouverte[$case] = $case;
  129.             $parent[$case] = $case_courante;
  130.          }
  131.       }
  132.    }
  133.    asort($cout_f_glob);
  134.    if(!empty($liste_ouverte)){
  135.       $case_courante = key($cout_f_glob);
  136.       $liste_fermee[$case_courante] = $case_courante;
  137.    }
  138. }
  139.  
  140. if($case_courante == $arrivee){
  141.    $resolu = TRUE;
  142.    $chemin = '';
  143.    while($case_courante != $depart){
  144.       $chemin = $case_courante.' => '.$chemin;
  145.       $case_courante = $parent[$case_courante];
  146.       $chemin_array[] = $case_courante;
  147.    }
  148. }
  149.  
  150. echo '<table>';
  151. for($i = 0; $i < $largeur; $i++){
  152.    echo '<tr>';
  153.    for($j = 0; $j < $hauteur; $j++){
  154.       $coordonnees[] = array($i, $j);
  155.       if(in_array((count($coordonnees)-1), $murs)) 
  156.          echo '<td class="mur"><a href="path.php?case='.(count($coordonnees)-1).'">'.(count($coordonnees)-1).'</a></td>';
  157.       elseif((count($coordonnees)-1) == $depart) 
  158.          echo '<td class="depart">'.(count($coordonnees)-1).'</td>';
  159.       elseif((count($coordonnees)-1) == $arrivee) 
  160.          echo '<td class="arrive">'.(count($coordonnees)-1).'</td>';
  161.       elseif($resolu && in_array((count($coordonnees)-1), $chemin_array)) 
  162.          echo '<td class="visite"><a href="path.php?case='.(count($coordonnees)-1).'">'.(count($coordonnees)-1).'</a></td>';
  163.       else 
  164.          echo '<td><a href="path.php?case='.(count($coordonnees)-1).'">'.(count($coordonnees)-1).'</a></td>';
  165.    }
  166.    echo '</tr>';
  167. }
  168. echo '</table>';
  169. echo '<a href="path.php?del=ok">Recommencer</a><br />';
  170. if($resolu) 
  171.    echo '<br /> Chemin le plus court : '.$chemin;
  172. else
  173.    echo '<br />Pas de chemin possible !';
  174. ?>
Retour