A star algorithm translate

Ask about general coding issues or problems here.

Moderators: macek, egami, gesf

dcdb723
New php-forum User
New php-forum User
Posts: 1
Joined: Thu Oct 11, 2012 9:45 pm

A star algorithm translate

Postby dcdb723 » Thu Oct 11, 2012 9:57 pm

Hi guys, can anyone help me switch Dijkstra algorithm to A star algorithm for this way finding?
I'll post both Dijkstra and A star algorithm, but I'm not sure if the code of A star algorithm is suitable for this. Hope you guys can provide some better A star code. Thanks a lottttttt!!!!!!!!

-----------------------------------astar.php------------------------------------
<?php
class AStar
{
const HV_COST = 10;
const D_COST = 14;
const ALLOW_DIAGONAL = true;
const ALLOW_DIAGONAL_CORNERING = false;

private $map = array();
private $startX, $startY, $endX, $endY;
public $shortestPath = array();

private $openList = array(), $closedList = array();

public function __construct($map, $startX, $startY, $endX, $endY)
{
$this->map = $map;

$this->startX = $startX;
$this->startY = $startY;

$this->endX = $endX;
$this->endY = $endY;

$H = $this->distBetween($startX, $startY, $endX, $endY);
$this->addToOpenList($startX, $startY, 0, $H, -1, -1);
}

public static function getEmptyMap($width, $height)
{
$map = array();

for ( $x = 0; $x < $width; $x++ )
for ( $y = 0; $y < $height; $y++ )
$map[$x][$y] = 0;

return $map;
}

public static function getRandomMap($width, $height)
{
$map = array();
for ( $x = 0; $x < $width; $x++ )
for ( $y = 0; $y < $height; $y++ )
$map[$x][$y] = !(bool)rand(0, 2);
return $map;
}
private function distBetween($startx, $starty, $x, $y)
{
$xDelta = abs($startx - $x);
$yDelta = abs($starty - $y);
$minDelta = min($xDelta, $yDelta);
if ( self::ALLOW_DIAGONAL )
$g = $minDelta * self::D_COST;
else
$minDelta = 0;
$g += ( $xDelta - $minDelta ) * self::HV_COST;
$g += ( $yDelta - $minDelta ) * self::HV_COST;
return $g;
}
public function findShortestPath()
{
$found = false;
while ( count($this->openList) != 0 )
{
$node = $this->getLowest();
$x = $node['x'];
$y = $node['y'];
if ( $x == -1 )
break;
$this->moveToClosedList($x, $y);
if ( $x == $this->endX && $y == $this->endY )
{
$found = true;
break;
}
// Foreach neighbour
for ( $x1 = $x - 1; $x1 <= $x + 1; $x1++ )
for ( $y1 = $y - 1; $y1 <= $y + 1; $y1++ )
{
if ( $this->isObstacle($x1, $y1) )
continue;

if ( $this->isClosed($x1, $y1) )
continue;

if ( !self::ALLOW_DIAGONAL_CORNERING && $y1 != $y && $x1 != $x )
{
if ( $x1 > $x && $this->isObstacle($x + 1, $y) )
continue;
if ( $x1 < $x && $this->isObstacle($x - 1, $y) )
continue;
if ( $y1 > $y && $this->isObstacle($x, $y + 1) )
continue;
if ( $y1 < $y && $this->isObstacle($x, $y - 1) )
continue;
}

$tentative_g_score = $node['data']['g'] + $this->distBetween($x, $y, $x1, $y1);

if ( !isset($this->openList[$x1][$y1]) || $tentative_g_score < $this->openList[$x1][$y1]['g'] )
$this->addToOpenList($x1, $y1, $tentative_g_score, $this->distBetween($x1, $y1, $this->endX, $this->endY), $x, $y );
}
}

if ( $found )
{
$this->traceBack($this->endX, $this->endY);
return true;
}
else
return false;
}
private function traceBack($x, $y)
{
while ( true )
{
$this->shortestPath[$x][$y] = true;
if ( !isset($this->closedList[$x][$y]) || $this->closedList[$x][$y] === false )
return;
$cx = $this->closedList[$x][$y]['x'];
$y = $this->closedList[$x][$y]['y'];
$x = $cx;
}
}
private function getLowest()
{
$lowestF = -1;
$lowestX = -1;
$lowestY = -1;
$dat = array();
foreach ( $this->openList as $x => $ar )
{
foreach ( $ar as $y => $data )
{
if ( $data['g'] + $data['h'] <= $lowestF || $lowestF == -1 )
{
$lowestF = $data['g'] + $data['h'];
$dat = $data;
$lowestX = $x;
$lowestY = $y;
}
}
}
return array('x' => $lowestX, 'y' => $lowestY, 'data' => $dat);
}
private function addToOpenList($x, $y, $g, $h, $parentX, $parentY)
{
$this->openList[$x][$y] = array('g' => $g, 'h' => $h, 'x' => $parentX, 'y' => $parentY);
}
private function removeFromOpenList($x, $y)
{
unset($this->openList[$x][$y]);
}

private function addToClosedList($x, $y, $parent)
{
$this->closedList[$x][$y] = $parent;
}
private function removeFromClosedList($x, $y)
{
unset($this->closedList[$x][$y]);
}
private function moveToClosedList($x, $y)
{
$parent = $this->openList[$x][$y];
$this->removeFromOpenList($x, $y);
$this->addToClosedList($x, $y, $parent);
}
public function isObstacle($x, $y)
{
return !isset($this->map[$x][$y]) || (bool)$this->map[$x][$y];
}
public function isClosed($x, $y)
{
return isset($this->closedList[$x][$y]);
}
}
>

