忍者ブログ
ゲームを作ったり、ゲームを遊びまくったりしている せっき~の生き様。   まずは目次をご覧ください
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

2014年9月4日 にあった、CEDECの講演についての記事です。


ゲーム世界を動かすサイコロの正体 ~
  往年のナムコタイトルから学ぶ乱数の進化と応用

 

バンダイナムコのプログラマさんより乱数の講演です。

・ゲームで使われている主要な乱数のしくみについて
・乱数のアルゴリズムが改良されていく歴史
・乱数の選択の注意点

などについて、取り上げられました。

 
(乱数分布などは せっかくなので 初め、自分で乱数プログラム組んで 用意しようかと思ったのですが
力尽きてしまい・・・

撮影した写真を使わせていただきました)

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

●はじめに

・真の乱数

→ 実際のサイコロ

予測不可能
再現不可能


・疑似乱数

→ ゲームプログラムで使われているのは こちら

でたらめに見えるが、法則性があり 実はすべて未来が決まっている
いつかは元の数字に戻る 周期がある)

 

●乱数の要素

・種 (seed)

・種を更新する アルゴリズム

・出力変換アダプタ
 (更新された種を 使いやすい形に変換する)

 

●今回の講演にむけて

ナムコから発売された、初期の業務用、家庭用 約50タイトルのプログラム(アセンブラ)を解析し

乱数アルゴリズムが どのように遷移していったのか 調査しました。


 業務用: 1980年代 (8ビット)
 家庭用: 1980年代前半 (MSX,ファミコン)

 

ちなみに、8ビットCPU というと・・・

 扱える数字   0~255
 メモリ空間   16 ~ 64KByte
 計算に使用できるレジスタ 1~2個
 掛け算、割り算 できない
 float   ない

 


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

●混沌な時代

・手探りで乱数を模索


VSyncカウンタ(画面同期カウンタ)の利用

 ・・・ プレイヤーがボタンを押した瞬間の VSyncカウンタを乱数として使用する方法


テーブル(乱数表)を参照する方法
  → しかし、「乱数表」を用意するメモリは勿体ない


 

・パックマンでは

プログラムのROM内のメモリを乱数表と見立てて使用する方法

実装例: A = *((char *)( seed & 0x1fff ))


問題点・・・

 一様な乱数では無い。
 プログラムを変えると、乱数も変わってしまう。

 

・ギャラガでは

Rレジスタを乱数として使用した

・・・ Z80特有の メモリのリフレッシュを行うためのカウンタ
    
    → メモリの情報保持のために、CPUの動作関係なしに常に動いているレジスタ
      不規則な数字が格納されている

実装例: A = *((char*)( 0x100 + Vcnt + R ))
     A = A + R


問題点・・・

 Z80以外のCPUでは使えない。
 再現性がない
 乱数の値が一様である保証が無い

 

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

●線形合同法

最も有名な乱数

 乱数 = ( seed * A + B ) mod 2^n


A = (4の倍数+1) 、 B = 奇数 の時、最大周期 2^n

C言語の rand()関数に使われているため 最もポピュラー

 

・ナムコのゲームでは 伝統的に

 seed * 5 + 1

が使われていた。


利点・・・

 掛け算がないCPUでも 容易に実装可能
 
 周期が最大 256 (8ビットなら)

 

具体例としては

 ポールポジション  seed * 5 + 1  +  Vカウンタ
 ディグダグ     seed * 5 + 1
 パック&パル    seed * 13 + 1

 

・欠点

分布を見てみると、縞になりやすい

 


下位ビットほど周期性がない

 → 下位1ビット目 周期2
   下位2ビット目 周期4
   下位3ビット目 周期8
   下位4ビット目 周期16

 


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

●線形帰還シフトレジスタ

電子回路でよく用いられる方法

シフト演算器の特定ビットをXORして戻すだけ

1回の操作(クロック)で 1ビットの乱数を得られる

どのビットを抽出して、XORを取るか? で周期が決まる。
(8ビットだと 最大周期255)


例)

 4ビット目7ビット目を抽出して乱数を作ります。

 レジスタが 01011000 という状態のとき 4ビット目と7ビット目のXORは 1

