## A star algorithm translate

Ask about general coding issues or problems here.

Moderators: macek, egami, gesf

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

### A star algorithm translate

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: No registered users and 2 guests