php生成迷宫和迷宫寻址算法实例 - 探讨 本帖最后由 westring 于 2010-11-01 21:40:25 编辑 解决方案 » 免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货 看图:图中红箭头处有下 “单墙”,在寻找通路,搜索到此格时,左侧判断为无墙,则转入 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]; <?phpheader('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]; }}?> 如果根据数据库里的数据显示不同的图片 bugzilla 请教大家个问题关于global 该怎么选择PHP还是ASP script中怎么做才能调用 php中的变量,如下所示: js菜单与flash冲突 用数据库类比不用数据库类有什么优势? 大家来帮我编译下代码,看那里错了 需要编写一个进销存管理系统 大家来看看这个翻页类如何?欢迎批评雅正....来者有奖:) 怎样理解DISCUZ代码? 输入localhost/phpmyadmin/index.php以后,无论输不输入用户名和密码,都出来一个空页面?
图中红箭头处有下 “单墙”,在寻找通路,搜索到此格时,左侧判断为无墙,则转入 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];
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];
}
}
?>