Бесконечная «Жизнь»

Материал из Blitz Et Cetera

Введение

В этой заключительной статье из цикла, будем избавляться от основного ограничения предыдущего алгоритма - размера поля. Это, конечно, приведет к заметному снижению скорости, но в некоторых задачах без гигантского поля просто не обойтись. Если взять поле со стороной, скажем, миллион ячеек (не заполняя его клетками случайным образом и не обрабатывая при этом около 10¹² / 2 ячеек) и поместить туда организм, даже распространяющийся на все поле, то он будет состоять из относительно небольшого количества клеток, поэтому скороть будет вполне приемлемой. Естественно, бесконечность в буквальном смысле реализовать не удастся, но поля со стороной в 4 миллиарда ячеек (2³²) будет вполне достаточно.

Основная проблема алгоритмов "Жизни" состоит в определении, заполнена ли ячейка, соседняя с данной. До сих пор она легко решалась созданием массива для ячеек всего доступного поля. Теперь доступны два варианта решения (может быть есть и другие):

• Разбить поле на квадратные блоки с фиксированным количеством ячеек и обрабатывать каждый блок отдельно. В таком случае, придется создать буфер по размеру блока, очищать и заполнять его информацией несколько раз за цикл (что существенно замедляет работу), создать массив для хранения координат активных блоков и, самое главное, обеспечить стыковку блоков. Попробуйте реализовать этот алгоритм самостоятельно.
• Организовать древовидную структуру доступа к ячейкам. При этом, создаются цепочки, позволяющие добраться до соседних пикселов. Мало того, что такой алгоритм сам по себе сложен, создание и удаление цепочек замедляет процесс. Но со всем этим вполне можно примириться. Рассмотрим этот алгоритм подробнее.

Одномерная древовидная структура

Чтобы понять суть и преимущества древовидной структуры, еще раз коснемся принципов действия десятичной системы счисления. В древности люди для обозначения количества объектов делали зарубки, рисовали черточки или завязывали узелки (это не что иное, как 1-ричная система счисления). Но чтобы обозначить, скажем, 123 объекта, им пришлось бы делать 123 зарубки, в то время как нам достаточно написать 3 символа. То есть, взять один раз по сто, два по десять и еще три объекта. В итоге, чтобы "добраться" до искомого числа нам нужно сделать 3 а не 123 шага. Причем, при увеличении шагов, количество возможных чисел возрастает в геометрической прогрессии. Теперь взгляните, как можно построить древовидную структуру для двоичной системы:

Здесь три уровня, на каждом из которых можно продолжить движение вниз (0, темно-серый блок) или сделать шаг вправо (1, светло-серый блок). Чем выше уровень, тем больше шаг (степень двойки).Если все числа (блоки первого уровня - снизу) не нужны, то структуру можно упростить. Например, необходимы числа 1, 4, 6, 7:

Выберем блок №6 в качестве исходной точки и определим последовательность шагов для достижения каждого из оставшихся блоков: №7 - вверх, шаг вправо, вниз; №4 - вверх, вверх, шаг влево, вниз, вниз; №1 - вверх, вверх, шаг влево, вверх, шаг влево, вниз, вниз, шаг вправо, вниз. Нетрудно заметить, что путь разбивается на два этапа: 1 - движение вверх, к корню дерева (иногда - шаги влево), 2 - вниз к искомому блоку (иногда - шаги вправо). Т. к. при подъеме мы переходим на указатель более высокого уровня, то шаг влево совершается автоматически.

В нашем алгоритме основное значение имеет указатель на исходный блок и положение конечного блока относительно исходного. Итак, дан исходный блок и приращение до конечного (N, dx). Теперь при поиске алгоритма создания пути возникают две задачи: на сколько уровней подниматься, когда шагать вправо при спуске.

Если приращение не равно 0 (в таком случае результат - исходный блок), то подъем вверх на один уровень обязателен. Поднимаясь от блоков №6 или №7, мы переходим на блок, с которого доступен переход на один из этих блоков. То есть, для данных (№6, +1) и (№7, -1) достаточно подняться только на один уровень. Будем отслеживать положение текущего блока изменением приращения. Рассмотрим ситуацию с поиском пути для данных (№7, -1): поднимаясь на блок более высокого уровня - "11", сделан шаг влево, увеличиваем приращение на 1 (так как мы приблизились к искомому блоку №6). Данные изменились - ("11",0). Для данных (№6, +1) результат подъема будет ("11", +1), т. к. шаг не был сделан. Так как от блока "11" можно сделать шаг (+1) или спуститься (+0), определим диапазон этого блока (он будет равен диапазону всех блоков этого уровня) - (0 - 1). Значит, для данных ("11", 0) и ("11", 1) подъем можно прекратить - приращения входят в диапазон блока.

Данные (№6, -2), где искомый блок - №4: подъем вверх - ("11",-2), диапазон (0 - 1). Приращение в диапазон не попадает, поднимаемся еще. Заметьте, шаг увеличивается в 2 раза. Поэтому, т. к. сделан шаг влево - увеличиваем приращение не на 1, а на 2 - данные ("1", 0), диапазон тоже увеличивается в два раза - (0 - 3). Теперь можно спускаться.

Еще более усложненный пример - данные (№6, -5), где искомый блок - №1. Подъем: (№6, -5), (0); ("11",-5), (0 - 1); ("1", -3), (0 - 3); ("корень", 1), (0 - 7). Подъем завершен, но как теперь правильно спуститься? Выручит двоичное представление приращения (оно теперь - 001). Так как в третьем разряде - 0, при спуске на третий уровень шаг вправо не делаем. То же самое и для второго уровня. В первом разряде - единица, поэтому шагаем вправо и приходим к искомому блоку.

А что делать, если искомые блоки выходят за пределы дерева? Взгляните на схему (сверху - путь для (№7, +4), снизу - (№1, -4)):

Cтруктуре придана гибкость за счет отказа от фиксированной нумерации блоков. Добавляются указатели четвертого уровня: в первом случае, бывший "корень" становится "темно-серым", чтобы можно было сделать шаг вправо к искомому блоку, во втором - "светло-серым", чтобы можно было сделать шаг влево. Еще один аспект - если соответствующие указатели отсутствуют, они создаются по мере надобности. Вообще, операция "надстройки" структуры повторяется до тех пор, пока блок не станет доступен (для отдаленных блоков).

Особенности алгоритма + программа

Так как поле двумерно, придется создавать двумерную древовидную структуру. Ее можно синтезировать из двух одномерных - для оси X и для оси Y. При этом возникают два нюанса: каждый указатель теперь указывает не на два, а на четыре указателя уровнем ниже. Указатель, в зависимости от уровня охватывает квадратную площадь, а подъем вверх завершается только тогда, когда искомый блок окажется в пределах этой площади (оба приращения будут лежать в диапазоне блока для каждой оси). Вот организмы: "паровоз" и "вирус".

Автор: Матвей Меркулов (E-mail: MattMerkulovgmail.com, ICQ: 392-274-050)