| Life> | Описание программы Особенности программирования | Скачать |
| Life> | Описание программы Особенности программирования | Скачать |
При программировании Игры возможны два подхода:
Представление пространства Игры в виде двухмерного массива элементов. При всей наглядности этой модели, она несет, однако, 2 серьезных недостатка:
ограниченность памяти компьютера не позволяет работать с достаточно большими массивами, которые могли бы проиллюстрировать бесконечное по условиям Конуэя пространство Life;
необходимость подавления краевых эффектов на границах массива значительно усложняет алгоритм.
Множество организмов игры представляет из себя динамически изменяемый список живых организмов и соседних с ними пустых клеток. Эта модель напрямую не моделирует дискретное множество клеток Конуэя, но только такой подход позволяет просчитать поведение колонии на практически бесконечном игровом поле и свободен от каких-либо краевых эффектов.
Мы выбрали 2-й вариант (Life 1.9). Организм или пустая клетка описывался записью (все примеры программного кода приводятся на Паскале, на котором и программировалась Life в нашем случае):
Т.к. тип longint ограничивается диапазоном -231…+231-1, то эти ограничения и есть предельные значения координат организмов, т.е. события Игры моделируются на поле размерами ~4,3*109 * 4.3*109, что практически равносильно бесконечному полю.
Колония представляет из себя набор организмов, организованных в очередь так, что указатель p предыдущего организма содержит адрес следующего организма. Эта очередь, организованная по полю p, называется общей очередью. Она начинается с переменной p0 типа pOrg и заканчивается организмом, у которого p=nil. Работа с очередью организуется с помощью циклов вида:
Т.к. в ряде случаев требуется обработка не всей колонии, а только ее части, например, только живых организмов, то клетки в очереди частично упорядочены, а части отделены друг от друга с помощью специальных меток-указателей типа ppOrg, содержащих адрес поля p граничного организма. Таких глобальных указателя два: pp1 отделяет множество живых организмов от множества пустых клеток; pp2 указывает на поле p последней пустой клетки в очереди. Кроме того, в процессе генерации каждого нового поколения в очереди определяются два локальных указателя (в процедуре Gener) ppa и ppb, ограничивающих часть очереди, по которой будет производиться коррекция числа соседей (процедура Calcul). При работе с указателями типа ppOrg цикл организуется следующим образом (граничные указатели ppa и ppb):
Такой цикл работает несколько медленнее, чем цикл по указателю типа pOrg, но экономия времени расчета достигается за счет обработки не всей очереди, а только нужной ее части.
Самой критичной частью программы обсчета вселенной Конуэя с точки зрения скорости расчета является подсчет числа соседей для организмов и пустых клеток. Дело в том, что для этого необходим двойной цикл по колонии, поэтому любое ускорение работы внутри этого цикла прямо ускоряет работу всей программы. Одной из таких мер, увеличивающих скорость работы программы, и было введение меток-указателей ppa и ppb, ограничивающих величину внешнего цикла за счет учета (при коррекции числа соседей) только тех элементов клеточного множества, состояние которых изменилось. Это повысило скорость работы программы от 2 до 8 раз в зависимости от конфигурациии колонии по сравнению со сквозным просчетом по всем клеткам.
Другой, и даже более радикальной мерой по повышению скорости расчета было введение хэширования при поиске соседних клеток, т.е. во внутреннем цикле. Для этого в организм был введен указатель h. Каждый организм отнесен к своей хэш-группе, номер которой определяется из его координат по формуле (y mod 16)*16 + (x mod 16). Легко видеть, что число хэш-групп равно 256. Для их обслуживания введен массив указателей hg:
Каждый элемент этого массива является начальным указателем в своей очереди (хэш-группе) организмов, организованной по полю h. Это значит, что указатель h предыдущего организма содержит адрес следующего организма в той же хэш-группе. Поле h последнего в хэш-группе организма равно nil. Очевидно, что разбиение колонии на хэш-группы теоретически уменьшает время поиска организма от десятков до сотен раз. На практике выигрыш для разных колоний составил от 4,5 до 13 раз.
Добившись приемлемой скорости расчета развития колоний (например, время расчета 5000 поколений для конфигурации acorn — желудь на компьютере PIII 550E составило 45 с), мы столкнулись с другим существенным ограничением, связанным с тем, что программа делалась под DOS — это ограничение по величине доступной оперативной памяти, т.е. в нашем случае ограничение количества организмов плюс соседних пустых клеток.
Чтобы несколько увеличить предельное число организмов в памяти, не выходя за рамки DOS’а, необходимо, очевидно, уменьшить размер памяти, занимаемой одним организмом. Описанный в начале этой статьи организм занимает 24 байта (8 байт — координаты, 8 байт — указатели, 1 байт — число соседей, и 7 байт пустые из-за того, что динамическая память выделяется порциями, кратными 8 байт).
Программа Life 1.8.1 работает с организмами, в которых отсутствует указатель p, но добавлен признак «живого» организма l:
При этом все циклы по указателю p заменены на двойной цикл по номеру хэш-группы и внутри нее по указателю h. Очевидно, такой алгоритм работает медленнее, но это замедление касается только второстепенных циклов ввода-вывода, прорисовки экрана при сдвиге «окна просмотра» и т.п. Что же касается основного цикла расчета числа соседей, то его алгоритм практически не изменился, разве что внешний цикл по указателям типа ppOrg заменен на цикл по специально формируемому динамическому массиву (очереди) ссылок на поменявшие состояние организмы.
В результате предельное количество организмов плюс пустых клеток, соседних с организмами, возросло на 35…40% с уменьшением скорости расчета на 15…20%.
Другой подход реализован в программе Life 1.8.2, где описание типа Org выглядит так:
«Выброшенное» из организма поле s на самом деле переместилось в 4 младших разряда координаты y. Настоящее значение координаты y равно полю y, деленному на 16 с помощью операции div. За счет этого «квадратное» поле размером 4,3 млрд * 4,3 млрд клеток сжимается в 16 раз по вертикали, но остается еще достаточно большим, чтобы считать его бесконечным.
В данном случае предельное число учитываемых клеток возрастает по сравнению с вариантом 1.8 ровно в 1,5 раза (никаких дополнительных динамических массивов, занимающих память, нет), а скорость не изменяется.
В заключение, несколько замечаний о размерах игрового поля, вернее, о его форме. Хотя число возможных вариантов сочетаний координат равно 4,3 млрд * 4,3 млрд (или 4,3 млрд * 268 млн для версии 1.8.2), при достижении предельных значений никакой границы не достигается. Сразу за координатой 231-1 следует координата -231. Переход через эту воображаемую границу не искажает колонии — это легко проверяется путем создания файла колонии, расположенной вблизи этой границы, загрузки его и поиска любого организма сервисной функцией «поиск организма». После того, как колония окажется в границах окна просмотра, мы сможем наблюдать ее развитие и движение через границу «плюс бесконечность — минус бесконечность».
Это означает, что пространство данной реализации игры Life является замкнутым по обеим координатам и имеет форму поверхности тора. Поэтому, например, глайдер, улетевший в бесконечность, рано или поздно совершит «кругосветное» путешествие и вернется в исходную точку с противоположной стороны. Правда, время такого путешествия при имеющихся гигантских размерах игрового поля выходит за всякие разумные рамки.
Все глобальные идентификаторы, упоминаемые в данной работе, т.е. переменные, массивы, процедуры реализованы в программе в виде полей и методов объекта колонии, имеющего тип THorde, однако этот факт не учитывался для достижения большей простоты изложения. Несколько по-другому на практике реализовано логическое поле l в версии 1.8.1 (оно занимает 4-й бит поля s), но это отличие не принципиально.