--------------------------------Dijkstra.php---------------------------------
<?php
class Dijkstra {

var $visited = array();
var $distance = array();
var $previousNode = array();
var $startnode =null;
var $map = array();
var $infiniteDistance = 0;
var $numberOfNodes = 0;
var $bestPath = 0;
var $matrixWidth = 0;

function Dijkstra(&$ourMap, $infiniteDistance) {
$this -> infiniteDistance = $infiniteDistance;
$this -> map = &$ourMap;
$this -> numberOfNodes = count($ourMap);
$this -> bestPath = 0;
}


function findShortestPath($start,$to) {
$this -> startnode = $start;
for ($i=0;$i<$this -> numberOfNodes;$i++) {
if ($i == $this -> startnode) {
$this -> visited[$i] = true;
$this -> distance[$i] = 0;
} else {
$this -> visited[$i] = false;
$this -> distance[$i] = isset($this -> map[$this -> startnode][$i])
? $this -> map[$this -> startnode][$i]
: $this -> infiniteDistance;
}
$this -> previousNode[$i] = $this -> startnode;
}

$maxTries = $this -> numberOfNodes;
$tries = 0;
while (in_array(false,$this -> visited,true) && $tries <= $maxTries) {
$this -> bestPath = $this->findBestPath($this->distance,array_keys($this -> visited,false));
if($to !== null && $this -> bestPath === $to) {
break;
}
$this -> updateDistanceAndPrevious($this -> bestPath);
$this -> visited[$this -> bestPath] = true;
$tries++;
}
}

function findBestPath($ourDistance, $ourNodesLeft) {
$bestPath = $this -> infiniteDistance;
$bestNode = 0;
for ($i = 0,$m=count($ourNodesLeft); $i < $m; $i++) {
if($ourDistance[$ourNodesLeft[$i]] < $bestPath) {
$bestPath = $ourDistance[$ourNodesLeft[$i]];
$bestNode = $ourNodesLeft[$i];
}
}
return $bestNode;
}

function updateDistanceAndPrevious($obp) {
for ($i=0;$i<$this -> numberOfNodes;$i++) {
if( (isset($this->map[$obp][$i]))
&& (!($this->map[$obp][$i] == $this->infiniteDistance) || ($this->map[$obp][$i] == 0 ))
&& (($this->distance[$obp] + $this->map[$obp][$i]) < $this -> distance[$i])
)
{
$this -> distance[$i] = $this -> distance[$obp] + $this -> map[$obp][$i];
$this -> previousNode[$i] = $obp;
}
}
}

function printMap(&$map) {
$placeholder = ' %' . strlen($this -> infiniteDistance) .'d';
$foo = '';
for($i=0,$im=count($map);$i<$im;$i++) {
for ($k=0,$m=$im;$k<$m;$k++) {
$foo.= sprintf($placeholder, isset($map[$i][$k]) ? $map[$i][$k] : $this -> infiniteDistance);
}
$foo.= "\n";
}
return $foo;
}

function getDistance($to){
$ourShortestPath = array();
$foo = '';
for ($i = 0; $i < $this -> numberOfNodes; $i++) {
if($to !== null && $to !== $i) {
continue;
}
$ourShortestPath[$i] = array();
$endNode = null;
$currNode = $i;
$ourShortestPath[$i][] = $i;
while ($endNode === null || $endNode != $this -> startnode) {
$ourShortestPath[$i][] = $this -> previousNode[$currNode];
$endNode = $this -> previousNode[$currNode];
$currNode = $this -> previousNode[$currNode];
}
$ourShortestPath[$i] = array_reverse($ourShortestPath[$i]);
if ($to === null || $to === $i) {
if($this -> distance[$i] >= $this -> infiniteDistance) {
$foo .= sprintf("no route from %d to %d. \n",$this -> startnode,$i);
} else {
$foo .= sprintf(' from %d => to %d = %d (distance) <br> Number of nodes : %d: Follow the route %s'."\n" ,
$this -> startnode,$i,$this -> distance[$i],
count($ourShortestPath[$i]),
implode('-',$ourShortestPath[$i]));
}
if ($to === $i) {
break;
}
}
}
// echo $this->distance[$to].":";
return $this->distance[$to];
}

function getResults($to) {
$ourShortestPath = array();
$foo = '';
for ($i = 0; $i < $this -> numberOfNodes; $i++) {
if($to !== null && $to !== $i) {
continue;
}
$ourShortestPath[$i] = array();
$endNode = null;
$currNode = $i;
$ourShortestPath[$i][] = $i;
while ($endNode === null || $endNode != $this -> startnode) {
$ourShortestPath[$i][] = $this -> previousNode[$currNode];
$endNode = $this -> previousNode[$currNode];
$currNode = $this -> previousNode[$currNode];
}
$ourShortestPath[$i] = array_reverse($ourShortestPath[$i]);
if ($to === null || $to === $i) {
if($this -> distance[$i] >= $this -> infiniteDistance) {
$foo .= sprintf("no route from %d to %d. \n",$this -> startnode,$i);
} else {
$foo .= sprintf(' from %d => to %d = %d (distance) <br> Number of nodes : %d:
Follow the route %s'."\n" ,
$this -> startnode,$i,$this -> distance[$i],
count($ourShortestPath[$i]),
implode('-',$ourShortestPath[$i]));
}
if ($to === $i) {
break;
}
}
}
return $ourShortestPath;//$foo;
}
} // end class
?>

