使用「樹的深度遍歷」原理:從隨機起點開始,隨機選擇未訪問的鄰居打通牆壁,回溯直到所有格子連通。產生的迷宮為「完美迷宮」——任意兩點間有且只有一條路徑。
<?php
class Maze {
private $w, $h, $grids = []; // 寬、高、格子狀態 (位元組: 1=上,2=右,4=下,8=左)
private $history = [], $history2 = [];
public function set($w, $h) { $this->w=$w; $this->h=$h; return $this; }
public function create() {
$this->grids = array_fill(0, $this->w * $this->h, 0);
$this->_walk(rand(0, count($this->grids)-1));
return $this;
}
public function get() { return $this->grids; }
// 取得死胡同 (僅一面通路) 供作為入口/出口
public function deadEnds($random = false) {
$ends = [];
foreach ($this->grids as $i => $v) {
$bits = 0;
foreach ([1,2,4,8] as $b) if ($v & $b) $bits++;
if ($bits === 1) $ends[] = $i;
}
if ($random) shuffle($ends);
return $ends;
}
private function _walk($start) {
$this->history = [$start];
$this->history2 = [];
$cur = $start;
while (($next = $this->_getUnvisitedNeighbor($cur)) !== -1) {
$cur = $this->_carve($cur, $next);
if ($cur === false) break; // 遇已訪問格子 (理論上不發生)
}
}
// 取得未訪問鄰居 (上右下左)
private function _getUnvisitedNeighbor($pos) {
$w = $this->w; $g = $this->grids;
$candidates = [];
// 上
if ($pos - $w >= 0 && $g[$pos-$w]===0) $candidates[] = $pos-$w;
// 右
if ($pos % $w != $w-1 && $g[$pos+1]===0) $candidates[] = $pos+1;
// 下
if ($pos + $w < count($g) && $g[$pos+$w]===0) $candidates[] = $pos+$w;
// 左
if ($pos % $w != 0 && $g[$pos-1]===0) $candidates[] = $pos-1;
return $candidates ? $candidates[array_rand($candidates)] : -1;
}
// 打通牆壁
private function _carve($from, $to) {
$diff = $to - $from;
$w = $this->w;
if ($diff === -$w) { $this->grids[$from] |= 1; $this->grids[$to] |= 4; } // 上
elseif ($diff === 1) { $this->grids[$from] |= 2; $this->grids[$to] |= 8; } // 右
elseif ($diff === $w) { $this->grids[$from] |= 4; $this->grids[$to] |= 1; } // 下
elseif ($diff === -1) { $this->grids[$from] |= 8; $this->grids[$to] |= 2; } // 左
$this->history[] = $from;
return $to;
}
}
// 使用
$maze = (new Maze())->set(20, 20)->create();
$grid = $maze->get();
$ends = $maze->deadEnds(true);
list($start, $end) = [$ends[0], $ends[1]];
echo "Start: $start, End: $end\n";
在生成的迷宮上尋找最短路徑。啟發式函數使用曼哈頓距離。
<?php
class AStar {
private $w, $h, $grids;
private $open = [], $closed = [];
public function set($w, $h, $grids) { $this->w=$w; $this->h=$h; $this->grids=$grids; return $this; }
public function search($start, $end) {
$this->open = []; $this->closed = [];
$this->pushNode($start, null, 0, $this->heuristic($start, $end));
while ($this->open) {
// 取 f 最小節點 (簡單線性搜尋,小迷宮可用;大圖請用優先隊列 SplPriorityQueue)
$bestIdx = 0;
foreach ($this->open as $i => $n) if ($n['f'] < $this->open[$bestIdx]['f']) $bestIdx = $i;
$current = $this->open[$bestIdx];
unset($this->open[$bestIdx]);
$this->open = array_values($this->open);
if ($current['pos'] === $end) return $this->reconstructPath($current);
$this->closed[$current['pos']] = $current;
$this->expandNeighbors($current, $end);
}
return []; // 無路徑
}
private function pushNode($pos, $parent, $g, $h) {
$this->open[] = ['pos'=>$pos, 'parent'=>$parent, 'g'=>$g, 'h'=>$h, 'f'=>$g+$h];
}
private function heuristic($a, $b) {
return abs($a % $this->w - $b % $this->w) + abs(intdiv($a, $this->w) - intdiv($b, $this->w));
}
private function expandNeighbors($node, $end) {
$pos = $node['pos']; $g = $node['g'];
$walls = $this->grids[$pos];
$w = $this->w;
// 四個方向:上右下左 對應位元 1,2,4,8
$dirs = [
1 => -$w, 2 => 1, 4 => $w, 8 => -1
];
foreach ($dirs as $bit => $delta) {
if (!($walls & $bit)) continue; // 有牆
$next = $pos + $delta;
if (isset($this->closed[$next])) continue;
$ng = $g + 1;
// 檢查 open list 中是否有更好路徑
$found = false;
foreach ($this->open as &$o) {
if ($o['pos'] === $next) {
if ($ng < $o['g']) { $o['g'] = $ng; $o['f'] = $ng + $o['h']; $o['parent'] = $pos; }
$found = true; break;
}
}
if (!$found) $this->pushNode($next, $pos, $ng, $this->heuristic($next, $end));
}
}
private function reconstructPath($node) {
$path = [];
while ($node) {
array_unshift($path, $node['pos']);
$node = $node['parent'] !== null ? $this->closed[$node['parent']] : null;
}
return $path;
}
}
// 尋路
$astar = (new AStar())->set($maze->w, $maze->h, $grid);
$path = $astar->search($start, $end);
echo 'Path length: ' . count($path) . ' steps: ' . implode(' -> ', $path);
<style>
.maze { display: grid; grid-template-columns: repeat(20, 20px); grid-template-rows: repeat(20, 20px); gap: 0; }
.cell { width:20px; height:20px; border:1px solid #999; box-sizing:border-box; position:relative; }
.cell[data-wall*="1"] { border-top:3px solid #000; }
.cell[data-wall*="2"] { border-right:3px solid #000; }
.cell[data-wall*="4"] { border-bottom:3px solid #000; }
.cell[data-wall*="8"] { border-left:3px solid #000; }
.cell.start { background:#0f0; } .cell.end { background:#f00; }
.cell.path { background:#ff0; opacity:0.6; }
</style>
<div class="maze">
<?php foreach ($grid as $i => $v): ?>
<div class="cell <?= $i==$start?'start':($i==$end?'end':(in_array($i,$path)?'path':'')) ?>"
data-wall="<?= $v ?>"></div>
<?php endforeach; ?>
</div>