PHP树生成迷宫及A*自己主动寻路算法
迷宫算法是採用树的深度遍历原理。这样生成的迷宫相当的细，并且死胡同数量相对较少！
随意两点之间都存在唯一的一条通路。
至于A*寻路算法是最大众化的一全自己主动寻路算法
完整代码已上传，http://download.csdn.net/detail/hello_katty/8885779 ，此处做些简单解释，还须要大家自己思考动手。废话不多说，贴上带代码
迷宫生成类：
/** 生成迷宫类
* @date 2015-07-10
* @edit http://www.lai18.com
* @version 1
**/
class Maze{ // Maze Create private $_w; private $_h; private $_grids; private $_walkHistory; private $_walkHistory2; private $_targetSteps; // Construct public function Maze() { $this->_w = 6; $this->_h = 6; $this->_grids = array(); } // 设置迷宫大小 public function set($width = 6, $height = 6) { if ( $width > 0 ) $this->_w = $width; if ( $height > 0 ) $this->_h = $height; return $this; } // 取到迷宫 public function get() { return $this->_grids; } // 生成迷宫 public function create() { $this->_init(); return $this->_walk(rand(0, count($this->_grids) -1 )); } // 获取死胡同点 public function block($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 ) { return array_pop($return); } else { return array_slice($return, 0, $n); } } /** 生成迷宫的系列函数 */ private function _walk($startPos) { $this->_walkHistory = array(); $this->_walkHistory2 = array(); $curPos = $startPos; while ($this->_getNext0() != -1) { $curPos = $this->_step($curPos); if ( $curPos === false ) break; } return $this; } private function _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; } private function _noStep() { $l = count($this->_targetSteps); for ($i = 0; $i < $l; $i ++) { if ($this->_targetSteps[$i] != -1) return false; } return true; } private function _step($curPos) { $this->_targetSteps = $this->_getTargetSteps($curPos); if ( $this->_noStep() ) { if ( count($this->_walkHistory) > 0 ) { $tmp = array_pop($this->_walkHistory); } else { return false; } 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; } private function _isRepeating($p) { $l = count($this->_walkHistory); for ($i = 0; $i < $l; $i ++) { if ($this->_walkHistory[$i] == $p) return true; } $l = count($this->_walkHistory2); for ($i = 0; $i < $l; $i ++) { if ($this->_walkHistory2[$i] == $p) return true; } return false; } private function _getNext0() { $l = count($this->_grids); for ($i = 0; $i <= $l; $i++ ) { if ( $this->_grids[$i] == 0) return $i; } return -1; } private function _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*寻路算法
/** 寻路算法
* @date 2015-07-10
* @edit http://www.lai18.com
* @version 1
**/
class AStar{ // A-star private $_open; private $_closed; private $_start; private $_end; private $_grids; private $_w; private $_h; // Construct public function AStar(){ $this->_w = null; $this->_h = null; $this->_grids = null; } public function set($width, $height, $grids) { $this->_w = $width; $this->_h = $height; $this->_grids = $grids; return $this; } // 迷宫中寻路 public function search($start = false, $end = false) { return $this->_search($start, $end); } /** 自己主动寻路 - A-star 算法 */ public function _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->_open as $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; } private function _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); } } private function _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; } } private function _getG($point) { return abs($this->_start - $point); } private function _getH($point) { return abs($this->_end - $point); } }
延伸阅读
《编程有用算法实现整理》系列技术文章整理收藏
1算法导论：选择排序的原理与实现
2一道PHP冒泡排序算法笔试题
3WordPress的用户password计算算法
4PHP实现四种经常使用的排序算法
5很直观的数据结构与算法演示
6深入探讨各种背包算法问题
7图解插入排序算法
8图解堆排序Heap Sort算法
9约瑟夫环(Josephus)问题的C++算法模拟
10趣味算法之兔子产子问题
11一些常见算法的JavaScript实现
12趣味算法之猴子吃桃问题
13平方根sqrt()函数的底层算法效率
14二叉搜索树的一些相关算法介绍
15欧几里德算法（辗转相处法）练手
16蚂蚁爬木杆问题的算法思路
17计算机编程中一些重要的算法
18面试中常见的一些算法问题
19JavaScript排序算法之希尔排序
20JavaScript排序算法之堆排序
21JavaScript排序算法之归并排序
22JavaScript排序算法之选择排序
23JavaScript排序算法之高速排序
24JavaScript排序算法之冒泡排序
25JavaScript排序算法之插入排序
26合并排序算法讲解与样例
27丑数Ugly Number查找算法
28求大数阶乘的算法
29各排序算法的C++实现与性能測试
30算法导论中一个蒙提霍尔问题
31实现一个栈并获取其最小元素
32亲身体验一下KMP算法
33面试算法题的高速思考方法
34矩阵逆时针旋转的算法
35Hash魔法：分布式哈希算法
36Hash魔法：一致性 hash 算法
37字符串逆序的各种实现算法
38用递归实现的高速排序
39收集一些top软件公司经典算法面试题
40趣味算法：猴子搬香蕉问题
41一些主流的个性化推荐算法评析
42趣味算法：生男生女的比例
43趣味算法：老鼠试毒瓶问题
44使用PHP内置的DES算法函数实现数据加密解密
45第九话：数据结构与算法的关系
46第12话：什么样的算法才是好算法
47第11话：算法的五个基本特征
48第13话：算法的性能分析
49第10话：什么是算法？
50第16话：算法的空间复杂度
51第15话：算法的最坏情况与平均情况
52第14话：怎样计算算法的时间复杂度
53顺序栈的进栈操作
54顺序栈：栈的顺序存储结构
55栈的定义与大概理解
56栈的抽象数据类型ADT
57链栈：栈的链式存储结构
58链栈的进栈操作
59获取顺序栈的栈顶元素
60顺序栈的出栈操作
61为什么要使用栈这样的数据结构
62链栈的置空操作与推断链栈是否为空
63递归。栈的重要应用之中的一个
64栈是怎样实现递归的
65链栈的出栈操作
66链栈的初始化与遍历
67漫谈递归：递归的思想
68漫谈递归：递归须要满足的两个条件
69漫谈递归：字符串回文现象的递归推断
70漫谈递归：二分查找算法的递归实现
71漫谈递归：递归的效率问题
72漫谈递归：递归与循环
73漫谈递归：循环与迭代是一回事吗？
74漫谈递归：从斐波那契開始了解尾递归
75漫谈递归：尾递归与CPS
76漫谈递归：补充一些Continuation的知识
77漫谈递归：PHP里的尾递归及其优化
78漫谈递归：从汇编看尾递归的优化
79高速排序里的学问：从猜数字開始
80高速排序里的学问：再看看称球问题
81高速排序里的学问：信息熵
82高速排序里的学问：高速排序的过程
83高速排序里的学问：霍尔与高速排序
84高速排序里的学问：霍尔快排的实现
85高速排序里的学问：枢纽元选择与算法效率
86高速排序里的学问：随机化快排
87Java程序猿必须掌握的8大排序算法
88RSA,DSA等加解密算法介绍
89权限项目总结（一）权限设计