---------------------call path.php-----------------------

<?php
include("Dijkstra.php");

// I is the infinite distance.
define('I',100000);

$access = $_POST['accessField'];
$from = $_POST['fromField'];
$to = $_POST['toField'];
$close = $_POST['closest'];
$closeID = 'z';

//echo $access.".:.".$from.".:.".$to.".:.".$close;

if($close != "Search for ...")
{
if($close=="Access Toilet")
{
$closeID = 'H';
}
if($close=="Lift")
{
$closeID = 'L';
}
if($close=="Security Phone")
{
$closeID = 'P';
}
}

// Size of the matrix
$matrixWidth = 180;

$segs = array();
$points = array();
$nodeID = array();
$targetID = array();

$file_handle = fopen("Segs.txt", "rb");

while (!feof($file_handle) ) {

$line_of_text = fgets($file_handle);
$parts = explode(',', $line_of_text);
if($access=="on")
{
$totalCost = (int)$parts[9] * (int)$parts[10];
}
else
{
$totalCost = (int)$parts[9];
}

array_push($points, array($parts[1],$parts[5],$totalCost));
array_push($segs, array($parts[0],$parts[1],$parts[2],$parts[3],$parts[4],$parts[5],$parts[6],$parts[7],$parts[8],$parts[9],$parts[10],$parts[11]));
}


