見出し画像

MGL週報 #12 - 続・タスクシステム（詳細編）など

Acerola

このエントリはゲーム開発用フレームワーク「MGL」の開発記録です．MGLは次のWebサイトにて無償で公開されています．

先週に引き続き，バージョン1.1.3のリリースに向けた作業を行なっています．
リリースは今週中のどこかで行う予定です．

タスクシステム改修の詳細

先週予告していた通り，MGLのタスクシステムの改修内容を少し詳しく説明しましょう．

この内容は極力簡潔に書くつもりでしたが，結局長めでやや専門的な内容になってしまいました．この手の内容は一旦適当に流し読みし，必要になった時に読み返す方が良いかもしれません．

なお，この変更はまだリリース前の段階ですので，今後変更になる可能性もあります．

変更前のタスクリスト

まず，変更前のタスクシステムの仕組みを説明します．次の図は，元々（バージョン1.1.2まで）のタスクリストの概略図です．

MGL 1.1.2までのタスクリスト

至ってシンプルな，何の捻りもない連結リストですね．

ここで重要な前提を先に説明しておきます．MGLのタスクシステムは実行順序に厳格であるため，TaskA→TaskB→TaskCの実行順は決して前後しません．もし新たにTaskBを追加したい場合，そのタスクは必ずTaskAよりも後かつTaskCよりも前の位置に挿入しなければなりません．

さて，連結リストは挿入と削除が高速な反面，ランダムアクセスができません．もし途中にある要素にアクセスしたい場合は，先頭から順に検索してその要素を見つけなければなりません．このため，要素数が増えれば増えるほどリストの検索コストが増大します．

図の例で言うと，新たにTaskBを追加しようとした場合，その挿入位置を特定するための検索コストはTaskAの数に比例してしまいます．今日主流のコンピュータの性能であれば100や200程度の数なら大きな問題に至らないかもしれませんが，それでも同じ処理に対してコストが大きく変動するのはアルゴリズムとして好ましいものではありません．タスクの数の桁が増えれば無視できないコストになるのは言わずもがなです．

また，この仕組みには並列処理においても大きな欠点があります．リストにアクセスしている間は競合を防ぐために異なるスレッドから書き換えることができません．しかし，各タスクはタスクリストの要素を順に実行するのですから，タスクの実行期間中に別のスレッドから変更を行うのは不可能ではなくともリスキーです．ドキュメントの既知の問題・不具合に書かれている「タスクノードの追加はタスクの実行と同じスレッドで行う必要がある」という問題は主にこれが原因です．（後々気付いたのですが，ドキュメントに書かれているタスクノードの削除に関しては誤りです．これは対策されていました）

これらの問題を今のデータ構造のまま解決することも可能かもしれませんが，まず間違いなくトリッキーなアルゴリズムになってしまうでしょう．こういった場合，アルゴリズムを捻るよりもデータ構造を扱いやすくする方が幸せになれます．

新しいタスクリスト

という訳で，新たに新調したタスクリストのデータ構造はこちらです．

MGL 1.1.3以降（予定）のタスクリスト

まず，タスクリストを単一ではなく，タスクの種類ごとに保持させるためにサブリストを追加しました．同種のタスクは同じサブリストに追加されます．これにより，タスクリストの検索コストはタスクの数ではなく，タスクの種類の数に比例するようになります．

また，サブリストはアクティブリストとスタンバイリストの2つのリストを保持しています．タスクを新たに追加した場合は最初にスタンバイリストへと追加され，それを適切なタイミングでアクティブリストの末尾に連結する仕組みです．具体的には，タスク実行前に全てのサブリストに対してアクティベートを行い，そのタイミングで全てのスタンバイタスクがアクティブになります．

この仕組みであれば，異なるスレッド間でタスクリストに変更を加える場合でも，同期処理をスタンバイリストに対してのみに限定できます．また，同期待ちが発生するのは同じサブリストに対する操作のみとなるため，不要なスピンロックの回避にも繋がります．

