Maison développement back-end tutoriel php php生成迷宫和迷宫寻址算法实例解决思路

php生成迷宫和迷宫寻址算法实例解决思路

Jun 13, 2016 pm 01:40 PM
array

php生成迷宫和迷宫寻址算法实例
较之前的终于有所改善。生成迷宫的算法和寻址算法其实是一样。只是一个用了遍历一个用了递归。参考了网上的Mike Gold的算法。

PHP code
<!--

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->
<?php //zairwolf z@cot8.com
header('Content-Type: text/html; charset=utf-8');
error_reporting(E_ALL);

//n宫格迷宫
define('M', 39);//宫数
define("S", 20);//迷宫格大小
$_posArr = array(array(0, -1), array(1, 0), array(0, 1), array(-1, 0));//当前点寻址的四个xy方向 上右下左

//生成迷宫
$maze = array();
$mazeUnit = array(1, 1, 1, 1);//上右下左
for($x=0; $x<=M; $x++){
    for($y=0; $y<=M; $y++){
        $maze[$x][$y] = $mazeUnit;
    }
}
$maze2 = array();//破墙后的已访问格子
$mazeOrder = array();//破墙顺序
$x = $y = 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];
        $pos = array($nx - $x, $ny - $y);
        foreach($_posArr as $key=&gt;$val){//循环四个方向,找出需要破的墙
            if($pos == $val) {
                $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][M][1] = 0;

//寻址
$pathArr = findPath($maze, 0, 0, false);
printMaze($maze, $pathArr);

echo "<img  src="maze.png" alt=" php生成迷宫和迷宫寻址算法实例解决思路 " > <a href="javascript:;" onclick="location.reload();">刷新</a>";

//打印迷宫和寻址结果by z@cot8.com
function printMaze($maze, $pathArr){
    $im = ImageCreate((M + 1) * S + 1, (M + 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, (M + 1) * S, $borderColor);//包边
    ImageLine($im, 0, 0, 0, S, $bg);//右上边开口
    ImageLine($im, (M + 1) * S, M * S, (M + 1) * S, (M + 1) * S, $bg);//左下边开口
    foreach($maze as $x=&gt;$xarr){//生成格子
        foreach($xarr as $y=&gt;$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);//左有线
            //if(in_array(array($x, $y), $pathArr)) ImageFilledEllipse($im, $x * S + S/2, $y * S + S/2, S, S, $pathColor);//寻址格
            if(in_array(array($x, $y), $pathArr)) ImageString($im, 1, $x * S + S/5, $y * S + S/5, array_search(array($x, $y), $pathArr), $pathColor);//寻址格
        }
    }
    ImagePNG($im, 'maze.png');
    ImageDestroy($im);
}

//寻址函数 z@cot8.com
function findPath($maze, $x, $y, $fromxy){
    global $_posArr;
    if($x == M &amp;&amp; $y == M){//到达出口
        Return array(array($x, $y));
    }
    foreach($_posArr as $key=&gt;$val){
        if($maze[$x][$y][$key]) continue;//为1则不通
        $nx = $x + $val[0];
        $ny = $y + $val[1];
        if(!isset($maze[$nx][$ny]) || $fromxy == array($nx, $ny)) continue;//边界超出或为来源点
        if($pathArr = findPath($maze, $nx, $ny, array($x, $y))) {
            array_unshift($pathArr, array($x, $y));
            Return $pathArr;//能到达出口
        }
    }
    Return false;
}


Copier après la connexion


------解决方案--------------------
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Article chaud

Repo: Comment relancer ses coéquipiers
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Combien de temps faut-il pour battre Split Fiction?
3 Il y a quelques semaines By DDD
R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
1 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Comment obtenir des graines géantes
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌

Article chaud

Repo: Comment relancer ses coéquipiers
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Combien de temps faut-il pour battre Split Fiction?
3 Il y a quelques semaines By DDD
R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
1 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Comment obtenir des graines géantes
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌

Tags d'article chaud

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Trier le tableau à l'aide de la fonction Array.Sort en C# Trier le tableau à l'aide de la fonction Array.Sort en C# Nov 18, 2023 am 10:37 AM

Trier le tableau à l'aide de la fonction Array.Sort en C#

Méthode simple et claire pour utiliser la fonction PHP array_merge_recursive() Méthode simple et claire pour utiliser la fonction PHP array_merge_recursive() Jun 27, 2023 pm 01:48 PM

Méthode simple et claire pour utiliser la fonction PHP array_merge_recursive()

Comment utiliser la fonction array_combine en PHP pour combiner deux tableaux en un tableau associatif Comment utiliser la fonction array_combine en PHP pour combiner deux tableaux en un tableau associatif Jun 26, 2023 pm 01:41 PM

Comment utiliser la fonction array_combine en PHP pour combiner deux tableaux en un tableau associatif

Explication détaillée de l'utilisation de la fonction PHP array_fill() Explication détaillée de l'utilisation de la fonction PHP array_fill() Jun 27, 2023 am 08:42 AM

Explication détaillée de l'utilisation de la fonction PHP array_fill()

Comment utiliser le module Array en Python Comment utiliser le module Array en Python May 01, 2023 am 09:13 AM

Comment utiliser le module Array en Python

Quelles sont les causes courantes d'ArrayStoreException en Java ? Quelles sont les causes courantes d'ArrayStoreException en Java ? Jun 25, 2023 am 09:48 AM

Quelles sont les causes courantes d'ArrayStoreException en Java ?

Introduction à l'utilisation de la fonction PHP array_change_key_case() Introduction à l'utilisation de la fonction PHP array_change_key_case() Jun 27, 2023 am 10:43 AM

Introduction à l'utilisation de la fonction PHP array_change_key_case()

Introduction à l'utilisation de la fonction PHP array_flip() Introduction à l'utilisation de la fonction PHP array_flip() Jun 27, 2023 am 08:24 AM

Introduction à l'utilisation de la fonction PHP array_flip()

See all articles