PowerShellで迷路を作る（穴掘り法）

Windowsに標準搭載されているPowerShellを使って迷路を作成します。
アルゴリズムには穴掘り法を用います。

穴掘り法とは

「穴掘り法」とは、迷路生成アルゴリズムの一種で次のような手順で迷路を生成します。

１．スタート地点の選定: 迷路の任意のセルを初期のスタート地点として選びます。

２．現在のセルの訪問: スタート地点から始めて、現在のセルを訪問済みとしてマークします。

３．ランダムな方向の選択: 現在のセルから、上下左右の4つの方向のうちランダムに1つを選びます。

４．次のセルの確認: 選んだ方向の次のセルが既に訪問済みでない場合、そのセルへ進みます。次のセルを訪問済みとしてマークし、現在のセルと次のセルの間の壁を取り除きます。

５．行き止まりの場合: 全ての隣接セルが既に訪問済みの場合、バックトラック（後戻り）して前のセルに戻り、再度ランダムな方向を選んで進行します。

６．すべてのセルが訪問済みになるまで繰り返し: 迷路全体が訪問されるまで、手順3〜5を繰り返します。

このプロセスにより、全てのセルが一度だけ訪問され、かつ全体が繋がった迷路が生成されます。この方法はシンプルでありながら、完全な迷路を生成するのに非常に効果的です。

プログラミング

# 迷路生成用の関数
function Generate-Maze {
    param (
        [int]$width,
        [int]$height
    )

    # 初期化
    $maze = @()
    for ($i = 0; $i -lt $height; $i++) {
        $maze += ,(@(1) * $width)
    }

    function Carve($x, $y) {
        $directions = @(0, 1, 2, 3)
        $directions = $directions | Get-Random -Count 4

        foreach ($direction in $directions) {
            $nx = $x
            $ny = $y

            switch ($direction) {
                0 { $nx += 2 } # 右
                1 { $nx -= 2 } # 左
                2 { $ny += 2 } # 下
                3 { $ny -= 2 } # 上
            }

            if ($nx -gt 0 -and $nx -lt $width -and $ny -gt 0 -and $ny -lt $height -and $maze[$ny][$nx] -eq 1) {
                $maze[$ny][$nx] = 0
                $maze[($y + $ny) / 2][($x + $nx) / 2] = 0
                Carve $nx $ny
            }
        }
    }

    # スタート地点を初期化
    $startX = 1
    $startY = 1
    $maze[$startY][$startX] = 0

    # 迷路を彫る
    Carve $startX $startY

    return $maze
}

# 迷路を生成
$width = 21 #迷路のサイズ幅
$height = 21 #迷路のサイズ高さ
$maze = Generate-Maze -width $width -height $height

# 迷路を表示
foreach ($row in $maze) {
    foreach ($cell in $row) {
        if ($cell -eq 1) {
            Write-Host -NoNewline "#"
        } else {
            Write-Host -NoNewline " "
        }
    }
    Write-Host
}

前に記事にした棒倒し方より自然な迷路ができあがります。

#迷路生成 #アルゴリズム  #穴掘り法 #棒倒し法 #プログラミング #ランダム #PowerShell #プログラミング初心者