Location: PHPKode > scripts > Path finder > class.pathfinder.php

$map=getMap(); //You can use whatever function you need for this purpose
$path=new PathFinder(); //Create new pathfinder object
$path->setOrigin($valuestring['ox'],$valuestring['oy']); //Set the start location
$path->setDestination($valuestring['dx'],$valuestring['dy']); //Set the destination
$path->setMap($map); //Assign the map to use for calculations
$result=$path->returnPath(); //Returns an array of all the walked steps

//Example of the map-array generating function
//This pathfinder example assumes that a square map is used. To use rectangular map you need to tweak the pathfinder a bit
//Here we assign one tile in four as 'unpassable'
//Map is an associative array which has a key of the tile's coordinates as the base. Only required array value is 'weight' but
//you can store additional information in the array for, say, public purposes, such as tile graphic data.
function getMap(){
			} else {
	return $map;
class PathFinder{

	//stores the map data array
	private $map=array();
	//stores origin and destination locations
	private $origX=0;
	private $origY=0;
	private $destX=0;
	private $destY=0;
	//this is used to store the returned path
	private $path=array();
	//this stores locations already looked at, this is temporary and is cleared if pathfinding gets stuck
	private $walked=array();
	//internal storage of squares count and map width
	private $mapSquares=0;
	private $mapWidth=0;
	//flag used to determine if path has been found
	private $found=0;
	//this is a failsafe if the calculation takes too long. It is limited to 100 solves by default
	//Should failsafe be unsuccessful then only partial path will be returned
	private $failSafe=0;
	public $failSafeLimit=100;
	//function to set the map, it needs to be an array
	public function setMap($map){
	//set origin location
	public function setOrigin($origX,$origY){
	//set destination location
	public function setDestination($destX,$destY){
	//calculates and returns path
	public function returnPath(){
		if($this->origX!=0 && $this->origY!=0 && $this->destX!=0 && $this->destY!=0 && !empty($this->map)){
			//this function runs recursively within itself until path is found or failSafe is reached
			return $this->path;
		} else {
			echo 'Insufficient pathfinder data, please define origin and destination points and a map';

	//main function for path calculation
	private function findPath($curX,$curY){
		//failsafe check here
			//resetting the default values for this current square
			//looping through all the nearby squares
							//making sure the checked square is within map boundries
							if($checkX>=1 && $checkY>=1 && $checkX<=$this->mapWidth && $checkY<=$this->mapWidth){
								if($checkX==$curX && $checkY==$curY){
									//this is the current square we are on, so ignore for now
								} else if($checkX==$this->destX && $checkY==$this->destY){
									//we have found the destination!
								} else {
									//if this square has not been 'walked' yet, then consider it as one of the next step
										$weight=(($x==-1 && $y==-1) || ($x==-1 && $y==1) || ($x==1 && $y==-1) || ($x==1 && $y==1))?$weight*1.4:$weight;
										//this makes sure the lowest cost square is used for next step
										if($estimatedCost<$lowestEstimatedCost || $lowestEstimatedCost==0){
			if($shortestX==0 || $shortestY==0){
				//if the shortest locations are 0 then calculation must have gotten stuck and we clear the walked path
				//and try to find a new path from where we got stuck, essentially a re-solve
			} else {
				//we store the next step into walked array (so it is not checked again during this path)
				//storing the location into path array
	//this is used to calculate estimated distance between two points
	private function estimatedCost($curX,$curY,$weight){
		return $value*$weight;


Return current item: Path finder