<?php
// Fonction d'exploration du graphe
// Parametres :
// $n = indice de la station en cours d'examen
// $mode = mode de transport utilise pour y arriver
// $GG et $PA = couts cumules
// $nbmax = nombre d'etapes autorisees
function explore ( $n, $mode, $GG, $PA, $nbmax ) {
global $tgv, $etapes, $trajets, $ggmax, $pamax ;
// On regarde si on n'a pas deja trouve un trajet a la fois plus rapide et moins cher
if ( ( isset ( $ggmax ) && $GG > $ggmax ) || ( isset ( $pamax ) && $PA > $pamax ) )
$optimise = false ;
else
$optimise = true ;
$trajet = reset ( $trajets ) ;
while ( $trajet && $optimise ) {
if ( $trajet['GG'] <= $GG && $trajet['PA'] <= $PA )
$optimise = false ;
$trajet = next ( $trajets ) ;
}
if ( $optimise ) {
// Inutile de mettre le point de depart parmi les etapes du trajet
if ( $n != 0 )
array_push ( $etapes, array ( 'n' => $n, 'mode' => $mode ) ) ;
// Si on est a l'arrivee, on vire les trajets plus chers et plus lents et on rajoute celui-la
if ( $n == 1 ) {
foreach ( array_keys ( $trajets ) as $i )
if ( $trajets[$i]['GG'] >= $GG && $trajets[$i]['PA'] >= $PA )
unset ( $trajets[$i] ) ;
array_push ( $trajets, array ( 'GG' => $GG, 'PA' => $PA, 'etapes' => $etapes ) ) ;
// Sinon, on continue d'explorer
} else {
$tgv[$n]['vue'] = true ;
foreach ( $tgv as $i => $station ) {
if ( ! $station['vue'] && ( $i == 1 || $nbmax > 1 ) ) {
$dh = max ( abs ( $station['x'] - $tgv[$n]['x'] ), abs ( $station['y'] - $tgv[$n]['y'] ) ) ;
$dv = abs ( $station['z'] - $tgv[$n]['z'] ) ;
// Etape a pied, sauf si on vient juste d'en faire une (en comptant +1PA parce que les stations sont souvent occupees)
if ( $mode != "D\xE9pl. \xC9cl." ) {
$dist = max ( $dh, $dv ) ;
$dPA = $dist / 0.9 + $dv + 1.0 ;
// Par la surface, on va parfois plus vite
if ( $dh + $station['z'] + $tgv[$n]['z'] > 0 ) {
$dPA_surface = ceil ( ( $dh - $tgv[$n]['z'] - $station['z'] ) / 2.0 ) / 0.9 - $tgv[$n]['z'] - $station['z'] + 2.0 ;
$dPA = min ( $dPA, $dPA_surface ) ;
}
explore ( $i, "D\xE9pl. \xC9cl.", $GG, $PA + $dPA, $nbmax - 1 ) ;
}
// Eventuellement on teste aussi l'etape en TGV
if ( isset ( $tgv[$n]['id'] ) && isset ( $station['id'] ) ) {
$dist_tgv = max ( $dh, $dv * 3 ) ;
// TGV demi-tarif, avec 1 DLA perdue a cause de la dispersion a l'arrivee
$dGG = ( int ) ceil ( $tgv[$n]['prix'] + $station['prix']
+ $tgv[$n]['coef'] * $station['coef'] * $dist_tgv * $dist_tgv / 4.0 ) ;
explore ( $i, "TGV \xBD-t.", $GG + $dGG, $PA + 12.0, $nbmax - 1 ) ;
// TGV plein tarif (action a 6 PA)
$dGG = ( int ) ceil ( $tgv[$n]['prix'] + $station['prix']
+ $tgv[$n]['coef'] * $station['coef'] * $dist_tgv * $dist_tgv / 2.0 ) ;
explore ( $i, "TGV pl. t.", $GG + $dGG, $PA + 6.0, $nbmax - 1 ) ;
}
}
}
$tgv[$n]['vue'] = false ;
}
if ( $n != 0 )
array_pop ( $etapes ) ;
}
} // function explore
// Recuperation des parametres
// x0, y0, z0 : coordonnees du point de depart
// x1, y1, z1 : coordonnees du point d'arrivee
// $ggmax, $pamax : nombre de GG et de PA qu'on n'est pas pret a depasser
// $nbmax : nombre maximum d'etapes
unset ( $x0, $y0, $z0, $x1, $y1, $z1, $ggmax, $pamax) ;
if ( is_numeric ( $_REQUEST['x0'] ) )
$x0 = ( int ) $_REQUEST['x0'] ;
if ( is_numeric ( $_REQUEST['y0'] ) )
$y0 = ( int ) $_REQUEST['y0'] ;
if ( is_numeric ( $_REQUEST['z0'] ) )
$z0 = ( int ) $_REQUEST['z0'] ;
if ( is_numeric ( $_REQUEST['x1'] ) )
$x1 = ( int ) $_REQUEST['x1'] ;
if ( is_numeric ( $_REQUEST['y1'] ) )
$y1 = ( int ) $_REQUEST['y1'] ;
if ( is_numeric ( $_REQUEST['z1'] ) )
$z1 = ( int ) $_REQUEST['z1'] ;
if ( is_numeric ( $_REQUEST['ggmax'] ) )
$ggmax = ( int ) $_REQUEST['ggmax'] ;
if ( is_numeric ( $_REQUEST['pamax'] ) )
$pamax = ( int ) $_REQUEST['pamax'] ;
if ( is_numeric ( $_REQUEST['nbmax'] ) )
$nbmax = ( int ) $_REQUEST['nbmax'] ;
else
$nbmax = 2 ;
// En-tete HTML
echo "<!DOCTYPE html PUBLIC \"-//W3C//DTD XHTML 1.0 Strict//EN\" \"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd\">\n" ;
echo "<html xmlns=\"http://www.w3.org/1999/xhtml\">\n" ;
echo " <head>\n" ;
echo " <meta http-equiv=\"content-type\" content=\"text/html;charset=windows-1252\" />\n" ;
echo " <link rel=\"icon\" href=\"favicon.ico\" />\n" ;
echo " <title>MountyHall - Agence de voyage Tr\xF5llesque</title>\n" ;
echo " <style type=\"text/css\">\n" ;
echo " img {\n" ;
echo " border:none;\n" ;
echo " width:12px;\n" ;
echo " height:12px;\n" ;
echo " }\n" ;
echo " </style>\n" ;
echo " </head>\n" ;
echo " <body>\n" ;
// Formulaire
echo " <form action=\"" . basename ( $_SERVER['SCRIPT_NAME'] ) . "\" method=\"post\">\n" ;
echo " <p>\n" ;
echo " De <span title=\"Coordonn\xE9es du point de d\xE9part\">(<input type=\"text\" name=\"x0\" size=\"3\"" ;
if ( isset ( $x0 ) )
echo " value=\"{$x0}\"" ;
echo " />, <input type=\"text\" name=\"y0\" size=\"3\"" ;
if ( isset ( $y0 ) )
echo " value=\"{$y0}\"" ;
echo " />, <input type=\"text\" name=\"z0\" size=\"3\"" ;
if ( isset ( $z0 ) )
echo " value=\"{$z0}\"" ;
echo " />)</span>\n" ;
echo " \xE0 <span title=\"Coordonn\xE9es du point d'arriv\xE9e\"> (<input type=\"text\" name=\"x1\" size=\"3\"" ;
if ( isset ( $x1 ) )
echo " value=\"{$x1}\"" ;
echo " />, <input type=\"text\" name=\"y1\" size=\"3\"" ;
if ( isset ( $y1 ) )
echo " value=\"{$y1}\"" ;
echo " />, <input type=\"text\" name=\"z1\" size=\"3\"" ;
if ( isset ( $z1 ) )
echo " value=\"{$z1}\"" ;
echo " />)</span>,\n" ;
echo " en pas plus de <input type=\"text\" name=\"nbmax\" size=\"1\" value=\"{$nbmax}\"" ;
echo " title=\"nombre d'\xE9tapes\" /> \xE9tape(s),\n" ;
echo " et avec GG'≤<input type=\"text\" name=\"ggmax\" size=\"4\"" ;
if ( isset ( $ggmax ) )
echo " value=\"{$ggmax}\"" ;
echo " title=\"prix total en GG' (laisser vide pour aucune limite)\" />\n" ;
echo " et PA≤<input type=\"text\" name=\"pamax\" size=\"2\"" ;
if ( isset ( $pamax ) )
echo " value=\"{$pamax}\"" ;
echo " title=\"dur\xE9e totale en PA (laisser vide pour aucune limite)\" />.\n" ;
echo " <input type=\"submit\" value=\"Et qu'\xE7a saute !\" title=\"Lancer la recherche\" />\n" ;
echo " </p>\n" ;
echo " </form>\n" ;
echo " <hr />\n" ;
// Le cas echeant, liste des trajets calcules
if ( $x0 != $x1 || $y0 != $y1 || $z0 != $z1 ) {
// Liste des stations de TGV
$fichier = "ftp://ftp.mountyhall.com/Public_StationsTGV.txt" ;
if ( $flux = @fopen ( $fichier, 'rt' ) ) {
$tgv = array ( ) ;
while ( $ligne = fgets ( $flux ) ) {
$champs = explode ( ";", $ligne, 7 ) ;
array_push ( $tgv, array ( 'id' => ( int ) $champs[0],
'x' => ( int ) $champs[1],
'y' => ( int ) $champs[2],
'z' => ( int ) $champs[3],
'prix' => ( int ) $champs[4],
'coef' => ( float ) $champs[5],
'nom' => preg_replace ( "/;[^;]*$/", "", $champs[6] ),
'vue' => false ) ) ;
}
fclose ( $flux ) ;
// Si les etremites sont des stations TGV, on les extrait de la liste
$dep = NULL ;
$arr = NULL ;
foreach ( array_keys ( $tgv ) as $n ) {
if ( $tgv[$n]['x'] == $x0 && $tgv[$n]['y'] == $y0 && $tgv[$n]['z'] == $z0 ) {
$dep = $tgv[$n] ;
unset ( $tgv[$n] ) ;
} elseif ( $tgv[$n]['x'] == $x1 && $tgv[$n]['y'] == $y1 && $tgv[$n]['z'] == $z1 ) {
$arr = $tgv[$n] ;
unset ( $tgv[$n] ) ;
}
}
// Sinon, on en cree de toutes pieces
if ( ! $dep )
$dep = array ( 'x' => $x0,
'y' => $y0,
'z' => $z0,
'nom' => "d\xE9part",
'vue' => false ) ;
if ( ! $arr )
$arr = array ( 'x' => $x1,
'y' => $y1,
'z' => $z1,
'nom' => "arriv\xE9e",
'vue' => false ) ;
// et on (re)place le depart et l'arrivee au debut de la liste, pour essayer d'optimiser le parcours du graphe
array_unshift ( $tgv, $arr ) ;
array_unshift ( $tgv, $dep ) ;
// Recherche des trajets
$etapes = array ( ) ;
$trajets = array ( ) ;
explore ( 0, "", 0, .0, $nbmax ) ;
// Tri des trajets par ordre decroissant de GG
$col_gg = array ( ) ;
foreach ( $trajets as $i => $trajet )
$col_gg[$i] = $trajet['GG'] ;
array_multisort ( $col_gg, SORT_DESC, SORT_NUMERIC, $trajets ) ;
// Affichage des trajets trouves
echo " <table rules=\"groups\">\n" ;
echo " <colgroup span=\"2\"></colgroup>\n" ;
echo " <colgroup span=\"2\"></colgroup>\n" ;
echo " <colgroup span=\"7\"></colgroup>\n" ;
echo " <thead>\n" ;
echo " <tr>\n" ;
echo " <th colspan=\"2\">Prix</th>\n" ;
echo " <th colspan=\"2\">Dur\xE9e</th>\n" ;
echo " <th colspan=\"7\">\xC9tapes</th>\n" ;
echo " </tr>\n" ;
echo " </thead>\n" ;
foreach ( $trajets as $trajet ) {
echo " <tbody>\n" ;
echo " <tr>\n" ;
echo " <td rowspan=\"" . count ( $trajet['etapes'] ) . "\" align=\"right\">{$trajet['GG']}</td>\n" ;
echo " <td rowspan=\"" . count ( $trajet['etapes'] ) . "\">GG</td>\n" ;
echo " <td rowspan=\"" . count ( $trajet['etapes'] ) . "\" align=\"right\">" ;
echo round ( $trajet['PA'], 1 ) . "</td>\n" ;
echo " <td rowspan=\"" . count ( $trajet['etapes'] ) . "\">PA</td>\n" ;
$etape = reset ( $trajet['etapes'] ) ;
$station = $tgv[$etape['n']] ;
echo " <td>{$etape['mode']}</td>\n" ;
echo " <td>⇒ {$station['nom']}" ;
if ( isset ( $station['id'] ) )
echo " ({$station['id']})" ;
echo "</td>\n" ;
echo " <td>(</td>\n" ;
echo " <td align=\"right\">{$station['x']},</td>\n" ;
echo " <td align=\"right\">{$station['y']},</td>\n" ;
echo " <td align=\"right\">{$station['z']})</td>\n" ;
echo " <td>\n" ;
echo " <a href=\"http://outilsrm.kathryl.net/cockpit.php?cX={$station['x']}&cY={$station['y']}" ;
echo "&cZ={$station['z']}\" title=\"Centrer sur la Vue2d\">\n" ;
echo " <img src=\"puce_vue2d.gif\" alt=\"puce_vue2d.gif\" />\n" ;
echo " </a>\n" ;
echo " </td>\n" ;
echo " </tr>\n" ;
while ( $etape = next ( $trajet['etapes'] ) ) {
echo " <tr>\n" ;
echo " <td>{$etape['mode']}</td>\n" ;
$station = $tgv[$etape['n']] ;
echo " <td>⇒ {$station['nom']}" ;
if ( isset ( $station['id'] ) )
echo " ({$station['id']})" ;
echo "</td>\n" ;
echo " <td>(</td>\n" ;
echo " <td align=\"right\">{$station['x']},</td>\n" ;
echo " <td align=\"right\">{$station['y']},</td>\n" ;
echo " <td align=\"right\">{$station['z']})</td>\n" ;
echo " <td>\n" ;
echo " <a href=\"http://outilsrm.kathryl.net/cockpit.php?cX={$station['x']}&cY={$station['y']}" ;
echo "&cZ={$station['z']}\" title=\"Centrer sur la Vue2d\">\n" ;
echo " <img src=\"puce_vue2d.gif\" alt=\"puce_vue2d.gif\" />\n" ;
echo " </a>\n" ;
echo " </td>\n" ;
echo " </tr>\n" ;
}
echo " </tbody>\n" ;
} // foreach ( $trajets...
echo " </table>\n" ;
} else // fopen
echo " <p>Impossible d'ouvrir <code>{$fichier}</code></p>\n" ;
echo " <hr />\n" ;
}
echo " <p>Et comme je n'ai d\xE9cid\xE9ment honte de rien, voil\xE0" ;
echo " <a href=\"source.php\" title=\"tgv.php\">le source du bidule</a>.</p>\n" ;
echo " </body>\n" ;
echo "</html>\n" ;
?>