Игра жизни Конвея - за решеткой

Хорошо, есть много вопросов о «Игре жизни Конвея», но этот довольно конкретный. Я собираюсь сначала набросить на вас кучу кода, разбить его и показать вам, в чем проблема.

Итак, вот моя реализация «Игры жизни» Конвея, прямо сейчас она ограничена консолью для отладки (JSfiddle - http://jsfiddle.net/georeith/C9Gyr/8/ - запустите, откройте консоль):

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 < yLen; ++y) {
    for (var x = 0, xLen = this.settings.columns; x < xLen; ++x) { 
      if (y === 0) {
        this.cellList.push([]);
        if (this.settings.grid.length <= 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 < 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 < 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] > this.maxX || coords[0] < 0 || coords[1] > this.maxY || coords[1] < 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 < 2 || cell.neighbours > 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 < 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 >= 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 < yLen; ++y) {
    for (var x = 0, xLen = this.settings.columns; x < 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;
}

Выбранный мной метод включает в себя массив всех ячеек, которые были живы в начале каждого поколения. Затем я перебираю каждого из их 8 соседей и решаю, создавать / удалять их.

Это отлично работает, когда я передаю wrap: false конструктору World (см. JSfiddle для реализации), это говорит ему зеркалировать стороны и не допускать переполнения. Однако этот стиль макета нарушает множество шаблонов, поскольку он заставляет ячейки возвращаться в себя, поэтому я также хочу позволить ему вычислять за пределами сетки.

Для этой цели я создал класс ShadowCell, который ведет себя в основном так же, как класс Cell (каждая мертвая или живая ячейка сетки является его экземпляром), за исключением того, что ShadowClass создается только тогда, когда несуществующая ячейка требуется вне сетки и предлагается для сборки мусора в тот момент, когда он больше не нужен (если он мертв после каждого поколения). В противном случае он имитирует атрибуты Cell классов и вписывается непосредственно в ту же логику, что и Cell.

Проблема

Если вы перейдете к «поколению 4» в выводе консоли, вы можете заметить, что это не совсем правильно ...

Я сузил эту проблему до реализации ShadowCell, потому что это работает, если я предоставлю достаточно отступов вокруг формы, чтобы она не переполняла сетку (это происходит при срабатывании ShadowCell), хотя, как я сказал ранее, ShadowCell является копией Cell class, он имеет те же атрибуты и передается, как если бы это был Cell.

Поскольку я хочу, чтобы они собирались сборщиком мусора, я не включаю их в общий массив сетки _14 _... это наводит меня на мысль, что проблема заключается в этом разделе кода:

// 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 < 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 < 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] > this.maxX || coords[0] < 0 || coords[1] > this.maxY || coords[1] < 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]];
      }
    }
    ...

Примечание. Живые ShadowCells не будут собираться мусором, поскольку они сохраняются в массиве с другими ячейками (я уверен в этом по моей отладке, посмотрите количество ячеек в выводе консоли и подсчитайте видимые ячейки ).

По какой-то причине класс ShadowCell вызывает неверное сообщение о соседях. Я попытался отладить его, следя за созданием, удалением и подсчетом соседей каждой отдельной ячейки в течение каждого поколения, но мой мозг умирает, прежде чем он сможет все это собрать. Несмотря на все мои усилия по отладке, я не понимаю, почему должно происходить такое поведение. ShadowCell в значительной степени совпадает с Cell для всего, что его использует (они используют те же самые функции положения. И т. Д.), Тот факт, что он не отображается, не должен быть причиной этого.

Для поколения 4 я получаю следующий результат, регистрируя создание карт теней, я вижу, что каждая из них создается один раз для каждого поколения (примечание: класс не отображается, потому что я использовал utils.extend() для создания их моментального снимка):

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…}

Вы вошли в строку 152 вот так:

if (!shadowCellHash[key]) {
  neighbour = shadowCellHash[key] = new ShadowCell(coords[0], coords[1]);
  neighbour.neighbourCoords = cell.neighbourCoords;
  console.log(utils.extend({}, neighbour));
} else {