JSでのConwayのライフの作成と最適化

彼のハムスターのデザインを最近更新したと思いましたが、404番目のエラーで異常なページを作成する必要がありますか？ 幼少期には（多くの読者がそうであるように） ConwayのLifeに感銘を受けたため、JSに実装することにしました。



人生では難しいように思われます：忙しいセルに2つまたは3つの隣接セルがある場合、ちょうど3つの空のセルがある場合、それは残りますか？ この記事では、アルゴリズムの最適化とキャンバスでのレンダリングについて説明します。JavaScriptでの整数/バイナリ算術の明らかではない瞬間もあります。



将来を見ると、 ここで最終結果を見ることができ、そこにソースが表示されます（CC BYライセンスの下でも）。

簡単な方法で行く

for(y=1;y<maxy-1;y++)//We do not process 1px border for(x=1;x<maxx-1;x++) { sum = data[readpage][y-1][x-1] + data[readpage][y-1][x ] + data[readpage][y-1][x+1] + data[readpage][y ][x-1] + data[readpage][y ][x+1] + data[readpage][y+1][x-1] + data[readpage][y+1][x ] + data[readpage][y+1][x+1]; if(sum==3 || (sum==2 && data[readpage][y][x])) data[writepage][y][x] = 1; else data[writepage][y][x] = 0; setColor(data[writepage][y][x]); drawCell(x,y); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

確かに機能しますが、問題は1つだけです-i7-3820@4.3GhzおよびFirefox 12では、このコードは8.5 FPS（1秒あたりのフレーム数）のみを計算して描画します。 簡単なテストでは、レンダリングが遅くなることが示されています。

レンダリングの最適化

ピクセルは変更された場合にのみ描画されます-67 FPS。



なぜなら コンテキスト内の現在の色を各セルに切り替えるのは非常に難しい操作です。2つのパスで描画します。最初にすべてのセルを作成し、次にすべてのセルを削除します。1秒あたり80フレームです。 すべての計算フィールドが表示されるわけではないので（世界の終わりとの衝突による「グリッチ」が表示されないように）、画面に非表示のセルを描画しようとはしていません-125 FPS。



実際には、オフスクリーンキャンバスでの描画は加速しませんでしたが、反対に、可視キャンバスへのコピーによるわずかな低下がありました。



setTimeoutではなくrequestAnimationFrameからフレームのレンダリングを開始するだけです-ユーザーが見ないときにアニメーションを描画しないようにするため（たとえば、ページがブラウザーの背景タブにある場合）



おそらくアルゴリズムを最適化するために続けなければならない...

既存の最適化方法

Hashlifeは、ほぼ無限のフィールドでチャンピオンシップを保持しています。大まかに言うと、フィールドは四分木に分割され、同一のブロックは計算されず、キャッシュからの結果がすぐに取得されます。 ここでの問題は、そのようなアルゴリズムがゆっくりと「ポップアップ」し、大量のメモリを消費し、私たちの分野（256 * 192）で-電子顕微鏡で釘を打つようなものです。



別のグループのアルゴリズムは、空の（または変更がない）計算からフィールドブロックを除外します。 しかし、私の場合、フィールドはほとんど常にアクティビティで密集しているので、速度の増加はありますが、素晴らしいことではありません。



別のアプローチは、変化するセルのキューを保存し、配列の量をすぐに更新することです。 つまり X * Y * 8操作を行う代わりに、（前のステップで変更されたセルの数）* 8のみを行います。 もちろん、キューでの作業にはかなりのオーバーヘッドがありますが、密なフィールドであっても3〜5倍の加速を簡単に得ることができます（弱く埋められた大きなフィールドの場合、これはかなり良いアルゴリズムです）。

しかし、私は自分の道を行きます

基本的な考え方は、JS配列はオブジェクトで構成されているため、それらへのアクセスは比較的遅いということです。 さて、条件によるセルの新しい状態の計算は、予測できない分岐のために、プロセッサにとって常に悪いです。 したがって、配列の呼び出し回数を最小限に抑え、分岐せずにコードを書き換えます。



