Реализация "жизни Конуэя" на javascript

gistfile1.js

//404-LIFE-JS 
//Author : Mikhail Svarichevsky [email protected]
//This work is licensed under Creative Commons Attribution 3.0 Unported License.
//You can read more about Conway's game of life at 
// http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
// http://ru.wikipedia.org/wiki/%D0%96%D0%B8%D0%B7%D0%BD%D1%8C_%28%D0%B8%D0%B3%D1%80%D0%B0%29 

//INIT --------------------------
//We are not using off-screen canvas for draving as we redraw only small part of screen,
//any copying everything from off-screen canvas is actually a bit slower
var gfx = document.getElementById('gfx');
var context = gfx.getContext('2d');

var page;// 0 / 1
var frame = 0;
var maxx = 256;
var maxy = 192;

//Hate this array initialization. Please, let me know if there is a portable way to create 3d array in 1 line.
var data = new Array(2);//flipping pages
data[0] = new Array(maxy);//Y
data[1] = new Array(maxy);//Y

for(page=0;page<2;page++)
  for (y=0;y<maxy;y++)
  {
    data[page][y]=new Array(maxx);
    for(x=0;x<=(maxx>>5);x++)//1 extra value so that we don't run over then array boundaries
      data[page][y][x]=0;
  }

page = 0;//First working page


function setColor(newColor)
{
  if(newColor)
    context.fillStyle = '#dc6783';else
    context.fillStyle = 'white';    
}

//We need to use requestAnimationFrame to stop animation when page is hidden in background tab, so that we don't load CPU when nobody is watching
window.requestAnimFrame = (function(){
  return  window.requestAnimationFrame       || 
          window.webkitRequestAnimationFrame || 
          window.mozRequestAnimationFrame    || 
          window.oRequestAnimationFrame      || 
          window.msRequestAnimationFrame     || 
          function( callback ){
            window.setTimeout(callback, 1);
          };
})();

//Here comes bit magic
//We store 32 bits in 1 array value
//Integers over 32 bit are stored as floating point
//So we should not expect things to 'wrap around' at 2^31 automagically like in C++
function getPixel(x,y,page)
{
  return (data[page][y][x>>5]>>(x&31))&1;//Cannot /32 as it would give floating point result in JS
}

function setPixel(x,y,page,value)
{
  data[page][y][x>>5] = (data[page][y][x>>5] & (~(1<<(x&31))))//clear position 
                        | 
                        ((value&1) << (x&31));//set our bit at proper position
}

function drawCell(x,y){}

function drawCellFunction(x,y)
{
  if(x<32 || y<32 || x>219 || y>150) return;
  //We shift out field a little so that user does not see funny glitches at the edges
  context.fillRect((x-32)*4+2, (y-32)*4+2, 3, 3);
}

function noDrawCellFunction(x,y){}//Used for benchmarks

function enableDrawing()
{
  drawCell = drawCellFunction;
}

function disableDrawing()
{
  drawCell = noDrawCellFunction;
}

