Dijkstra's Algo

Jezpur schreef op 11.06.2009 19:01

Had je dan niet beter in dat topic verder kunnen gaan?

code weggezet omdat het anders een hele lange pagina werd

<?php
$game = new game(array('2'=>'5'),array('1'=>'1'));
#$game->obstacles(array('2'=>'2'));

$game->obstacles(array('2'=>'1'));
$game->right();
?>

<?php
$game = new game(array('5'=>'2'),array('1'=>'1'));
#$game->obstacles(array('2'=>'2'));

$game->obstacles(array('2'=>'1'));
$game->right();
?>

<?php
error_reporting(E_ALL);

class AStar{

	public function __construct($grid,$start,$einde) {
		$this->grid	= $grid;
		$this->start	= $start;
		$this->einde	= $einde;
		$rows		= 20;
		$cols		= 20;
		$this->rows	= strlen($rows);
		$this->cols	= strlen($cols);
		$this->limiet	= strlen($cols)*strlen($rows);

		$this->einde	= $einde;
		$this->einde	= $einde;

		$this->Path();
	}

	public function Grid($x,$y){
		return $this->grid[$y][$x]===0;
	}

	public function Node($Parent,$Pp){
		foreach($Pp as $z=>$Point) {
			if($z=='x') {
				$Pointx	= $z;
			} elseif($z=='y') {
				$Pointy	= $z;
			}
		}
		return array(
			'Parent'	=> $Parent,
			'value'		=> $Pointx+($Pointy*$this->cols),
			'x'		=> $Pointx,
			'y'		=> $Pointy,
			'f'		=> 0,
			'g'		=> 0
		);
	}




	public function Path(){
			$Start		=$this->Node(null,array('x'=>$this->start[0],'y'=>$this->start[1]));
			$StartOpen	=$this->Node(null,array('x'=>$this->start[0],'y'=>$this->start[1]));
			$Goal		=$this->Node(null,array('x'=>$this->einde[0],'y'=>$this->einde[1]));
			$AStar		=Array($this->limiet);
			$Open		=Array($Start);
			$Closed[]	='';
			$result[]	='';
			$Successors	= '';
			$Node		= '';
			$Path		= '';
print_r($Open);
			$length	=strlen($Open);

			while($length){
				$max=$this->limiet;
				$min=-1;
				for($i=0;$i<$length;$i++){
					if($StartOpen['f'][$i]<$max){
						$max=$StartOpen['f'][$i]; 
						$min=$i;
					}
				};

				$Node=array_splice($StartOpen,$min);

				if($Node['value']===$Goal['value']){

					array_push($Closed,$Node);
					$Path=$Closed[1];

					do {
						array_push($result,$Path['x'],$Path['y']);
					}

					
					while($Path=$Path['Parent']);
						$AStar=$Closed;
					
					array_reverse($result);
				} else {
					$Successors=$this->Successors($Node['x'],$Node['y']);
					for($i=0;$i<strlen($Successors);$i++){
						$Path=$this->Node($Node,$Successors[$i]);
					if($Path['value']){
						$Path['g']=$Node[3]+$this->Manhattan($this->Successors[$i],$Node);
						$Path['f']=$Path[3]+$this->Manhattan($this->Successors[$i],$Goal);
						array_push($Open,$Path);
					};
				};
				array_push($Closed,$Node);
			};
		};
		return $result;
	}

	function Successors($x,$y){
echo $y;
		$N	=$y-1;
		$S	=$y+1;

		$E	=$x+1;
		$W	=$x-1;

		$N2	=$N>-1&&$this->Grid($x,$N);
		$S2	=$S<$this->rows&&$this->Grid($x,$S);
		$E2	=$E<$this->cols&&$this->Grid($E,$y);
		$W2	=$W>-1&&$this->Grid($W,$y);
		$result[] ='';

		if($N2) {
			array_push($result,array('x'=>$x,'y'=>$N));
		}
		if($E2) {
			array_push($result,array('x'=>$E,'y'=>$y));
		}
		if($S2) {
			array_push($result,array('x'=>$x,'y'=>$S));
		}
		if($W2) {
			array_push($result,array('x'=>$W,'y'=>$y));
		}

		return $result;
	}

	public function Manhattan($point,$goal){
		return abs($point[0]-$goal[0])+abs($point[1]-$goal[1]);
	}
}




function GridGenerator($width, $height){
		$result = Array($height);

		for($i = 0; $i < $height; $i++) {
			$result[$i] = Array($width);
			for($j = 0; $j < $width; $j++) {
				$result[$i][$j] = ($j * $i) % 7 ? floor(rand(0,1) * 200) % 2 : 0;
			}
		};
		return $result;
}

$gb	= GridGenerator('20','20');
$sb	= array(ceil(rand() * (20 * 20)),0);
$random = true;
$l	= 20;




for($i = 0; $i < 20; $i++) {

	for($k = 0; $k <$l; $k++) {

		if($gb[$i][$k] !== 0) {

		} else {
			if($random && $sb <= $i + ($k * $l)) {
				$random = false;
			} else {
					$bot = new AStar($gb,$sb,$sb);


			}
		}
	}
}


?>