ＣＥＤＥＣの講演
「ゲーム世界を動かすサイコロの正体 ～ 往年のナムコタイトルから学ぶ乱数の進化と応用」

より、
乱数を使った ドルアーガの塔の 迷路生成のアリゴリズムについて紹介です。

講演内容は、こちらです http://sekigames.gg-blog.com/Entry/288/



講演者の方も、
「ナムコの乱数を取り上げるなら、ドルアーガの塔をせざるえない」
という程、外せない内容との事です

「このテーマだけで講演時間を全て使っても説明しきれない」


（講演では、時間の関係で 触りのみでしたので
ある程度、せっき～の解釈で補完しています）



--------------------------------------------------------------------

●概要

ドルアーガの塔の 各ステージの迷路は、全てランダムで生成されています。



各ステージで、8ビット（０～２５５）の乱数のｓｅｅｄ値を与え、乱数を作っています。
（ｓｅｅｄ値が同じなため、何度プレイしても　同じ結果になります
ドルアーガの塔の全ステージデータは ６０バイトと、容量削減に繋がっています）
 
↑　こちら、誤りでした。
　各階のｓｅｅｄ値は １階は１、２階は２ と 階数をｓｅｅｄ値として初期化している　との事です。
　
　ドルアーガの塔のステージデータは ６０バイトすら 必要ありませんでした。
　後述の理由で、６０階のｓｅｅｄ値だけ 特別 255 で初期化されています。
 
 
 

各柱から ランダムで壁を伸ばします。



2ビットの乱数 （0～3）を取得し

00： 上に伸びる壁
01： 下に伸びる壁
10： 右に伸びる壁
11： 左に伸びる壁


伸ばした先の柱が、「外壁」 ｏｒ 「既に壁がある柱」 だった場合
新たに「壁のない柱」から スタート

そうでなければ、伸ばした先の柱 で 同じ処理を行う

　→　　


これを繰り返し、全ての柱に 壁があるなら迷路完成




--------------------------------------------------------------------

●しかし

完全にランダムに迷路を作った場合

とても複雑な迷路になって、足の遅いギルだと 制限時間内にゴールできないかも？
 
 
↑　完全ランダムで作られた複雑な迷路

 
ここで、ドルアーガの塔 の乱数アルゴリズムの工夫が活きます。




--------------------------------------------------------------------

●線形帰還シフトレジスタ の使い方に工夫

詳しくは、乱数講演本編を参照ですが
（http://sekigames.gg-blog.com/Entry/288/）



ドルアーガの塔は、線形帰還シフトレジスタ を使っています。
このアルゴリズムは、１ビットの乱数を生成するアルゴリズムです。


２ビットの乱数を作るのであれば　本来、線形帰還シフトレジスタの処理を２回すれば良いのですが

ドルアーガの塔では、
線形帰還シフトレジスタ で得た 乱数の1ビットと
前回得た乱数 1ビット

を使って 2ビットを生成しています。



前回、生まれた乱数が 1だった場合

次の壁は
10： 右に伸びる壁
11： 左に伸びる壁




右に伸びる壁（10） の後は、
必ず 上に伸びる壁（00）か、下に伸びる壁（01） になります。

となると、
右下へのジグザグ壁 というのが生まれやすい
（10 → 01 → 10 → 01 → 10 → 01 → )



--------------------------------------------------------------------

●更には

ドルアーガの塔で有名な 最終面のステージ



これは、seed値に 0xff を与えると生まれます。


線形帰還シフトレジスタ の弱点として、特定のseed値を与えると　同じ結果ばかりを返す
というものがあります。

今回の例の場合、1を返し続けたのですね

その結果、左に伸びる壁 (11) を生み続けて、あのような迷路が作られました。


本来、線形帰還シフトレジスタ の弱点ともいえる挙動なのですが
それすら、ゲームデザインとして見事に活用されたのは 頭が下がります。


--------------------------------------------------------------------

●まとめ

このようにして、ドルアーガの塔の迷路は作られています。


迷路を作るアルゴリズム なんてものは、いろいろあると思いますが
このように、線形帰還シフトレジスタ の特性を活かしたアルゴリズム というのは　ならではと思います。

ここが、講演者によると ドルアーガの味との事ですが

大変面白いお話でした。

[50回]