読者です 読者をやめる 読者になる 読者になる

c++でスマートポインタを使いつつ複雑なデータ構造を実現する(キーバインディングのために)

昨日くらいからゲームで使うイベントハンドラを作っています。そこで各イベントに割り当てられたコールバック関数を管理するデータ構造を考えていています。hashの添字でアクションをバインドして、そこからコールバックを呼ぶみたいなやつ。これを管理するわかりやすいデータ構造とコールバックの関係は、

アクションハッシュ[アクション名1]-*コールバック関数ポインタ
アクションハッシュ[アクション名2]-*コールバック関数ポインタ
アクションハッシュ[アクション名3]-*コールバック関数ポインタ
アクションハッシュ[アクション名4]-*コールバック関数ポインタ

みたいなのが分かりやすい。

アクションハッシュ[ジャンプボタン]-*ジャンプを実現させる関数ポインタ
アクションハッシュ[パンチボタン]-*パンチを実現させる関数ポインタ
アクションハッシュ[キックボタン]-*キックを実現させる関数ポインタ
アクションハッシュ[必殺技入力]-*必殺技を実現させる関数ポインタ

と書くともうちょっとわかりやすいでしょうか。

しかし、このままだと1アクションに1機能しか割り当てができない。また、シーンの移動などで、ジャンプが出来ない状態になった時、コールバックを削除する際に関数ポインタの型みたいなのを総なめにしないといけない。

これらを解決するために

アクションハッシュ[アクション名]
 ┗アクションに対応したコールバック配列
   ┣コールバック情報が入った構造体1
   ┣コールバック情報が入った構造体2
   ┗コールバック情報が入った構造体3

みたいなデータ構造を検討してみた。アクションへはo(1)で到達できるし、コールバックのリストは基本1つか多くても片手で数えられるはずなので、そこを線形処理しても大してコストはかからないだろうというわけ。最終情報が構造体なのは、IDで管理したりコールバック属性(他のリスナーを排他にするかとか、スリープとか)を管理するため。

でテストで書いたコードがこれ

#include <iostream>
#include <deque>
#include <unordered_map>

// 上の例でいえばこのクラスが最終的なデータ=コールバックが入った構造体と同じ場所に位置する
class TestClass {
public:
    int my_num = 0;
    TestClass(int i) : my_num(i) {}
    void hello(){
        std::cout << "hello world:" << my_num << std::endl;
    }
}; 
 
int main() {
    // 最終データをスマポでくるんだ宣言
    using sPtrTestClass  = std::shared_ptr<TestClass>;
    // さらにそれをスマポでくるんだdeque(上記の例でいえば配列)
    using sPtrDequeTest  = std::shared_ptr<std::deque<sPtrTestClass>>;
    // さらにそれをスマポでくるんだunordered_map。キーは文字列型
    using sPtrTContainer = std::shared_ptr<std::unordered_map<std::string, sPtrDequeTest>>;

    // 上記までがデータ構造の準備。以下データの登録

    // 最終データを3つくってみる
    sPtrTestClass t1{ new TestClass(1)};
    sPtrTestClass t2{ new TestClass(2)};
    sPtrTestClass t3{ new TestClass(3)};

    // 最終データをdequeに3つ放り込む
    sPtrDequeTest ary{new std::deque<sPtrTestClass>{t1, t2, t3}};

    //  アクションを登録するハッシュの初期化
    sPtrTContainer map{new std::unordered_map<std::string, sPtrDequeTest> {}};

    // テストという添字でdequeを突っ込む
    (*map.get())["test"] = std::move(ary);

    // アクション"test"に登録されているデータの呼び出し例。実際はイテレータで先頭からコールバックを呼び出すことになる
    (*(*map.get())["test"].get())[0]->hello();
    (*(*map.get())["test"].get())[1]->hello();
    (*(*map.get())["test"].get())[2]->hello();

}
出力:
hello world:1
hello world:2
hello world:3

usingほげほげの部分がまず何をしているか意味がわかりづらい。これはデータ構造が3段階で、そのままデータ構造を表現するとあほみたいな表記になるので、3段階それぞれにusingで別名を付けています。それをしなかった場合、アクションを登録するハッシュの型は

std::shared_ptr<std::unordered_map<std::string,  std::shared_ptr<std::deque<std::shared_ptr<TestClass>>>>>;

ということになる。3層構造ってだけでもう取り返しが付かないシンタックス。

また呼び出し部分

(*(*map.get())["test"].get())[0]->hello();

これもごちゃごちゃしてわからない。これ何してるかというとstdのスマートポインタには添字アクセスのオペランドを処理する機能が付いていない。そのため、生ポインタを取得する.get()を2度(ハッシュの添字解決、dequeの添字解決)行っている。->みたいにアクセスできるもんだとてっきり思ってたが、そうではないらしい。

map->["test"]->[0]->hello();

みたいなのをイメージしてくれたら良い。

できないことはないC++なので、上記の表記もきっと実現できるんだろうけど、ここまで書いていったい僕は何をやっているんだろうという気持ちになってきて、やめました。

とりあえず目的のデータ構造は実現できたが果たしてコレが必要なのだろうか。

本当に必要なの?

気になった所としては

  • 適当にstd::vectorやarrayに格納してforで回したほうが速いんじゃないか?
  • 各オブジェクトの生成コストのが高いんじゃないか?
  • こんなゴミみたいなコードほんとにみんな書いてるのか?

コードを高速化する手段 – 二流プログラマの三流な日常

上記ページなんかではvectorをmapやlistに代替えするにはそれ相応のデータ規模でないとむしろ遅くなるという言及があります。やはり、100や200のキーバインドにこんなデータ構造を使うのはバカげている気がしてきます。
baptiste-wicht.com

std::vector and std::deque perform always faster than std::list with very small data
(小さなデータを扱う時、std::listよりstd::vectorやstd::dequeのほうが常に速い)

ふうむ。

僕はWeb出身です。なので、データへのアクセスに関しては線形探索は絶対避けるべき。ソートもまず避ける。できるだけo(1)を目指すのが正義だと思っています。だからこそ今回のようなデータ構造を実現しようとしてきたわけです。しかし、この発想の根源というのは、秒間数万だとか数百万リクエストに対して数万数十万のユーザーを識別しつつスケーラビリティの乏しいDBを保護するためのものなわけです。これがスタンドアロンな実行環境になると、1度頭を切り替えたほうが良いと思えてきました。ざっくり言えばループで総当りしたほうが良い場合のほうが多いのではないか?

アクションへのo(1)アクセスのために添字が使いたいからといって、バインディングマップを馬鹿正直にunordered_mapで管理する必要があるのかもちょっとした疑問が出て来ます。添字はenumでいいのでは? じゃあvectorで良いということになります。

また、プレイヤーから入力される情報は限られています。キーボードのキーの数、マウスのカーソル位置とボタンが3つくらい、あとはゲームパッド。これらの中からゲームが対応すべき入力の種類なんて、いいとこ10や20なんじゃないか。じゃあ、mapじゃなくてゲームに予想されるアクションを変数で確保しておくこともやぶさかじゃないんじゃないかなあという考えにも行き着く。

さらに1つのアクションに対するコールバックを複数管理する必要性もここまでくると良くわからなくなってきた。たとえばジャンプボタンを押すと2人のキャラが同時にジャンプするにしたって…。1つのコールバック関数で管理してコールバック関数側で2人分を動かしたほうがいいんじゃないか。


などと考えているため全然ゲーム制作が進みません。。

※最終的にステート単位でキーバインドを管理する事にしました