fclose($file_handle);
$fh = fopen("Nodes.txt", "rb");
while (!feof($fh) ) {

$line_of_text = fgets($fh);
$partsNodes = explode(',', $line_of_text);
if($partsNodes[1]==$from)
{
$fromID = $partsNodes[0];
}
if($partsNodes[1]==$to)
{
$toID = $partsNodes[0];
}
if($partsNodes[5]==$closeID)
{
$cntL++;
array_push($targetID, $partsNodes[0]);
}
array_push($nodeID, array($partsNodes[0],$partsNodes[1]));
}
fclose($fh);
$ourMap = array();
// Read in the points and push them into the map

for ($i=0,$m=count($points); $i<$m; $i++) {
$x = $points[$i][0];
$y = $points[$i][1];
$c = $points[$i][2];
$ourMap[$x][$y] = $c;
$ourMap[$y][$x] = $c;
}

// ensure that the distance from a node to itself is always zero
// Purists may want to edit this bit out.

for ($i=0; $i < $matrixWidth; $i++) {
for ($k=0; $k < $matrixWidth; $k++) {
if ($i == $k) $ourMap[$i][$k] = 0;
}
}

// initialize the algorithm class
$dijkstra = new Dijkstra($ourMap, I,$matrixWidth);

$minDist = I;
for($i=0, $num=count($targetID); $i<$num;$i++){
$t = $targetID[$i];
$dijkstra->findShortestPath($fromID, $t);
$v = $dijkstra->getDistance($t);
if($minDist>$v)
{
$minDist = $v;
$toID = $t;
}
}
// Display the results
$dijkstra->findShortestPath($fromID, $toID);

$timeID = time();
$playListFile = "playlist".$timeID.".xml";

$fw = fopen($playListFile,'w');
fwrite($fw,"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n");
fwrite($fw,"<playlist version=\"1\" xmlns=\"http://xspf.org/ns/0/\">\n");
fwrite($fw,"<title>Wayfinding Videos</title>\n");
fwrite($fw,"<info>http://YourWebpageHere/</info>\n");
fwrite($fw,"\n <trackList>\n");


$nodePath = $dijkstra -> getResults((int)$toID);
for($i = 0; $i < count($nodePath[$toID])-1; $i++)
{
$n1 = $nodePath[$toID][$i];
$n2 = $nodePath[$toID][$i+1];

for($j = 0; $j < sizeof($segs)-1; $j++)
{
if($n1 == $segs[$j][1] && $n2 == $segs[$j][5])
{
fwrite($fw," <track>\n");
fwrite($fw," <title>".$segs[$j][0]."_".$segs[$j][6].".FLV</title>\n");
fwrite($fw," <location>videos/".$segs[$j][0]."_".$segs[$j][6].".FLV</location>\n");
//fwrite($fw,"&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <info>http://www.google.com/search?hl=en&amp;q=" .$segs[$j][0]."_".$segs[$j][6]. ".FLV</info>\n");<br>
fwrite($fw," </track>\n");
}
elseif($n1 == $segs[$j][5] && $n2 == $segs[$j][1])
{
fwrite($fw," <track>\n");
fwrite($fw," <title>".$segs[$j][0]."_".$segs[$j][2].".FLV</title>\n");
fwrite($fw," <location>videos/".$segs[$j][0]."_".$segs[$j][2].".FLV</location>\n");
//fwrite($fw,"&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <info>http://www.google.com/search?hl=en&amp;q=" .$segs[$j][0]."_".$segs[$j][2]. ".FLV</info>\n");<br>
fwrite($fw," </track>\n");
}
}
}
fwrite($fw," </trackList>\n");
fwrite($fw,"</playlist>");
fclose($fw);

echo "<HTML><HEAD><TITLE>Generated Route</TITLE>";

