# Calculating Route Trough Map

## Recommended Posts

Hey people, I am really getting used php and I have made some neat systems on witch visitors replied with great respect. A few weeks ago I decided to take my coding to the next step. I am currently building a game on witch you actually see army's walking on a map from point A to B.My goal is to make this game for everyone. This includes people that are using browsers witch not even support javascript and java applets etc. I came to the conclusion that I was only able to use php with basic css for when it comes to the actual system behind the game. I use javascript/Ajax to insert some dynamics like making the army's walk without a page refresh. (letting ajax refresh the army coordinates)My systems works as follows: -First I made a game-map with a normal table with one column (1000*1000 pixels width)-Php loads div's with coordinates witch repressend the bases (goals)-Second, php loads the army div's witch repressend the current possition of the army's-php calculates the distance between the base (point and the army (point A) by using A2 * B2 = C2:

`<?phpfunction pythagoras(\$x,\$y,\$z=0) {  return sqrt(\$x*\$x + \$y*\$y + \$z*\$z);} ?>`

-php has now the sides of a tri-angle and it knows that one of the sides is 90 degrees so it can calculate the corner in witch the army walks-php checks if Y-distance or X-distance are positive or negative. Based on that it decides wether to use tan, sin or cos.-php now has a distance and (unix) time, so it can calculate the current position of the army. -put al of this in a loop and the army will walk and stop at the given point B. Now I want to take this a little step further. The army's walk and everything will be updated on page refresh. (or with help of AJAX only the army div's)My second goal is letting the army avoid any obstacles. So when I say that coordinate X:Y is an obstacle, php has to calculate a path around it. I can do this easily by letting the army's walk trough checkpoints (fixed paths) but I php to actually calculate the shortest way automaticly.Can anyone give me a hint where to start? to be clear:Point A wants to go to point B, but in between there is a lake. Now point A has to walk along the edge of the lake to get to point B

##### Share on other sites

Pathfinding algorithms are one of the classic AI problems:http://www.google.com/search?client=opera&...-8&oe=utf-8

##### Share on other sites

Perfect! this is exactly what I am looking for. It took me 2 days to make a concept of my own witch had no real potential and now I see that I was looking into the wrong direction. Edited by Redroest
##### Share on other sites

The tutorial You gave me was great. I now understand the concepts of A* but now I need to have a sample of a php version I tried to make one myself, but i am totally stuck on this. I already searched google for an example of a php A* algorithm, but without results. Maybe someone wants to help me by converting a flas version to php?

##### Share on other sites

Flash doesn't exactly convert very well to PHP. Flash has all the interface stuff in as well, PHP doesn't really do anything with the interface, it just deals with data. Flash and Actionscript would be more comparable to Javascript than it would to PHP. Actionscript and Javascript are both based on the same language.

##### Share on other sites

Ok, I came this far and I don't have any clue if I'm doing a good job. first I made the table with width in my index.php:

`<?phpecho "<body>";echo "<table class='Map' width='".\$playfield_size."' height='".\$playfield_size."' background='Nederland.jpg' align='center' border='0'>";echo "  <tr>";echo "	<td valign='top'>";include("pathfinder.php");//echo "	  <div id='ObjectOutput'></div>";echo "	</td>";echo "  </tr>";echo "</table>";echo "</body>";?>`

