Le jeu de la vie de Conway - au-delà de la grille

Question

Ok, donc il y a beaucoup de questions sur « Le jeu de la vie de Conway », mais celle-ci est assez spécifique.Je vais d'abord devoir vous lancer un tas de code, le décomposer et vous montrer où se situe le problème.

Voici donc l'implémentation de Game of Life de Conway jusqu'à présent, pour le moment, elle est limitée à la console pour le débogage (JSfiddle - http://jsfiddle.net/georeith/C9Gyr/8/ - lancez-le, ouvrez votre console) :

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

La méthode que j'ai choisie implique un tableau de toutes les cellules vivantes au début de chaque génération.Je parcoure ensuite chacun de leurs 8 voisins et décide de les créer/supprimer.

Cela fonctionne très bien quand je passe wrap: false au World constructeur (voir JSfiddle pour l'implémentation), cela lui indique de refléter les côtés et de ne pas autoriser le débordement.Cependant, ce style de disposition brise de nombreux modèles car il fait revenir les cellules sur elles-mêmes, je souhaite donc également lui permettre de calculer au-delà de la grille.

Dans ce but j'ai créé le ShadowCell classe qui se comporte essentiellement de la même manière que la Cell classe (chaque cellule de la grille morte ou vivante en est une instance) sauf que la ShadowClass n'est créé que lorsqu'une cellule inexistante est requise en dehors de la grille et est proposée au garbage collection dès qu'elle n'est plus nécessaire (si elle est morte après chaque génération).Sinon, il imite le Cell classe les attributs et s'inscrit directement dans la même logique que Cell fait.

Le problème

Si vous allez à "génération 4" dans la sortie de la console, vous remarquerez peut-être que ce n'est pas tout à fait correct...

J'ai réduit ce problème au ShadowCell implémentation car cela fonctionne si je fournis suffisamment de remplissage autour de la forme pour qu'elle ne déborde pas de la grille (c'est à ce moment-là que ShadowCell entre en jeu), même si, comme je l'ai dit plus tôt ShadowCell est une copie du Cell classe, il a les mêmes attributs et est transmis comme s'il s'agissait d'un Cell.

Parce que je veux qu'ils soient récupérés, je ne les inclut pas dans le tableau global de la grille. World.cellList...cela m'amène à croire que le problème réside dans cette section de 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 < 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]];
      }
    }
    ...

Note: Vivant ShadowCellLes s ne seront pas récupérés car ils seront stockés dans un tableau avec les autres cellules (j'en suis certain grâce à mon débogage, consultez le nombre de cellules dans la sortie de votre console et comptez les cellules visibles).

Pour une raison quelconque, le ShadowCell classe semble provoquer des rapports incorrects des voisins.J'ai tenté de le déboguer en suivant la création, la suppression et le comptage des voisins de chaque cellule individuelle au cours de chaque génération, mais mon cerveau meurt avant de pouvoir tout rassembler.Malgré tous mes efforts de débogage, je ne vois pas pourquoi ce comportement devrait se produire. ShadowCell est à peu près la même chose qu'un Cell à tout ce qui l'utilise (ils utilisent exactement les mêmes fonctions de position .etc), le fait qu'il ne soit pas rendu ne devrait pas en être la cause.

Pour la génération 4, j'obtiens le résultat suivant en enregistrant la création de cartes d'ombre, je peux voir que chacune est créée une fois par génération (remarque :La classe ne s'affiche pas parce que j'ai utilisé utils.extend() pour en créer un instantané) :

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

Connecté à la ligne 152 comme ceci :

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

Answer 1

shadowCellHash n'est pas initialisé avec tous les ShadowCells avant de commencer à parcourir chaque cellule à la recherche de voisins.Quand la boucle vérifie [5,-1] pour les voisins, ça ne trouve pas [6,-1] parce que ce n'est pas dans shadowCellHash.Depuis [6,-1] n'est pas trouvé, un nouveau mort [6,-1] est créé, et [5,-1] n'est pas né parce qu'il n'a pas assez de voisins vivants.

Je pense avoir résolu votre problème en repeuplant avec impatience shadowCellHash au début de chaque 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;
        }
    }
  }