tuedaの日記

2016-08-20

[] async/awaitを使ってUniformGridの衝突判定を非同期化してみる

空間アクセラレーター(UniformGridとかQuadTreeの事、標準的には何というんだろう)に衝突判定の問い合わせ(クエリー)をするのに非同期でやりたい、

という考えは誰でも思いついて実際 async/await で実装できる。一回実際に実装してみたいと思っていたのですよ。

UniformGridは前回作ったやつ。100個の○と1つAABBを入れて適当に動かして計測した。

UniformGrid(インターフェースはIAccelerator)に自分(shape)が何かと衝突しているかどうかを問い合わせる

同期メソッド CollidesAny() と非同期メソッド CollidesAnyAsync() を実装してある。呼び出し方はこんな感じ。

CollidesAnyAsnyc() の戻り値は Task<bool> でawaitを使って非同期実行かつ await より下を「継続実行」できる。

同期バージョン

        protected override void OnUpdate(int msec) {
            var acc = World.GetComponent<IAccelerator>();
            var shape = GetComponent<ICollisionShape>();

            var hit = acc.CollidesAny(shape); 
            circle.OutlineColor = hit ? Color.Red : Color.White;
        }

非同期バージョン

        protected override async void OnUpdate(int msec) {
            var acc = World.GetComponent<IAccelerator>();
            var shape = GetComponent<ICollisionShape>();

            var hit = await acc.CollidesAnyAsync(shape); 
            circle.OutlineColor = hit ? Color.Red : Color.White;
        }

CollidesAnyAsync() の実装はこんな感じ。

        public Task<bool> CollidesAnyAsync(ICollisionShape shape) {
            var task = Task.Run(() => CollidesAny(shape));
            //task.Wait();
            return task;
        }

コメントアウトしている task.Wait() はデバッグ用にここで強制的に待ち(同期実行化)を入れられるようにしてある。

ぶっちゃけ Task.Run() してるだけです。

そして実行結果。

同期バージョン

f:id:tueda_wolf:20160820181947p:image:w360

非同期バージョン

f:id:tueda_wolf:20160820181946p:image:w360

遅くなってるやん orz

まず同期バージョンの CollideAny を測ると20サイクル前後で帰ってきている。長くても100サイクル。

(ちょっと早すぎる気がするが深く考えないでおこう)

そもそも UnifromGrid の問い合わせなら一瞬で終わる。正確な衝突判定が必要な時は少し時間が掛かるがそれでも円とAABBだけなので100サイクルもかからず終わるだろう。

この時点でもう非同期化する必要がないのがわかるが、非同期版も測ると5万サイクル以上(なぜか段々長くなる)。

.Netのasync/awaitはスレッドプールを使ったかなり軽量な仕組みのはずだが、それでも起動には(問い合わせより)全然重いコストがかかる。

