PowerShellで迷路を作る（棒倒し法）
Windowsに標準搭載されているPowerShellを使って迷路を作成します。
アルゴリズムには棒倒し法を用います。
棒倒し法とは？
棒倒し法は、比較的シンプルなアルゴリズムで迷路を生成する方法の一つです。まるで棒を倒すように、壁をランダムに壊していくことで迷路を作り上げていきます。
棒倒し法の具体的な手順
１．初期状態:
まず、迷路の枠となる外壁を作ります。
その中に、縦横交互に壁を配置します。この壁が、これから倒していく「棒」にあたります。
２．棒を倒す:
配置した壁を、上下左右のいずれかへランダムに倒します。
３．繰り返し:
2.の操作を、すべての壁が倒れるか、または迷路全体が一つにつながるまで繰り返します。
プログラミング
PowerShellの棒倒し法のコードを記述してみましょう。
$tempmaze=@(
"▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓",
"▓ ▓",
"▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓",
"▓ ▓",
"▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓",
"▓ ▓",
"▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓",
"▓ ▓",
"▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓",
"▓ ▓",
"▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓"
)
for($i = 1;$i -lt 10;$i++) {
$i
$kabemoji = "▓"
$maze = @($tempmaze)
for($y = 2;$y -lt $maze.length-1;$y+=2) {
for($x = 2;$x -lt $maze[$y].length-1;$x+=2) {
if($maze[$y][$x] -eq $kabemoji) {
$rand = Get-Random -Minimum 1 -Maximum 5
if($rand -eq 1){$maze[$y-1]=$maze[$y-1].Remove($x,1);$maze[$y-1]=$maze[$y-1].insert($x,$kabemoji);}
if($rand -eq 2){$maze[$y]=$maze[$y].Remove($x+1,1);$maze[$y]=$maze[$y].insert($x+1,$kabemoji);}
if($rand -eq 3){$maze[$y+1]=$maze[$y+1].Remove($x,1);$maze[$y+1]=$maze[$y+1].insert($x,$kabemoji);}
if($rand -eq 4){$maze[$y]=$maze[$y].Remove($x-1,1);$maze[$y]=$maze[$y].insert($x-1,$kabemoji);}
}
}
}
$maze
}
実行するとランダムな迷路が10個できあがります。
棒倒し法のメリット
シンプル: アルゴリズムが簡単なので、プログラミング初心者でも比較的容易に実装できます。
ランダム性: 壁をランダムに倒すため、毎回異なる迷路が生成されます。
効率性: 他のアルゴリズムに比べて、比較的少ない計算量で迷路を作ることができます。
棒倒し法で生成される迷路の特徴
通路の幅: 基本的に通路の幅は2マスになります。
複雑さ: ランダム性が高いですが、複雑すぎる迷路は生成されにくいです。
ループ: スタートからゴールまでたどり着けないループが発生する場合があります。
棒倒し法の欠点を補うランダムシード
棒倒し法には壁をランダムに倒すため毎回異なる迷路が生成される欠点があります。これは回避することができます。
乱数を発生させるGet-Randomコマンドレットを実行するときに乱数の種になるランダムシード値を指定します。
こうすることで乱数を毎回同じ数値にすることができます。
具体的にはこうです
Get-Random -SetSeed 10
Get-Random -SetSeed 10
Get-Random -SetSeed 10
実行してみるとどうですか？
PS C:\temp> Get-Random -SetSeed 10
Get-Random -SetSeed 10
Get-Random -SetSeed 10
801353165
801353165
801353165なんど実行しても同じ結果が出力されます。
違うパソコンでも同じOSであれば同じ結果になります。
（もしかしたら違うOSでもPowerShellなら同じ結果かも）
さらに改良してランダムシード値を毎回再設定するようにしてみました。
$rand = 10
for($i = 0;$i -lt 5;$i++) {
$rand = Get-Random -SetSeed $rand
write-host $rand
}
これを実行すると
乱数が5つ表示されますが、これも何度実行しても同じ結果になります。
PS C:\temp>
$rand = 10
for($i = 0;$i -lt 5;$i++) {
$rand = Get-Random -SetSeed $rand
write-host $rand
}
801353165
115889428
238673097
1191199168
549837297
乱数は、乱数の種になるランダムシード値を指定することで何度でも同じ結果を出すことができるのです。
棒倒し法の話に戻るとランダムシード値を用いることで何度でも同じ迷路を作り出すことができます。このテクニックはナムコ社の「ドルアーガの塔」というゲームでマップデータを圧縮する為に使用されています。全60フロアで1フロア１８ｘ３６のマップデータを8bitに収めるために使用されました（詳しくは検索）。
ランダムシード値を用いたサンプルプログラムはこちら
$tempmaze=@(
"▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓",
"▓ ▓",
"▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓",
"▓ ▓",
"▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓",
"▓ ▓",
"▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓",
"▓ ▓",
"▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓",
"▓ ▓",
"▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓"
)
for($i = 1;$i -le 10;$i++) {
$i
$mazapattern = @(0,40,3,57,86,96,8,11,13,27,6)
$rand = Get-Random -SetSeed $mazapattern[$i] #ランダムシートを指定する
$kabemoji = "▓"
$maze = @($tempmaze)
for($y = 2;$y -lt $maze.length-1;$y+=2) {
for($x = 2;$x -lt $maze[$y].length-1;$x+=2) {
if($maze[$y][$x] -eq $kabemoji) {
$rand = Get-Random -Minimum 1 -Maximum 5
if($rand -eq 1){$maze[$y-1]=$maze[$y-1].Remove($x,1);$maze[$y-1]=$maze[$y-1].insert($x,$kabemoji);}
if($rand -eq 2){$maze[$y]=$maze[$y].Remove($x+1,1);$maze[$y]=$maze[$y].insert($x+1,$kabemoji);}
if($rand -eq 3){$maze[$y+1]=$maze[$y+1].Remove($x,1);$maze[$y+1]=$maze[$y+1].insert($x,$kabemoji);}
if($rand -eq 4){$maze[$y]=$maze[$y].Remove($x-1,1);$maze[$y]=$maze[$y].insert($x-1,$kabemoji);}
}
}
}
$maze
}
実行すると迷路が10個でてきますが何回実行しても同じです。
1988年頃、友達の家にPC8801やMSXがありました。それらを扱う雑誌も置いてありまして、そのどれかに棒倒し方が載っていたのを思い出してプログラムを書いてみました。たしかN88BASICだったと思うんですけど。
#迷路生成 #アルゴリズム #棒倒し法 #プログラミング #ランダム #PowerShell #プログラミング初心者 #MSX #N88BASIC