другая игра Жизни вопрос (бесконечная сетка)?

Question

Я играл с игрой жизни Конвея и недавно обнаружил некоторые удивительно быстрые реализации, такие как Hashlife и Golly. (скачать Golly here - http://golly.sourceforge.net/)

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

Большое спасибо

Answer 1

Wikipedia explains it. Основная идея состоит в том, что Game of Life от Conway демонстрирует локальность, поскольку информация перемещается с небольшой скоростью по сравнению с размером рисунка и максимальной плотностью заполненных клеток, составляет около 1/2 из клеток в любом регионе. (Больше будет убивать клетки из-за переполненности.)

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

Answer 2

В этой ситуации можно представить живые узлы с некоторым видом разреженной матрицы. Например, если мы храним список из (LivingNode, Coordinate) пар вместо массива Nodes, где каждый из них либо жив, либо мертв, мы просто меняем Coordinates, а не увеличиваем размер массива. Таким образом, пространство, необходимое для этого, пропорционально числу LivingNodes.

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

EDIT: Так что это было от головы. Выступает Wikipedia has an article, который показывает гораздо более продуманное решение. Ну что ж! :) Наслаждаться.