谈谈PHP树生成迷宫及A*自动寻路算法

迷宫生成类：

/** 生成迷宫类
 * @date 2015-07-10
 * @edit http://www.lai18.com
 * @version 1
 **/
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 _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*寻路算法

/** 寻路算法
 * @date 2015-07-10
 * @edit http://www.lai18.com
 * @version 1
 **/
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 _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);
    }
}