はじめに
ドルアーガの塔はナムコから発売された60階建ての塔を攻略するゲームです。
それぞれの階（フロア）は迷路状となっていますが、プログラムに各フロアの迷路データは持っておらず、１つのseed値から乱数を生成し、迷路を作成しています。
どうやって実装しているのか、以前から気になっていましたので、調べて再現しました。
アルゴリズムについての参考情報
ゲーム世界を動かすサイコロの正体 ～往年のナムコタイトルから学ぶ乱数の進化と応用
ドルアーガの塔 乱数の工夫の正体
参考情報を読み、わかったことを以下に記載します。
乱数の種(seed)
- 各フロアで、8ビット（0～255）の乱数のseed値を与えている。
- seed値は、フロア1は0、フロア2は1、つまり フロアnはn-1をseed値として、乱数を初期化している。
- ただし、フロア60のseed値だけは、特別に255を使用している。
乱数生成方法
- 線形帰還シフトレジスタを使用。
- 4ビット目 と 7ビット目を抽出して、XOR。
- レジスタを一つシフトし下位１ビットに 得られた乱数を入れる。
壁の生成方法
- 各柱から ランダムで壁を伸ばす。
- 2ビットの乱数 （2進数で、0b00～0b11）を取得し、
- 00： 上に伸びる壁
- 01： 下に伸びる壁
- 10： 右に伸びる壁
- 11： 左に伸びる壁
- 伸ばした先の柱が、「外壁」または「既に壁がある柱」だった場合、新たに「壁のない柱」から スタート。そうでなければ、伸ばした先の柱 で 同じ処理を行う。
- これを繰り返し、全ての柱に 壁があるなら迷路完成。
ソースコード
参考情報だけでは、実装するための情報が不足していますが、試行錯誤を行い、迷路を再現することができました。
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
乱数を生成するための関数です。いわゆるクロージャ(Closures)構造で実装しました。
引数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 |
| | | | | | |
+-----------------------------------------------------+
参考情報
ドルアーガの塔
ゲーム世界を動かすサイコロの正体 ～往年のナムコタイトルから学ぶ乱数の進化と応用
ドルアーガの塔 乱数の工夫の正体