PHP如何实现树的深度编历生成迷宫及A*自动寻路算法
发表于:2024-10-20 作者:千家信息网编辑
千家信息网最后更新 2024年10月20日,这篇文章主要为大家展示了"PHP如何实现树的深度编历生成迷宫及A*自动寻路算法",内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下"PHP如何实现树的深度编历生成
千家信息网最后更新 2024年10月20日PHP如何实现树的深度编历生成迷宫及A*自动寻路算法
这篇文章主要为大家展示了"PHP如何实现树的深度编历生成迷宫及A*自动寻路算法",内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下"PHP如何实现树的深度编历生成迷宫及A*自动寻路算法"这篇文章吧。
具体分析如下:
有一同事推荐了三思的迷宫算法,看了感觉还不错,就转成php
三思的迷宫算法是采用树的深度遍历原理,这样生成的迷宫相当的细,而且死胡同数量相对较少!
任意两点之间都存在唯一的一条通路。
至于A*寻路算法是最大众化的一全自动寻路算法
迷宫生成类:
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*寻路算法复制代码 代码如下: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); }}
以上是"PHP如何实现树的深度编历生成迷宫及A*自动寻路算法"这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注行业资讯频道!
迷宫
算法
生成
深度
内容
篇文章
代码
死胡同
学习
帮助
不错
之间
全自动
函数
原理
同事
大小
感觉
数量
方向
数据库的安全要保护哪些东西
数据库安全各自的含义是什么
生产安全数据库录入
数据库的安全性及管理
数据库安全策略包含哪些
海淀数据库安全审计系统
建立农村房屋安全信息数据库
易用的数据库客户端支持安全管理
连接数据库失败ssl安全错误
数据库的锁怎样保障安全
网络安全宣传知识竞赛标语
医院门诊预约挂号软件开发
软件开发属于高新技术财务
cs go官方服务器连接失败
海尔软件开发待遇
曲靖妙推网络技术有限公司
高斯数据库字段长度
网络安全源端鉴别
信息化与网络安全相关论文
艾尔网络技术服务
网络安全检测报告怎么写
北京有道网络技术
计算机网络技术和互联网的区别
wep实现网络安全的重要手段
2020保密与网络安全试题
剑网3服务器排名
是一次数据库
网络通信协议软件开发
河北九善互联网科技有限公司
提高软件开发需求
数据库请销假程序怎么写
网络安全论文的目的及意义
怎样设计数据库功能模块
网络安全合作 致辞
国家铁路局网络安全技术中心
沭阳自动化网络技术厂家价格
单片机软件开发类面试题
网络安全法对人才的要求
软件开发人员跳槽频率
天津pdu服务器电源要多少钱