Как реализовать завершение игры «Жизнь» на Си?

Question

[Pudjak]

Одно из условий остановки игры, если поле зацикливается.
Но как это реализовать? Знаю способ, с запуском "скрытой" игры, которая будет течь в 2 раза быстрее, и сравнивать поле этой игры с полем оригинальной каждый ход. Затем на каком то моменте поля совпадут и с этого момента запустить сравнение по ходам со стартовым первоначальным полем. Когда совпадут, получается зациклилось.
Но можно ли как-то попроще это реализовать?...

И ещё вопрос. Игра идёт в бесконечном цикле через sleep-задержку. Как можно реализовать изменение переменной в sleep, так сказать в реальном времени? Ну то есть допустим игра идёт, стоит sleep(a), a=100(милисекунд). По нажатию плюсика, например, к переменной a прибавляем ещё 100 милисекунд. Без conio.h и getch (так как Линукс)

Answer 1

[mayton2019]

Отвечу на первую часть вопроса

Одно из условий остановки игры, если поле зацикливается.
Но как это реализовать? Знаю способ, с запуском "скрытой" игры, которая будет течь в 2 раза быстрее, и сравнивать поле этой игры с полем оригинальной каждый ход. Затем на каком то моменте поля совпадут и с этого момента запустить сравнение по ходам со стартовым первоначальным полем. Когда совпадут, получается зациклилось.
Но можно ли как-то попроще это реализовать?...

Я не программировал Convay-s Life т.к. было не особо интересно. Но я наблюдал работу приложения Golly. Там можно было проводить сутки напролет в экспериментах, задавая различные конфигурации клеток и вот к чему я пришел.

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

Короче клеточный автомат имеет свойства которые невыводимы из начальной конфигурации в общем случае.

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

Нерешенные вопросы:
1) Поле бесконечное? Как быть с конечными ресурсами оперативной памяти?
2) Поле конечное? Уничтожаем клетки (глайдеры) которые вылетают за границу поля?
3) Поле завернутое в тор (бублик)? Будем ли считать линейные трансформации поля - эквивалентными к исходному?

Данные вопросы вобщем-то тоже влияют на проблему завершения жизни Конвея.

По поводу идеи автора с удвоением времени. Может не сработать если период повтора не будет кратен двойке.
По сути надо не сравнивать x и 2x эпоху. А записывать в базу данных все x - 1 эпох и проверять все-с-последней.
Но такая сверх-задача невыполнима например с растущим бесконечным полем.

Вторая часть вопроса не так интересна. Ее можно задать отдельным вопросом в habr.

Comments

[Pudjak]

А в каком случае он может быть не равен двойке, меньше двойки же он быть не может? Допустим на поле есть один зацикливающийся элемент и один, который через 2 хода умрёт.
Через N и 2N ходов мы получим, что поля совпадают (причём повторяющийся элемент находится там, где находился на старте). Но цикл ещё не закончен, так как на старте был ещё один умерший элемент. Поэтому с момента совпадения полей на N и 2N полях, я решил запустить новую скрытую игру со старта без 2х скорости и сравнивать оригинальную с ней. Ну и получается, когда на стартовой умрёт элемент, поля совпадут и вот тут и начнётся цикл.

Например, 2 элемента идут к друг к другу, через 30 секунд сталкиваются, образуя зацикливающуюсяя фигуру, которая проходит цикл за 70 секунд. В этом случае сравнение с 2х скоростью ничего не даст. Такое, получается, возможно?

Поле замкнуто само на себя.

[Wataru]

mayton2019

По поводу идеи автора с удвоением времени. Может не сработать если период повтора не будет кратен двойке.

Нет. Сработает всегда. Основное поле двигается на 1 ход, вспомогательное - на 2. Вспомогательное обгоняет основное на 1 шаг за каждую итерацию. Через 2 итерации - будет 2 шага. Через K - K шагов. Рано или поздно расстояние между двумя полями (в смысле шагов) станет равно периоду.

[mayton2019]

Wataru, хорошо. Почему 2? Вот я хочу умножать на полтора. Вот такая у меня эвристическая идея.

[Wataru]

mayton2019, потому что 2-1=1. За каждую итерацию расстояние между двумя состояниями будет изменятся на 1. Ну и это же количество шагов - так что число должно быть целым.

[mayton2019]

Wataru, хорошо. Вот у меня есть 30 осцилляторов с периодом кратным простым числам

7, 11, 13, 17, 19, 23, 29, 31, 37, 41

их полный период составит произведение этих чисел или 1 257 665 051

грубо говоря 1 миллиард эпох.

Теперь давайте добавим сюда ваш отстающий снимок который видит взад ровно в два раза
и прикинем когда он сработает.

[Wataru]

mayton2019, Да, этот метод требует сделать максимум один лишний круг по циклу. Но в задаче и так надо все состояния до зацикливания сгенерировать (Т.е. все 1 257 665 051). Так что один лишний круг не сильно все портит.

Answer 2

[Wataru]

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

Можно запоминать предыдущие поля. Хотя бы в виде хешей для экономия памяти. Чтобы из-за коллизии не заврешаться раньше времени, можно считать несколько принципиально разных хешей (допустим, sha256 и какой-то полиномиальный хеш), и плюс брать "слепок" от поля (какие-то 256 разбросанных по полю клеток).

Или, если поле не большое, то можно вместе с хешом хранить все поле. Если где-то хеши совпали, то дальше нужнол сравнивать уже поля целиком поклеточно.

Comments

[mayton2019]

Вы можете хранить 100% хешей но при этом 1% реальных снимков эпохи. Учитывая строгую формулу движения вперед - при нахождении одинакового хеша вы всегда можете взять тот самый близкий 1% и сделать "перемотку" эпох вперед и таким образом быстро проверить коллизия это или реальное совпадение.