 |
Дата публикации: 23.03.2001
Лев Наумов,
lnaumov@chat.ru
Автор благодарит своих учителей, особенно, учителя математики, Максима Яковлевича Пратусевича, и учителя физики Сергея Анатольевича Чивилихина, без которых ничего этого бы не было. Отдельная благодарность Родиону Горковенко (Rodion.Gorkovenko@p14.f1194.n5030.z2.fidonet.org), который корректировал, предлагаемую Вашему вниманию, статью и помогал при разработке описываемых здесь идей.
Эффективная организация данных для повышения скорости поиска клеток и разрешения отношений соседства при реализации клеточного автомата Джона Хортона Конвея “Жизнь”
Чтобы не обременять читателя, в дальнейшем условимся называть этот автомат просто игрой Жизнь. О правилах этой игры написано немало, поэтому мы не будем останавливаться на них, а сразу перейдём непосредственно к теме этой статьи. Тем же, кто либо не знает правил, либо просто хочет прочитать ещё раз о них, можем порекомендовать книгу [1], с которой, пожалуй, начинали все “жизнелюбы”, или книгу [4].
Идея применения вычислительных машин для слежения за ходом игры – не нова. Сам Джон Хортон Конвей использовал компьютер для наблюдения за причудливыми конфигурациями своего детища. Без моделирующих программ увидеть большинство интереснейших превращений, происходящих по ходу игры, было бы просто невозможно. Некоторым вопросам написания таких программ и посвящена данная статья.
 Итак, с точки зрения программирования, Жизнь – трудоёмкая, для компьютера, задача, так как требует довольно больших ресурсов машины на непрерывный пересчёт состояний моделируемого мира (под “миром”, здесь и далее, будет пониматься плоскость, разбитая на клетки, на которой рассматривается колония). В чём же этот пересчёт заключается? Фактически, на каждой итерации нужно разрешать отношение соседства между конкретными объектами, то есть, уметь узнавать, сколько у него соседних клеток. Эта статья и посвящена именно тому, как это сделать максимально эффективно (ясно, что вариант полного перебора мест гипотетической дислокации клеток мы рассматривать не будем, тем более, что его применение проблематично на “бесконечных” полях, которые и представляют основной интерес при моделировании процесса Жизни). Далее под “местами” будем понимать позиции, на которых могут стоять клетки, элементарную область в рассматриваемом мире (“A” на рисунке 1), а под “клетками” – места, в которых есть жизнь (“B” на том же рисунке).
“Объектами” будем называть “клетки” и “места”. Эту терминологию лучше запомнить, так как она будет постоянно использоваться.
Конечно, приведённые здесь методы не претендуют на то, чтобы быть истиной в высшей инстанции, и автор с удовольствием будет общаться с людьми, которые поделятся с ним своими мыслями по этому поводу.
Любой мало-мальски серьёзный проект начинается с продумывания и организации структур данных, необходимых при решении задачи. Первая дилемма, встающая перед нами – хотим мы использовать динамические или статические структуры для хранения информации о клетках. Под статическими структурами имеется в виду, конечно, массив. Очевидно, недостатков у этого метода представления данных – более чем достаточно. Хватит даже одного: размеры популяции (число клеток в ней) неизбежно будут ограничены. Зачем же он нужен? Метод, основанный на использовании массива, программируется, пожалуй, проще, чем любой другой. Иногда Жизнь реализуют в декоративных целях: неплохая экранная заставка – развитие случайно сгенерированной популяции на поле, скажем, в 1024 на 768 мест, то есть, по пикселю на место. Зачем в такой программе трудиться над списками или другими динамическими структурами? Кроме того, здесь – тривиальный способ ускорения разрешения отношения соседства – сортировка.
1. Сортировка
Итак, пусть нам дан массив на m элементов некоторой структуры, LifeCell, содержащей два информационных поля. Допустим, такой структуры:
struct LifeCell
{
int x,y;
};
Будем хранить в нём информацию о существующих клетках на данный момент времени. То есть, если место с координатами x0 и у0 является клеткой, то в массиве должен присутствовать элемент, имеющий поля со значениями x0 и y0. Пусть на данном шаге моделирования у нас будет заполнено n элементов. Так как размеры популяции, как правило, не постоянны во времени, то n будет меняться от итерации к итерации. Вот вам и очевидное ограничение: n не может превосходить m!
Как происходит разрешение отношения соседства для объекта с координатами x0, y0? Для него нам нужно найти в массиве все соседние клетки (смотрите рисунок 2), тогда остальные его соседи являются местами. Обращаем Ваше внимание на то, что такой поиск нужно производить не только для n клеток, которые содержатся в массиве, но и для всех окружающих их объектов, то есть именно, для ближайших восьми соседей, так как это – места гипотетического возникновения жизни. Таким образом, на каждой итерации придётся разрешать отношение соседства для 9*n объектов (n клеток, у каждой – 8 соседей).
 На главную  Версия для печати  Обсудить в форуме  Отправить по почте
| |
|