もう1点，細かいメリットとして，各々のサブリストはアクティブリストとスタンバイリストの先頭と末尾を保持しています．このため，サブリストが特定された後であれば，それ以上リストの検索は発生しません．タスクの追加やアクティベート処理は，単に要素の一部を書き換えるだけで完結します．

問題点

この仕組みの欠点は，タスクの種類が増えればそれに比例してサブリストの検索コストが増加することです．これは作るゲームの規模によっては問題となる場合があるでしょう．

参考までに，「反撃BLOCKS」のタスクは66種類，「ぺぐそり＋」は32種類でした．中にはデバッグ用タスクもあり，これら全てが同時に登録されている訳ではありませんが，ゲームの規模に対するタスクの種類はおおよそこれくらいです．（作り方によっても変わってくるため，あまり参考にはならないかもしれません）

この問題に対する解決策も一応2つほど考えてあります．

まず1つ目は，サブリストを更に階層化して管理する案．例えばサブリストを4つのグループに分けて管理し，上手く均等に分散させれば検索コストは約4分の1になります．

もう1つは，タスクの種類を識別するための値（タスクID）の最大値分の配列を用意し，連結リストではなく配列アクセスにする案です．この方法ならランダムアクセスが可能なため検索そのものが発生しません．ただし，タスクIDが連番である必要があり，先にIDの最大値を知る必要もあります．つまり，ユーザー側にいくつかのルールを課す必要が生じます．

将来どのような対処を行うにせよ，現時点ではこの問題に取り組むのは時期尚早と言えるため，少なくとも次のバージョンには入れる予定はありません．クヌース先生の言葉を借りるなら「早すぎる最適化は全ての悪の元凶」です．

ゲームパッド入力の不具合

新タスクシステムの実験のためにちょっとしたゲームっぽい何かを作って気付いたのですが，ゲームパッドに関する結構まずい不具合を発見してしまいました．Appleが正式にサポートしているゲームパッドにおいて，左スティックの状態から擬似的に更新されるアナログ4方向が正しく反映されていません．

アナログ4方向が何なのかと言うと，左スティックの入力を通常のD-Padのように擬似的にボタン入力として扱うための仕組みです．左スティックを右に倒せばAnalogRightが，上に倒せばAnalogUpが，右上に倒せばその両方がボタンの入力状態として更新されます．

この入力状態の更新処理は，左スティックの入力角度を元に算出して行なっています．一方，AppleのGameControllerフレームワークにも同じようにスティックの入力方向をボタンとして扱うAPIがあった（と勘違いしていた）ため，これをそのまま利用していました．

しかし，どうやらAppleのAPIは「少しでもその方向に傾いていれば入力扱い」だったようです．その結果，真っ直ぐ右にスティックを倒したつもりでも右上か右下のどちらかに入ってしまうという問題が発生しています．理屈上は極めて正確に右に倒せば正しく入力されますが，これを正しいと呼ぶプレイヤーはまずいないでしょう．

……でもさ，

if (gamepad.leftThumbstick.right.pressed)
{
    ...
}

って書いて上や下にスティックを倒しても条件が成立するとは思わないじゃないですか．いや，私の確認不足が最大の理由なのですが．

また，DualShock4/DualSenseの別名定義で□ボタンと△ボタンが逆になっているという問題も見つけてしまいました．こちらは純然たる私のうっかりミスです．

MGLはかなり多くのゲームパッドに対応しており，動作確認のための各種製品も置き場に困るくらい大量に用意してあったりもします．一方で，普段使用するのはそのうちの一部でしかないため，チェックが甘い製品があるのも事実です．今一度，時間を多く割いてでも手元の製品の動作検証を行う必要がありそうです．

……とりあえず，今後は使用するゲームパッドを日替わりで変更しましょうか．

その他

お仕事依頼のご相談がさっぱり来ないので今週もリンク貼り付けておきますね．

あなたの依頼で救われる命があります．ここに．

この記事が気に入ったらサポートをしてみませんか？