js/pattern-detector.js - master - hamster75/Life

js/pattern-detector.js
84 строки3 KB
Dmitry Smirnov
initial public
13 май 2026, 09:15
13 май 2026, 09:15117500d
function _norm(cells) {
  if (!cells.length) return '';
  let minX = Infinity, minY = Infinity;
  for (const [x, y] of cells) { if (x < minX) minX = x; if (y < minY) minY = y; }
  return cells
    .map(([x, y]) => [x - minX, y - minY])
    .sort((a, b) => a[1] - b[1] || a[0] - b[0])
    .map(([x, y]) => `${x},${y}`)
    .join('|');
}

function _rot(cells)  { return cells.map(([x, y]) => [y, -x]); }
function _flip(cells) { return cells.map(([x, y]) => [-x, y]); }

function _allVariants(cells) {
  const set = new Set();
  let c = cells;
  for (let i = 0; i < 4; i++) {
    set.add(_norm(c));
    set.add(_norm(_flip(c)));
    c = _rot(c);
  }
  return [...set];
}

function _miniStep(cells) {
  const cnt = new Map();
  for (const [x, y] of cells)
    for (let dy = -1; dy <= 1; dy++)
      for (let dx = -1; dx <= 1; dx++) {
        if (!dx && !dy) continue;
        const k = `${x + dx},${y + dy}`;
        cnt.set(k, (cnt.get(k) || 0) + 1);
      }
  const alive = new Set(cells.map(([x, y]) => `${x},${y}`));
  const next = [];
  for (const [k, n] of cnt)
    if (n === 3 || (n === 2 && alive.has(k)))
      next.push(k.split(',').map(Number));
  return next;
}

function _allPhaseVariants(phase0, period) {
  const set = new Set();
  let c = phase0;
  for (let i = 0; i < period; i++) {
    for (const h of _allVariants(c)) set.add(h);
    c = _miniStep(c);
  }
  return [...set];
}

const _PULSAR = [
  [2,0],[3,0],[4,0],[8,0],[9,0],[10,0],
  [0,2],[5,2],[7,2],[12,2],[0,3],[5,3],[7,3],[12,3],[0,4],[5,4],[7,4],[12,4],
  [2,5],[3,5],[4,5],[8,5],[9,5],[10,5],
  [2,7],[3,7],[4,7],[8,7],[9,7],[10,7],
  [0,8],[5,8],[7,8],[12,8],[0,9],[5,9],[7,9],[12,9],[0,10],[5,10],[7,10],[12,10],
  [2,12],[3,12],[4,12],[8,12],[9,12],[10,12],
];

const _db = new Map();
function _add(name, variants) { for (const h of variants) _db.set(h, name); }

_add('Блок',    _allVariants([[0,0],[1,0],[0,1],[1,1]]));
_add('Улей',    _allVariants([[1,0],[2,0],[0,1],[3,1],[1,2],[2,2]]));
_add('Батон',   _allVariants([[1,0],[2,0],[0,1],[3,1],[1,2],[3,2],[2,3]]));
_add('Лодка',   _allVariants([[0,0],[1,0],[0,1],[2,1],[1,2]]));
_add('Мигалка', _allPhaseVariants([[0,0],[1,0],[2,0]], 2));
_add('Жаба',    _allPhaseVariants([[1,0],[2,0],[3,0],[0,1],[1,1],[2,1]], 2));
_add('Маяк',    _allPhaseVariants([[0,0],[1,0],[0,1],[1,1],[2,2],[3,2],[2,3],[3,3]], 2));
_add('Пульсар', _allPhaseVariants(_PULSAR, 3));
_add('Глайдер', _allPhaseVariants([[1,0],[2,1],[0,2],[1,2],[2,2]], 4));
_add('LWSS',    _allPhaseVariants([[1,0],[2,0],[3,0],[4,0],[0,1],[4,1],[4,2],[0,3],[3,3]], 4));

export function normHash(cells) { return _norm(cells); }

export function detectPatterns(framesArray) {
  for (const cells of framesArray) {
    const h = _norm(cells);
    if (_db.has(h)) return _db.get(h);
  }
  return null;
}