PHP树的深度编历生成迷宫及A*自动寻路算法实例分析

PHP树的深度编历生成迷宫及A*自动寻路算法实例分析

 这篇文章主要介绍了PHP树的深度编历生成迷宫及A*自动寻路算法,实例分析了php实现A*寻路算法的技巧,具有一定参考借鉴价值,需要的朋友可以参考下

 

 

本文实例讲述了PHP树的深度编历生成迷宫及A*自动寻路算法。分享给大家供大家参考。具体分析如下：

有一同事推荐了三思的迷宫算法，看了感觉还不错，就转成php
三思的迷宫算法是采用树的深度遍历原理，这样生成的迷宫相当的细，而且死胡同数量相对较少！
任意两点之间都存在唯一的一条通路。

至于A*寻路算法是最大众化的一全自动寻路算法

废话不多说，贴上带代码

迷宫生成类：

代码如下:

类迷宫{
// 创建迷宫
私人$_w;
私人$_h;
私人$_grids;
私人$_walkHistory;
私人$_walkHistory2;
私人$_targetSteps;
// 构造
公共函数迷宫（）{
$this->_w = 6;
$this->_h = 6;
$this->_grids = array();
}
// 设置迷宫大小
公共函数集($width = 6, $height = 6) {
if ( $width > 0 ) $this->_w = $width;
if ( $height > 0 ) $this->_h = $height;
返回 $this;
}
// 到达迷宫
公共函数 get() {
返回 $this->_grids;
}
// 生成迷宫
公共函数create() {
$this->_init();
return $this->_walk(rand(0, count($this->_grids) -1 ));
}
// 获取死胡同点
公共函数块($n = 0, $rand = false) {
$l = count($this->_grids);
for( $i = 1; $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);
} 其他 {
return array_slice($return, 0, $n);
}
}
/**
|---------------------------------------------------------------
| 生成迷宫的系列函数
|---------------------------------------------------------------
*/
私有函数 _walk($startPos) {
$this->_walkHistory = array();
$this->_walkHistory2 = array();
$curPos = $startPos;
while ($this->_getNext0() != -1) {
$curPos = $this->_step($curPos);
if ( $curPos === false ) 中断;
}
返回 $this;
}
私有函数 _getTargetSteps($curPos) {
$p = 0;
$a = array();
$p = $curPos - $this->_w;
if ($p > 0 && $this->_grids[$p] === 0 && ! $this->_isRepeating($p)) {
array_push($a, $p);
} 其他 {
array_push($a, -1);
}
$p = $curPos 1;
if ($p % $this->_w != 0 && $this->_grids[$p] === 0 && ! $this->_isRepeating($p)) {
array_push($a, $p);
} 其他 {
array_push($a, -1);
}
$p = $curPos $this->_w;
if ($p _grids) && $this->_grids[$p] === 0 && ! $this->_isRepeating($p)) {
array_push($a, $p);
} 其他 {
array_push($a, -1);
}
$p = $curPos - 1;
if (($curPos % $this->_w) != 0 && $this->_grids[$p] === 0 && ! $this->_isRepeating($p)) {
array_push($a, $p);
} 其他 {
array_push($a, -1);
}
返回 $a;
}
私有函数 _noStep() {
$l = count($this->_targetSteps);
for ($i = 0; $i if ($this->_targetSteps[$i] != -1) return false;
}
返回真；
}
私有函数_step($curPos) {
$this->_targetSteps = $this->_getTargetSteps($curPos);
if ( $this->_noStep() ) {
if ( count($this->_walkHistory) > 0 ) {
$tmp = array_pop($this->_walkHistory);
} 其他 {
返回错误；
}
array_push($this->_walkHistory2, $tmp);
返回 $this->_step($tmp);
}
$r = 兰特(0, 3);
while ( $this->_targetSteps[$r] == -1) {
$r = 兰特(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);
返回 $isCross ？假：$nextPos;
}
私有函数 _isRepeating($p) {
$l = count($this->_walkHistory);
for ($i = 0; $i if ($this->_walkHistory[$i] == $p) return true;
}
$l = count($this->_walkHistory2);
for ($i = 0; $i if ($this->_walkHistory2[$i] == $p) return true;
}
返回错误；
}
私有函数 _getNext0() {
$l = count($this->_grids);

for ($i = 0; $i if ( $this->_grids[$i] == 0) return $i;
}
返回-1;
}
私有函数_init() {
$this->_grids = array();
for ($y = 0; $y _h; $y ) {
for ($x = 0; $x _w; $x ) {
array_push($this->_grids, 0);
}
}
返回 $this;
}
}

 

A*寻路算法

代码如下：

AStar 类{
// A 星
私人$_open;
私人 $_close;
私人 $_start;
私人$_end;
私人$_grids;
私人$_w;
私人$_h;
// 构造
公共函数 AStar(){
$this->_w = null;
$this->_h = null;
$this->_grids = null;
}
公共函数集（$宽度，$高度，$网格）{
$this->_w = $width;
$this->_h = $height;
$this->_grids = $grids;
返回 $this;
}
// 迷宫中寻路
公共函数搜索($start = false, $end = false) {
返回 $this->_search($start, $end);
}
/**
|---------------------------------------------------------------
| 自动寻路 - A-star 算法
|---------------------------------------------------------------
*/
公共函数_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->_close[$start] = $point;
while ( 0 _open) ) {
$minf = false;
foreach( $this->_open as $key => $maxNode ) {
if ( $minf === false || $minf > $maxNode['f'] ) {
$minIndex = $key;
}
}
$nowNode = $this->_open[$minIndex];
取消设置($this->_open[$minIndex]);
if ( $nowNode['i'] == $this->_end ) {
$tp = array();
while( $nowNode['p'] !== null ) {
array_unshift($tp, $nowNode['p']);
$nowNode = $this->_close[$nowNode['p']];
}
array_push($tp, $this->_end);
休息；
}
$this->_setPoint($nowNode['i']);
}
$this->_close = array();
$this->_open = array();
返回 $tp;
}
私有函数 _setPoint($me) {
$point = $this->_grids[$me];
// 所有任选方向入队列
if ( $point & 1 ) {
$next = $me - $this->_w;
$this->_checkPoint($me, $next);
}
if ( $point & 2 ) {
$下一个 = $me 1;
$this->_checkPoint($me, $next);
}
if ( $point & 4 ) {
$next = $me $this->_w;
$this->_checkPoint($me, $next);
}
if ( $point & 8 ) {
$下一个 = $me - 1;
$this->_checkPoint($me, $next);
}
}
私有函数 _checkPoint($pNode, $next) {
if ( $this->_close[$next] ) {
$_g = $this->_close[$pNode]['g'] $this->_getG($next);
if ( $_g $this->_close[$next]['g'] = $_g;
$this->_close[$next]['f'] = $this->_close[$next]['g'] $this->_close[$next]['h'];
$this->_close[$next]['p'] = $pNode;
}
} 其他 {
$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->_close[$next] = $point;
}
}
私有函数 _getG($point) {
return abs($this->_start - $point);
}
私有函数 _getH($point) {
return abs($this->_end - $point);
}
}

 

完整实例代码点击此处本站下载。

有需要的大家可以直接下demo，看看效果！

希望本文对大家的php程序设计有所帮助。