Намиране на най-кратък път – ИГРА

Автор: lortnoc

Урок за малко напреднали !!

В този урок ще ви покажа, как се намира най-кратък път от даден връх до всички останали в ориентиран граф с неотрицателни тегла на ребрата. Реализирал съм алгоритъма на Дейкстра, с модификации и притеглен матричен граф. Няма да обеснявам на дълго и широко, който си разбира ще го разбере … Може да се използва за направа на игри и т.н.

<?PHP
class path {

private $visited = array();
private $distance = array();
private $prev = array();
private $start = null;
private $map = array();
private $inf = 0;
private $nodes = 0;
private $best = 0;

public function __construct(&$map) {
$this -> inf = WALK;
$this -> map = &$map;
$this -> nodes = sizeof($map);
$this -> best = 0;
}

public function find($start, $to = null) {
$this->start = $start;
for ($i=0; $i<$this->nodes; $i++) {
if ($i == $this->start) {
$this->visited[$i] = true;
$this->distance[$i] = 0;
} else {
$this->visited[$i] = false;
$this->distance[$i] = isset($this->map[$this->start][$i])
? $this->map[$this->start][$i]
: $this->inf;
}
$this->prev[$i] = $this->start;
}
$max = $this->nodes;
$tries = 0;
while (in_array(false,$this->visited,true) && $tries <= $max) {
$this->best = $this->fBest($this->distance, array_keys($this->visited, false, true));
if($to !== null && $this->best === $to) {
break;
}
$this->update($this->best);
$this->visited[$this->best] = true;
$tries++;
}
}

private function fBest($distance, $left) {
$best = $this -> inf;
$best2 = 0;
$rand = 0;
if(IS_RAND_PATH) {
$rand = mt_rand(1,1000);
}
for ($i = 0,$m=sizeof($left); $i < $m; $i++) {
if($rand < 500) {
if($distance[$left[$i> < $best) {
$best = $distance[$left[$i>;
$best2 = $left[$i];
}
} else {
if($distance[$left[$i> <= $best) {
$best = $distance[$left[$i>;
$best2 = $left[$i];
}
}
}
return $best2;
}

private function update($o) {
for ($i=0;$i<$this -> nodes;$i++) {
if((isset($this->map[$o][$i]))
&& (!($this->map[$o][$i] == $this->inf) || ($this->map[$o][$i] == 0 ))
&& (($this->distance[$o] + $this->map[$o][$i]) < $this->distance[$i])
)
{
$this->distance[$i] = $this->distance[$o] + $this->map[$o][$i];
$this->prev[$i] = $o;
}
}
}

public function construct($to = null) {
$path = array();
for ($i = 0; $i < $this->nodes; $i++) {
if($to !== null && $to !== $i) {
continue;
}
$path[$i] = array();
$end = null;
$current = $i;
$path[$i][] = $i;
while ($end === null || $end != $this->start) {
$path[$i][] = $this->prev[$current];
$end = $this->prev[$current];
$current = $this->prev[$current];
}
$path[$i] = array_reverse($path[$i]);
if ($to === null || $to === $i) {
if($this->distance[$i] >= $this->inf) {
if ($to === $i) {
return "нестава !!!";
break;
}
}
if ($to === $i) {
return $path[$i];
break;
}
}
}
return $path;
}
}
//функция за построяване на графа
function fillGraphMatrix($per, $max, $no) {
$map = array();
$coord = array();
for ($i = 1; $i <= $max; $i++) {
if(!in_array($i, $no)) {
$left = (($i - 1) < 0) || (($i - 1) % $per == 0) ? 0 : $i - 1;
$right = ($i % $per == 0) ? 0 : $i + 1;
$top = ($i - $per) < 0 ? 0 : ($i - $per);
$bottom = ($i + $per) > $max ? 0 : ($i + $per);
if($left) {$coord[] = array($i, $left, in_array($left, $no) ? WALK : T);}
if($right) {$coord[] = array($i, $right, in_array($right, $no) ? WALK : T);}
if($top) {$coord[] = array($i, $top, in_array($top, $no) ? WALK : T);}
if($bottom) {$coord[] = array($i, $bottom, in_array($bottom, $no) ? WALK : T);}
}
}

for ($i=0,$m=sizeof($coord); $i<$m; $i++) {
$x = $coord[$i][0];
$y = $coord[$i][1];
$c = $coord[$i][2];
$map[$x][$y] = $c;
$map[$y][$x] = $c;
}

for ($i=0; $i < $max; $i++) {
for ($k=0; $k < $max; $k++) {
if ($i == $k) $map[$i][$k] = 0;
}
}
return $map;
}


//Общо взето се използва така ->

//бекрайно тегло
define('WALK', 1000);
//тегла
define('T', 5);
//откриване на произволни пътища
define('IS_RAND_PATH', false);

//разни неща за формата
$start = !isset($_POST['from']) ? 0 : (int)$_POST['from'];
$end = !isset($_POST['to']) ? 0 : (int)$_POST['to'];
//полета през където неможе да се минава
$no = array(6,9,23,45,67,34,98,23,56,57,58,32,35,74,75,84,73,94);
//по колко на ред
$per = 10;
//общо колко
$max = 100;
//стройм графа -> направил съм го свързан ляво, дясно, горе, долу, но не и подиагонал
$map = fillGraphMatrix($per, $max, $no);
//създаваме обект от нашия клас
$path = new path($map);
//намираме пътя от старт точка до край друга
$path->find($start, $end);
//извличаме пътя
$path = $path->construct($end);

//визуализация
header('Content-Type: text/html; charset=windows-1251');

?>
<form action="" method="POST">
Намери път от <input type="text" name="from" size="5" value="<?=$_POST['from'];?>"> до ->
<input type="text" name="to" size="5" value="<?=$_POST['to'];?>">
<input type="submit" name="findpath" value="изчертай">
</form><br>
<?

echo '<table><tr><td valign="top"><table bgcolor="#cccccc" border="0" cellpadding="0" cellspacing="1"><tr>';
for ($i = 0, $p = 1; $i < $max; $i++) {
if($i && ($i % $per == 0)) {
echo '</tr><tr>';
}
$tile = $p;
$color = '';
if(is_array($path) && in_array($p, $path)) {
$color = 'background-color: red;';
}
if(in_array($p, $no)) {
echo '<td style="font-family: Verdana; font-size: 10px; width:32px; height:32px;" bgcolor="gray" align="center">' . $tile . '</td>';
} else {
echo '<td style="'.$color.' font-family: Verdana; font-size: 10px; width:32px; height:32px;" bgcolor="white" align="center">' . $tile . '</td>';
}
$p++;
}
echo '</tr></table></td><td valign="top">';
if($start && $end) {
echo "Дебъг: ";
echo "<pre>"; print_r($path); echo "</pre>";
}
echo '</td></tr></table>';
?>

Дано съм бил полезен !