1という乱数を得た後

レジスタを一つシフトし (01011000 → 10110000)
下位1ビットに 得られた乱数 1 を入れる (10110001


 → レジスタは 10110001 になる  (この時のXORは 0
 → レジスタは 01100010 になる  (この時のXORは 0
 → レジスタは 11000100 になる  (この時のXORは 1
 → レジスタは 10001001 になる  (この時のXORは 1
 → ・・・

こうして、得られたビットを 乱数として扱う。



利点・・・
 出力ビットのばらつきがとても良い

 

・実際の使用例

ギャラクシアンギャラガで 背景の星の配置に 使用していた。

他には、
ボスコニアン   6ビット目と14ビット目のXOR の反転 + Rレジスタ
マッピー     0ビット目と7ビット目のXOR の反転
ドラゴンバスター 8ビット目と15ビット目のXOR の反転

 

ドルアーガの塔 での使用例

ステージのフロアを 乱数で生成している。
(種はフロア毎に固定なので 毎回同じ形のステージになる)

4ビット目と7ビット目のXOR の反転 したものを使用


より踏み込んだ内容は、こちらにまとめました。
http://sekigames.gg-blog.com/Entry/291/




・欠点

 実装したコードを見ても、パッと見 何をしている処理か良く分からない。

 1回の操作では、1ビットしか取得できない
 (8ビットの乱数を得るためには 8回操作をしないといけない)

 変化しない形が存在する

 → 00000000 は何度操作しても 00000000 になる。
   (初期化に注意)

 

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

●80年代 中頃


・線形合同法 + 線形帰還シフトレジスタ

両方の結果を足して、それを乱数とする手法

 

線形合同法線形帰還シフトレジスタ いいとこどり

→ 線形合同法の 下位ビットの周期性が改善
  線形帰還シフトレジスタの上位ビットの履歴も隠蔽

→ 乱数の周期が拡大
   (周期 55552)

 


●80年代末

テーブル参照主義 の復権

この頃 メモリが増大(MByteの時代) CPUはまだまだ遅かった


Sin、Cos、Atan、Sqrt なんでもテーブルに入れてしまえ
な時代だった

 

●90年代

C言語の襲来

→ 乱数アルゴリズムを自作せず
 rand() をそのまま利用するコードが主流に


→ 線形合同法の問題が再び・・・

 

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

●現在の乱数

・GFSR (Generalized Feedback Sift Register)


線形帰還シフトレジスタ を32個並べれば 1回の操作で 32ビット乱数が取れる

  シフトレジスタ → ワード列の配列

 

欠点

 周期は 1ビット分の線形帰還シフトレジスタ と同じ

 適切な種で初期化しないと、適切な乱数が生まれてくれない

 

これが進化して

Twisted GFSR

→ メルセンヌ・ツイスター法  (超長大周期 2の19937乗 - 1)

 

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

●まとめ

乱数は その性質を見極めて、正しく使いましょう


癖のある乱数も 使い方次第でゲームに味わいを生むことができる

→ ドルアーガの塔が とても良い例


過去の乱数アルゴリズム の反省点や改良から
今の メルセンヌ・ツイスター法 が生まれたという事もあり 過去の技術史を読む解くのも大変意義があります。

 

拍手[5回]

PR
この記事にコメントする
お名前
タイトル
文字色
メールアドレス
URL
コメント
パスワード   Vodafone絵文字 i-mode絵文字 Ezweb絵文字
» adidas football boots
Here's our starting XI for today – and it's just the ?濓? change as Kieran replaces Nacho#AFCvHCFC pic.
adidas football boots URL 2017/08/01(Tue)14:43:10 編集
プロフィール
HN:
せっき~
性別:
男性
職業:
ゲームプログラマ
自己紹介:
古いパソゲー、ボードゲーム、カードゲームを熱狂的に遊んでいます。


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

連絡先は
sekisekiseki(あっと)gmail.com
最新コメント
[08/18 モンクレール ブランソン コピー]
[08/17 located here]
[08/17 resource]
[08/17 シュプリーム 激安]
[08/16 Ana Clara]
カウンター
ついったー

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