つまり非同期化する意味は無い。要するに企画倒れですね(^^;

3次元のポリゴンの判定だとベクトル計算を多用するのでもう少し違ってくるはずだが、単純な衝突判定を非同期化するメリットは何もない事がわかった。

実装上の注意点

非同期の衝突問い合わせを実装する上での注意点は2つ。

1つは、UniformGridのを同時に書き込み(修正)、クエリーしてはいけない。UnfiromGridは毎フレーム構築しフレームの一番はじめに行う。クエリーはフレームの途中。

こういう場合ロックするのではなく今クエリーに使っているUniformGridとは別に新しく構築し一気に入れ替えるのが鉄板。それがこれ。

        protected override void OnUpdate(int msec) {
            var shapes = World.Finds<ICollisionShape>();
            
            var tmp = new Dictionary<uint, List<ICollisionShape>>();
            foreach (var shape in shapes) {
                var indices = GetCellIndicesOnShape(shape);
                foreach (var index in indices) {
                     if (!tmp.ContainsKey(index)) {
                            tmp.Add(index, new List<ICollisionShape>());
                        }
                    tmp[index].Add(shape);
                }
            };
            cells = tmp;
        }

データは cells に入っているが直前のフレームのクエリーがまだ使っている可能性があるので消したり変更してはいけない。必ずそれとは別に作って(tmp)最後に入れ替える。

古い方は参照が切れるけどそのまま有効なのでクエリーで使い終わったらGCによって勝手に消える。

この最後の参照の入れ替えが.Netで確実にスレッドセーフであるかどうか怪しいが(よね?)、誰も問題にしていないということはたぶん大丈夫なんだろうと思う。

この常に新しいコレクションを作って丸ごと入れ替える戦略はMSのライブラリ ImmutableList でも使われている基本戦略。

(これデザインパターンみたいな名前がありそうだけど何と言うのだろう)

もう1つは非同期なので実行されるまでに衝突に使う座標が動いている可能性があること。

このゲームオブジェクト(EnemyCircle)は3つのコンポーネントからなり、

になっている。上から1,2,3の順番で実行される。

        public static Node Create(float x, float y, string name) {
            var nod = new Node(name);
            var cmp1 = new EnemyCircle(20);
            var cmp2 = new FeCircleShape(20);
            var cmp3 = new EnemyController();
            nod.Attach(cmp1);
            nod.Attach(cmp2);
            nod.Attach(cmp3);
            nod.Position = new Vector2f(x, y);

            return nod;
        }

1つ目のコンポーネントで衝突判定を行うが、同期実行の場合はここで完結するのでゲームオブジェクトの位置が動くことはない。

非同期の場合は1つ目の実行が終わる前に2つ目、3つ目が実行されるのでコントローラーによってオブジェクトの位置が動く事がある(というか確実に動く)。

何が困るかというとUniformGridはメモリを節約するためオブジェクトのモートン番号を持っているセルしかデータを持っていない(Dictionaryで実装している)ので、

うっかりコントローラーが位置を動かしてオブジェクトが1つも無かったセルに入るとデータが存在しないのでKeyNotFoundで落ちる。

下側のコメントアウトしている方が落ちるソース。上がキーが存在していないチェックあり。

        IEnumerable<ICollisionShape> PickupNearbyShapes(ICollisionShape shape) {
            var results = new List<ICollisionShape>();
            foreach (var x in GetCellIndicesOnShape(shape)) {
                if (cells.ContainsKey(x)) {
                    results.AddRange(cells[x]);
                }
                else {
                   // do nothing
                }
            }

            return results.Distinct();

            /*
            return (from x in GetCellIndicesOnShape(shape)
                    from shapes in cell[x]
                    select shapes).Distinct();
            */
        }

LINQで書けば一発だが、これは上記の理由で落ちる。LINQでDictionaryを扱う上ですごく不便なのはこの「キーが存在しない時」をうまく書けないこと。TryGetValue()はLINQには不適。

ImmutableDictionary では GetValueOrDefulat() でキーが存在しない時は null が返せるようになったが、やっぱりみんな不便だったんだろう。

2016-08-19

[] ゲームにはQuadTreeより圧倒的にUniformGridを使うべき

少なくともゲームでUniformGridではなくQuadTreeを実装する価値はまったくないと言える。

UniformGrid

UniformGridは簡単だ。ゲーム全体を縦横等間隔に区切って(i,j)のセルにかかっているオブジェクトをリストで持っておけばいい。

オブジェクトが区切り線をまたいでいるか、そもそもセルより大きい場合は複数のセルに登録される。

衝突判定の時は自分が重なっているセル(複数)に所属している全オブジェクトをリストアップすれば、それが衝突する可能性があるオブジェクトの全てだ。

セルは(i,j)の組を直接キーにする

Dictionary<Tuple<int,int>, Objects> cells

より、(i,j)の組から単一のint値を作ってキーにした方がいい。

Dictionary<int, Objects> cells

インデックスは j*width + i みたいなので良いが、モートン数(z-orderとも)を使うと通っぽくて素敵だ。

GenerateMortonCode()は下記のようになる。理論的な話はStackOverflowなどに沢山ある。

        uint SeperateBy1(ushort n) {
            uint i = (uint)n;
            i = (i | (i << 8)) & 0x00ff00ff;
            i = (i | (i << 4)) & 0x0f0f0f0f;
            i = (i | (i << 2)) & 0x33333333;
            return (i | (i << 1)) & 0x55555555;
        }

        uint GenerateMortonCode(ushort x, ushort y) {
            return SeperateBy1(x) | (SeperateBy1(y) << 1);
        }

UniformGridの利点はとにかく作るのも検索するのも簡単という点に尽きる。なにせ基本的にはセルサイズで割ってモートン数を計算するだけだ。

欠点はあまりメモリ効率が良くないという点だ。オブジェクトが境界線をまたいでる時は2つ登録されるし、そもそもセルより大きなオブジェクトは複数の参照が登録される。

参照の数は平均すればオブジェクトの2倍ぐらいだろうか。

あとUniformGridは毎フレームリセットしオブジェクトを再登録する。毎回作りなおさずに変更をトラッキングする手も考えられるがどちらが良いか不明。

QuadTree

QuadTree(4分木)も簡単だ。ひたすら4分割してセルに含まれるオブジェクトが一定数に達するか一定の深さに達するまで分割を繰り返す。

境界にまたがるオブジェクトは上位のノードに所属し1つのノードが複数のノードに登録されることはない。かならずオブジェクト全体を完全に含むセルに登録される。

QuadTreeの利点はUniformGridよりメモリ効率がいい事だ。境界をまたぐオブジェクトは(またがないで済む)上位ノードに登録されるので参照はオブジェトの数と同じになる。

QuadTreeもモートン数を使ってインデックス化するが、モートン数は階層(level)ごとに計算するのでキーはモートン数と階層の組になる。

Dictionary<Tuple<int,uint>, Objects> cells

まずこれが断然ダメ。Tupleは値型だがGetHashCode()で要素のボクシングが起きるのでキーが単一の整数値だったUniformGridに比べて格段に遅くなる。

一応線形4分木と言ってモートン数をルート階層から順に並べてキーを単一の整数値化もできるが、効果は予想の範囲内だと思われるので試したことはない。

モートン数を使った4分木の検索は最下層でオブジェクトを覆うすべてのセルのモートン数を求めてそこに登録されている衝突候補を記録し、

さらに1つ上の階層のモートン数を全部求めて〜、を一番上まで繰り返せばいい。

モートン数を求める際は毎回まじめに計算する必要はなくモートン数の性質から1つ下のモートン数を2ビット右にシフトすれば上位階層のモートン数になる。

重複したモートン数が出てくるので.Distinct()で重複を削除するのを忘れずに。

これをすべての階層分繰り返すと最終的にはモートン数は1つだけ”0”になる。ルート階層(分割なし)のモートン数はただ1つ0だけ。


で、このノードを上にたどったり下に辿るコストが馬鹿にならないのがQuadTreeを採用しない理由。

メモリとCPUのトレードオフ

UniformGridとQuadTreeの違いはオブジェクトが境界線をまたぐとき「両方のセルに登録する」のがUniformGrid、「上位のまたがないセルに1つだけ登録する」のがQuadTree。

結局のとところ両者の本質的な違いはこれだけだ。

UniformGridは冗長だがセル(i,j)がわかれば衝突する可能性のあるオブジェクトは自明なのに大してQuadTreeはツリーの上下も見ないと衝突候補を選び出せない。

この計算コストは最適化の余地はあるものの0にはできずUniformGridを超える事もありえない。

つまり○分木というと高速っぽいイメージがあるが、どう頑張ってもUnifromGridの方が早い。

UniformGridで唯一気になるのはメモリ効率の悪さに由来するキャッシュヒット率の悪化だが、

どうせ2Dのゲームで使う衝突判定はせいぜい100個なので気にしてもしょうがないと思う。.Netだし。

100個の円を適当に動かして衝突判定を行った結果。

全部vs全部

f:id:tueda_wolf:20160819201204p:image:w360

QuadTree

f:id:tueda_wolf:20160820092834p:image:w360

UniformGrid

f:id:tueda_wolf:20160819201200p:image:w360

2016-08-17

[] AltSeedなるゲームエンジンがあるのを知ったよ!

全然別の調べ物をしていたらAltSeedなるC++,C#ゲームエンジンを見つけたよ!

ざっとチュートリアルとかドキュメントを見ただけど、うん描画ライブラリに毛が生えた程度だな。

(チュートリアルが充実しているのは評価したい)

狙いは非常にいいと思うけど正直イマイチ。昔ながらの継承をベースにゲームを構築してるのでそれだけで使う気になれない。

気になったの階層型のシーン構造を作れない。アニメーションが作れない。シーンからゲームオブジェクトを探す仕組みがない。


AltSeedに限らず前から思っているんだがゲームエンジンは描画やキー入力から独立してゲームそのものを作るのに必要な機能だけ提供して欲しいと思う。

正直ゲームエンジンと称するものが単なる描画・キー入力ライブリでがっかりする事が多い。


2Dで良いから日本のゲーム業界で標準となるようなモダンなゲームエンジンが必要だとともう。

高校でプログラミング習うようになるしね。プログラミング習ったらゲーム作るよね!

2016-07-30

[] Visual Studioのソリューションエクスプローラーのインラインクラスビュー(?)を消せる拡張機能が存在する

Visual Studioのうんこ機能の1つ、ソリューションエクスプローラーのインラインクラスビュー(?)は消せる!

そういう拡張機能を作ってくれた人がいる!

https://visualstudiogallery.msdn.microsoft.com/62461a72-4255-4eac-a630-52758e9c3723

開発チームは何考えてエクスプローラーでファイルを表示してる時にクラスのメンバーを全部インライン表示しようと思ったのか・・・

ファイルが多くなると(普通は多くなる)邪魔どころの騒ぎではなく、エクスプローラーが使い物にならなくなる。

あそこにファイル以外に表示されたら困るんだよ! 完璧に諦めていたがあのインライン表示を隠す拡張機能があった。

やったね!

あとファイルの下にファイルを階層化してくれる拡張も入れるといい感じ

https://visualstudiogallery.msdn.microsoft.com/3ebde8fb-26d8-4374-a0eb-1e4e2665070c

この2つを入れたらだいぶスッキリした。まったくVisualStudioは最高だぜ。

f:id:tueda_wolf:20160730182224p:image

2016-07-24

[] 関東で地震多くね?

http://www3.nhk.or.jp/sokuho/jishin/

ここ1周間、伊豆から北関東にかけて規模はさほど大きくないもののずいぶん地震が発生している。

マジで東海地震か関東大震災のどちらかの前震だと思うんだが関東民大丈夫か。