Комментарии 7
Спасибо за статью. Правильно ли я понимаю, что эволюцию через 2^k — 1 получить наиболее трудозатратно?
Пожалуй, да. Способ получить результат через время T мог бы быть таким:
Берем интересующую нас область S, она порождается из области S0=S*T (здесь * — расширение на T клеток в каждую сторону). Предположим, что мы знаем результат развития области S0 через время T1=N1*k, где N1 — степень двойки, k=[T/N1]. Этот результат представлен как двумерный массив квадратов со стороной 2*N1. Теперь смотрим. Если T-T1<N1/2, то разбиваем каждый квадрат на четыре части, это и будет массив для следующего шага. Если нет, придется просчитать эволюцию на N1/2 шагов вперед. Для самих квадратов со стороной 2*N1 берем их результат, для квадратов на стыках — пользуемся тем же методом, что и в Unite. Насколько я понимаю, новых квадратов в словарь при этом не добавится, но доказать это утверждение еще не пробовал.
После получения нового массива полезно проверить, какие клетки на краю нам нужны, и выбросить лишние.
Берем интересующую нас область S, она порождается из области S0=S*T (здесь * — расширение на T клеток в каждую сторону). Предположим, что мы знаем результат развития области S0 через время T1=N1*k, где N1 — степень двойки, k=[T/N1]. Этот результат представлен как двумерный массив квадратов со стороной 2*N1. Теперь смотрим. Если T-T1<N1/2, то разбиваем каждый квадрат на четыре части, это и будет массив для следующего шага. Если нет, придется просчитать эволюцию на N1/2 шагов вперед. Для самих квадратов со стороной 2*N1 берем их результат, для квадратов на стыках — пользуемся тем же методом, что и в Unite. Насколько я понимаю, новых квадратов в словарь при этом не добавится, но доказать это утверждение еще не пробовал.
После получения нового массива полезно проверить, какие клетки на краю нам нужны, и выбросить лишние.
Глаз упорно читает «HalfLife» вместо «HashLife» ))
Алгоритм мутновато описан, я ничего не понял пока не прочитал эту статью.
Помню на своём первом компе делал жизнь по другому: считался bounding-box где что-то есть + поле билось на достаточно крупные квадраты и там, где ничего нет — расчет не проводился.
Позволяло бодренько гонять на поле 2048x2048 и выше на P-133 :-)
Позволяло бодренько гонять на поле 2048x2048 и выше на P-133 :-)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
HashLife на коленке