Как реализовать двухмерный сотовый автомат на JavaScript?

Пока у меня есть это:

const rand = (min, max) => Math.floor(Math.random() * (max - min + 1) + min)

// rule:
  // if an even number of nodes are touching
  // the center node, then flip
  // else skip.

// rule:
  // for the start nodes (top row),
  // they are randomly turned on and off.

const cellularAutomaton = [
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
]

const update = () => {
  let int = rand(0, 7)
  let row = cellularAutomaton[0]
  row[int] = row[int] ? 0 : 1
  // now, how to update the remaining rows?
  for (let i = 1, n = cellularAutomaton.length; i < n; i++) {
    row = cellularAutomaton[i]
    for (let k = 0, m = row.length; k < m; k++) {
      let neighbors = surrounding(i, k)
      let count = sum(neighbors)
      if (even(count)) {
        row[k] = row[k] == 1 ? 0 : 1
      }
    }
  }
}

const even = value => value % 2 == 0

const sum = neighbors => {
  let sum = 0
  let u = 0
  while (u < 3) {
    let v = 0
    while (v < 3) {
      let value = neighbors[u][v]
      if (value != null) {
        sum += value
      }
      v++
    }
    u++
  }
  return sum
}

const surrounding = (row, column) => {
  let prevRow = cellularAutomaton[row - 1]
  let nextRow = cellularAutomaton[row + 1]
  let left = cellularAutomaton[row][column - 1]
  let right = cellularAutomaton[row][column + 1]
  let neighbors = []

  if (prevRow) {
    let a = prevRow[column - 1]
    let b = prevRow[column]
    let c = prevRow[column + 1]
    neighbors.push([a, b, c])
  } else {
    neighbors.push([null, null, null])
  }

  neighbors.push([left, null, right])

  if (nextRow) {
    let a = nextRow[column - 1]
    let b = nextRow[column]
    let c = nextRow[column + 1]
    neighbors.push([a, b, c])
  } else {
    neighbors.push([null, null, null])
  }

  return neighbors
}

let i = 0

const watch = () => {
  i++
  if (i == 100) {
    clearInterval(interval)
  }
}

const render = () => {
  let out = []
  let a="■"
  let b = '□'

  for (let i = 0, n = cellularAutomaton.length; i < n; i++) {
    row = cellularAutomaton[i]
    let outrow = []
    for (let k = 0, m = row.length; k < m; k++) {
      let value = row[k]
      if (value) {
        outrow.push(a)
      } else {
        outrow.push(b)
      }
    }
    out.push(outrow.join(' '))
    out.push('n')
  }

  console.clear()
  console.log(out.join(''))
}

const draw = () => {
  update()
  watch()
  render()
}

const interval = setInterval(draw, 1000)

Я правильно это делаю? Я никогда не видел реализации клеточных автоматов и поэтому не знаю, есть ли более эффективный способ сделать это. Пожалуйста, дайте мне знать, как это исправить. Что можно сделать иначе или более эффективно? В частности, поиск соседей, я не уверен, хорошо ли у меня это получилось. Кроме того, что обычно делают двухмерные клеточные автоматы на краях? Заворачивают ли они их на другую сторону? Значит, у всего одинаковое количество соседей? Я не совсем уверен, как теория соотносится с кодом, и если теоретически число соседей одинаково для каждого ящика.

Примечание. В этом ЦС у меня есть случайное «семя» в первой строке для инициализации значений. То есть по замыслу, я хочу по сути «сыграть в автомат», и это случайное семя функции — это всего лишь воображаемый ритм (не слишком изящный для этого поста).

В качестве примечания: если у вас есть какие-либо предложения по поводу типов правил, которые можно создать, оставьте, пожалуйста, комментарий, я хотел бы создать произвольные центры сертификации и не уверен, с чего начать.

Рассмотрение

• Используйте точку с запятой

• Используйте индексирование на основе 0. Ваш rand функция не требует + 1

• Использовать const для значений, которые не меняются. Например в функции surrounding все переменные могут быть константами prevRow, nextRow, left, right, neighbors, a, b, а также c

• В исполняемом коде по возможности избегайте условных операторов и выражений.

  У тебя есть линия row[k] = row[k] == 1 ? 0 : 1 Значение строки[k] будет только 1 или 0. Тройное число медленнее, чем добавление 1 и побитового И 1. Строка row[k] = (row[k] + 1) & 1; изменит значение между 0 и 1

