アルゴリズム
授業の流れ
- アルゴリズムとは
- 定義(事前にレポート課題で個々の「アルゴリズム」に対するイメージを聞いて,それをマクラに話を始める)
- 基本的な構成要素
- 順接,反復,条件分岐
- をゲーム内のキャラクタの動作例を交えながら説明(当然ながら例は山ほどある)
- フローチャートの表現もさりげなく使用
- 「プログラム」との違い
- ミニテスト:「ボタンを押したらキャラクターがジャンプする」のアルゴリズムを考えてみよう
- 図形で表現してみる
- 参考として,ジャンプ動作のあるゲームをいろいろ
- アルゴリズム検証
- コンピュータにかませるとどうなる?の典型例
- デモプログラムなどを使って説明
- 物理の公式を忠実に当てはめるとどうなる?
- 人間が自然と感じる動作は,物理法則に従った場合が多い(特にリアルな映像がウリの場合)
- とはいえ,ゲームの世界ではどこかに「ウソ」の計算が入る方が,かえってリアルに見えることもある
- 「どのアルゴリズムでも,必ずしも間違いではない」という説明を行う
- どういう動作をさせたいかという仕様次第
- コンピュータにかませるとどうなる?の典型例
- アルゴリズム設計の注意点
- 設計の仕方によってゲームに悪影響を及ぼす
- ミニテスト: 追いかけてくる敵キャラ
- 理想的な追い方を設計すると,人間には絶対に避けられなくなる
- 整列動作
- ゲームのアイテム整列(例えば50音順)処理
- 同じように見える整列処理も,ゲームによって速度が異なることがある
- 数が少ないより,数が多い方が時間がかかる
- 6枚のカード整列(ここではゲームとは独立)
- 「2枚の比較」「2枚の位置交換」「1枚を別の場所に移動」しかできない,と仮定
- 計算量の話(時間計算量,空間計算量)
- ゲームのアイテム整列(例えば50音順)処理
- 裏技とバグの違い
- 作成者が,アルゴリズム設計のレベルで意図している動作:裏技
- 最近は「裏技」と呼べるものが少ない・・・
- 作成者が意図してない(設計漏れ,設計ミス)ことで起こる動作:バグ
- 作成者が,アルゴリズム設計のレベルで意図している動作:裏技
- アルゴリズムを作る時に注意すべき事
- 設計意図どおりの動きがそのアルゴリズムで実現できるか(正当性)
- 十分な速度で実行できるか(計算量)
- 想定しうる全動作をカバーできているか(網羅性)
使用題材
スーパーマリオブラザーズ (1985, 任天堂)
- ジャンプ動作
- Verlet積分(整数の加減算だけで,放物運動の座標を擬似的に計算可能)で計算
- (参考: マリオのジャンプ実装法とVerlet積分(Gemmaの日記) http://d.hatena.ne.jp/Gemma/20080517/1211010942)
- ジャンプ中も十字キーの左右である程度動きの制御が可能
- ボタンの押下時間でジャンプの高さが変化
- Verlet積分(整数の加減算だけで,放物運動の座標を擬似的に計算可能)で計算
マイティボンジャック (1986, テクモ)
- ジャンプ動作
- Aボタン1回で画面の下から上までジャンプ可能
- ボタンの押下時間でジャンプの高さが変化
- ジャンプ中にAボタンを押すと,ジャンプ動作をキャンセル
パックランド (ファミコン版 1985, ナムコ)
- ジャンプ動作
- 十字ボタンで(どの方向を押しても)ジャンプ
- ボタンの押下時間に関わらずジャンプの高さは一定
スペランカー (ファミコン版 1985, アイレム)
- 参考: (バーチャルコンソール版)
- ジャンプ動作
- Aボタンでジャンプ
- ボタンの押下時間に関わらずジャンプの高さは一定
- ジャンプの高さは人間の限界に遠くない(半キャラクタ分)
- 小ネタ
- 「史上最弱の主人公」として一部有名
- (ネタ参考スペランカー講座(クソゲー処理概論)・・・学習内容には全く関係ないけど)
- 「史上最弱の主人公」として一部有名
きこりの与作 (1981, エポック社)
- ジャンプ動作
- ジャンプボタンを押下→一定の高さまで一定速度でジャンプ→一定速度で下に下がる→地面に到達すると着地
- ジャンプ中は一切の操作を受け付けない
- (参考動画(YouTube): )
スターフォース (1984, テーカン)
- 「自機を追いかけてくる敵」をネタに使用
- 「現在の自機の位置」ではなく「少し前の自機の位置」の方向へ移動
- 数秒おきに「現在の自機の位置」の方向へ向かってくる
- 次第に間合いを詰められていく仕組み
カルドセプト エキスパンション (1999, メディアファクトリー)
カルドセプトサーガ (2006, バンダイナムコゲームズ)
- カード整列 http://www.youtube.com/watch?v=I7W4ameEDBE
- なぜか異常に遅い・・・
グラディウス (ファミコン版 1986, コナミ)
- 裏技
- 上上下下左右左右BA
- 「コナミコマンド」と呼ばれる有名な裏技
- これをフローチャートで示
- 上上下下左右左右BA
パックマン (1980, ナムコ)
- 敵キャラの動きのアルゴリズムが,裁判記録として残っている例
- 東京地裁 昭和56(ワ)8371 判決文 (参照: http://tyosaku.hanrei.jp/hanrei/cr/4932.html )
その他
Hatetris http://qntm.org/files/hatetris/hatetris.html
- その時点で一列をそろえるのに一番不都合なブロックが落ちてくる
- JavaScriptで設計されているので,ソースコードを確認可能