本文实例讲述了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); } }
完整实例代码点击此处本站下载。
有需要大家可以直接下demo,看看效果!
希望本文所述对大家的php程序设计有所帮助。
本文向大家介绍java图的深度优先遍历实现随机生成迷宫,包括了java图的深度优先遍历实现随机生成迷宫的使用技巧和注意事项,需要的朋友参考一下 最近经常在机房看同学在玩一个走迷宫的游戏,比较有趣,自己也用java写一个实现随机生成迷宫的算法,其实就是一个图的深度优先遍历算法.基本思想就是,迷宫中的每个点都有四面墙,然后呢。 1、从任意一点开始访问(我的算法中固定是从(0,0)点开始),往四个方向中
下面是DFS算法的伪代码http://www.mazeworks.com/mazegen/mazetut/index.htm 创建一个CellStack(后进先出)来保存单元格位置列表 设置TotalCells=网格中的单元格数 随机选择一个单元格并将其命名为CurrentCell 设置VisitedCells=1 在探访牢房时 别的 从CellStack中弹出最近的单元格条目 使其成为Curre
本文向大家介绍10分钟教你用python动画演示深度优先算法搜寻逃出迷宫的路径,包括了10分钟教你用python动画演示深度优先算法搜寻逃出迷宫的路径的使用技巧和注意事项,需要的朋友参考一下 深度优先算法(DFS 算法)是什么? 寻找起始节点与目标节点之间路径的算法,常用于搜索逃出迷宫的路径。主要思想是,从入口开始,依次搜寻周围可能的节点坐标,但不会重复经过同一个节点,且不能通过障碍节点。如果走到
本文向大家介绍Java项目实现寻找迷宫出路,包括了Java项目实现寻找迷宫出路的使用技巧和注意事项,需要的朋友参考一下 本文实例为大家分享了Java实现寻找迷宫出路的具体代码,供大家参考,具体内容如下 项目名称 寻找迷宫出路 项目描述 给定一个自定义迷宫,0表示能通过,1表示不能通过。通过程序找出正确的迷宫出路,并将正确的路线改为2输出。 代码实现 测试类 主类:实现主方法 MazeNode:结点
我基于Prim的算法编写了一个迷宫生成器程序: 该算法是Prim算法的随机版本。 从满是墙的网格开始 (来自维基百科) 我已经理解了算法,我只是停留在这一部分:“知道相邻单元是否构成迷宫的一部分”(这意味着,首先获取相邻单元),因为这些单元实际上是树的节点(迷宫,一个二维单元阵列),而墙是这些节点之间的边,我认为有必要用一对点(x,y)来识别每面墙。我如何知道两个电池是否由一堵墙连接?(请记住,每
我正在尝试实现DFS回溯算法,该算法涉及利用维基百科上的堆栈(而不是递归算法)。我试图生成一个由0和1组成的迷宫,其中1代表一堵墙,0代表一条可用路径。对于迷宫中不是墙的任何给定空间,必须始终有一条有效的路径,可以从任何其他非墙单元格到达。 我从一个迷宫开始,它是一个二维大小的迷宫阵列[15][20],然后按照算法将需要标记为已正确访问的单元格标记为已访问。最初,所有单元格(不包括外部边框)都标记