echo " <script type=\"text/javascript\" src=\"http://ajax.googleapis.com/ajax/libs/swfobject/2.1/swfobject.js\"></script>";
echo "\n <script type=\"text/javascript\">";
echo "\n var flashvars =";
echo "\n {";
echo "\n 'file': '".$playListFile."',";
echo "\n 'id': 'playerId',";
echo "\n 'autostart': 'true',";
echo "\n 'logo': './images/crest.png',";
echo "\n 'repeat': 'list'";
echo "\n };\n";
echo "\n var params =";
echo "\n {";
echo "\n 'allowfullscreen': 'true',";
echo "\n 'allowscriptaccess': 'always',";
echo "\n 'bgcolor': '#FFFFFF'";
echo "\n };\n";
echo "\n var attributes =";
echo "\n {";
echo "\n 'id': 'playerId',";
echo "\n 'name': 'playerId'";
echo "\n };\n";
echo "\n swfobject.embedSWF('player.swf', 'player', '320', '240', '9.0.124', false, flashvars, params, attributes);";
echo "\n </script>\n";
echo "\n <script type=\"text/javascript\">";
echo "\n var player = null;\n";
echo "\n function playerReady(obj)";
echo "\n {";
echo "\n player = gid(obj.id);";
echo "\n };\n";
echo "\n function gid(name)";
echo "\n {";
echo "\n return document.getElementById(name);";
echo "\n };";
echo "\n </script>";
echo "\n </HEAD>";
echo "\n <body style=\"background-color:#F1E7CE; font-family:Arial\">";
echo "\n <table border=\"0\" cellspacing=\"0\" >";
echo "\n <tr>";
echo "\n <td style=\"width:550px; height:100px; background-color:#c7b37f\"><img src=\"images/banner_crest.png\" height=\"95px\"/></td>";
echo "\n <td style=\"width:400px; background-color:#c7b37f; vertical-align:text-bottom; text-align:right; color:Black; font-size:24px; font-family:Arial\">Accessibility Wayfinding Project</td>";
echo "\n </tr>";
echo "\n </table>";
echo "\n <p>Click <a href=\"./printer.php?from=".$fromID."&to=".$toID."&access=".$access."\">here</a> for a printer friendly version. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href=\"./index.html\">Search</a> again.</p>";
echo "\n <div id=\"playercontainer\" class=\"playercontainer\"><a id=\"player\" class=\"player\" href=\"http://www.adobe.com/shockwave/download/download.cgi?P1_Prod_Version=ShockwaveFlash\">Get the Adobe Flash Player to see this video.</a></div><P>";

//echo "\n <div style=\"position:absolute; top:0; right:0\"><img src=\".\\mapImages\\".$mapName.".gif\" alt=\"$mapName\" style=\"border:4px\"></div>";

//echo $toID;

for($i = 0; $i < count($nodePath[$toID])-1; $i++)
{
$n1 = $nodePath[$toID][$i];
$n2 = $nodePath[$toID][$i+1];
$stair = "Stairs";
for($j = 0; $j < sizeof($segs)-1; $j++)
{
if($n1 == $segs[$j][1] && $n2 == $segs[$j][5])
{
if(trim($segs[$j][11])===$stair || trim($segs[$j][11])==="Lift")
{
echo "<H4>Use the ".$segs[$j][11]."</H4>";
}
else
{
echo "<H4>Travel along the ".$segs[$j][11]."</h4>";
}
echo "<img src=\"./images/".$segs[$j][2]."_".$segs[$j][0].".jpg\" height=\"240\" alt=\"view from ".$segs[$j][2]." to ".$segs[$j][6]."\"><p>";
}
elseif($n1 == $segs[$j][5] && $n2 == $segs[$j][1])
{
if(trim($segs[$j][11])===$stair || trim($segs[$j][11])==="Lift")
{
echo "<H4>Use the ".$segs[$j][11]."</H4>";
}
else
{
echo "<H4>Travel along the ".$segs[$j][11]."</h4>";
}
echo "<img src=\"./images/".$segs[$j][6]."_".$segs[$j][0].".jpg\" height=\"240\" alt=\"view from ".$segs[$j][6]." to ".$segs[$j][2]."\"><p>";
}

}
}
echo " </BODY>\n";
echo "</HTML>";
?>

Return to “PHP coding => General”

Who is online

Users browsing this forum: Google Feedfetcher and 1 guest