「ドルアーガの塔」の迷路生成アルゴリズム

# はじめに

[**ドルアーガの塔**](https://ja.wikipedia.org/wiki/%E3%83%89%E3%83%AB%E3%82%A2%E3%83%BC%E3%82%AC%E3%81%AE%E5%A1%94)はナムコから発売された60階建ての塔を攻略するゲームです。
それぞれの階（フロア）は迷路状となっていますが、プログラムに各フロアの迷路データは持っておらず、１つのseed値から乱数を生成し、迷路を作成しています。
どうやって実装しているのか、以前から気になっていましたので、調べて再現しました。

# アルゴリズムについての参考情報

[ゲーム世界を動かすサイコロの正体 ～往年のナムコタイトルから学ぶ乱数の進化と応用](http://sekigames.gg-blog.com/Entry/288/)
[ドルアーガの塔　乱数の工夫の正体](http://sekigames.gg-blog.com/Entry/291/)

参考情報を読み、わかったことを以下に記載します。

## 乱数の種(seed)
* 各フロアで、8ビット（0～255）の乱数のseed値を与えている。
* seed値は、フロア1は0、フロア2は1、つまり フロアnはn-1をseed値として、乱数を初期化している。
* ただし、フロア60のseed値だけは、特別に255を使用している。

## 乱数生成方法

* [線形帰還シフトレジスタ](https://ja.wikipedia.org/wiki/%E7%B7%9A%E5%BD%A2%E5%B8%B0%E9%82%84%E3%82%B7%E3%83%95%E3%83%88%E3%83%AC%E3%82%B8%E3%82%B9%E3%82%BF)を使用。
* 4ビット目 と 7ビット目を抽出して、XOR。
* レジスタを一つシフトし下位１ビットに 得られた乱数を入れる。

## 壁の生成方法

* 各柱から ランダムで壁を伸ばす。
* 2ビットの乱数 （2進数で、0b00～0b11）を取得し、
 * 00： 上に伸びる壁
 * 01： 下に伸びる壁
 * 10： 右に伸びる壁
 * 11： 左に伸びる壁
* 伸ばした先の柱が、「外壁」または「既に壁がある柱」だった場合、新たに「壁のない柱」から スタート。そうでなければ、伸ばした先の柱 で 同じ処理を行う。
* これを繰り返し、全ての柱に 壁があるなら迷路完成。

# ソースコード

参考情報だけでは、実装するための情報が不足していますが、試行錯誤を行い、迷路を再現することができました。

```d:maze.d
import std.conv;
import std.stdio;
import std.string;

const MAX_X = 17;		// 横方向の柱の数
const MAX_Y = 8;		// 縦方向の柱の数
const DIR_U = 0b00;		// 上方向
const DIR_R = 0b01;		// 右方向
const DIR_D = 0b10;		// 下方向
const DIR_L = 0b11;		// 左方向

bool [MAX_Y][MAX_X] pole;		// 柱
bool [MAX_Y+1][MAX_X] wall1;	// 縦方向の壁
bool [MAX_Y][MAX_X+1] wall2;	// 横方向の壁

ubyte delegate() dRand(ubyte u)
{
	ubyte seed = u;
	ubyte prev = u & 0b01;
	return {
		ubyte r1 = ((seed >> 7) ^ (seed >> 4)) & 0b01;
		ubyte r2 = r1 ^ 1;
		seed = cast(ubyte)((seed << 1) | r2);
		r1   = cast(ubyte)((prev << 1) | r2) & 0b11;
		prev = r2;
		return ( r1 );
	};
}

void buildWall(int x, int y, ubyte delegate() dr)
{
	if ( x < 0 || x > MAX_X - 1 || y < 0 || y > MAX_Y - 1 || pole[x][y] ){
		return;
	}
	pole[x][y] = true;
	while ( true ){
		switch ( dr() ){
			case DIR_U:	// 上(DIR_U)
				if ( wall1[x][y] ){ break; }	// やり直し
				wall1[x][y] = true;
				buildWall(x, y-1, dr);
				return;
			case DIR_R:	// 右(DIR_R)
				if ( wall2[x+1][y] ){ break; }	// やり直し
				wall2[x+1][y] = true;
				buildWall(x+1, y, dr);
				return;
			case DIR_D:	// 下(DIR_D)
				if ( wall1[x][y+1] ){ break; }	// やり直し
				wall1[x][y+1] = true;
				buildWall(x, y+1, dr);
				return;
			default:	// 左(DIR_L)
				if ( wall2[x][y] ){ break; }	// やり直し
				wall2[x][y] = true;
				buildWall(x-1, y, dr);
				return;
		}
	}
}

void showMap()
{	// MAP表示
	string[MAX_Y * 2 + 3] line;
	line[0] = line[$ - 1] =
		"+-----------------------------------------------------+";
	for ( int y = 0; y <= MAX_Y; y++ ){	// 縦方向の壁
		for ( int x; x < MAX_X; x++ ){
			line[y * 2 + 1] ~= ( wall1[x][y] ) ? " | " : "   ";
		}
		line[y * 2 + 1] = "| " ~ line[y * 2 + 1] ~ " |";
	}
	for ( int y = 0; y < MAX_Y; y++ ){	// 横方向の壁
		for ( int x; x <= MAX_X; x++ ){
			line[y * 2 + 2] ~= ( wall2[x][y] ) ? "--O" : "  O";
		}
		line[y * 2 + 2] = "|" ~ line[y * 2 + 2].chop ~ "|";
	}
	for ( int y = 0; y < line.length; y++ ){
		writeln(line[y]);
	}
}

void main(string[] args)
{
	auto dr = dRand(args[1].to!ubyte);
	for ( int x = MAX_X - 1; x >= 0; x-- ){
		for ( int y = 0; y < MAX_Y; y++ ){
			buildWall(x, y, dr);
		}
	}
	showMap();
}
```

# ソースコード補足説明

##`dRand`
乱数を生成するための関数です。いわゆる[クロージャ](https://qiita.com/tags/%e3%82%af%e3%83%ad%e3%83%bc%e3%82%b8%e3%83%a3)([Closures](https://qiita.com/tags/closure))構造で実装しました。
引数`u`というseed値を与えることで、乱数生成処理を返します。

##`buildWall`
柱の位置`x`,`y`から、壁を生成する処理です。
`dr`で乱数を生成しながら、壁を伸ばします。
壁を伸ばしたい方向にすでに壁がある場合は、乱数の生成をやり直します。

##`showMap`
生成された迷路を表示する処理です。
`wall1`が縦方向、`wall2`が横方向の壁の状態を保存する配列となっていて、`true`なら壁を出力します。

##`main`
実行時に引数`args[1]`にseed値をセットします。入力値チェックは実装していませんので、ご注意ください。
フロア1は`0`、フロア2は`1`、・・・、フロア59は`58`、フロア60は`255`を`args[1]`にセットすることで、迷路を再現できます。
`dRand`を呼び出して、乱数生成処理を取得します。
`buildWall`を呼び出して、すべての柱より壁を伸ばします。
`showMap`を呼び出して、生成された迷路を表示します。

# 実行結果
```
D:\Dev>dmd -m64 maze.d

D:\Dev>maze 0
+-----------------------------------------------------+
|                 |                             |     |
|  O--O--O  O--O  O  O--O--O--O--O--O--O  O  O  O  O--|
|     |        |        |                 |  |        |
|  O--O--O--O--O--O--O  O--O--O--O  O--O--O--O--O--O  |
|  |     |     |           |           |              |
|  O--O  O  O  O  O--O--O  O--O  O  O  O--O  O--O--O  |
|     |     |        |        |  |  |     |  |  |  |  |
|--O  O--O  O--O--O--O--O--O  O--O  O--O  O--O  O  O  |
|        |        |              |     |  |  |        |
|  O--O  O--O--O  O--O  O--O  O  O--O  O--O  O--O  O--|
|  |     |  |        |     |  |     |           |     |
|  O--O  O  O--O--O  O--O  O--O--O--O--O  O--O--O--O  |
|     |  |     |        |              |           |  |
|--O  O--O  O  O--O  O  O--O  O  O  O  O--O  O  O--O--|
|           |     |  |     |  |  |  |     |  |        |
|--O  O  O--O--O  O--O--O  O--O--O--O--O  O--O--O--O  |
|     |        |     |                 |        |     |
+-----------------------------------------------------+
```

# 参考情報

[ドルアーガの塔](https://ja.wikipedia.org/wiki/%E3%83%89%E3%83%AB%E3%82%A2%E3%83%BC%E3%82%AC%E3%81%AE%E5%A1%94)
[ゲーム世界を動かすサイコロの正体 ～往年のナムコタイトルから学ぶ乱数の進化と応用](http://sekigames.gg-blog.com/Entry/288/)
[ドルアーガの塔　乱数の工夫の正体](http://sekigames.gg-blog.com/Entry/291/)

[線形帰還シフトレジスタ](https://ja.wikipedia.org/wiki/%E7%B7%9A%E5%BD%A2%E5%B8%B0%E9%82%84%E3%82%B7%E3%83%95%E3%83%88%E3%83%AC%E3%82%B8%E3%82%B9%E3%82%BF)

[クロージャ](https://qiita.com/tags/%e3%82%af%e3%83%ad%e3%83%bc%e3%82%b8%e3%83%a3)
[Closures](https://qiita.com/tags/closure)