本文實現兩大經典算法的 PHP 版本：
代碼採用面向對象封裝，邏輯清晰，可直接集成至遊戲或教學演示項目。
迷宮以二維網格扁平化為一維數組 $grids，每個單元格用 4 位掩碼表示四面牆壁通道：
值為 0 表示未訪問，非 0 表示已開通相應方向。
<?php
class Maze {
private $w, $h, $grids = [];
private $walkHistory = [], $walkHistory2 = [], $targetSteps = [];
public function set($width = 6, $height = 6) {
$this->w = max(1, $width);
$this->h = max(1, $height);
return $this;
}
public function create() {
$this->_init();
$this->_walk(rand(0, count($this->grids) - 1));
return $this;
}
public function get() { return $this->grids; }
// 獲取死胡同（僅一面通道）用作起終點候選
public function block($n = 0, $rand = false) {
$deadEnds = [];
foreach ($this->grids as $i => $v) {
if (in_array($v, [1,2,4,8])) $deadEnds[] = $i;
}
if ($rand) shuffle($deadEnds);
if ($n == 0) return $deadEnds;
return $n == 1 ? array_pop($deadEnds) : array_slice($deadEnds, 0, $n);
}
private function _init() {
$this->grids = array_fill(0, $this->w * $this->h, 0);
}
private function _walk($startPos) {
$this->walkHistory = []; $this->walkHistory2 = [];
$cur = $startPos;
while ($this->_getNext0() != -1) {
$cur = $this->_step($cur);
if ($cur === false) break;
}
}
// 獲取四個方向可走的下一步
private function _getTargetSteps($cur) {
$steps = [-1, -1, -1, -1]; // 上右下左
$w = $this->w;
// 上
$p = $cur - $w;
if ($p >= 0 && $this->grids[$p] === 0 && !$this->_isRepeating($p)) $steps[0] = $p;
// 右
$p = $cur + 1;
if ($p % $w != 0 && $this->grids[$p] === 0 && !$this->_isRepeating($p)) $steps[1] = $p;
// 下
$p = $cur + $w;
if ($p < count($this->grids) && $this->grids[$p] === 0 && !$this->_isRepeating($p)) $steps[2] = $p;
// 左
$p = $cur - 1;
if ($cur % $w != 0 && $this->grids[$p] === 0 && !$this->_isRepeating($p)) $steps[3] = $p;
return $steps;
}
private function _noStep() {
foreach ($this->targetSteps as $v) if ($v != -1) return false;
return true;
}
private function _step($cur) {
$this->targetSteps = $this->_getTargetSteps($cur);
if ($this->_noStep()) {
if (empty($this->walkHistory)) return false;
$back = array_pop($this->walkHistory);
$this->walkHistory2[] = $back;
return $this->_step($back); // 回溯
}
// 隨機選擇一個可用方向
$r = rand(0, 3);
while ($this->targetSteps[$r] == -1) $r = rand(0, 3);
$next = $this->targetSteps[$r];
// 打通雙向通道
$walls = [
[1, 4], // 上: 當前開上(1), 下一開下(4)
[2, 8], // 右: 當前開右(2), 下一開左(8)
[4, 1], // 下
[8, 2], // 左
];
list($curWall, $nextWall) = $walls[$r];
$this->grids[$cur] ^= $curWall;
$this->grids[$next] ^= $nextWall;
$this->walkHistory[] = $cur;
return $next;
}
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;
}
}
?><?php
class AStar {
private $w, $h, $grids;
private $open = [], $closed = [];
private $start, $end;
public function set($width, $height, $grids) {
$this->w = $width; $this->h = $height; $this->grids = $grids;
return $this;
}
public function search($start = false, $end = false) {
if ($start !== false) $this->start = $start;
if ($end !== false) $this->end = $end;
$this->open = []; $this->closed = [];
$this->open[] = ['i'=>$this->start, 'g'=>0, 'h'=>$this->_h($this->start), 'f'=>$this->_h($this->start), 'p'=>null];
$this->closed[$this->start] = end($this->open);
while (!empty($this->open)) {
// 找 open 中 f 最小的節點
$minIdx = 0; $minF = PHP_INT_MAX;
foreach ($this->open as $k => $node) {
if ($node['f'] < $minF) { $minF = $node['f']; $minIdx = $k; }
}
$cur = $this->open[$minIdx];
unset($this->open[$minIdx]);
$this->open = array_values($this->open); // 重建索引
if ($cur['i'] == $this->end) {
// 重構路徑
$path = [];
while ($cur['p'] !== null) {
array_unshift($path, $cur['p']);
$cur = $this->closed[$cur['p']];
}
$path[] = $this->end;
$this->open = $this->closed = [];
return $path;
}
$this->_expand($cur['i']);
}
return []; // 無路徑
}
private function _expand($idx) {
$val = $this->grids[$idx];
$dirs = [
1 => -$this->w, // 上
2 => 1, // 右
4 => $this->w, // 下
8 => -1, // 左
];
foreach ($dirs as $bit => $delta) {
if ($val & $bit) {
$next = $idx + $delta;
$this->_checkPoint($idx, $next);
}
}
}
private function _checkPoint($from, $next) {
$g = $this->closed[$from]['g'] + 1; // 均勻代價 1
if (isset($this->closed[$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'] = $from;
}
} else {
$node = [
'i' => $next,
'g' => $g,
'h' => $this->_h($next),
'f' => $g + $this->_h($next),
'p' => $from
];
$this->open[] = $node;
$this->closed[$next] = $node;
}
}
// 啟發函數：曼哈頓距離（網格無對角線）
private function _h($pos) {
$x1 = $pos % $this->w; $y1 = intdiv($pos, $this->w);
$x2 = $this->end % $this->w; $y2 = intdiv($this->end, $this->w);
return abs($x1 - $x2) + abs($y1 - $y2);
}
}
?><?php
// 1. 生成 20x20 迷宮
$maze = new Maze();
$maze->set(20, 20)->create();
$grids = $maze->get();
// 2. 選取兩個死胡同作為起點終點
$blocks = $maze->block(2, true); // 隨機取 2 個
$start = $blocks[0]; $end = $blocks[1];
// 3. A* 尋路
$astar = new AStar();
$astar->set(20, 20, $grids);
$path = $astar->search($start, $end);
echo "起點: $start, 終點: $end\n";
echo "路徑長度: " . count($path) . " 步\n";
echo "路徑節點: " . implode(' -> ', $path) . "\n";
// 4. 可視化輸出（簡易文本）
$display = $grids;
foreach ($path as $p) $display[$p] = '*'; // 標記路徑
$display[$start] = 'S'; $display[$end] = 'E';
for ($y=0; $y<20; $y++) {
for ($x=0; $x<20; $x++) echo str_pad($display[$y*20+$x] ?? ' ', 3);
echo "\n";
}
?>| 算法 | 時間複雜度 | 空間複雜度 | PHP 優化建議 |
|---|---|---|---|
| DFS 迷宮生成 | O(W×H) | O(W×H) | 使用位運算、避免函數調用開銷、大迷宮考慮 C 擴展 |
| A* 尋路 | O((W×H) log(W×H)) | O(W×H) | Open 列表用最小堆，Closed 用數組/哈希，啟發函數內聯 |
PHP 雖非高性能計算首選，但憑藉靈活的數組與面向對象特性，足以實現教學級、輕量級遊戲邏輯。生產環境高併發遊戲服務建議使用 C++/Go/Rust 實現核心算法，PHP 做業務協調層。
