採用樹的深度遍歷原理生成迷宮，特點：
<?php
class Maze {
private $_w, $_h, $_grids, $_walkHistory, $_walkHistory2, $_targetSteps;
public function __construct() {
$this->_w = 6;
$this->_h = 6;
$this->_grids = [];
}
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) {
$return = [];
foreach ($this->_grids as $i => $v) {
if ($v == 1 || $v == 2 || $v == 4 || $v == 8) $return[] = $i;
}
if ($rand) shuffle($return);
if ($n == 0) return $return;
return $n == 1 ? array_pop($return) : array_slice($return, 0, $n);
}
// 核心生成邏輯
private function _walk($startPos) {
$this->_walkHistory = $this->_walkHistory2 = [];
$curPos = $startPos;
while ($this->_getNext0() != -1) {
$curPos = $this->_step($curPos);
if ($curPos === false) break;
}
return $this;
}
private function _getTargetSteps($curPos) {
$a = [];
// 上、右、下、左 四個方向
$dirs = [-$this->_w, 1, $this->_w, -1];
foreach ($dirs as $idx => $offset) {
$p = $curPos + $offset;
$valid = ($p >= 0 && $p < count($this->_grids) && $this->_grids[$p] === 0 && !$this->_isRepeating($p));
// 邊界檢查：左/右邊界
if ($idx == 1 && $p % $this->_w == 0) $valid = false;
if ($idx == 3 && ($curPos % $this->_w) == 0) $valid = false;
$a[] = $valid ? $p : -1;
}
return $a;
}
private function _noStep() {
foreach ($this->_targetSteps as $v) if ($v != -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 = $this->_grids[$nextPos] != 0;
// 位元操作打通牆壁：1=上, 2=右, 4=下, 8=左
$wallMap = [
0 => [$curPos => 1, $nextPos => 4],
1 => [$curPos => 2, $nextPos => 8],
2 => [$curPos => 4, $nextPos => 1],
3 => [$curPos => 8, $nextPos => 2],
];
foreach ($wallMap[$r] as $pos => $bit) {
$this->_grids[$pos] ^= $bit;
}
array_push($this->_walkHistory, $curPos);
return $isCross ? false : $nextPos;
}
private function _isRepeating($p) {
return in_array($p, $this->_walkHistory) || in_array($p, $this->_walkHistory2);
}
private function _getNext0() {
foreach ($this->_grids as $i => $v) if ($v == 0) return $i;
return -1;
}
private function _init() {
$this->_grids = [];
for ($y = 0; $y < $this->_h; $y++) {
for ($x = 0; $x < $this->_w; $x++) {
array_push($this->_grids, 0);
}
}
return $this;
}
}
?>
<?php
class AStar {
private $_open, $_closed, $_start, $_end, $_grids, $_w, $_h;
public function __construct() {
$this->_w = $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);
}
private function _search($start = false, $end = false) {
if ($start !== false) $this->_start = $start;
if ($end !== false) $this->_end = $end;
$point = [
'i' => $start,
'g' => 0,
'h' => $this->_getH($start),
'f' => $this->_getH($start),
'p' => null
];
$this->_open[] = $point;
$this->_closed[$start] = $point;
while (count($this->_open) > 0) {
// 找 f 值最小的節點
$minIndex = null;
$minF = null;
foreach ($this->_open as $k => $node) {
if ($minF === null || $node['f'] < $minF) {
$minF = $node['f'];
$minIndex = $k;
}
}
$nowNode = $this->_open[$minIndex];
unset($this->_open[$minIndex]);
if ($nowNode['i'] == $this->_end) {
// 重構路徑
$path = [];
while ($nowNode['p'] !== null) {
array_unshift($path, $nowNode['p']);
$nowNode = $this->_closed[$nowNode['p']];
}
array_push($path, $this->_end);
$this->_closed = $this->_open = [];
return $path;
}
$this->_setPoint($nowNode['i']);
}
$this->_closed = $this->_open = [];
return [];
}
private function _setPoint($me) {
$grid = $this->_grids[$me];
// 四個方向：上右下左
if ($grid & 1) $this->_checkPoint($me, $me - $this->_w);
if ($grid & 2) $this->_checkPoint($me, $me + 1);
if ($grid & 4) $this->_checkPoint($me, $me + $this->_w);
if ($grid & 8) $this->_checkPoint($me, $me - 1);
}
private function _checkPoint($pNode, $next) {
if (isset($this->_closed[$next])) {
$g = $this->_closed[$pNode]['g'] + $this->_getG($next);
if ($g < $this->_closed[$next]['g']) {
$this->_closed[$next]['g'] = $g;
$this->_closed[$next]['f'] = $g + $this->_closed[$next]['h'];
$this->_closed[$next]['p'] = $pNode;
}
} else {
$point = [
'i' => $next,
'p' => $pNode,
'h' => $this->_getH($next),
'g' => $this->_getG($next),
'f' => 0
];
$point['f'] = $point['h'] + $point['g'];
$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); }
}
?>
<?php $maze = new Maze(); $maze->set(20, 20)->create(); $grids = $maze->get(); $blocks = $maze->block(2, true); // 取兩個隨機死胡同作為起終點 $start = $blocks[0]; $end = $blocks[1]; $astar = new AStar(); $astar->set(20, 20, $grids); $path = $astar->search($start, $end); echo "起點: $start, 終點: $end\n"; echo "路徑長度: " . count($path) . "\n"; print_r($path); ?>
abs(start-end)）作為 H 值，適配網格地圖
