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;

　　}

　　}

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

　　}

　　}