 |
| Планер (Glider) |
Игра жизнь Джона Конвея
Conway's Game of Life с 70-х годов превратилась из математической головоломки в сферу исследований именитых ученых. Жизнь - это простой клеточный автомат, с двумя состояниями каждой клетки: "живая" и "мертвая" и несколькими элементарными правилами изменения состояний:
- Если у клетки ровно три живых соседа, то в ней "зарождается" жизнь;
- Если у клетки есть два или три соседа, и она жива, то она продолжает жить, иначе она "погибает" - от "одиночества" или от "перенаселения".
У каждой клетки 8 соседей. Подробнее можно прочесть
на вики.
На
rosettacode.org можно найти десятки реализаций. Но ни одной на Objective-C. Постараемся восполнить этот пробел.
'Преждевременная оптимизация - корень всех зол' (с) Дональд Кнут
Не будем спорить с маэстро и сделаем простейшую реализацию алгоритма: двойной массив, в котором будут храниться NSNumber - если клетка жива или NSNull - если нет заполним случайными числами:
 |
| Инициализируем "вселенную" игры Жизнь. |
Далее нам на каждом шаге необходимо запомнить предыдущие состояния и обновлять их исходя из этого состояния. Для этого создадим копию существующего массива:
 |
| Быстрый способ сделать deep copy массива |
И реализуем обход всех клеток:
Функция neighborsCount считает количество живых соседей. Запускаем с полем в 10000 клеток и получаем среднее время выполнения около 0,039 с, а это 25 кадров в секунду (FPS), и это без учета времени на отрисовку. (Да, даже при такой скорости пользователь ничего не увидит, но и 10000 -это не много.)
 |
| Игра жизнь |
Не густо.
Запускаем профайлер, и видим, что основное время тратится именно на пересоздание массива со старыми значениями с помощью NSKeyedArchiver/Unarchiver.
Первое-же что приходит в голову - создать этот массив один раз и просто менять из местами, в конце каждой итерации.
Так реализованы большинство алгоритмов на RosettaCode.
Реализуем, запускаем, меряем: 0.024 секунды (1.6 кратное ускорение / 42 FPS). Уже не плохо, но ведь можно еще?
Если внимательно посмотреть, то видно, что для вычисления столбца совершенно не нужно держать в памяти все старые значения. Вполне достаточно только знать старые значения предыдущего и текущего столбца (следующий столбец, который также необходим в расчетах еще не был изменен, поэтому можно его использовать напрямую):
После профилирования - 0.015 c (x2,6 кратное ускорение), что уже довольно неплохо.
Ну и напоследок небольшой пример того, что можно сделать используя такой простой клеточный автомат:
 |
Игра "Жизнь" (Conway's Game of Life)
|
Смотри также:
Писькомерка для программистов
Комментарии
Отправить комментарий