Find a random path in a pixel grid

findpath.php

<?php
/**
 * some backtrack magic to find a random path
 * */

class Point {
	public $x, $y;
	
	function __construct ($x, $y) {
		$this->x = $x;
		$this->y = $y;
	}
	
	/**
	 * check if the point is inside rect
	 * 
	 * @param	(x1|y1)	numeric		upper-left corner
	 * @param	(x2|y2)	numeric		bottom-right corner
	 * @return	bool	true if Point is in rect or on the edge, else false
	 *	*/
	function is_in_rect ($x1, $y1, $x2, $y2) {
		return $this->x <= $x2 && $this->x >= $x1 && $this->y <= $y2 && $this->y >= $y1;
	}
	
	function __toString () {
		return "(" . $this->x . "|" . $this->y . ")";
	}
}

class Backtracker {
	private $path = null;
	private $area = null;
	private $goal = null;
	private $bad_nodes = array();
	/** 
	 * checks if a step is valid (unused, does not touch path, not out of bounds)
	 * @param	$step	Point				Point to check
	 * @return	bool	true if valid, else false
	*  */
	private function is_valid_step ($step) {
		// on map
		if (! $step->is_in_rect ($this->area["x1"], $this->area["y1"], $this->area["x2"], $this->area["y2"]))
			return false;
		
		// enough space to path
		for ($i = 0; $i < count($this->path) - 2; $i++) 
		{
			if ($step->is_in_rect($this->path[$i]->x - 1, $this->path[$i]->y - 1,
									$this->path[$i]->x + 1, $this->path[$i]->y + 1))
				return false;
		}
		
		// not already used
		if (in_array ($step, $this->path))
			return false;
		
		// your own checks here...
		
		return true;
	}
	
	private function get_steps ($pos) {
		return array(
			//new Point($pos->x - 1, $pos->y - 1),	/* north east */
			//new Point($pos->x - 1, $pos->y + 1),	/* south west */
			
			new Point($pos->x, $pos->y - 1),		/* north */
			new Point($pos->x, $pos->y + 1),		/* south */
			new Point($pos->x + 1, $pos->y),		/* east */
			new Point($pos->x - 1, $pos->y),		/* west */
			
			//new Point($pos->x + 1, $pos->y - 1),	/* north east */
			//new Point($pos->x + 1, $pos->y + 1),	/* south east */
		);
	}
	
	private function path_to_goal_exists ($from) {
		return !in_array($from, $this->bad_nodes);
	}
	
	/** 
	 * recursive backtrack method to find a random path
	 * @param	$step	Point				step to check recursively
	 * @return	bool	true if a path was found, (else false; is impossible)
	*  */
	private function step ($step) {
		if (! $this->is_valid_step ($step))
			return false;
		
		//~ /*DEBUG*/path2img ($this->path, $this->area["x2"]+1, $this->area["y2"]+1);
		//~ /*DEBUG*/echo $step . "\n";
		//~ /*DEBUG*/echo count($this->path) . "\n";
		//~ /*DEBUG*/shell_exec("read fdg");
		
		// add step to path
		array_push ($this->path, $step);
		
		// goal reached, end recursion
		if ($step == $this->goal)
			return true;
		
		// optimize: discard impasses
		if ($this->path_to_goal_exists ($step)) {
			// all neighbor points
			$steps = $this->get_steps ($step);
			shuffle($steps);
			
			foreach ($steps as $nextstep) 
			{
				if ($this->step ($nextstep))
					return true;
			}
			
			// dead node
			array_push($this->bad_nodes, $step);
		}
		// remove step and go back!
		array_pop ($this->path);
		return false;
	}
	
	/** 
	 * find a random path
	 * @param	$start	Point		point to start at, MUST be in allowed area
	 * @param	$end	Point		goal, MUST be in allowed area
	 * @param	(x1|y1)	numeric		allowed area, upper left corner
	 * @param	(x2|y2)	numeric		allowed area, bottom right corner
	 * @return	array	the generated path or null if no path was found (not possible)
	*  */
	public function find_path ($start, $end, $x1, $y1, $x2, $y2) {
		$this->area = compact("x1", "y1", "x2", "y2");
		$this->goal = $end;
		$this->path = array();
		$this->bad_nodes = array();
		
		// start recursion
		if ($this->step ($start))
			return $this->path;
		else
			return null; // this should NEVER happen!
	}
	
	function path2img ($file = "/tmp/path.png", $zoom = 5) {
		$w = $this->area['x2'] + 1;
		$h = $this->area['y2'] + 1;
		$im = imagecreatetruecolor ($w * $zoom, $h * $zoom);
		$color = imagecolorallocate($im, 155, 155, 155);
		foreach ($this->path as $point) 
		{
			imagefilledrectangle ($im, $point->x * $zoom, $point->y * $zoom, ($point->x+1) * $zoom - 1, ($point->y+1) * $zoom - 1, $color);
		}
		$color = imagecolorallocate($im, 155, 0, 0);
		foreach ($this->bad_nodes as $point) 
		{
			imagefilledrectangle ($im, $point->x * $zoom, $point->y * $zoom, ($point->x+1) * $zoom - 1, ($point->y+1) * $zoom - 1, $color);
		}
		imagepng($im, $file);
	}
}

?>