首页 > 代码库 > PHP树生成迷宫及A*自己主动寻路算法
PHP树生成迷宫及A*自己主动寻路算法
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权限项目总结(一)权限设计
延伸阅读
PHP树生成迷宫及A*自己主动寻路算法