「がんばれない」けど「がんばりたい」

ITエンジニアの仕事のこと。AI、機械学習、ディープラーニング。地頭力。車のこと。

Algorithmic Efficiency bin-lattice spatial subdivision|Nature of Code

f:id:studio23c:20171027004203p:plain プログラムではloop処理が多数使われます。これまでTryしてきた事もフンダンにloop処理を書いてきました。前回のFlocking SystemでBoidオブジェクトの数が多くなるとフレームレートも伴って落ちて行きます。私が使っているMacBookPro15 2011 earyモデルでも110個くらいのBoidオブジェクトだと60fps近く出るのですが、それ以上になると途端に処理が重くなります。

この記事では幾つか処理を軽くする為のアルゴリズムの1つとして有名なbin-lattice spatial subdivisionをまとめてみようと思います。

vimeo.com


Flocking Systemではループ内で自分以外のboidオブジェクトとの距離を計算し、その距離によって次の振る舞いを決定していますが、例えば100個のboidオブジェクトが存在する場合、毎フレームごとに100 x 100 = 10,000回チェックを行います。最近のコンピュータの処理速度は速いので、この程度だと問題ないのですが、1000個のboidオブジェクトになるとどうでしょうか? 1000 x 1000 = 1000000回(百万)のチェックや計算を1フレームで行う必要になります。


bin-Lattice spatial subdivision 画面全体を幾つかの小さなcell(グリッド)の集まりと考えるアルゴリズムです。例えば2,000boidsオブジェクトが存在すると仮定すると、1フレームで計算する回数は2,000 x 2000 = 4000000(4百万)回になります。 この条件で画面を10分割する事が出来ないか?そして処理を細かくすることで、負荷を下げる事が出来ないか?という事をイメージしてみます。 10x10分割すると1つのcellには平均で20個のboidオブジェクトが存在する事になります。もちろんboidは動き回るので任意のフレーム(サイクル)において、boidが多く存在するcellもあれば少ない…もしくは全く存在しないcellも発生します。ですが、平均すると任意のタイミングにおいて1cellあたり20個(20 x 10 x 10 = 2,000)のboidsオブジェクトが存在する計算になります。 このように画面を【分割】して、それぞれのcellを1つの画面のように考えて処理を行えば全体の処理数を減らす事が出来ます。

上述の条件を例にすると1画面の場合は4,000,000回/サイクルだったのに対して、10分割した場合、1cell辺り平均20boidsとすると、20 x 20 = 400回/サイクル。このcellが10 x 10個存在するので1サイクル辺りの総処理数は400 x 10 x 10 = 40,000回/サイクル。1/100の処理に落とす事が出来ます。


実装(c++)
まず考え方として「画面は10x10マスに分割されている」というイメージが重要になります。つまり主人公がこれまでboidオブジェクトだったのに対して分割された個々のcellに変化するイメージを持ってください。実は今までも同じ様に【画面(cell)】が主人公だったのですが画面数(cell数)=1だったので意識として主人公はboidの様に感じていたとも言えます。

主人公がcellになったので、そのcell単位でloopを回して処理を行って行きます。流れとしては、

1)任意のcellに注目
2)cell内に存在するboidオブジェクトに対してseparation, cohesion, align処理を行う

1)の任意のcellの管理はどう行えばイイでしょう?10 x 10のcellを管理するので2次元配列になるイメージは着きやすいかと思います。

では配列の型は何になりますか?cellというクラスを作りますか? 否もう一度!これまでのflocking systemで、どうやっていたのか?を思い出してみます。1つの画面内で行っていました。cell1個っていうイメージです。この時にcellクラスなんて作ってないですよね? 全てのboidオブジェクトは1cell内に存在していたのです。逆に言うと1 x 1のマスに全てのboidオブジェクトが存在しているとも言えます。 今回は10 x 10分割されています。なので各cellを1つの画面として捉え、そのcell内のboidオブジェクトに着目して処理を行う事が出来ます。

では任意cell内に存在するboidオブジェクトを参照するにはどうすれば良いでしょうか。前回でのboidオブジェクトは1つの配列で管理していました。

vectorBoid> boids;

このvector配列内にオブジェクトが1x1に分割したcell…つまり画面全体に存在していました。今回は上記vectorとは別に10 x 10の2次元配列を用意します。そしてそれぞれの要素には最大でboids.size()個のboidオブジェクトの参照が入れられるようにします。

vectorvectorBoid*> > cells;

cellsはvectorなのでcells[0]の様にブランケット内にindexを指定して参照可能です。型はBoidではなくて vector<Boid> 。つまりvectorの中にvectorがある=2次元配列というわけです。


[setup]

1)分割数を決める
明示的に10x10と決めるのではなくて1つのcellの幅と高さをピクセルで指定しcols, rowsという変数に分割数を代入します。int scale = 16;としてcellの幅と高さを16ピクセルに指定するなどです。

2)2次元配列の宣言
ここは上述した通りです。適当に宣言しておきます。宣言した配列もvectorなので1)で決まったcols * rows個のメモリを確保しておきましょう。

