Pathfinding

Pathfinding.php
<?php
/**
 * 
 * @author Pim <[email protected]>
 * @version 1.0
 * @package Pathfinding
 *
 */

/**
 * The Pathfinding class
 * 
 * Finds the shortest path between a starting point and an ending point
 * Uses the following algorithm
 * 	1. Starts at the starting point
 * 	2. Finds all connected points
 * 	3. Then does the following with every connected point
 * 		- If the point is an ending point, add this route to {@link $_goodRoutes}
 * 		- If the point is reached quicker in another route, do not do anything
 * 		- Else add the last distance to the total distance and go to step 2
 * 	4. After all {@link $_goodRoutes} have been found, they are sorted by distance
 * 	5. The shortest {@link $_goodRoutes} is returned
 * 
 * @package Pathfinding
 */
class Pathfinding
{
	/**
	 * Stores the points
	 * @var array
	 */
	private $_points = array();
	
	/**
	 * Stores the shortest distance to every point
	 * @var array
	 */
	private $_shortestRouteTo = array();
	
	/**
	 * Stores all routes leading to an ending point
	 * @var array
	 */
	private $_goodRoutes = array();
	
	/**
	 * The time the finding took
	 * @var int
	 */
	private $_findingTime;
	
	/**
	 * The constructor, if an parameter is given, they are passed through to {@link addPoints()}
	 * @param array|null $array
	 */
	public function __construct($array = null)
	{
		if(!is_null($array)) {
			$this->addPoints($array);
		}
	}
	
	/**
	 * Adds an point to {@link $_points}
	 * @param Pathfinding_Point $p
	 * @return Pathfinding
	 */
	public function addPoint(Pathfinding_Point $p)
	{
		$this->_points[$p->getName()] = $p;
		
		return $this;
	}
	
	/**
	 * Adds multiple points to {@link $_points}
	 * @param array $a
	 * @return Pathfinding
	 */
	public function addPoints(array $a)
	{
		foreach($a as $point) {
			$this->_points[$point->getName()] = $point;
		}
		return $this;
	}
	
	/**
	 * The main finding function, doing steps 1, 4 and 5 of the previous discribed algorithm
	 * @param Pathfinding_Point $start
	 * @return array The found route
	 * 
	 * @todo Return multiple routes if more than one route is the shortest
	 */
	public function find(Pathfinding_Point $start)
	{
		if($start instanceof Pathfinding_Point) {
			$startingPoint = $start;
		} else if (is_string($start)) {
			$startingPoint = $this->_points[$start];
		}
		
		// Time the finding
		$startingTime = microtime(true);
		
		$this->_shortestRouteTo[$startingPoint->getName()] = 0;
		$this->_findRecursion(array($startingPoint), 0);
		
		// Sorts the found routes by distance, ascending
		usort($this->_goodRoutes, array($this, '_sortRoutes'));
		
		$this->_findingTime = microtime(true) - $startingTime;
		
		// Returns the shortest of the found routes
		return reset($this->_goodRoutes);
	}
	
	/**
	 * Step 2 and 3 of the previous discribed algorithm
	 * @param array $route The route until this point
	 * @param int $distance The distance until this point
	 * @return null
	 */
	private function _findRecursion(array $route, $distance)
	{
		$point = end($route);
		foreach($point->getLinks() as $link) {
			// If the point has not been reached yet, or has only been reached in a longer distance
			if(!isset($this->_shortestRouteTo[ $link['point']->getName() ]) ||
				$this->_shortestRouteTo[ $link['point']->getName() ] > $distance + $link['distance']) {
					
				$newRoute = $route;
				$newRoute[] = $link['point'];
				$newDistance = $distance + $link['distance'];
				
				// If the point is an ending point
				if($link['point']->isEnd()) {
					$this->_goodRoutes[] = array('route' => $newRoute, 'distance' => $newDistance);
				} else {
					$this->_shortestRouteTo[ $link['point']->getName() ] = $newDistance;
					// Continues the search
					$this->_findRecursion($newRoute, $newDistance);
				}
			}
		}
	}
	
	/**
	 * Sorts the routes by distance, ascending
	 * @see usort()
	 * @param array $a
	 * @param array $b
	 * 
	 * @return int
	 */
	private function _sortRoutes(array $a, array $b)
	{
		return ($a['distance'] < $b['distance']) ? -1 : 1;
	}
	
	/**
	 * Returns the time the finding took
	 * @return float
	 */
	public function time()
	{
		return $this->_findingTime;
	}
	
	/**
	 * Formats the found route nicely
	 * @static
	 * @param array $route
	 * @return string
	 */
	public static function formatRoute(array $route)
	{
		$string = '';
		$previous = null;
		foreach($route['route'] as $point) {
			if(!is_null($previous)) {
				// Prints the distance between points
				$string .= ' - '.$point->getDistance($previous).' - ';
			}
			$string .= '<strong>'.$point->getName().'</strong>';
			$previous = $point;
		}
		// Prints the total distance
		$string .= ' = '.$route['distance'];
		return $string;
	}
}
?>
Pathfinding_Point.php
<?php
/**
 * 
 * @author Pim <[email protected]>
 * @version 1.0
 * @package Pathfinding
 *
 */

/**
 * The Pathfinding point class
 * 
 * Discribes a point and the links to other points
 * 
 * @package Pathfinding
 */
class Pathfinding_Point
{
	/**
	 * The links
	 * @var array
	 */
	private $_links = array();
	
	/**
	 * The points name
	 * @var string
	 */
	private $_name;
	
	/**
	 * Wether the point is an ending point
	 * @var boolean
	 */
	private $_isEnd;
	
	/**
	 * The consructor, sets {@link $_name} and {@link $_isEnd}
	 * @param string $name
	 * @param boolean $isEnd
	 */
	public function __construct($name, $isEnd = false)
	{
		$this->_name = $name;
		$this->_isEnd = $isEnd;
	}
	
	/**
	 * Returns {@link $_name}
	 * @return string
	 */
	public function getName()
	{
		return $this->_name;
	}
	
	/**
	 * Returns {@link $_isEnd}
	 * @return boolean
	 */
	public function isEnd()
	{
		return $this->_isEnd;
	}
	
	/**
	 * Adds an link to this and the other point
	 * 
	 * @param Pathfinding_Point $p
	 * @param int $distance The distance between the two points, default is 1
	 * @param boolean $forwarded If the call is made by the other point
	 * 
	 * @see $_links
	 * 
	 * @return Pathfinding_Point
	 */
	public function addLink(Pathfinding_Point $p, $distance = 1, $forwarded = false)
	{
		$this->_links[ $p->getName() ] = array('point' => $p, 'distance' => $distance);
		
		if(!$forwarded) {
			$p->addLink($this, $distance, true);
		}
		
		return $this;
	}
	
	/**
	 * Adds multiple links
	 * @see addLink()
	 * @param array $a
	 * 
	 * @return Pathfinding_Point
	 */
	public function addLinks(array $a)
	{
		foreach($a as $distance => $point) {
			$this->addLink($point, $distance);
		}
		
		return $this;
	}
	
	/**
	 * Returns {@link $_links}
	 * 
	 * @return array
	 */
	public function getLinks()
	{
		return $this->_links;
	}
	
	/**
	 * Returns the distance between the points
	 * @param Pathfinding_Point $p
	 * @return int
	 */
	public function getDistance(Pathfinding_Point $p)
	{
		return $this->_links[ $p->getName() ]['distance'];
	}
}
?>