Вопрос по sparse-matrix, cellular-automata, algorithm, data-structures, conways-game-of-life – еще один вопрос игры жизни (бесконечная сетка)?

15

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

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

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

Ваш Ответ

2   ответа
6

Википедия объясняет это, Основная идея заключается в том, что Конвейs Игра Жизни проявляет локальность, поскольку информация движется с медленной скоростью по сравнению с размером рисунка, а максимальная плотность заполненных ячеек составляет около 1/2 ячейки в любом регионе. (Больше убьет клетки из-за переполненности.)

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

8

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

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

РЕДАКТИРОВАТЬ: Так что это было с моей головы. ОказываетсяВ Википедии есть статья это показывает гораздо более продуманное решение. Ну что ж! :) Наслаждаться.

Я только что видел Джоренs ответ выше и прочитал ссылку в Википедии. Теперь я понимаю, но это хитрая штука. Большое спасибо вам обоим за ответы. (как программист, я чувствую совершенно новый уровень неадекватности сейчас! :)) Kieran
Я понятия не имею, как Голли делает это - просто предлагает подход. Источник Golly доступен, если вы хотите проверить это. JoshJordan
когда я'Я смотрю на бегущего Голли (невероятно быстро) и наблюдаю за тем, как планеры бегут от края, если я затем уменьшаю масштаб и следую за ними, когда они уходят в космос, как они узнают, куда идти в сетке? сетка - это список координат? или он вообще существует? Kieran

Похожие вопросы