Игра жизни Конвея - за решеткой
Итак, есть много вопросов "Игры жизни Конвея", но этот довольно специфический. Сначала мне придется набросать на вас кучу кода, разбить его и показать, в чем проблема.
Итак, вот моя реализация игры Conway Game of Life, которая сейчас ограничена консолью для отладки (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 класс, он имеет те же атрибуты и передается, как если бы он был Cell,
Поскольку я хочу, чтобы они собирались мусором, я не включаю их в общий массив сетки 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'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 для всего остального, кто его использует (они используют точно такие же функции позиции.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
// 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;
}
}
}