Оптимизация «игры жизни» Конвея

Question

Чтобы экспериментировать, я (давно) реализовал Игру Жизни Конвея (и я знаю этот связанный вопрос!).

Моя реализация работала, сохраняя 2 массива логических значений, представляющих «последнее состояние» и «обновляемое состояние» (2 массива менялись на каждой итерации). Хотя это достаточно быстро, я часто задавался вопросом, как это оптимизировать.

Одна из идей, например, заключалась бы в предварительном вычислении на итерации N зон, которые могли бы быть модифицированы на итерации (N + 1) (чтобы ячейка не принадлежала такой зоне даже не будет рассматриваться для модификации на итерации (N + 1)). Я знаю, что это очень расплывчато, и я никогда не тратил время на детали ...

У вас есть идеи (или опыт!) О том, как оптимизировать (для скорости) итерации Game of Life?

Answer 1

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

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

Answer 2

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