Игра Жизни

Обновление

В игре жизни есть два состояния: предыдущее состояние и новое состояние. Вы смешиваете их, записывая новое состояние платы в тот же массив, что и предыдущее состояние платы.

Это означает, что рождение и смерть ячейки слева и в строке выше будут подсчитаны неправильно.

Правильный метод — это двойная буферизация состояния платы.

Два массива, один содержит предыдущее состояние ячеек, а другой — новое состояние. Каждый тик игры жизни вы меняете местами два массива.

Подсчитайте соседние ячейки из предыдущего состояния и обновите текущее состояние. Визуализируйте новое состояние и меняйте буферы местами. Текущее состояние становится предыдущим, а старое предыдущее состояние используется для установки следующего нового состояния.

Смотри переписать

Края

Существует столько стратегий для ребер, сколько вы можете себе представить.

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

Использование краевых деформаций (используйте ячейку на противоположном крае) наиболее точно соответствует бесконечной доске.

Если вы используете ограниченные края, тогда ячейки за пределами сетки настраиваются в состояние, при котором не создаются и не уничтожаются ячейки на краю.

Представление

• Индексирование массива имеет небольшие накладные расходы, уменьшение количества раз, которое вы индексируете в массиве, уменьшит эти накладные расходы.

  Вместо использования 2D-массива вы можете использовать одномерный массив и уменьшить индексирование массива.

• Ваш метод подсчета соседей ужасающе неэффективен. Вы создаете 3 новых массива, затем повторяете каждый, проверяя, не null для подсчета живых клеток.

  Вам нужно только посчитать состояние ячеек, нет необходимости создавать копию каждой ячейки. См. «Переписать»

  В примере используются два массива поиска для предоставления смещений соседним ячейкам. Массив платы представляет собой одномерный массив, и только ячейки на краю должны вычислять индекс ячейки по координатам x и y.

• Консоль — не очень быстрый способ отображения данных. В этом случае вы можете использовать растровое изображение холста и записывать ячейки непосредственно в пиксели. Смотрите, переписать.

Переписать

Перезапись реализует Игра жизни Конвея 160 на 160 ячеек, отображающих результат в элементе холста.

Заметки

• Он написан для повышения производительности, однако может быть намного быстрее (использование однопоточного JS может обрабатывать более миллиона ячеек), но код начинает становиться очень сложным из-за оптимизации.

• Пограничные ячейки обрабатываются иначе, чем остальные, и используют значение на противоположном крае для подсчета в качестве соседей.

• Функция обновления возвращает количество живых клеток. Это используется для сброса игры, когда все клетки мертвы.

• Специальная записка Оптимизация подсчета

  При подсчете соседей цикл завершается, когда количество соседей равно 4, так как набор правил имеет тот же результат для подсчетов 4,5,6,7,8, поэтому нет подсчета очков выше 4.

  Если вы измените наборы правил, вам, возможно, придется удалить оптимизацию.

  Кроме того, есть и другие ранние выходы из цикла счета.

"use strict";

const RESET_TIME = 1000; // in millisecond
const TICK_TIME = 32;    // in millisecond
const SIZE = 160;         // in cells

// Cell rules
const DIE = -1, BIRTH = 1, NO_CHANGE = 0;

// RULES index of items is neighbor count. 
// 5 Items as rules for count 4,5,6,7,8 have same outcome
// First rule set for dead cells, second for live cells
const RULES = [
    [NO_CHANGE, NO_CHANGE, NO_CHANGE, BIRTH,     NO_CHANGE],
    [DIE,       DIE,       NO_CHANGE, NO_CHANGE, DIE]
];
// MAX_COUNT max living neighbors to count
const MAX_COUNT = RULES[0].length - 1;

// next two arrays are offsets to neighbors as 1D and 2D coords
const NEIGHBOR_OFFSETS = [
    -SIZE - 1, -SIZE, -SIZE + 1,
    -1,                1,
     SIZE - 1,  SIZE,  SIZE + 1
];
const EDGE_OFFSETS = [ // as coord pairs, x, y for cells at edge
    -1, -1, 0, -1, 1, -1,
    -1, 0,         1, 0,
    -1, 1,  0, 1,  1, 1
];

// double buffered board state
var BOARDS = [new Array(SIZE * SIZE).fill(0), new Array(SIZE * SIZE).fill(0)];
var currentState = 0;

