萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 實作迷宮生成 (DFS 深度優先) 與 A* 尋路演算法

第一部分:迷宮生成 - 深度優先搜尋 (DFS) / Prim 演算法變體

使用「樹的深度遍歷」原理:從隨機起點開始,隨機選擇未訪問的鄰居打通牆壁,回溯直到所有格子連通。產生的迷宮為「完美迷宮」——任意兩點間有且只有一條路徑。

Maze 類別核心邏輯

<?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";

第二部分:A* 尋路演算法

在生成的迷宮上尋找最短路徑。啟發式函數使用曼哈頓距離。

AStar 類別

<?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);

視覺化輸出 (HTML + CSS)

<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>

擴充方向

  • 加入權重地形 (泥地、草地) → Dijkstra / 加權 A*。
  • 3D 迷宮 (多樓層、樓梯)。
  • 即時多人遊戲:WebSocket 同步迷宮狀態與玩家位置。
  • 程序生成關卡:房間 + 走廊 (BSP Tree、Cellular Automata)。
copyright © 萬盛學電腦網 all rights reserved