PHP树的深度编历生成迷宫及A*自动寻路算法实例分析
本文实例讲述了PHP树的深度编历生成迷宫及A*自动寻路算法。分享给大家供大家参考。具体分析如下：
有一同事推荐了三思的迷宫算法，看了感觉还不错，就转成php
三思的迷宫算法是采用树的深度遍历原理，这样生成的迷宫相当的细，而且死胡同数量相对较少！
任意两点之间都存在唯一的一条通路。
至于A*寻路算法是最大众化的一全自动寻路算法
废话不多说，贴上带代码
迷宫生成类：
classMaze{
//MazeCreate
private$_w;
private$_h;
private$_grids;
private$_walkHistory;
private$_walkHistory2;
private$_targetSteps;
//Construct
publicfunctionMaze(){
$this->_w=6;
$this->_h=6;
$this->_grids=array();
}
//设置迷宫大小
publicfunctionset($width=6,$height=6){
if($width>0)$this->_w=$width;
if($height>0)$this->_h=$height;
return$this;
}
//取到迷宫
publicfunctionget(){
return$this->_grids;
}
//生成迷宫
publicfunctioncreate(){
$this->_init();
return$this->_walk(rand(0,count($this->_grids)-1));
}
//获取死胡同点
publicfunctionblock($n=0,$rand=false){
$l=count($this->_grids);
for($i=1;$i<$l;$i++){
$v=$this->_grids[$i];
if($v==1||$v==2||$v==4||$v==8){
$return[]=$i;
}
}
//随机取点
if($rand)shuffle($return);
if($n==0)return$return;
if($n==1){
returnarray_pop($return);
}else{
returnarray_slice($return,0,$n);
}
}
/**
|---------------------------------------------------------------
|生成迷宫的系列函数
|---------------------------------------------------------------
*/
privatefunction_walk($startPos){
$this->_walkHistory=array();
$this->_walkHistory2=array();
$curPos=$startPos;
while($this->_getNext0()!=-1){
$curPos=$this->_step($curPos);
if($curPos===false)break;
}
return$this;
}
privatefunction_getTargetSteps($curPos){
$p=0;
$a=array();
$p=$curPos-$this->_w;
if($p>0&&$this->_grids[$p]===0&&!$this->_isRepeating($p)){
array_push($a,$p);
}else{
array_push($a,-1);
}
$p=$curPos+1;
if($p%$this->_w!=0&&$this->_grids[$p]===0&&!$this->_isRepeating($p)){
array_push($a,$p);
}else{
array_push($a,-1);
}
$p=$curPos+$this->_w;
if($p<count($this->_grids)&&$this->_grids[$p]===0&&!$this->_isRepeating($p)){
array_push($a,$p);
}else{
array_push($a,-1);
}
$p=$curPos-1;
if(($curPos%$this->_w)!=0&&$this->_grids[$p]===0&&!$this->_isRepeating($p)){
array_push($a,$p);
}else{
array_push($a,-1);
}
return$a;
}
privatefunction_noStep(){
$l=count($this->_targetSteps);
for($i=0;$i<$l;$i++){
if($this->_targetSteps[$i]!=-1)returnfalse;
}
returntrue;
}
privatefunction_step($curPos){
$this->_targetSteps=$this->_getTargetSteps($curPos);
if($this->_noStep()){
if(count($this->_walkHistory)>0){
$tmp=array_pop($this->_walkHistory);
}else{
returnfalse;
}
array_push($this->_walkHistory2,$tmp);
return$this->_step($tmp);
}
$r=rand(0,3);
while($this->_targetSteps[$r]==-1){
$r=rand(0,3);
}
$nextPos=$this->_targetSteps[$r];
$isCross=false;
if($this->_grids[$nextPos]!=0)
$isCross=true;
if($r==0){
$this->_grids[$curPos]^=1;
$this->_grids[$nextPos]^=4;
}elseif($r==1){
$this->_grids[$curPos]^=2;
$this->_grids[$nextPos]^=8;
}elseif($r==2){
$this->_grids[$curPos]^=4;
$this->_grids[$nextPos]^=1;
}elseif($r==3){
$this->_grids[$curPos]^=8;
$this->_grids[$nextPos]^=2;
}
array_push($this->_walkHistory,$curPos);
return$isCross?false:$nextPos;
}
privatefunction_isRepeating($p){
$l=count($this->_walkHistory);
for($i=0;$i<$l;$i++){
if($this->_walkHistory[$i]==$p)returntrue;
}
$l=count($this->_walkHistory2);
for($i=0;$i<$l;$i++){
if($this->_walkHistory2[$i]==$p)returntrue;
}
returnfalse;
}
privatefunction_getNext0(){
$l=count($this->_grids);
for($i=0;$i<=$l;$i++){
if($this->_grids[$i]==0)return$i;
}
return-1;
}
privatefunction_init(){
$this->_grids=array();
for($y=0;$y<$this->_h;$y++){
for($x=0;$x<$this->_w;$x++){
array_push($this->_grids,0);
}
}
return$this;
}
}
A*寻路算法
classAStar{
//A-star
private$_open;
private$_closed;
private$_start;
private$_end;
private$_grids;
private$_w;
private$_h;
//Construct
publicfunctionAStar(){
$this->_w=null;
$this->_h=null;
$this->_grids=null;
}
publicfunctionset($width,$height,$grids){
$this->_w=$width;
$this->_h=$height;
$this->_grids=$grids;
return$this;
}
//迷宫中寻路
publicfunctionsearch($start=false,$end=false){
return$this->_search($start,$end);
}
/**
|---------------------------------------------------------------
|自动寻路-A-star算法
|---------------------------------------------------------------
*/
publicfunction_search($start=false,$end=false){
if($start!==false)$this->_start=$start;
if($end!==false)$this->_end=$end;
$_sh=$this->_getH($start);
$point['i']=$start;
$point['f']=$_sh;
$point['g']=0;
$point['h']=$_sh;
$point['p']=null;
$this->_open[]=$point;
$this->_closed[$start]=$point;
while(0<count($this->_open)){
$minf=false;
foreach($this->_openas$key=>$maxNode){
if($minf===false||$minf>$maxNode['f']){
$minIndex=$key;
}
}
$nowNode=$this->_open[$minIndex];
unset($this->_open[$minIndex]);
if($nowNode['i']==$this->_end){
$tp=array();
while($nowNode['p']!==null){
array_unshift($tp,$nowNode['p']);
$nowNode=$this->_closed[$nowNode['p']];
}
array_push($tp,$this->_end);
break;
}
$this->_setPoint($nowNode['i']);
}
$this->_closed=array();
$this->_open=array();
return$tp;
}
privatefunction_setPoint($me){
$point=$this->_grids[$me];
//所有可选方向入队列
if($point&1){
$next=$me-$this->_w;
$this->_checkPoint($me,$next);
}
if($point&2){
$next=$me+1;
$this->_checkPoint($me,$next);
}
if($point&4){
$next=$me+$this->_w;
$this->_checkPoint($me,$next);
}
if($point&8){
$next=$me-1;
$this->_checkPoint($me,$next);
}
}
privatefunction_checkPoint($pNode,$next){
if($this->_closed[$next]){
$_g=$this->_closed[$pNode]['g']+$this->_getG($next);
if($_g<$check['g']){
$this->_closed[$next]['g']=$_g;
$this->_closed[$next]['f']=$this->_closed[$next]['g']+$this->_closed[$next]['h'];
$this->_closed[$next]['p']=$pNode;
}
}else{
$point['p']=$pNode;
$point['h']=$this->_getH($next);
$point['g']=$this->_getG($next);
$point['f']=$point['h']+$point['g'];
$point['i']=$next;
$this->_open[]=$point;
$this->_closed[$next]=$point;
}
}
privatefunction_getG($point){
returnabs($this->_start-$point);
}
privatefunction_getH($point){
returnabs($this->_end-$point);
}
}
完整实例代码点击此处本站下载。
有需要大家可以直接下demo，看看效果！
希望本文所述对大家的php程序设计有所帮助。