フィールドをビット形式で保存します（配列要素ごとに32個の値）。 JSの32ビット数は、符号付き（！）整数として正確に格納および解釈されますが、32ビットの少なくとも1つのユニットをクロールすると、実数を取得できます。 もう1つの興味深い機能は、JSに2つの右シフトコマンド、>>および>>>があることです。 >>>は、数値を符号なしとして扱います（そして符号付きビットではなく、空のスペースにゼロを「プッシュ」します）。 これは、32ビットすべてを使用する数値を操作するときに使用する必要があるシフトです。



これで、左から右に線に沿って進むと、値＆7の3つの連続したセルの値をすぐに取得できます。 これらのセルの合計を計算するには-8つの可能な組み合わせのルックアップテーブルを作成し、一度でも遅い配列にアクセスしないように-1つの数値にプッシュします。

 // Bitcounting trick: // IN CNT CNTBIN // 000 0 00 // 001 1 01 // 010 1 01 // 011 2 10 // 100 1 01 // 101 2 10 // 110 2 10 // 111 3 11 // Magik lookup number = 0b00000000000000001110100110010100 // Least significant ^ // in octal 0164624
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これで、配列への追加の呼び出しなしで、3つのセルの合計を一度に計算できます。

 sum = (0164624 >> ((value& 7)<<1)) & 3;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

同様に、上段と下段の金額を計算できます。 合計をカウントするセル自体を除外するには、中央の行で＆7ではなく＆5を実行します。 したがって、配列にアクセスせずに3行から3つの合計を取得しました。



次に、セルの新しい状態を取得する必要があります-再びルックアップテーブルを実行し、3ビットが合計（最大8）、1ビット-古い状態になります：

 /*state_lookup = [ //Old cell state //0 1 0 , 0 // 0 SUM , 0 , 0 // 1 , 0 , 1 // 2 , 1 , 1 // 3 , 0 , 0 // 4 , 0 , 0 // 5 , 0 , 0 // 6 , 0 , 0 // 7 , 0 , 0 // 8 ];*/ state_lookup = 0340; //0b0000000011100000;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これで、次のように分岐せずにセルの新しい状態を取得できます。

 (0340 >>> ((sum<<1) | (v2&1)))&1
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

32個のセルすべてを計算する方法を考えるだけです。このためには、左右に加えて1つのセルにアクセスする必要があります。 作業をそれぞれ16セルの2つの部分に分割し、左右に少なくとも1つのセルを追加でロードする必要があります（負の数値をシフトするときに上位桁に余分なものが入らないように、符号なしの右シフトが必要です）。 両方の16セルの半分を計算した後、完成した32ビットの数値が配列に書き込まれ、変更されたセルを描画する必要があります。



生まれた細胞は次のように取得できます。

 need_draw = (new_state ^ data[readpage][y ][x]) & new_state;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして死者：

 need_draw = (new_state ^ data[readpage][y ][x]) & ~new_state;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

need_draw == 0の場合、何も描画する必要はありません。それ以外の場合は、32ビットを超えて必要な変更を描画します。



最終的なコードは[ソースの表示]に表示されます。ここでは煩雑になりません。



また、ネイティブアプリケーションのハッピーライターは、512個のシングルビット値のルックアップテーブルを持つことができます。9ビットの古い環境から新しい状態を直接受信できます。 ルックアップテーブルは64バイトを使用し、L1キャッシュラインに正確に適合します...えー、夢、夢...

結果

最終的な速度は、古いコンピューターでもパフォーマンスにある程度の余裕があります（アニメーションコードは1秒あたり30フレーム以下を描画しようとします）。

ブラウザ	レンダリング付きFPS	レンダリングなしのFPS
Firefox 12	473	1545
IE 9	209	451
Chrome 19	274	1210

注目すべきは、Firefoxでハードウェアアクセラレーションを無効にすると、レンダリングの速度が〜1.5倍低下することです。 しかし、全体として、FireFoxがChromeによって設定されたパフォーマンスのレベルに到達したことを嬉しく思います。



ここでテストできます： レンダリングあり 、 レンダリングなし 。



完成したフォームの結果はここに表示されます 。 ちなみに、あなたが私のサイトでどんなジャムをうっかり見てしまったら-3@14.byにそれについて自由に書いてください 、私はむしろあなたからそれらについて学びたいです...



コメントの中で、さらなる最適化と一般的な生活についてのアイデアがあります！