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,$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,-1);
??????? }
??????? $p = $curPos + $this->_w;
??????? if ($p < count($this->_grids) && $this->_grids[$p] === 0 && ! $this->_isRepeating($p)) {
??????????? array_push($a,-1);
??????? }
??????? $p = $curPos - 1;
??????? if (($curPos % $this->_w) != 0 && $this->_grids[$p] === 0 && ! $this->_isRepeating($p)) {
??????????? 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);
??? }
}