The table in index.php is in fact the playground in witch my script will work. Now I include pathfinder.php witch contains the A* script (or what it looks like haha ) Normally I always load my functions as soon as my page loads, but for the ease I inserted them into pathfinder.php. When I test this script it will give me a path to point B with a slight curve, but since there are no obstacles yet it should go in a straight line.I know that this script is not yet ready and there are a few things missing. I just did not figure out yet on how to implement them. `<?php//Calculate shortest distance with X and Yfunction pythagoras(\$x,\$y,\$z=0) {  return sqrt(\$x*\$x + \$y*\$y + \$z*\$z);} //Search Value X and Value Y in a multidimensional array (custom made to shorten loading time)function array_in_array(\$Nodes, \$Y, \$X) {	\$i=0;  foreach(\$Nodes AS \$key => \$value) 	{	if((\$value["X"] == \$X) && (\$value["Y"] == \$Y))		{	  \$i++;	}  }	if(\$i > 0)	{	return true;  }	else	{	  return false;	}} //Sort array's in array'sfunction sksort(&\$array, \$subkey="id", \$sort_ascending=false) {  if (count(\$array))		\$temp_array[key(\$array)] = array_shift(\$array);	foreach(\$array as \$key => \$val)		{	  \$offset = 0;	  \$found = false;	  foreach(\$temp_array as \$tmp_key => \$tmp_val)	  {		if(!\$found and strtolower(\$val[\$subkey]) > strtolower(\$tmp_val[\$subkey]))		{		  \$temp_array = array_merge( (array)array_slice(\$temp_array,0,\$offset),			array(\$key => \$val),			array_slice(\$temp_array,\$offset)		  );		  \$found = true;		}		\$offset++;	  }	  if(!\$found) \$temp_array = array_merge(\$temp_array, array(\$key => \$val));	}	if (\$sort_ascending) \$array = array_reverse(\$temp_array);  else 	  \$array = \$temp_array;}\$OpenNodes = array();function OpenNodes(\$FinalX, \$FinalY, \$Xdistance, \$Ydistance, \$Speed, \$Dspeed, \$i, \$o, \$playfield_size, \$ParentX, \$ParentY, \$F, \$H, \$G){  global \$OpenNodes, \$ClosedNodes, \$SelectedNode;		\$X = \$ParentX-\$Speed;	\$Y = \$ParentY;	//If statement makes sure that no double coordinates will be inserted  if(!array_in_array(\$OpenNodes, \$Y, \$X))	{	  //Childnode West:	  \$OpenNodes[\$i]["ParentX"]   = \$ParentX;	  \$OpenNodes[\$i]["ParentY"]   = \$ParentY;	  \$OpenNodes[\$i]["X"]		 = \$ParentX-\$Speed;	  \$OpenNodes[\$i]["Y"]		 = \$ParentY;	\$OpenNodes[\$i]["Xdistance"] = \$FinalX - \$OpenNodes[\$i]["X"];	\$OpenNodes[\$i]["Ydistance"] = \$FinalY - \$OpenNodes[\$i]["Y"];	\$OpenNodes[\$i]["G"] = \$Speed;	  \$OpenNodes[\$i]["H"] = pythagoras(\$OpenNodes[\$i]["Xdistance"],\$OpenNodes[\$i]["Ydistance"],\$z=0);		\$OpenNodes[\$i]["F"] = \$OpenNodes[\$i]["H"] + \$OpenNodes[\$i]["G"];		\$i++;		}	\$X = \$ParentX-\$Speed;	\$Y = \$ParentY+\$Speed;  if(!array_in_array(\$OpenNodes, \$Y, \$X))	{	//Childnode North-West:	  \$OpenNodes[\$i]["ParentX"]   = \$ParentX;	  \$OpenNodes[\$i]["ParentY"]   = \$ParentY;		  \$OpenNodes[\$i]["X"]		 = \$ParentX-\$Speed;	  \$OpenNodes[\$i]["Y"]		 = \$ParentY+\$Speed;		\$OpenNodes[\$i]["Xdistance"] = \$FinalX - \$OpenNodes[\$i]["X"];	\$OpenNodes[\$i]["Ydistance"] = \$FinalY - \$OpenNodes[\$i]["Y"];	\$OpenNodes[\$i]["G"] = \$Dspeed;	  \$OpenNodes[\$i]["H"] = pythagoras(\$OpenNodes[\$i]["Xdistance"],\$OpenNodes[\$i]["Ydistance"],\$z=0);		\$OpenNodes[\$i]["F"] = \$OpenNodes[\$i]["H"] + \$OpenNodes[\$i]["G"];	\$i++;		}	\$X = \$ParentX;	\$Y = \$ParentY+\$Speed;  if(!array_in_array(\$OpenNodes, \$Y, \$X))	{	//Childnode North:	  \$OpenNodes[\$i]["ParentX"]   = \$ParentX;	  \$OpenNodes[\$i]["ParentY"]   = \$ParentY;		  \$OpenNodes[\$i]["X"]		 = \$ParentX;	  \$OpenNodes[\$i]["Y"]		 = \$ParentY+\$Speed;			\$OpenNodes[\$i]["Xdistance"] = \$FinalX - \$OpenNodes[\$i]["X"];	\$OpenNodes[\$i]["Ydistance"] = \$FinalY - \$OpenNodes[\$i]["Y"];	\$OpenNodes[\$i]["G"] = \$Speed;	  \$OpenNodes[\$i]["H"] = pythagoras(\$OpenNodes[\$i]["Xdistance"],\$OpenNodes[\$i]["Ydistance"],\$z=0);		\$OpenNodes[\$i]["F"] = \$OpenNodes[\$i]["H"] + \$OpenNodes[\$i]["G"];	\$i++;	}	\$X = \$ParentX+\$Speed;	\$Y = \$ParentY+\$Speed;  if(!array_in_array(\$OpenNodes, \$Y, \$X))	{	//Childnode North-East:	  \$OpenNodes[\$i]["ParentX"]   = \$ParentX;	  \$OpenNodes[\$i]["ParentY"]   = \$ParentY;		  \$OpenNodes[\$i]["X"]		 = \$ParentX+\$Speed;			\$OpenNodes[\$i]["Y"]		 = \$ParentY+\$Speed;		\$OpenNodes[\$i]["Xdistance"] = \$FinalX - \$OpenNodes[\$i]["X"];	\$OpenNodes[\$i]["Ydistance"] = \$FinalY - \$OpenNodes[\$i]["Y"];	\$OpenNodes[\$i]["G"] = \$Dspeed;	  \$OpenNodes[\$i]["H"] = pythagoras(\$OpenNodes[\$i]["Xdistance"],\$OpenNodes[\$i]["Ydistance"],\$z=0);		\$OpenNodes[\$i]["F"] = \$OpenNodes[\$i]["H"] + \$OpenNodes[\$i]["G"];	\$i++;	}	\$X = \$ParentX+\$Speed;	\$Y = \$ParentY;  if(!array_in_array(\$OpenNodes, \$Y, \$X))	{	//Childnode East:	  \$OpenNodes[\$i]["ParentX"]   = \$ParentX;	  \$OpenNodes[\$i]["ParentY"]   = \$ParentY;	  \$OpenNodes[\$i]["X"]		 = \$ParentX+\$Speed;			\$OpenNodes[\$i]["Y"]		 = \$ParentY;			\$OpenNodes[\$i]["Xdistance"] = \$FinalX - \$OpenNodes[\$i]["X"];	\$OpenNodes[\$i]["Ydistance"] = \$FinalY - \$OpenNodes[\$i]["Y"];	  \$OpenNodes[\$i]["G"] = \$Speed;	  \$OpenNodes[\$i]["H"] = pythagoras(\$OpenNodes[\$i]["Xdistance"],\$OpenNodes[\$i]["Ydistance"],\$z=0);		\$OpenNodes[\$i]["F"] = \$OpenNodes[\$i]["H"] + \$OpenNodes[\$i]["G"];	\$i++;	}	\$X = \$ParentX+\$Speed;	\$Y = \$ParentY-\$Speed;  if(!array_in_array(\$OpenNodes, \$Y, \$X))	{	//Childnode South-East:	  \$OpenNodes[\$i]["ParentX"]   = \$ParentX;	  \$OpenNodes[\$i]["ParentY"]   = \$ParentY;	  \$OpenNodes[\$i]["X"]		 = \$ParentX+\$Speed;			\$OpenNodes[\$i]["Y"]		 = \$ParentY-\$Speed;		\$OpenNodes[\$i]["Xdistance"] = \$FinalX - \$OpenNodes[\$i]["X"];	\$OpenNodes[\$i]["Ydistance"] = \$FinalY - \$OpenNodes[\$i]["Y"];	\$OpenNodes[\$i]["G"] = \$Dspeed;	  \$OpenNodes[\$i]["H"] = pythagoras(\$OpenNodes[\$i]["Xdistance"],\$OpenNodes[\$i]["Ydistance"],\$z=0);		\$OpenNodes[\$i]["F"] = \$OpenNodes[\$i]["H"] + \$OpenNodes[\$i]["G"];	\$i++;		}	\$X = \$ParentX;	\$Y = \$ParentY-\$Speed;	  if(!array_in_array(\$OpenNodes, \$Y, \$X))	{	//Childnode South:	  \$OpenNodes[\$i]["ParentX"]   = \$ParentX;	  \$OpenNodes[\$i]["ParentY"]   = \$ParentY;		  \$OpenNodes[\$i]["X"]		 = \$ParentX;			\$OpenNodes[\$i]["Y"]		 = \$ParentY-\$Speed;			\$OpenNodes[\$i]["Xdistance"] = \$FinalX - \$ParentX;	\$OpenNodes[\$i]["Ydistance"] = \$FinalY - (\$ParentY-\$Speed);	  \$OpenNodes[\$i]["G"] = \$Speed;	  \$OpenNodes[\$i]["H"] = pythagoras(\$OpenNodes[\$i]["Xdistance"],\$OpenNodes[\$i]["Ydistance"],\$z=0);		\$OpenNodes[\$i]["F"] = \$OpenNodes[\$i]["H"] + \$OpenNodes[\$i]["G"];	\$i++;	}	\$X = \$ParentX-\$Speed;	\$Y = \$ParentY-\$Speed;  if(!array_in_array(\$OpenNodes, \$Y, \$X))	{	//Childnode South-West:	  \$OpenNodes[\$i]["ParentX"]   = \$ParentX;	  \$OpenNodes[\$i]["ParentY"]   = \$ParentY;		  \$OpenNodes[\$i]["X"]		 = \$ParentX-\$Speed;			\$OpenNodes[\$i]["Y"]		 = \$ParentY-\$Speed;				\$OpenNodes[\$i]["Xdistance"] = \$FinalX - \$OpenNodes[\$i]["X"];	\$OpenNodes[\$i]["Ydistance"] = \$FinalY - \$OpenNodes[\$i]["Y"];	  \$OpenNodes[\$i]["G"] = \$Dspeed;	  \$OpenNodes[\$i]["H"] = pythagoras(\$OpenNodes[\$i]["Xdistance"],\$OpenNodes[\$i]["Ydistance"],\$z=0);		\$OpenNodes[\$i]["F"] = \$OpenNodes[\$i]["H"] + \$OpenNodes[\$i]["G"];	\$i++;	}  //Sort childnodes on longest distance and pick the one with the lowest distance to destination  sksort(\$OpenNodes, "F", true);  //Set values to make list of steps	\$F = round(\$OpenNodes["F"]);	\$G = round(\$OpenNodes["G"]);	\$H = round(\$OpenNodes["H"]);	\$Xdistance = \$OpenNodes["Xdistance"];	\$Ydistance = \$OpenNodes["Ydistance"];	\$ChildX =  \$OpenNodes["X"];	\$ChildY =  \$OpenNodes["Y"];		SelectedNodes(\$FinalX, \$FinalY, \$Xdistance, \$Ydistance, \$Speed, \$Dspeed, \$i, \$o, \$playfield_size, \$ChildX, \$ChildY, \$F, \$H, \$G);}function SelectedNodes(\$FinalX, \$FinalY, \$Xdistance, \$Ydistance, \$Speed, \$Dspeed, \$i, \$o, \$playfield_size, \$ChildX, \$ChildY, \$F, \$H, \$G){	  global \$OpenNodes, \$ClosedNodes;	//Store choosen nodes in the ClosedNode array	\$ClosedNodes[\$o]["X"]		 = \$ChildX;	\$ClosedNodes[\$o]["Y"]		 = \$ChildY;  \$ClosedNodes[\$o]["Xdistance"] = \$FinalX - \$ChildX;  \$ClosedNodes[\$o]["Ydistance"] = \$FinalY - \$ChildY;	\$ClosedNodes[\$o]["H"]		 = \$H;	\$ClosedNodes[\$o]["G"]		 = \$G;  \$ClosedNodes[\$o]["F"]		 = \$F;  \$o++;	//If distance in pixels is shorter or ecual to 14 (One step is max 14 pixels so make sure it doesn't overshoot)  if(\$F <= 14)	{	  echo "Destination reached.<br />";	}	else	{	  //Show choosen path	echo "<div style='position: absolute; display: block; left:".\$ChildX."px; bottom:".\$ChildY."px; border-width: 1px; background-color: #00cccc; border-color: #000000; border-style: solid; #000000; width: 10px; height: 10px;'><a href='#' title='".\$F."'></a></div>"; 			//Make function recursive until destination X and destination Y are found		return OpenNodes(\$FinalX, \$FinalY, \$Xdistance, \$Ydistance, \$Speed, \$Dspeed, \$i, \$o, \$playfield_size, \$ChildX, \$ChildY, \$F, \$H, \$G); 	}}//Size of the playfield in pixels (in this case a table)\$playfield_size = 1000;//Horizontal and vertical steps per movement\$Speed = 10;//Diagonal steps per movement\$Dspeed = 14;//Start-coordinate\$ParentX = 200;\$ParentY = 400;//End-coordinate\$FinalX = 700;\$FinalY = 800;//Total distance X\$TotalX = \$FinalX - \$ParentX;//Total distance Y\$TotalY = \$FinalY - \$ParentY;//Total distance "H" to destination\$H = pythagoras(\$TotalX,\$TotalY,\$z=0);//Total distance and walking costs "G" \$F = \$H;//Costs to make the first step\$G = 0;//Counters\$o = 0;\$i = 0;//Start calculationecho SelectedNodes(\$FinalX, \$FinalY, \$TotalX, \$TotalY, \$Speed, \$Dspeed, \$i, \$o, \$playfield_size, \$ParentX, \$ParentY, \$F, \$H, \$G);//Show the Open Nodesforeach(\$OpenNodes AS \$key => \$value){  echo "<div style='position: absolute; left:".\$value["X"]."px; bottom:".\$value["Y"]."px; border-width: 1px; border-color: red; border-style: solid; width: 10px; height: 10px;'><a href='#' title='".\$F."'></a></div>"; }	echo "<div style='position: absolute; left:".\$ParentX."px; bottom:".\$ParentY."px; background-color: #000000; width: 10px; height: 10px;'><a href='#'></a></div>"; echo "<div style='position: absolute; left:".\$FinalX."px; bottom:".\$FinalY."px; background-color: #000000; width: 10px; height: 10px;'><a href='#'></a></div>";  ?>`

##### Share on other sites

Ok, this script looks for a path and it works. I now somehow have to add some code that keeps looking for faster paths.

##### Share on other sites

You need to give each path a weight. Every 1 step should count as 1 towards the weight, so once you calculate several paths you can determine which has the lowest weight, or the fewest number of steps.