// canvas for display
const display = Object.assign(document.createElement("canvas"), {width: SIZE, height: SIZE});
display.ctx = display.getContext("2d");
display.pixels = display.ctx.getImageData(0, 0, SIZE, SIZE);
display.buf32 = new Uint32Array(display.pixels.data.buffer);
const PIXELS = [0, 0xFF000000];  // Uint32 pixel value NOTE channel order ABGR
                                 // eg 0xFF000000 is black 0xFF0000FF is red
document.body.appendChild(display);
display.addEventListener("click", randomize);  // click to restart

// start game
randomize();
tick();


function randomize(density = 0.1) {
    const b = BOARDS[currentState % 2];
    var i = b.length;
    while (i--) { b[i] = Math.random() < density ? 1 : 0 }
    render();
}
function render() {
    const b = BOARDS[currentState % 2], d32 = display.buf32;
    var i = b.length;
    while (i--) { d32[i] = PIXELS[b[i]] }
    display.ctx.putImageData(display.pixels, 0, 0);
}
function update() {    
    var x, y = SIZE, idx = SIZE * SIZE - 1, count, k, total = 0;

    // Aliases for various constants and references to keep code line sizes short. 
    const ps = BOARDS[currentState % 2];        // prev state
    const ns = BOARDS[(currentState + 1) % 2]; // new state
    const NO = NEIGHBOR_OFFSETS, EO = EDGE_OFFSETS, S = SIZE, S1 = SIZE - 1;
    while (y--) {
        x = SIZE;
        while (x--) {
            count = 0;
            if (x === 0 || x === S1 || y === 0 || y === S1) {
                k = 0;
                while (k < EO.length && count < MAX_COUNT) {
                    const idxMod = (x + S + EO[k]) % S + ((y + S + EO[k + 1]) % S) * S;
                    count += ps[idxMod];
                    k += 2;
                }
            } else {
                k = 0;
                while (k < NO.length && count < MAX_COUNT) { count += ps[idx + NO[k++]] }
            }
            const useRule = RULES[ps[idx]][count];
            if (useRule === DIE) { ns[idx] = 0 }
            else if (useRule === BIRTH) { ns[idx] = 1 }
            else { ns[idx] = ps[idx] }
            total += ns[idx];
            idx --;
        }        
    }
    return total;
}

function tick() {
    const living = update();
    currentState++;
    render();
    if (living) {    
        setTimeout(tick, TICK_TIME);
    } else {
        randomize();
        setTimeout(tick, RESET_TIME);
    }
}

canvas {
  width: 640px;
  height: 640px;
  image-rendering: pixelated;
  border: 1px solid black;
}

Щелкните холст, чтобы сбросить

Правильность

Во-первых, ваш алгоритм, похоже, неправильно реализует обновление состояния решетки: как только вы обновите состояние одной ячейки, количество соседей любых соседних ячеек изменится. Обычно этого не должно происходить: большинство CA определены так, что концептуально каждая ячейка меняет состояние в один и тот же момент.

Это означает, что при обновлении решетки вам нужно будет каким-то образом запомнить, как выглядела окрестность каждой ячейки. перед вы начали их обновлять. Есть несколько возможных способов сделать это (некоторые из которых я упомяну ниже), но одним из наиболее распространенных решений является двойная буферизация.

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

Пограничные случаи

Опять же, существует множество вариантов обработки ячеек по краям, и вы можете выбрать любую из них:

1. Просто предположите, что любые ячейки вне массива всегда остаются в каком-то фиксированном состоянии (например, состоянии 0).

2. Оберните края так, чтобы нижний ряд прилегал к верхнему ряду, а крайний правый столбец примыкал к крайнему левому.

3. Расширяйте массив по мере распространения ячеек, чтобы узор развивался, как если бы он находился на бесконечной решетке без краев.

4. Сделай что-нибудь еще. Действительно, как хотите. Может быть, сделать края зеркалами, чтобы каждая граничная ячейка считалась одной из своих соседей. Или обновите граничные ячейки в соответствии с каким-либо внешним входом. Или что-то.

Варианты 2 и 3, указанные выше, имеют то преимущество, что клеточный автомат будет локально вести себя одинаково во всех точках, делая края невидимыми. Большинство других вариантов будут иметь тенденцию приводить к необычному поведению около краев, либо потому, что ячейки за краем не подчиняются тому же правилу CA, что и ячейки внутри решетки, либо потому, что граф смежности ячеек выглядит иначе около краев.

