迷路生成アルゴリズム穴堀法実装サンプル

スクリプト

# 穴掘り法による迷路生成プログラム
use strict;
my $width = 20; # ダンジョンの東西の幅
my $height = 20; # ダンジョンの南北の幅
my $mwidth = $width * 2; # データ上は設定値の2倍+1の幅を持つ。
my $mheight = $height * 2;
my $map = []; # ダンジョン構造体
my $filename = 'dungeon.txt'; # 保存ファイル名
# ダンジョンを一旦壁で埋め尽くす。
foreach my $x ( 0..$mwidth ) {
	foreach my $y ( 0..$mheight ) {
		$map->[$x]->[$y] = 1;
	}
}
# 出発点の設定
my @root = ([1, 1]); # 左上隅
# 迷路の生成
while ( @root ) {
	my $root = pop @root; # 現在地点を取得
	my ( $x, $y ) = @{$root}; # 現在地点の座標を展開
	$map->[$x]->[$y] = 0; # 現在地点を通路に変更。
	my @next = (); # 取り得る可能な選択肢を格納する。
	# まず、東西南北の選択肢を作る。
	if ( $x > 1 ) { push @next, [$x-2, $y]; }
	if ( $y > 1 ) { push @next, [$x, $y-2]; }
	if ( $x < $mwidth-1 ) { push @next, [$x+2, $y]; }
	if ( $y < $mheight-1 ) { push @next, [$x, $y+2]; }
	# その方向にいけるかどうかを検証し、選別する。
	@next = grep { $map->[$_->[0]]->[$_->[1]] } @next;
	@next or next; # 可能な選択肢がなければ、前の選択肢に戻る。
	# その中から一つを選択する。
	my $next = $next[int(rand()*scalar @next)];
	# その選択肢の位置と現在位置を通路に変更する。
	$map->[($x+$next->[0])/2]->[($y+$next->[1])/2] = 0;
	# @rootに現在位置と次の位置を追加。
	push @root, $root;
	push @root, $next;
}
# 迷路の保存
open ( OUT, ">$filename" );
foreach my $y ( 0..$mheight ) {
	foreach my $x ( 0..$mwidth ) {
		print OUT $map->[$x]->[$y];
	}
	print OUT "\n";
}
close ( OUT );

実行後例

11111111111111111111111111111111111111111
10001000000000000010000000100010000000001
11101111101111101110111010101011111011101
10001000100010001000100010101000001000101
10111010111011101011101110101111101110101
10100010001000101000101000101010001000101
10111011101110101110101110101010111011111
10000010101000100010100010101000100000001
11111110101011111110111010101110111111101
10000010001010000000100010100010000000001
10111110111010111111101110111010111111111
10001000100000000010001010001010100000001
10101011111111111110111011101011101111101
10101000000010001000100010001000000000101
11101111111010101011101110111111111110101
10001000001010101010000010000000001000101
10101011111010101011101011111111101011101
10100010000010101000101000000010001000101
10101110111110101110111110111010111110101
10101000100000101000100010001000100000101
10111011111110101010101011111011111110101
10000010000000100010101000001010000010101
10111110101111111011101111101010111011101
10100010101010000010000010001010001010001
10101011101010111110111110111011101010101
10001010001000001000001000100000001000101
11111010111111111011111011111111111111101
10001010000000000010001010000000000010001
11101010111111111110101010111111101010111
10001010000000101000101010100000101010001
10101011111110101011101010101110111011101
10101010000010001010000010101010000010101
10111010111011111010111110101011111110101
10000010100000100010100010101000100000001
10111110111110101111101010101011101111111
10100000001000100000001000101010001000001
10101111101011101111111111101010111011101
10101000101010000010000000001010100010001
10111010101011111110111111111010111110101
10000010001000000000100000000000000000101
11111111111111111111111111111111111111111

分かりづらいのではてな記法にしてみる。

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■

■