function do1step()
{
  //As we have a rather small field, and it's supposed to be quite full,
  //quadtree optimization won't be effective here, as well as recording queue of cells changing state.
  
  //Hashing & memorization would require alot of memory to be effective and are "slow to start"
  
  //One optimization which might be useful here is to store cellstates as 32-bit per array value
  //Then as you go from left to right, you shift in new data each 16 bits (so that we always can access -1..17 cells)
  //take (&7) of the value to take first 3 cells, and using lookup table you calculate sum at first & last row.
  //(On modern CPU's we have special instruction for bitcointing - POPCNT, but it's such a luxury for JavaScript)
  //To save on memory access for lookup table, we pack it into 1 integer 
  //For middle row you use value (&5)
  //Although number of operation is not much lower, we are saving alot on slow array accesses and branches
  //
  // 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
  // Magick lookup number = 0b00000000000000001110100110010100
  //                                      Least significant  ^
  // Surely Javascript cannot eat binary constants, so we have to convert to dec or hex manually.
  // As it won't be readable anyway, let's convert it to octal just for lulz:
  // Magic number = 0164624
  // So now to calculate number of set bits in first 3 bits in our number we do:
  // (0164624 >> (number & 7)) & 3; So we need just 3 operations and no extra memory accesses
    
    
  //New state magic contant
  //Bit meaning: [...SSSSB] where S is sum, B is old cell state. 
  //This bit ordering allows faster calculation of lookup code
  //As a result we are getting new cell state
  //Rules are from http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
  //state_lookup = 0340;//0b0000000011100000;
  /*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
  ];*/
    
  readpage = page;
  writepage = 1-page; 
  
  //Set color to 1, as we draw all 1's first
  //We do so as color switch on canvas context is a slow operation
  //Doing 2 passes on the scene is still faster by ~50% than doing so in 1 pass but switching color on each cell
  //Too sad we can't have 2 contexts of the same canvas with different settings 
  setColor(1);
  
  //Saving partial sums for previous rows is not worth it, 
  //as we are not really reducing number of memory accesses
  
  //Calculating sums at the time of setting cell to 1
  //would require additional array pass to clear an array of sums
  //On C it might have been faster with memset and linear array, but on JS this approach might be slower.
  for(y=1;y<maxy-1;y++)//We do not process 1px border
  {
    //Let the magic begin
    v1 = 0;//previous line                                                         
    v2 = 0;//current value current line, current position is 2nd bit
    v3 = 0;//next line
    savedv1 = data[readpage][y-1][0];//Saved array values, so that we don't reread same values
    savedv2 = data[readpage][y  ][0];
    savedv3 = data[readpage][y+1][0];
    for(x=0;x<(maxx)>>5;x++)
    {
      v1=(savedv1<<1) | (v1>>>16);//input values must be shifted by 1 bit so that we can write at 32-bit boundary            
      v2=(savedv2<<1) | (v2>>>16);            
      v3=(savedv3<<1) | (v3>>>16);
      new_state = 0;
      
      s1=0;s2=0;s3=0;
      
      for(bit=0;bit<16;bit++)
      {
        sum = ((0164624 >>> (((v1>>>bit)&7)<<1))&3)+ 
              ((0164624 >>> (((v2>>>bit)&5)<<1))&3)+//&5 because we skip middle cell when calculating number of surrounding cells;
              ((0164624 >>> (((v3>>>bit)&7)<<1))&3);
          
        new_state |= ((0340 >>> ((sum<<1) | ((v2>>>(bit+1))&1)))&1)<<bit;
      }
      //shift input values by 16 and load some more data
      tmp1=data[readpage][y-1][x+1];
      tmp2=data[readpage][y  ][x+1];
      tmp3=data[readpage][y+1][x+1];
      
      v1=(savedv1>>>15) | (tmp1<<17);            
      v2=(savedv2>>>15) | (tmp2<<17);            
      v3=(savedv3>>>15) | (tmp3<<17);
      
      savedv1 = tmp1;
      savedv2 = tmp2;
      savedv3 = tmp3;
      
      for(bit=0;bit<16;bit++)
      {
        sum = ((0164624 >>> (((v1>>>bit)&7)<<1))&3)+ 
              ((0164624 >>> (((v2>>>bit)&5)<<1))&3)+//&5 because we skip middle cell when calculating number of surrounding cells;
              ((0164624 >>> (((v3>>>bit)&7)<<1))&3);

        new_state |= ((0340 >>> ((sum<<1) | ((v2>>>(bit+1))&1)))&1)<<(bit+16);
      }
      
      //New state for 32 cells is done, save them & draw all 1's
      data[writepage][y  ][x] = new_state;
      need_draw = (new_state ^ data[readpage][y  ][x]) & new_state;//Draw only changed cells, which are 1              
      
      if(need_draw)
        for(bit=0;bit<32;bit++)
          if((need_draw>>bit)&1)
            drawCell(x*32+bit,y);
    }
  }
  
  //Now draw all 0's
  setColor(0);
  for(y=1;y<maxy-1;y++)
    for(x=0;x<(maxx)>>5;x++)
    {
      new_state = data[writepage][y  ][x];
      need_draw = (new_state ^ data[readpage][y  ][x]) & (~new_state);//Draw only changed cells, which are 0              
      
      if(need_draw)
        for(bit=0;bit<32;bit++)
          if((need_draw>>bit)&1)
            drawCell(x*32+bit,y);
    }
   
  //No need to copy array, just flip the page
  page = 1-page;
}

function frameEventHandler()
{
  do1step();
  frame++;

  if(frame<20000)//Show must not go on for too long to save some power if page is left open accidentally
    setTimeout(function() {requestAnimFrame(frameEventHandler);}, Math.max(33 , 800.0/(frame+1)));
}

//NoDraw Performance, FPS (i7-3820 @4.3Ghz)
//            int storage     bit storage        FastBit  FastBit+Draw +Clipping
// FF12:         480                               1530      323          467
// IE9 :         177                               426       190          214
// Chrome:                                         1212      235          274

function benchmark_setTestData()
{
  //set test field
  enableDrawing();  
  for(iy=0;iy<maxy;iy++)
    for(ix=0;ix<maxx;ix++)
    {
      setPixel(ix,iy,page,(((~~(Math.sin((ix+1)*0.27365427)*Math.sin((iy+1)*0.8236465)*100000000.0))%2)==0)?1:0);//Some predictable randomization. We can't use random() as we cannot set seed is JS  
      setColor(getPixel(ix,iy,page));
      drawCell(ix,iy);//Shift it a little bit so that we don't see borders on the screen where behavior might be broken a bit  
    }
}

function benchmark_doIt()
{
  disableDrawing();//So that we test only computations
  start = new Date().getTime();

  for(i=0;i<5000;i++)
    do1step();

  end = new Date().getTime();
  //Redraw whole field to show final state
  enableDrawing();  
  for(iy=0;iy<maxy;iy++)
    for(ix=0;ix<maxx;ix++)
    {
      setColor(getPixel(ix,iy,page));
      drawCell(ix,iy);//Shift it a little bit so that we don't see borders on the screen where behavior might be broken a bit  
    }
  
  alert("FPS: " + (1000*5000/(end-…

gistfile2.html

<html>
<head></head>
<body>
<canvas id="gfx" width="755" height="479">
<img src="/i/404.png" alt="Canvas support is needed to show some fancy animation">
</canvas>
</body>
</html>