Вариант 3 действительно имеет некоторые очевидные проблемы с производительностью, особенно если правило CA, которое вы используете, имеет тенденцию отображать быстро распространяющиеся шаблоны ячеек. Таким образом, варианты 1 и 2, вероятно, являются наиболее популярными для простых реализаций CA.

Эффективность

ОК, это глубокий Кроличья нора. Чтобы вкратце понять, насколько глубоко, взгляните на мой предыдущий ответ об оптимизации клеточных автоматов в Java. И это даже не входит ни в какие В самом деле передовые методы оптимизации.

Вот несколько общих вещей, о которых следует помнить:

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

• Просчитайте все, что сможете. Если вы можете сэкономить хотя бы одну наносекунду на ячейку в своем основном цикле обновления, потратив в 10000 раз больше времени на предварительные вычисления вне цикла, это того стоит, если ваша решетка будет больше 100 × 100 ячеек.

• Старайтесь не обновлять ячейки, которые вам не нужны. Я дал несколько конкретных предложений по этому поводу в конце предыдущего ответа, связанного выше, но один из вариантов — сохранить список только что измененных ячеек и обновлять только эти ячейки и их соседей на следующем временном шаге. (Или, в качестве альтернативы, также включите соседей любых ячеек, которые изменились в списке, чтобы он напрямую включал каждую ячейку, которая может нуждаться в обновлении в следующий раз.)

  Обратите внимание, что прирост производительности от этого будет во многом зависеть от правила CA и иногда может быть отрицательным. Для правил, в которых большинство ячеек меняется редко, такая оптимизация может быть огромным преимуществом. Для правил, в которых большинство ячеек изменяется почти все время, лучше просто обновлять каждую ячейку в хорошо оптимизированном цикле.

• Предварительно рассчитайте и сохраните счетчики соседей. Эта оптимизация специфична для «тотальных» правил, где следующее состояние каждой ячейки зависит только от ее собственного состояния и количества активных соседних ячеек. В этом случае вместо подсчета активных соседей каждой ячейки на каждом временном шаге вы можете сохранить счетчик в массиве состояний вместе с состоянием самой ячейки и, когда ячейка меняет состояние, увеличивать или уменьшать количество соседей любого соседние клетки.

Две последние оптимизации, описанные выше, также можно использовать для устранения необходимости в двойной буферизации. По сути, вместо чтения из одного массива и записи в другой альтернативный способ гарантировать, что обновления состояния ячеек происходят «одновременно», состоит в том, чтобы поставить их в очередь в списке, а затем, как только вы определили, какие ячейки действительно нужно изменить, цикл хоть список и собственно обновите ячейки. Опять же, см. Связанный ранее ответ для примера.

Советы по JavaScript

Поскольку вы используете JS, вот пара конкретных вещей, которые следует учитывать:

• Вместо того, чтобы использовать setInterval() для планирования ваших временных шагов подумайте о переносе всех тяжелых вычислений в веб-работник нить. Таким образом, ваша страница останется отзывчивой, даже если обновления потребляют больше процессорного времени, чем ожидалось.

• Вместо использования классических массивов JS рассмотрите возможность использования типизированные массивы вместо. Они более компактны и, вероятно, быстрее, чем классические массивы, и также отлично работают для передачи данных в веб-воркеры и от них.

• Если вы действительно хотите оптимизировать внутренний цикл обновления, вы всегда можете попробовать переписать его в WebAssembly. Но такая микрооптимизация действительно должна выполняться только после того, как будут использованы все другие практические варианты оптимизации.

Наконец, возможно, наиболее эффективной оптимизацией было бы переписать вашу симуляцию CA как Фрагментный шейдер WebGL вместо кода JS. Таким образом, он может работать на графическом процессоре, который намного лучше подходит для такого рода вычислений, чем центральный процессор. Вы также можете использовать шейдеры как для фактического обновления состояния CA, так и для рендеринга результирующей решетки на экране, если это то, что вы хотите сделать.

Я никогда не делал этого сам, поэтому у меня нет конкретных советов, но шейдеры WebGL, безусловно, способны на это и многое другое. (См., Например, Shadertoy для некоторых примеров.)