<?php

//EXAMPLE OF USE
/*
$map=getMap(); //You can use whatever function you need for this purpose
require('class.pathfinder.php');
$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(){
	$map=array();
	for($x=1;$x<=20;$x++){
		for($y=1;$y<=20;$y++){
			$rand=rand(1,4);
			if($rand==1){
				$map[$x.'x'.$y]=array('weight'=>'10.0');
			} else {
				$map[$x.'x'.$y]=array('weight'=>'1.0');
			}
		}
	}
	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){
		$this->map=$map;
		$this->mapSquares=count($this->map);
		$this->mapWidth=sqrt($this->mapSquares);
	}
	
	//set origin location
	public function setOrigin($origX,$origY){
		$this->origX=$origX;
		$this->origY=$origY;
		
	}
	
	//set destination location
	public function setDestination($destX,$destY){
		$this->destX=$destX;
		$this->destY=$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
			$this->findPath($this->origX,$this->origY);
			return $this->path;
		} else {
			echo 'Insufficient pathfinder data, please define origin and destination points and a map';
			die();
		}
	}

	//main function for path calculation
	private function findPath($curX,$curY){
		//failsafe check here
		$this->failSafe++;
		if($this->failSafe>=$this->failSafeLimit){
			$this->found=1;
		}
		if($this->found!=1){
			//resetting the default values for this current square
			$lowestEstimatedCost=0;
			$shortestX=0;
			$shortestY=0;
			//looping through all the nearby squares
			for($x=-1;$x<=1;$x++){
				if($this->found==0){
					for($y=-1;$y<=1;$y++){
						if($this->found==0){
							$checkX=$x+$curX;
							$checkY=$y+$curY;
							//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!
									$this->found=1;
									$this->path[]=$this->destX.'x'.$this->destY;
								} else {
									//if this square has not been 'walked' yet, then consider it as one of the next step
									if(!in_array($checkX.'x'.$checkY,$this->walked)){
										$weight=$this->map[$checkX.'x'.$checkY]['weight'];
										$weight=(($x==-1 && $y==-1) || ($x==-1 && $y==1) || ($x==1 && $y==-1) || ($x==1 && $y==1))?$weight*1.4:$weight;
										$estimatedCost=$this->estimatedCost($checkX,$checkY,$weight);
										//this makes sure the lowest cost square is used for next step
										if($estimatedCost<$lowestEstimatedCost || $lowestEstimatedCost==0){
											$lowestEstimatedCost=$estimatedCost;
											$shortestX=$checkX;
											$shortestY=$checkY;
										}
									}
								}
							}
						}
					}
				}
			}
		}
		if($this->found!=1){
			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
				$this->walked=array();
				$this->walked[]=$curX.'x'.$curY;
				$this->findPath($curX,$curY,$this->destX,$this->destY);
			} else {
				//we store the next step into walked array (so it is not checked again during this path)
				$this->walked[]=$shortestX.'x'.$shortestY;
				//storing the location into path array
				$this->path[]=$shortestX.'x'.$shortestY;
				$this->findPath($shortestX,$shortestY,$this->destX,$this->destY);
			}
		}
	}
	
	//this is used to calculate estimated distance between two points
	private function estimatedCost($curX,$curY,$weight){
		$dx=$this->destX-$curX;
		$dy=$this->destY-$curY;
		$value=sqrt(($dx*$dx)+($dy*$dy));
		return $value*$weight;
	}

}

?>