php生成迷宫和迷宫寻址算法实例 - 探讨

Question

本帖最后由 westring 于 2010-11-01 21:40:25 编辑

Answer 1

看图：
图中红箭头处有下 “单墙”，在寻找通路，搜索到此格时，左侧判断为无墙，则转入 0，0 格继续搜索，此时程序进入死循环。导致此问题的原因：生成迷宫的起始单元格为0，0格，而拆墙时，将此格复制到$maze2,但未将此格从$maze中移除，后续的流程中，再次搜索到0，0 格时，再次将0，0格移至$maze2,导致原来数据丢失，拆墙信息不一至，出现了单墙。解决方法很简章：
方法1：将原来的
if(empty($maze2[$x][$y])) $maze2[$x][$y] = $maze[$x][$y];
代码改为
if(empty($maze2[$x][$y])){
 $maze2[$x][$y] = $maze[$x][$y];
 unset($maze[$x][$y]); 即可。
方法2：进一步研究，发现if(empty($maze2[$x][$y])) $maze2[$x][$y] = $maze[$x][$y];
代码只在从0，0格搜索时，执行了一次，放在循环体内，每次都要判断，降低了程序执行效率；将该代码放到进入循环前，并将原代码删除即可。
如下
$x = $y = 0;//初始入口
$maze2[0][0] = $maze[0][0];//增加
unset($maze[0][0]);//增加
while(count($maze)>0{
    $tmpArr = array();
    foreach($_posArr as $val){
        $nx = $x + $val[0];
        $ny = $y + $val[1];
        if(isset($maze[$nx][$ny])){//未破墙过的格子
            $tmpArr[] = array($nx, $ny);
        }
    }
    if($tmpArr){//有未破墙的格子，随机出一个，破墙
        list($nx, $ny) = $tmpArr[array_rand($tmpArr)];
        $maze2[$nx][$ny] = $maze[$nx][$ny];
//删除       if(empty($maze2[$x][$y])) $maze2[$x][$y] = $maze[$x][$y];

Answer 2

<?php
header('Content-Type: text/html; charset=GB2312');
error_reporting(E_ALL);//宫格迷宫
define('M',50);//横向
define('N',40);//纵向
define("S", 4);//迷宫格大小
define('DEBUG',true);//$_posArr = array(array(0, -1), array(1, 0), array(0, 1), array(-1, 0));//当前点寻址的四个xy方向 上右下左
//生成迷宫
if( defined( 'DEBUG') ) echo '开始生成迷宫: ' . microtime() .'<br>';
$maze = array();
$mazeUnit = array(1, 1, 1, 1);//上右下左
for($x=0; $x<=M; $x++){
    for($y=0; $y<=N; $y++){
        $maze[$x][$y] = $mazeUnit;
    }
}
$maze2 = array();//破墙后的已访问格子
$mazeOrder = array();//破墙顺序
$x = $y = 0;//初始入口
$maze2[0][0] = $maze[0][0];
unset($maze[0][0]);
while(count($maze)>0)
{
    $tmpArr = array();
    foreach($_posArr as $val)
    {
        $nx = $x + $val[0];
        $ny = $y + $val[1];
        if(isset($maze[$nx][$ny]))  //未破墙过的格子
        {
            $tmpArr[] = array($nx, $ny);
        }
    }
    if($tmpArr){//有未破墙的格子，随机出一个，破墙
        list($nx, $ny) = $tmpArr[array_rand($tmpArr)];
        $maze2[$nx][$ny] = $maze[$nx][$ny];
$key = array_search(array($nx - $x, $ny - $y),$_posArr);
        $maze2[$x][$y][$key] = 0;//原格子破墙
        $maze2[$nx][$ny][($key+2)%4] = 0;//新格子破墙
        //设置新的当前格后返回继续while循环
        $x = $nx;
        $y = $ny;
        $mazeOrder[] = array($x, $y);
        unset($maze[$x][$y]);//去掉已破墙的格子
        if(empty($maze[$x])) unset($maze[$x]);
    }else{//当前xy周围不存在未破墙的格子，返回上一个格子继续破墙
        array_pop($mazeOrder);
        if($mazeOrder) list($x, $y) = $mazeOrder[count($mazeOrder) - 1];
    }
}
//留出出口
$maze = $maze2;
$maze[0][0][3] = 0;
$maze[M][N][1] = 0;if( defined( 'DEBUG') ) echo '生成迷宫结束，开始寻找通路: ' . microtime() .'<br>';$pathArr = array();findPath();
if( defined( 'DEBUG') ) echo '寻找通路结束，开始绘图: ' . microtime() .'<br>';if( !is_array ($pathArr)) 
$pathArr = array(array(-1, -1));
$pathArr[] = array(M + 1, N);
printMaze($maze, $pathArr);
if( defined( 'DEBUG') ) echo '绘图结束: ' . microtime() .'<br>';echo "<img src='maze.png'> <a href='javascript:location.reload();' >刷新</a><br>";//打印迷宫和寻址结果by [email protected]
function printMaze($maze, $pathArr){
    $im = ImageCreate((M + 1) * S + 1, (N + 1) * S + 1);
    $bg = ImageColorAllocate($im, 236, 233, 216);
    $pathColor=ImageColorAllocate($im, 255, 0, 0);
    $exitColor=ImageColorAllocate($im, 134, 255, 0);
    $borderColor = ImageColorAllocate($im, 0, 0, 0);
    ImageRectangle($im, 0, 0, (M + 1) * S, (N + 1) * S, $borderColor);//包边
    ImageLine($im, 0, 0, 0, S, $bg);//右上边开口
    ImageLine($im, (M + 1) * S, N * S, (M + 1) * S, (N + 1) * S, $bg);//左下边开口
    foreach($maze as $x=>$xarr){//生成格子
        foreach($xarr as $y=>$unit){
            if($unit[0]) ImageLine($im, $x * S , $y * S  , ($x + 1) * S, $y * S, $borderColor);            //上有线
            if($unit[1]) ImageLine($im, ($x + 1) * S , $y * S, ($x + 1) * S, ($y + 1) * S, $borderColor);//右有线
            if($unit[2]) ImageLine($im, $x * S, ($y + 1) * S , ($x + 1) * S, ($y + 1) * S , $borderColor);//下有线
            if($unit[3]) ImageLine($im, $x * S , $y * S, $x * S , ($y + 1) * S, $borderColor);            //左有线
        }
    }
//   ImagePNG($im, 'maze1.png');
   $ox = -1;
   $oy = 0;
//imagesetthickness($im,2);
   foreach($pathArr as $pt) 
   {
$x = $pt[0]; $y = $pt[1];
ImageLine($im,  $ox * S + 0.5 * S , $oy * S + 0.5 * S ,  $x * S + 0.5 * S , $y * S + 0.5 * S, $pathColor);
$ox = $x;
$oy = $y;
   }
   ImagePNG($im, 'maze.png');
   ImageDestroy($im);
}function findPath()
{
global $_posArr;
global $maze;
global $pathArr;
$x = 0; 
$y = 0; 
$key = 0 ;
$fromxy = array(-1,0);
array_push( $pathArr, array($x,$y,$key,$fromxy));
while(count( $pathArr) > 0 )
{
if( $x == M && $y == N ) { return ;}
while($key < 4  )
{
if( $maze[$x][$y][$key])  { $key ++ ; continue ;} 
$val = $_posArr[$key]; 
$nx = $x + $val[0];
$ny = $y + $val[1];
    if(($nx < 0 || $nx > M)||($ny < 0 || $ny > N) || $fromxy == array($nx, $ny)) { $key ++ ; continue ;} 
$fromxy = array($x,$y);
array_push( $pathArr, array($nx,$ny,$key + 1,$fromxy));
$x = $nx;
$y = $ny;
$key = 0;
continue 2;
}
list($x,$y,$key,$fromxy) = array_pop($pathArr);
list($x,$y,$tmp,$fromxy) = $pathArr[count($pathArr)-1];
}
}
?>