忍者ブログ
ゲームを作ったり、ゲームを遊びまくったりしている せっき~の生き様。   まずは目次をご覧ください
CEDECの講演
ゲーム世界を動かすサイコロの正体 ~ 往年のナムコタイトルから学ぶ乱数の進化と応用

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

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



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

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


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



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

●概要

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



各ステージで、8ビット(0~255)の乱数のseed値を与え、乱数を作っています。
(seed値が同じなため、何度プレイしても 同じ結果になります
ドルアーガの塔の全ステージデータは 60バイトと、容量削減に繋がっています

 
↑ こちら、誤りでした。
 各階のseed値は 1階は1、2階は2 と 階数をseed値として初期化している との事です。
 
 ドルアーガの塔のステージデータは 60バイトすら 必要ありませんでした。
 後述の理由で、60階のseed値だけ 特別 255 で初期化されています。
 
 
 

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



2ビットの乱数 (0~3)を取得し

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


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

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

 →  


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




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

●しかし

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

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

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




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

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

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



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


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

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

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



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

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




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

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



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

●更には

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



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


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

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

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


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


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

●まとめ

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


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

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

大変面白いお話でした。

拍手[40回]

PR
この記事にコメントする
お名前
タイトル
文字色
メールアドレス
URL
コメント
パスワード   Vodafone絵文字 i-mode絵文字 Ezweb絵文字
プロフィール
HN:
せっき~
性別:
男性
職業:
ゲームプログラマ
自己紹介:
古いパソゲー、ボードゲーム、カードゲームを熱狂的に遊んでいます。


ついったー
http://twitter.com/seki_seki_seki

連絡先は
sekisekiseki(あっと)gmail.com
最新コメント
[03/24 como ganhar dinheiro na internet com baixo investimento]
[03/24 セリーヌ コピー 店舗]
[03/24 como ganhar dinheiro na master liga pes 2013 ps3]
[03/23 João Antônio]
[03/23 Como ganhar dinheiro Com blogs na internet]
カウンター
ついったー

Copyright © [ せっき~のゲーム屋さん ] All rights reserved.
Special Template : 忍者ブログ de テンプレート and ブログアクセスアップ
Special Thanks : 忍者ブログ
Commercial message : [PR]