File Mordruga
   |
Posted - 2007.11.17 14:48:00 -
[1]
Edited by: File Mordruga on 17/11/2007 15:01:42
<?php
$jumps = array();
$cnx = odbc_connect ("evedb", "sauser", "sapassword") or die ();
$rst = odbc_exec($cnx, <<<SQL
SELECT fromSolarSystemID, toSolarSystemID
FROM mapSolarSystemJumps
SQL
);
while (odbc_fetch_row($rst))
$jumps[odbc_result($rst, "fromSolarSystemID")][] = odbc_result($rst, "toSolarSystemID");
odbc_free_result($rst);
function calcRoute($a, $b) {
global $jumps;
if ($a === $b) { # same solarSystem, don't calc
return array($a);
}
$openList = array(); # solarSystems yet to be parsed
$closeList = array(); # solarSystems already parsed
$openList["_$b"] = array($b, 0, 0); # (solarSystem, g, parent)
$found = false;
while (($i = array_shift($openList)) !== NULL) { # $i - current solarSystem
$ns = $jumps[$i[0]]; # neighbours (1 jump away from $i)
while (($n = array_shift($ns)) !== NULL) {
if ($n == $a) { # found the destination
$found = true;
$closeList[$a] = array(0, $i[0]); # [solarSystem] = (g, parent)
$ns = array();
$openList = array();
} elseif (!array_key_exists($n, $closeList) && !array_key_exists("_$n", $openList)) {
$openList["_$n"] = array($n, $i[1]+1, $i[0]); # add the neighbour to openList
} # else repeated solarSystem (already parsed)
}
$closeList[$i[0]] = array($i[1], $i[2]); # parsed the solarSystem
}
if ($found) {
$i = $a;
while ($i !== 0) { # parent = 0 <=> null parent
$route[] = $i;
$i = $closeList[$i][1];
}
return $route;
}
return null;
}
function calcNumberJumps($a, $b) {
global $jumps;
if ($a === $b) { # same solarSystem, don't calc
return 0;
}
$openList = array(); # solarSystems yet to be parsed
$closeList = array(); # solarSystems already parsed
$openList["_$b"] = array($b, 0, 0); # (solarSystem, g, parent)
$found = false;
while (($i = array_shift($openList)) !== NULL) { # $i - current solarSystem
$ns = $jumps[$i[0]]; # neighbours (1 jump away from $i)
while (($n = array_shift($ns)) !== NULL) {
if ($n == $a) { # found the destination
$found = true;
$closeList[$a] = array(0, $i[0]); # [solarSystem] = (g, parent)
$ns = array();
$openList = array();
} elseif (!array_key_exists($n, $closeList) && !array_key_exists("_$n", $openList)) {
$openList["_$n"] = array($n, $i[1]+1, $i[0]); # add the neighbour to openList
} # else repeated solarSystem (already parsed)
}
$closeList[$i[0]] = array($i[1], $i[2]); # parsed the solarSystem
}
if ($found) {
$c = 0;
$i = $a;
while ($i !== 0) { # parent = 0 <=> null parent
$route[] = $i;
$i = $closeList[$i][1];
$c++;
}
return $c-1;
}
return -1;
}
print_r(calcRoute(30000142,30002791));
echo (calcNumberJumps(30000142,30002791)."\n");
?> |