Игра «Жизнь» Джона Конуэя

Игра «Жизнь» (Conway's Game of Life) — забавнейшая штука, которую серьезные люди сурово называют «клеточный автомат». Ее придумал английский математик Джон Конуэй (John Horton Conway) в далеком 1970 году.

Игровая поверхность представляет собой бесконечное или ограниченное поле, разделенное на определенное количество клеток. Каждая клетка может быть или живой или мертвой. С каждым ходом население поля меняется в соответствии с простыми правилами:

• Клетка, у которой менее двух соседей, умирает от одиночества;
  
• Клетка, у которой более трех соседей, умирает от перенаселения;
  
• Мертвая клетка, у которой ровно три соседа, оживает.
  

Игровой мир развивает без помощи игрока. От него лишь требуется расставить клетки для первого поколения. Часто развитие мира становится совершенно не предсказуемым. Клетки образуют сложные узоры, и как только вам начинает казаться, что вы все поняли, они вдруг вымирают, или «повисают» в бесконечном цикле.
Вот, что пишут о происхождении игры на Википедии:

Джон Конуэй заинтересовался проблемой, предложенной в 1940-х годах известным математиком Джоном фон Нейманом, который пытался создать гипотетическую машину, которая может воспроизводить сама себя. Джону фон Нейману удалось создать математическую модель такой машины с очень сложными правилами. Конуэй попытался упростить идеи предложенные Нейманом, и в конце концов ему удалось создать правила, которые стали правилами игры «Жизнь».

Идея мне так понравилась, что я решил написать собственную реализацию игры на Javascript.

Игры играми, а в «Жизни» можно даже реализовать машину Тьюринга. Между прочем, применяемый им алгоритм Hashfile вычисляет 6,366,548,773,467,669,985,195,496,000 (6 октиллионов) поколений в секунду на скромном Intel Duo 2GHz. Для сравнения, моя не оптимизированная версия генерирует 5 поколений в секунду, и то «Глайднерное ружье Госпера» заметно притормаживает даже в Firefox. Есть над чем задуматься.

Вебмастерам на заметку:
Как я уже писал, я особо не заморачивался с оптимизацией, но производительность хваленого Firefox'а меня действительно удивила. Ружье Госпера на нем начинает резко притормаживать уже где-то на 4-5 глайдере. IE 7 притормаживает стабильно, без резких перепадов, но, кажется, и то работает быстрее ФФ. Тестов я не проводил, поэтому точно сказать не могу. Safari и Chrome не начали тормозить ни через 10, ни 20 минут работы ружья.

Запись в моем блоге