3)boids配列の初期化
前回と同様にvector boids内にインスタンスを入れて行きます。


[update]

1)cells配列をクリア
boidオブジェクトは常にlocationが更新されるため、所属するcellも変化します。そのためupdate内で毎回cells配列を更新する為に、一旦前フレームで取得したboidオブジェクトの参照をクリアしています。

2)各boidオブジェクトの参照をcellsに登録
boids配列に存在する各々のboidオブジェクトが、どのcellに所属するかを決定し、boidオブジェクトの参照(アドレス)をcellsに登録して行きます。 boidオブジェクトのlocationを参照し、どのcell(2列目の3行目のcellなのか?など)かを決定し、そのcellにアドレスをpush_backしていきます。

3)各cell毎に処理を実行。
各cell内に存在する各boidオブジェクトを取り出しflocking behaviorsメソッドを実行します。この部分は前Flocking Systemと変わりません。 ここで注意。各cell内で閉じたboidオブジェクトに対して行うと、Flocking で行っているseparationやcohesion,alignが、boidから他のboidまでの距離を計算して振る舞いを決めているため、その距離のしきい値がcell内からはみ出してしまう可能性が多分にあります。そのため「cell毎に処理を行う」と記述していますが、実は上下左右のcellを含めて1つの画面と見なしています。 上述した距離の値がcellから絶対に飛び出さない値になっていれば良いと思いますが、cell(16 x 16ピクセル)の範囲の、どの位置にboidが存在するかは分からない(端っこにいるかもしれない)ので、上下左右のcellを含めた合計9個のcellを1つのcellと見なして処理を行う事をセオリーとしていた方が良いと今は思っています。

[draw]

boids配列内に存在する各々のboidオブジェクトをdrawします。ここも前Flocking Systemと変更ないですね。


要するに きも となるのは、

  • 画面を分割する事
  • boidオブジェクトを分割されて出来たcellの適切なcellに登録する事
  • cell毎にboidオブジェクトの次の振る舞いを決定する事

の3点になります。一番きもになるのは、結局「画面を分割する」イメージですね。

コード|updateのところだけ参考に掲載しておきます。

void testApp::update(){

    //cellsが保持するオブジェクトの参照を削除
    for (int i = 0; i &lt; cols; i++) {
        for (int j = 0; j &lt; rows; j++) {
            cells[i*rows+j].clear();
        }
    }


    //全てのBoidオブジェクト参照をcellsに登録
    int allBoidSize = boids.size();
    for (int i = 0; i &lt; allBoidSize; i++)
    {
        //このBoidが、cellsのどこに当てはまるかを登録する
        Boid* v = &amp;boids[i];

        int x = int(v-&gt;location.x) / scl;
        int y = int(v-&gt;location.y) / scl;
        if (x == cols) x-=1;
        if (y == rows) y-=1;

        if (x &gt;= 0 &amp;&amp; x &lt; cols &amp;&amp; y &gt;= 0 &amp;&amp; y &lt; rows)
        {
            cells[(x*rows) + y].push_back(v);
        }
    }


    //cells毎に処理
    for (int x = 0; x &lt; cols; x++)
    {
        for (int y = 0; y &lt; rows; y++)
        {
            //x,yのcell内に存在するBoidオブジェクトAに対して
            //applyBehaviors, update, borderを行う。
            //この時、それぞれのBoidオブジェクトが比較する他Boidオブジェクトは、
            //画面内全てのBoidではなく、
            //オブジェクトAが存在するcell内+cellの上下左右cellに存在する
            //Boidオブジェクトにする。

            //cellを決定し注目するBoidオブジェクト参照を得る
            //cells[*]にはBoidのアドレス型が入る【配列】が入っている
            vector&lt;Boid*&gt;cell = cells[x*rows+y];
            for (int vIndex = 0; vIndex &lt; cells[x*rows+y].size(); vIndex++)
            {
                //注目するBoidオブジェクトの参照A
                Boid* v = cell[vIndex];

                //比較するBoidオブジェクトを作成する
                boids2.clear();
                for (int n = -1; n &lt;= 1; n++)
                {
                    for (int m = -1; m &lt;= 1; m++)
                    {
                        int index_search_x = x + n;
                        int index_search_y = y + m;
                        if (index_search_x &gt;=0 &amp;&amp; index_search_x &lt; cols &amp;&amp; index_search_y &gt;= 0 &amp;&amp; index_search_y &lt; rows)
                        {
                            vector&lt;Boid*&gt;searchCell = cells[index_search_x * rows + index_search_y];
                            for (int targetBoidIndex = 0; targetBoidIndex &lt; searchCell.size(); targetBoidIndex++)
                            {
                                Boid* other = searchCell[targetBoidIndex];
                                boids2.push_back(*other);
                            }
                        }
                    }
                }

                v-&gt;applyBehaviors(boids2, separationSlider, alignSlider, cohesionSlider);
                v-&gt;update();
                v-&gt;borders();
            }

        }
    }
}