Help please to convert Dijkstra to A star algorithm

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
aziz88
Forum Newbie
Posts: 1
Joined: Fri Oct 12, 2012 12:46 am

Help please to convert Dijkstra to A star algorithm

Post by aziz88 »

Hi guys, I'm having trouble converting Dijkstra algorithm to A star. Actually the A star algorithm class is attached as well as Dijkstra but the file callPath needs to be changed as it's currently working with Dijkstra. I appreciate your help

A star algorithm:

Code: Select all

<?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 algorithm:
<?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 
?>
____________________________________________________________
callPath file(the one to be changed):
<?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&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&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>";
	

?>
Last edited by Benjamin on Fri Oct 12, 2012 1:59 am, edited 1 time in total.
Reason: Added [syntax=php||htm||css||javascript||sql||etc] - Please use [syntax] tags when posting code in the forums! Thanks.
Post Reply