Conway Game of Life - вне сетки

Хорошо, поэтому есть много вопросов "Конвей игра Жизни", но это довольно специфично. Сначала мне придется бросить кучу кода, сломать его и показать, где проблема.

Итак, вот моя реализация Game of Life в Conway до сих пор, теперь она ограничена консолью для отладки (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" на выходе консоли, вы можете заметить, что это не совсем правильно...

Hmmmmm

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

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

// 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 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]];
      }
    }
    ...

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

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

Для поколения 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 {

Ответы

Ответ 1

shadowCellHash не инициализируется со всеми ShadowCell, прежде чем вы начнете цикл через каждую ячейку, ища соседей. Когда цикл проверяет [5,-1] для соседей, он не находит [6,-1], потому что он не находится в shadowCellHash. Поскольку [6,-1] не найден, создается новый мертвый [6,-1], а [5,-1] не рождается, потому что ему не хватает живых соседей.

Я думаю, что я решил вашу проблему, с нетерпением переполняя shadowCellHash в начале каждого World.tick

JSFiddle

  // 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; i < this.lifeList.length; i++) {
        var cell = this.lifeList[i];
        if (cell.key) {
          shadowCellHash[cell.key] = cell;
        }
    }
  }