這篇文章主要介紹了PHP樹的深度編歷生成迷宮及A*自動(dòng)尋路算法,實(shí)例分析了php實(shí)現(xiàn)A*尋路算法的技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下

本文實(shí)例講述了PHP樹的深度編歷生成迷宮及A*自動(dòng)尋路算法。分享給大家供大家參考。具體分析如下：

有一同事推薦了三思的迷宮算法，看了感覺還不錯(cuò)，就轉(zhuǎn)成php

三思的迷宮算法是采用樹的深度遍歷原理，這樣生成的迷宮相當(dāng)?shù)募?xì)，而且死胡同數(shù)量相對(duì)較少！

任意兩點(diǎn)之間都存在唯一的一條通路。

至于A*尋路算法是最大眾化的一全自動(dòng)尋路算法

廢話不多說，貼上帶代碼

迷宮生成類：

代碼如下:

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();

}

// 設(shè)置迷宮大小

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 ));

}

// 獲取死胡同點(diǎn)

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;

}

}

// 隨機(jī)取點(diǎn)

if ( $rand ) shuffle($return);

if ( $n == 0 ) return $return;

if ( $n == 1 ) {

return array_pop($return);

} else {

return array_slice($return, 0, $n);

}

}

/**

|---------------------------------------------------------------

| 生成迷宮的系列函數(shù)

|---------------------------------------------------------------

*/

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);

}

/**

|---------------------------------------------------------------

| 自動(dòng)尋路 - 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];

// 所有可選方向入隊(duì)列

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);

}

}

完整實(shí)例代碼點(diǎn)擊此處本站下載。

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

希望本文所述對(duì)大家的php程序設(shè)計(jì)有所幫助。

更多信息請(qǐng)查看IT技術(shù)專欄