title: Conway's Game of Life - beyond the grid
body: <p>Ok so there are a lot of "Conway's Game of Life" questions but this one is pretty specific. I'm going to have to throw a bunch of code at you first, break it down and show you where the issue is.</p>
  
  <p>So here is my Conway's Game of Life implementation so far, right now it is limited to the console for debugging (JSfiddle - <a href="http://jsfiddle.net/georeith/C9Gyr/8/" rel="nofollow noreferrer">http://jsfiddle.net/georeith/C9Gyr/8/</a> - fire it up, open your console):</p>
  
  <pre><code>var utils = {};
  
  /*
   * utils.extend()
   * - Extend initial object with all properties of following objects, objects later in the argument list take precedence.
   */
  utils.extend = function(obj) {
    var args = Array.prototype.slice.call(arguments, 1);
    for (var i = args.length; i--;) {
      for (var prop in args[i]) {
        obj[prop] = args[i][prop];
      }
    }
    return obj;
  }
  
  /*
   * utils.defaults()
   * - Overwrite initial object with properties of following objects only if key is present in the initial object.
   */
  utils.defaults = function(obj) {
    var args = Array.prototype.slice.call(arguments, 1);
    for (var i = args.length; i--;) {
      for (var prop in args[i]) {
        if (obj.hasOwnProperty(prop)) {
          obj[prop] = args[i][prop];
        }
      }
    }
    return obj;
  }
  
  /* no-wrap positioning functions */
  var calcPos = {
    ul: function(cell) {
      return [cell.x - 1, cell.y - 1];
    },
    um: function(cell) {
      return [cell.x, cell.y - 1];
    },
    ur: function(cell) {
      return [cell.x + 1, cell.y - 1];
    },
    l: function(cell) {
      return [cell.x - 1, cell.y];
    },
    r: function(cell) {
      return [cell.x + 1, cell.y];
    },
    ll: function(cell) {
      return [cell.x - 1, cell.y + 1];
    },
    lm: function(cell) {
      return [cell.x, cell.y + 1];
    },
    lr: function(cell) {
      return [cell.x + 1, cell.y + 1];
    }
  }
  
  var worldDefaults = {
    rows: 50,
    columns: 50,
    wrap: true, // left edge is mirrored on right, top edge is mirrored on bottom. Vice versa
    speed: -1, // milliseconds (minimum time, waits until end of last tick to calculate from)
    grid: []
  }
  var World = function (opts) {
    this.settings = utils.defaults(worldDefaults, opts);
  
    this.maxX = this.settings.columns - 1;
    this.maxY = this.settings.rows -1;
    for (var y = 0, yLen = this.settings.rows; y &lt; yLen; ++y) {
      for (var x = 0, xLen = this.settings.columns; x &lt; xLen; ++x) { 
        if (y === 0) {
          this.cellList.push([]);
          if (this.settings.grid.length &lt;= x) {
            this.settings.grid.push([]);
          }
        }
        var cell = new Cell();
        cell.x = x;
        cell.y = y;
        cell.alive = !!this.settings.grid[x][y];
  
        if (cell.alive) {
          this.lifeList.push(cell);
        }
  
        var lx = (x) ? x - 1 : this.maxX;
        var uy = (y) ? y - 1 : this.maxY;
        var ux = (x == this.maxX) ? 0 : x + 1;
        var ly = (y == this.maxY) ? 0 : y + 1;
  
        cell.neighbourCoords = (this.settings.wrap) ?
        [
          [lx, uy],   [x, uy],  [ux, uy],
          [lx,  y], /*[x,  y]*/ [ux,  y],
          [lx, ly],   [x, ly],  [ux, ly]
        ]
        :
        [
          calcPos.ul, calcPos.um, calcPos.ur,
          calcPos.l, calcPos.r,
          calcPos.ll, calcPos.lm, calcPos.lr
        ]
        ;
        this.cellList[x][y] = cell;
      }
    }
  }
  World.prototype.generation = 0;
  World.prototype.cellList = [];
  World.prototype.lifeList = [];
  World.prototype.changeList = [];
  World.prototype.nextTick = null;
  
  /* Progresses the world */
  World.prototype.tick = function() {
    var newLifeList = [];
    this.changeList = [];
  
    // This hash goes out of scope after each tick allowing any dead shadowCells to be garbage collected
    if (!this.settings.wrap) {
      var shadowCellHash = {};
    }
  
    for (var i = 0, iLen = this.lifeList.length; i &lt; iLen; ++i) {
      var cell = this.lifeList[i];
      if (cell.key) {
        shadowCellHash[cell.key] = cell;
      }
      cell.neighbours = 0;
      cell.lastIterated = this.generation;
  
      for (var j = 0, jLen = cell.neighbourCoords.length; j &lt; jLen; ++j) {
  
        var coords;
        var neighbour;
        if (this.settings.wrap) {
          coords = cell.neighbourCoords[j];
          neighbour = this.cellList[coords[0]][coords[1]];
  
        } else {
          coords = cell.neighbourCoords[j](cell);
          if (coords[0] &gt; this.maxX || coords[0] &lt; 0 || coords[1] &gt; this.maxY || coords[1] &lt; 0) {
            // This neighbour is off the screen so will require a shadowCell
            var key = ''+coords[0]+','+coords[1];
            if (!shadowCellHash[key]) {
              neighbour = shadowCellHash[key] = new ShadowCell(coords[0], coords[1]);
              neighbour.neighbourCoords = cell.neighbourCoords;
            } else {
              neighbour = shadowCellHash[key];
            }
          } else {
            neighbour = this.cellList[coords[0]][coords[1]];
          }
        }
  
  
        if (neighbour.lastIterated !== this.generation) {
          neighbour.neighbours = 0;
          neighbour.lastIterated = this.generation;
        }
        if (neighbour.alive !== neighbour.changed) {
          // neighbour started as alive
          ++cell.neighbours;
        } else {
          // neighbour started as dead
          ++neighbour.neighbours;
          if (neighbour.neighbours === 3) {
            neighbour.alive = true;
            neighbour.changed = true;
            neighbour.changeIndex = this.changeList.push(neighbour) - 1;
          } else if (neighbour.neighbours === 4) {
            // neighbour has reverted to dead
            neighbour.alive = false;
            neighbour.changed = false;
            neighbour.changeIndex = -1;
            this.changeList[neighbour.changeIndex] = undefined;
          }
        }
      }
      if (cell.neighbours &lt; 2 || cell.neighbours &gt; 3) {
        cell.changed = true;
        cell.alive = false;
        cell.changeIndex = this.changeList.push(cell) - 1;
      } else {
        newLifeList.push(cell);
      }
    }
  
    for (var i = 0, iLen = this.changeList.length; i &lt; iLen; ++i) {
      var cell = this.changeList[i];
      if (cell !== undefined) {
        cell.changeIndex = -1;
        if (cell.alive) {
          newLifeList.push(cell);
        }
        cell.update();
        cell.changed = false;
      }
    }
  
    this.lifeList = newLifeList;
    ++this.generation;
    this.onTick();
  
    var that = this;
    if (this.settings.speed &gt;= 0) {
      this.nextTick = setTimeout(function() {
        that.tick();
      }, this.settings.speed);
    }
    return this;
  }
  
  World.prototype.out = function() {
    var s = '';
    for (var y = 0, yLen = this.settings.rows; y &lt; yLen; ++y) {
      for (var x = 0, xLen = this.settings.columns; x &lt; xLen; ++x) {
        s += (this.cellList[x][y].alive)? '\u2B1B' : '\u2B1C';
      }
      s += '\n';
    }
    s += '\u21B3 Generation: ' + this.generation + ' -- Cells: ' + this.lifeList.length + ' \u21B5';
    s += '\n';
    return s;    
  }
  
  World.prototype.stop = function() {
    this.speed = -1;
  }
  
  World.prototype.onTick = function() {
    return this;
  }
  
  var Cell = function() {
    return this;
  }
  Cell.prototype.x = 0;
  Cell.prototype.y = 0;
  Cell.prototype.neighbours = 0;
  Cell.prototype.alive = false;
  Cell.prototype.changed = false;
  Cell.prototype.changeIndex = -1;
  Cell.prototype.lastIterated = -1;
  
  /*
   * ShadowCell
   * - non rendered cell for use in no-wrap
   */
  var ShadowCell = function(x,y) {
    this.x = x;
    this.y = y;
    this.key = ''+this.x+','+this.y;
    return this;
  }
  ShadowCell.prototype = utils.extend({}, Cell.prototype);
  ShadowCell.prototype.isShadow = true;
  ShadowCell.prototype.update = function(){
    return this;
  };
  
  /*
   * Cell.update()
   * - Update cell after tick
   */
  Cell.prototype.update = function() {
    this.render();
    return this;
  }
  
  /*
   * Cell.render()
   * - Placeholder function to be overwritten by rendering engine
   */
  Cell.prototype.render = function() {
    return this;
  }
  </code></pre>
  
  <p>The method I have chosen involves an array of all the cells that are alive at the start of each generation. I then iterate over each of their 8 neighbours and decide whether to create/delete them.</p>
  
  <p>This works great when I pass <code>wrap: false</code> to the <code>World</code> constructor (see JSfiddle for implementation), this tells it to mirror the sides and not allow overflow. However that style of layout breaks a lot of patterns as it causes cells to come back on themselves so I also want to allow it to calculate beyond the grid.</p>
  
  <p>For this purpose I created the <code>ShadowCell</code> class which behaves mostly the same as the <code>Cell</code> class (each grid cell dead or alive is an instance of it) except that the <code>ShadowClass</code> is only created when a non-existent cell is required outside of the grid and is offered for garbage collection the moment it is no longer required (if it is dead after each generation). Otherwise it mimics the <code>Cell</code> classes attributes and fits directly into the same logic that <code>Cell</code> does.</p>
  
  <h2>The issue</h2>
  
  <p>If you go to "generation 4" in the console output you may notice it isn't quite right...</p>
  
  <p><img src="https://i.stack.imgur.com/iUqFC.png" alt="Hmmmmm"></p>
  
  <p>I have narrowed this issue down to the <code>ShadowCell</code> implementation because this works if I provide enough padding around the shape so that it does not overflow the grid (which is when <code>ShadowCell</code> kicks in), although like I said earlier <code>ShadowCell</code> is a copy of the <code>Cell</code> class, it has the same attributes and gets passed in as if it was a <code>Cell</code>.</p>
  
  <p>Because I want these to be garbage collected I do not include these in the overall grid array <code>World.cellList</code>... this leads me to believe the problem lies in this section of code:</p>
  
  <pre><code>// This hash goes out of scope after each tick allowing any dead shadowCells to be garbage collected
  
  if (!this.settings.wrap) {
    var shadowCellHash = {};
  }
  
  for (var i = 0, iLen = this.lifeList.length; i &lt; iLen; ++i) {
    var cell = this.lifeList[i];
    if (cell.key) {
      shadowCellHash[cell.key] = cell;
    }
    cell.neighbours = 0;
    cell.lastIterated = this.generation;
  
    for (var j = 0, jLen = cell.neighbourCoords.length; j &lt; jLen; ++j) {
  
      var coords;
      var neighbour;
      if (this.settings.wrap) {
        coords = cell.neighbourCoords[j];
        neighbour = this.cellList[coords[0]][coords[1]];
  
      } else {
        coords = cell.neighbourCoords[j](cell);
        if (coords[0] &gt; this.maxX || coords[0] &lt; 0 || coords[1] &gt; this.maxY || coords[1] &lt; 0) {
          // This neighbour is off the screen so will require a shadowCell
          var key = ''+coords[0]+','+coords[1];
          if (!shadowCellHash[key]) {
            // ShadowCell not in hash, let's create one
            neighbour = shadowCellHash[key] = new ShadowCell(coords[0], coords[1]);
            neighbour.neighbourCoords = cell.neighbourCoords; 
            // NOTE: neighbourCoords are a set of functions that return values relative to the cell you pass to them. I am not literally giving the `ShadowCell` the same neighbour positions here.
          } else {
            neighbour = shadowCellHash[key];
          }
        } else {
          // This neighbour is on screen, grab its cell.
          neighbour = this.cellList[coords[0]][coords[1]];
        }
      }
      ...
  </code></pre>
  
  <p><strong>Note:</strong> Alive <code>ShadowCell</code>s will not be garbage collected as they get stored in an Array with the other cells (I am certain of this from my debugging, see the cell count in your console output and count the visible cells).</p>
  
  <p>For some reason the <code>ShadowCell</code> class appears to cause incorrect reporting of neighbours. I have attempted to debug it by following the creation, deletion and counted neighbours of each individual cell during each generation but my brain dies before it can put it all together. For all my debugging efforts I can't see why this behaviour should occur . <code>ShadowCell</code> is pretty much the same as a <code>Cell</code> to everything else that uses it (they use the exact same position functions .etc), the fact it doesn't get rendered shouldn't be the cause of this.</p>
  
  <p>For generation 4 I get the following output by logging the creation of shadow maps, I can see that each is being created once per generation (note: The class doesn't show because I used <code>utils.extend()</code> to create a snapshot of them):</p>
  
  <pre><code>Object {x: 5, y: -1, key: "5,-1", neighbourCoords: Array[8], neighbours: 0…}
  Object {x: 6, y: -1, key: "6,-1", neighbourCoords: Array[8], neighbours: 0…}
  Object {x: 7, y: -1, key: "7,-1", neighbourCoords: Array[8], neighbours: 0…}
  Object {x: 4, y: -1, key: "4,-1", neighbourCoords: Array[8], neighbours: 0…}
  Object {x: -1, y: 1, key: "-1,1", neighbourCoords: Array[8], neighbours: 0…}
  Object {x: -1, y: 2, key: "-1,2", neighbourCoords: Array[8], neighbours: 0…}
  Object {x: -1, y: 3, key: "-1,3", neighbourCoords: Array[8], neighbours: 0…}
  Object {x: 5, y: -2, key: "5,-2", neighbourCoords: Array[8], neighbours: 0…}
  Object {x: 6, y: -2, key: "6,-2", neighbourCoords: Array[8], neighbours: 0…}
  Object {x: 7, y: -2, key: "7,-2", neighbourCoords: Array[8], neighbours: 0…}
  Object {x: -1, y: 4, key: "-1,4", neighbourCoords: Array[8], neighbours: 0…}
  </code></pre>
  
  <p>Logged on line 152 like so:</p>
  
  <pre><code>if (!shadowCellHash[key]) {
    neighbour = shadowCellHash[key] = new ShadowCell(coords[0], coords[1]);
    neighbour.neighbourCoords = cell.neighbourCoords;
    console.log(utils.extend({}, neighbour));
  } else {
  </code></pre>