Home >Backend Development >PHP Tutorial >PHP tree deep calendar generation maze and A* automatic pathfinding algorithm example analysis, maze example analysis_PHP tutorial
PHP tree deep calendar generation maze and A* automatic pathfinding algorithm example analysis, maze example analysis_PHP tutorial
- WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOriginal
- 2016-07-13 10:04:331039browse
Example analysis of deep chronological maze generation of PHP trees and A* automatic pathfinding algorithm, maze example analysis
This article describes the deep chronological generation of mazes and A* of PHP trees through examples *Automatic pathfinding algorithm. Share it with everyone for your reference. The specific analysis is as follows:
A colleague recommended Sansi’s maze algorithm. After reading it, I thought it was pretty good, so I converted it to PHP
Sansi's maze algorithm uses the principle of tree depth traversal. The maze generated in this way is quite thin, and the number of dead ends is relatively small!
There is only one path between any two points.
As for the A* pathfinding algorithm, it is the most popular fully automatic pathfinding algorithm
No further nonsense, just paste the code
Maze generation class:
Copy code The code is as follows: 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();
}
//Set the maze size
Public function set($width = 6, $height = 6) {
If ( $width > 0 ) $this->_w = $width;
If ( $height > 0 ) $this->_h = $height;
return $this;
}
// Get the maze
Public function get() {
return $this->_grids;
}
// Generate maze
Public function create() {
$this->_init();
return $this->_walk(rand(0, count($this->_grids) -1 ));
}
// Get the dead end point
Public function block($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;
}
}
// Randomly pick points
if ( $rand ) shuffle($return);
if ( $n == 0 ) return $return;
if ( $n == 1 ) {
return array_pop($return);
} else {
return array_slice($return, 0, $n);
}
}
/**
|------------------------------------------------- ---------------
| | Series of functions to generate maze
|------------------------------------------------- ---------------
*/
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
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
if ($this->_walkHistory[$i] == $p) return true;
}
$l = count($this->_walkHistory2);
for ($i = 0; $i
if ($this->_walkHistory2[$i] == $p) return true;
}
return false;
}
private function _getNext0() {
$l = count($this->_grids);
for ($i = 0; $i
if ( $this->_grids[$i] == 0) return $i;
}
return -1;
}
private function _init() {
$this->_grids = array();
for ($y = 0; $y _h; $y ++) {
for ($x = 0; $x _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);
}
/**
|------------------------------------------------- ---------------
| Automatic path finding - A-star algorithm
|------------------------------------------------- ---------------
*/
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
$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);
}
}
完整实例代码点击此处本站下载。
有需要大家可以直接下demo，看看效果！
希望本文所述对大家的php程序设计有所帮助。