close

Вход

Забыли?

вход по аккаунту

Ковалев Дмитрий Игоревич. Разработка браузерной игры «Жизнь»

код для вставки
2
3
Содержание
Аннотация…………………………………………………………………………5
Abstract………………………………………………………………………….….6
Введение…………………………………………………………………………...7
Глава 1. Обзор источников по теме исследования. Выбор инструментария для
решения задачи………………………………………………………………..…11
1.1 Библиографический обзор……………………………………………11
1.2 Выбор инструментария…...…………………………………………..18
Глава 2. Реализация браузерной игры «Жизнь. Типовые конфигурации……22
2.1 Реализация браузерной игры «Жизнь»……………………………...22
2.2 Типовые конфигурации………………………………………………29
Заключение……………………………………………………………………….41
Список литературы ……………………………………………………………...42
Приложение………………………………………………………………………43
4
АННОТАЦИЯ
Выпускная квалификационная работа на тему «Разработка браузерной
игры «Жизнь»» содержит 40страниц текста, рисунков - 25, фрагментов кода 8, использованных источников - 8.
Ключевые слова: клеточный автомат, генетические законы, типовые
конфигурации.
Предмет
исследования.
Содержание
программного
обеспечения
для
математического моделирования и браузерной реализации игры «Жизнь».
Объект исследования.Игра «Жизнь» и ее типовые конфигурации.
Цель работы.Исследование задачи и разработка программного обеспечения
для браузерной вариации игры «Жизнь».
Результат работы.В выпускной квалификационной работе разработан
скрипт на языке JavaScript [7], который используется в HTMLпрограмме,
позволяющий воспроизвести браузерный вариант игры «Жизнь».
Работа имеет теоретическое и практическое значение, т.к. с помощью
разработанной программы и самой игры «Жизнь» можно проводить
исследования в различных областях наук.
5
ABSTRACT
Graduation qualifying work on the theme "Development of the browser
game"Life"» contains 40pages of text, pictures -25, code snippets - 8, used sources
- 8.
Key words: cellular automaton, genetic laws, typical configurations.
Subject of study. The content of the software for mathematical modeling and
browser implementation of the game "Life".
Object of study. Game "Life" and its typical configuration.
Objective. Research tasks and software development for the browser variation of
the game "Life".
The result of the work. In the final qualifying work a JavaScript [7] script was
developed, which is used in the HTML program, which allows to reproduce the
browser version of the game "Life".
The work is of theoretical and practical importance, because with the help of the
developed program and the game "Life" itself, it is possible to conduct research in
various exact sciences.
6
ВВЕДЕНИЕ
Обоснование выбора темы и ее актуальность
Клеточный автомат — дискретная модель, изучаемая в математике,
теории вычислимости, физике, теоретической биологии и микромеханике.
Включает регулярную решётку ячеек, каждая из которых может находиться в
одном из конечного множества состояний, таких как 1 и 0. Решетка может
быть любой размерности. Для каждой ячейки определено множество ячеек,
называемых окрестностью. К примеру, окрестность может быть определена
как все ячейки на расстоянии не более 2 от текущей (окрестность фон
Неймана ранга 2). Для работы клеточного автомата требуется задание
начального состояния всех ячеек и правил перехода ячеек из одного
состояния в другое. На каждой итерации, используя правила перехода и
состояния соседних ячеек, определяется новое состояние каждой ячейки.
Обычно правила перехода одинаковы для всех ячеек и применяются сразу ко
всей решётке.
Игра «Жизнь» и ее модификации повлияла на многие разделы таких
точных наук как математика, информатика, физика.Это, в частности:










теория автоматов,
теория алгоритмов,
теория игр и математическое программирование,
алгебра и теория чисел,
теория вероятностей и математическая статистика,
комбинаторика и теория графов,
фрактальная геометрия,
вычислительная математика,
теория принятия решений,
математическое моделирование.
Кроме того, многие закономерности, обнаруженные в игре, имеют свои
аналогии в других, подчас совершенно «нематематических» дисциплинах.
Например:
7
1. Кибернетика. Сама игра является удачной попыткой Конуэя доказать
существование простых самовоспроизводящихся систем, а также
появление некоего «разума» у самовоспроизводящихся систем.
2. Биология. Внешнее сходство с развитием популяций примитивных
организмов впечатляет.
3. Бактериология. Некоторые интересные
вариации игры с
дополнительными условиями могут с точностью повторить
размножение бактерий, которые с случайной вероятностью могут
мутировать (по условию модификации) и уже новый вид начинает
заполнять всё пространство. Данный механизм с точностью повторяет
эволюцию бактерий, которые в конце концов эволюционировали до
человека.
4. Физиология. Рождение и смерть клеток аналогичны процессу
возникновения и исчезновения нейронных импульсов, которые и
формируют процесс мышления. А также аналогичны созданию
импульсов в нервной системе многоклеточных организмов.
5. Астрономия. Эволюции некоторых сложных колоний удивительным
образом схематично повторяют этапы развития спиралевидных
галактик.
6. Физика твёрдого тела. Теория автоматов вообще и игра «Жизнь» в
частности используются для анализа «явлений переноса» —
диффузии, вязкости и теплопроводности.
7. Квантовая физика. Поведение «жизненных» ячеек (рождение новых и
взаимное уничтожение) во многом напоминают процессы,
происходящие при столкновении элементарных частиц.
8. Наномеханика. Стационарные и пульсирующие колонии являются
показательным примером простейших устройств, созданных на
основе нанотехнологий.
9. Электротехника. Правила игры используются для моделирования
самовосстанавливающихся электрических цепей.
10. Химия. Конфигурации, подобные строящимся в игре, возникают во
время химических реакций на поверхности, в частности в опытах М.
С. Шакаевой возникают движущиеся молекулярные конструкции
аналогичные «жизненному» планеру. Также предпринимаются
попытки объяснить периодические химические реакции с помощью
многомерных клеточных автоматов. Самоорганизацией элементарных
частиц также занимается супрамолекулярная химия.
11. Социология. Процессы доминации, вытеснения, поглощения,
сосуществования, слияния и уничтожения популяций во многих
аспектах схожи с явлениями, происходящими при взаимодействии
больших, средних и малых социальных групп.
8
12. Философия. Приведённый список примеров в очередной раз
подтверждает, что всё во Вселенной развивается по одним и тем же
нескольким фундаментальным законам.
Степень разработанности проблемы
Основное
направление
исследования
клеточных
автоматов
—
алгоритмическая разрешимость тех или иных задач. Также рассматриваются
вопросы построения начальных состояний, при которых клеточный автомат
будет решать заданную задачу.
Игру Джона Конуэя «Жизнь», придуманную им в 1970 году, можно
назватьнаиболее интересным клеточным автоматом. В компьютерных
реализациях игры поле ограничено и (как правило) верхняя граница поля
«соединена» с нижней, а левая граница — с правой, что представляет собой
эмуляцию поверхности тора, но на экране поле всегда отображается в виде
равномерной
сетки.
Простейший
алгоритм
«смены
поколения»
последовательно просматривает все ячейки решётки и для каждой ячейки
подсчитывает соседей, определяя судьбу каждой клетки (не изменится,
умрёт, родится).
Правила игры таковы, что никакое взаимодействие не может
передаваться быстрее хода шахматного короля. Его скорость-одна клетка в
любом направлении. Зачастую такую скорость называют «скоростью света».
Предмет исследования
Содержание программного обеспечения для разработки браузерного
варианта игры «Жизнь».
Объект исследования
Браузерная игра «Жизнь».
Цель работы
Исследование
задачи
и
разработка
программного
обеспечения
для
браузерноговарианта игры «Жизнь»,а такжеанализ типовых конфигураций.
Основные задачи исследования:
1. Обзор источников по теме исследования. Выбор инструментария для
решения задачи;
9
2. Реализация браузерной игры «Жизнь».
3. Анализ типовых конфигураций.
Теоретическое и практическое значение работы
Работа имеет теоретическое и практическое значение, т.к. полученные
теоретические результаты можно использовать в исследовании клеточных
автоматов и игры «Жизнь» в частности, т.к. для нее существует огромное
кол-во модификаций, подстроенных под разные точные науки, в которых она
может использоваться.
Структура работы
Во введении обосновывается актуальность решаемой задачи, ставится
цель и задачи исследования, а также основные направления исследования.
В первой главе производится библиографический обзор источников по
теме исследования и ставится задача, а также выбирается инструментарий
для решения этой задачи.
Во второй главе описывается программная реализация поставленной
задачи и типовые конфигурации.
В заключении делается вывод о полученных в ходе исследования
результатах работ.
Приводится список использованных источников.
В
приложении
используется
листинг
обеспечения.
10
исходного
программного
ГЛАВА 1. ОБЗОР ИСТОЧНИКОВ ПО ТЕМЕ ИССЛЕДОВАНИЯ.
ВЫБОР ИНСТРУМЕНТАРИЯ ДЛЯ РЕШЕНИЯ ЗАДАЧИ
1.1 Библиографический обзор
Теория клеточных автоматов связана с именами фон Неймана и
Конрада Цузе.Она имеет многообразное прикладное применение, а также
фундаментальное значение для всей науки. Начиная с работы Т. Тоффоли и
Н. Марголуса 80-х гг «Машины клеточных автоматов»[2], клеточные
автоматы стали использоваться в моделях физико-химических процессов.
Клеточно-автоматное моделирование к середине 90-х гг. проникло в
гуманитарные науки при изучении мультиагентных систем в урбанистике
(толпа, транспортная пробка). В последнее время материал о клеточных
автоматах стали часто публиковать в самых разных разделах науки. Также,
одновременно с этим, развивается и математическая теория клеточных
автоматов.
Одним из самых известных клеточных автоматов является игра
«Жизнь». Вот уже сорок лет она привлекает пристальное внимание ученых,
не смотря на то, что состоит всего лишь из трех простых правил.Игру
«Жизнь» придумал американский математик Джон Хортон Конуэй. Джон
фон Нейман пытался создать гипотетическую машину, которая может
воспроизводить сама себя.Нейману удалось создать математическую модель
такой машины с очень сложными правилами. Конуэй же заинтересовался
этой проблемой и, в свою очередь, попытался упростить идеи, предложенные
Нейманом.В конце концов ему удалось создать правила, которые в
последствии и стали правилами игры «Жизнь».Партнер для данной игры не
является чем-то обязательным, в неё можно играть одному. Ситуации,
возникающие в процессе игры, имеют схожесть с реальными процессами,
которые происходят при зарождении, развитии и гибели колоний живых
организмов. Именно из-за этого «Жизнь» можно отнести к быстро
развивающейся категории так называемых «моделирующих игр».Такие игры
в основном имитируют процессы, происходящие в живой природе.
Для того, чтобы сыграть в игру «Жизнь»понадобится доска больших
размеров, на которой обязательно должны быть нанесены клетки, как в
шахматах или шашках. Так же пригодятся и много плоских фишек двух
цветов, или же несколько наборов шашек.Ходы можно рисовать и на бумаге,
однако, проще будет воспользоваться специальными программами,
способными смоделировать эту игру на компьютере.
11
Смысл игры «Жизнь» достаточно прост, располагая фишки
(организмы), расставленные по одной в клетке, можно проследить за
эволюцией исходной позиции под действием «генетических законов»
Конуэя. Данные законы управляют рождением, гибелью и выживанием
фишек. Данные правила подбирались Конуэем долго и тщательно, а затем
проверялись на практике. Таким образом, он добивался удовлетворяли трём
условиям:
1. Не должно быть ни одной исходной конфигурации, для которой
существовало
бы
простое
доказательство
возможности
неограниченного роста популяции;
2. В то же время должны существовать такие начальные конфигурации,
которые заведомо обладают способностью беспредельно развиваться;
3. Должны существовать простые начальные конфигурации, которые в
течение значительного промежутка времени растут, претерпевают
разнообразные изменения и заканчивают свою эволюцию одним из
следующих трёх способов: полностью исчезают (либо из-за
перенаселённости, то есть слишком большой плотности фишек, либо
наоборот, из-за разрежённости фишек, образующих конфигурацию),
переходят в устойчивую конфигурацию и перестают изменяться
вообще или же, наконец, выходят на колебательный режим, то есть
бесконечный цикл превращений с определенным периодом.
Генетические законы, разработанные Конуэем,достаточно просты.
Первым деломнеобходимообратить внимание на то, что каждая клеткана
доскеимеет восемь соседних клеток, четыре из которых имеют с ней общие
стороны, а другие четыре – общие диагонали. Также необходимо помнить,
что игровая доска бесконечна. Генетические законы или правила игры
содержат в себе три пункта: выживание, гибель и рождение. Разберем
каждый из них:
1. Выживанием следует считать переход в следующее поколение каждой
фишки, имеющей вокруг себя две или три соседние фишки;
2. Каждая фишка, имеющая около себя больше трёх соседей, погибает, то
есть снимается с доски из-за перенаселённости. От одиночества фишка
погибает в том случае, когда вокруг нее свободны все соседние клетки
или занята всего лишь одна. Данные процессы называются гибелью;
3. Рождением следует называть процесс, когда около одной пустой
клетки находятся ни больше, ни меньше, а ровно три фишки. На
следующем ходу на эту клетку кладется новая фишка.
Необходимо понимать, что рождение и гибель каждого из организмов
происходят одновременно. Один ход в эволюции начальной конфигурации
12
получается путем образования одного поколения из вместе взятых
организмов.Чтобы начать игру, необходимо определиться с начальной
конфигурацией, которая будет эволюционировать в процессе игры. Т.к. в
этой игре очень легко запутаться, следует очень аккуратно и внимательно
совершать каждое действие. Для начала составляем из черных фишек
простой организм, способный прожить хотя бы пару ходов. Теперь же,
придерживаясь генетических законов Конуэя, выбираем, какие из живых
клеток должны погибнуть на этом ходу и вновь кладем на них черные
фишки, образовав таким образом небольшую башенку. Следующим этапом
будет рождение. На каждую клетку, на которой должен произойти акт
рождения ставится белая фишка. Перед переходом на следующий шаг,
следует внимательно проверить, не сделано ли где ошибок, а затем снять все
«башенки» с доски. Закончив, получится первое поколение. Чтобы получить
следующее, нужно проделать аналогичные действия и так до тех пор, пока
организм полностью не исчезнет со стола.
Каждый раз, уже после начала игры, популяции переживают
достаточно интересные изменения. Некоторые начальные расположения
фишек могут исчезнуть на первых ходах, а некоторые могут существовать
бесконечно долго. Все зависит от того, как именно задать начальную
конфигурацию. Однако, чаще всего они переходят в одно из двух состояний.
Первое Конуэй любил называть «любители спокойной жизни», т.е. такое
состояние не изменяется на протяжении оставшихся ходов. Во втором случае
конфигурация переходит в колебательный режим. Также стоит отметить, что
симметрия в данной игре ведет себя несколько странно. Не симметричные
организмы, спустя несколько поколений, эту самую симметрию обретают и
все ее свойства, приобретенные в процессе эволюции, никак не
утрачиваются, а наоборот, обогащаются.
Согласно гипотезе Конуэя, не существует ни одной начальной
конфигурации, которая способна бесконечно расти. По-другому говоря,
любая конфигурация, состоящая из конечного числа фишек, не может
перейти конфигурацию, в которой число фишек превосходило бы некий
конечный верхний предел. Пожалуй, эта задача является одной из самых
сложных и глубоких задач, способных возникнуть в игре «Жизнь». Когда
описание игры появилось в октябрьском номере журнала ScientificAmericanза
1970 год, Конуэй предлагал премию тому, кто до конца года первым докажет
или опровергнет его гипотезу. Опровергнуть гипотезу Конуэя можно было
бы, например, построив конфигурацию, к которой, следуя правилам игры,
все время приходилось бы добавлять новые фишки, например, «ружье» (рис.
1), конфигурация, которая через определенное число ходов «выстреливает»,
13
движущиеся фигуры вроде «планера», или «паровоз, пускающий дым из
трубы» - движущаяся конфигурация, оставляющая за собой «клубы дыма»).
Также игрой Конуэя «Жизнь» заинтересовались ученые, занимающиеся
разработкой проблем, связанных с использованием ЭВМ. Стоит обратить
внимание на некоторые основные факты развития «теории клеточных
автоматов»-области науки, занимающейся изучением игр, аналогичных игре
Конуэя «Жизнь».
Рис. 1. Планерное ружье
В 1950 году Джон фон Нейман поставил перед собой задачу доказать
возможность существования самовоспроизводящихся автоматов. Достаточно
обеспечить такую машину надлежащими инструкциями, чтобы она смогла
воспроизвести точную копию самой себя. В дальнейшем, эти две машины
(«мама» и «дочь») смогут построить еще две. Последующие четыре машины
построят восемь и так до бесконечности. «Кинематические» модели машины,
способные передвигаться по складу запасных частей, отбирать необходимые
детали и собирать новые машины, один в один похожие на нее,
поспособствовали фон Нейману впервые доказать существование
самовоспроизводящихся автоматов. Спустя время фон Нейман дал более
изящное и абстрактное доказательство возможности существования
самовоспроизводящихся машин, благодаря идее, высказанной его другом
Станиславом Уламом.
Работая над новым доказательством, фон Нейман часто использовал
понятие «однородного клеточного пространства», которое в свою очередь
14
эквивалентно бесконечной шахматной доске. В этом пространстве клетки
могут находится в любом, но конечном числе «состояний», в том числе в
состоянии «покоя» (называемом так же пустым, или нулевым состоянием).
Конечное число соседних клеток напрямую оказывает влияние на состояние
любой клетки. В соответствии с «правилами перехода», которые необходимо
применять одновременно ко всем клеткам, состояния пространства
изменяются во времени дискретно. Клетки соответствуют основным частям
автомата с конечным числом состояний, а конфигурация из «живых» клетокидеализированной модели автомата. Именно в таком клеточном
пространстве и происходит действие придуманной Конуэем игры «Жизнь». В
данной игре соседними клетками считаются восемь клеток, окружающих ее.
Клетка может находитсятолько в двух состояниях: либо на ней стоит фишка,
либо клетка пуста. Правила перехода определяются генетическими законами
Конуэя (рождение, гибель и выживание). С помощью правила перехода к
пространству, в котором каждая клетка или ячейка могла находится в 29
состояниях и имела четыре соседние клетки (примыкающие к данной по
вертикали и горизонтали), фон Нейман доказал существование
самовоспроизводящейся конфигурации, которая состоит в общей сложности
из 200000 клеток.
Причина таких невообразимых размеров конфигурации объяснялась
тем, что фон Нейман хотел применить свое доказательство к уже
существующим автоматам. Он специально подобрал такое клеточное
пространство, которое способно воспроизвести машину Тьюринга. Машина
Тьюринга — этоидеальный автомат, который способен производить любые
вычисления. Был назван в честь А. М. Тьюринга, английского математика и
изобретателя. Фон Нейман получил возможность создать «универсальный
конструктор», «погрузив» универсальную машину Тьюринга в созданную им
конфигурацию. Подобный конструктор способен построить любую
конфигурацию в пустых клетках пространства, в том числе и свою точную
копию. После смерти фон Неймана в 1957 году, некоторым энтузиастам
удалось значительно упростить предложенное им доказательство
существования самовоспроизводящейся системы (стоит иметь ввиду, что
здесь говорится именно о «чистом» доказательстве существования, а не о
построении используемой в доказательстве фон Неймана конфигурации).
Одним из них был Эдвин Р. Бэнкс, выпускник инженерного факультета
Массачусетского технологического института. В данном доказательстве
используются только те ячейки, которые могут находится лишь в четырех
состояниях.
С. Улам исследовал большое количество автоматов, отличающихся
друг от друга схемой примыкания соседних клеток, числом состояний и
15
правилами перехода, что в дальнейшем поспособствовало ему описать
несколько подобных игр. Как и в игре Конуэя, клетки в игре Улама могут
находиться в двух состояниях, но соседнимисчитаются клетки,
примыкающие к данной лишь по вертикали и по горизонтали, но не по
диагонали («соседи» в смысле фон Неймана).Рождение фишки происходит
на клетке, имеющей одного и только одного соседа, а все клетки n-го
поколения погибают после рождения (n+2)-го поколения. Иначе говоря, на
любом этапе эволюции, выживают лишь два последних поколения. Также
Улам проводил эксперименты и с такими играми, в которых две
конфигурации растут до тех пор, пока не столкнутся друг с другом. В
следующей за столкновением «битве» одной стороне иногда удавалось
одержать верх над другой, иногда обе армии исчезали. Улам рассмотрел так
же игры на трехмерных досках-кубических «паркетах», заполняющих все
пространство. Наиболее важные результаты Улама были собраны в
отдельные статьи иопубликованы в сборнике «Очерки теории клеточных
автоматов».
Игры, подобные предыдущим, можно устроить на бесконечных досках,
заменив форму обычных квадратных клеток на форму клеток в виде
равносторонних треугольников и правильных шестиугольников. В принципе
эти игры не вносят каких-либо нововведений, хоть и имеют между собой
сильные внешние различия.Применяя соответствующие определения
«соседних» клеток, их всегда можно свести к эквивалентным играм на
обычной доске с клетками в форме квадратов. Соседними могут быть не
только клетки, имеющие общие стороны или вершины. В шахматах,
например, для клетки, на которой стоит конь, соседними (то есть влияющими
на ее состояние) считаются все клетки, на которые можно пойти конем или
на которых стоят угрожающие ему фигуры. Как заметил Беркс, такие игры,
как шахматы, шашки и го, допустимо рассматривать как клеточные автоматы
со сложными окрестностями каждой клетки (окрестностью называется
совокупность соседей) и правилами перехода. Противники, делая очередной
ход, выбирают среди множества допустимых состояний то, которое должно
привести их к определенному конечному состоянию-выигрышу.
Среди наиболее значительных вкладов в теорию клеточных автоматов
наибольшую известность получил предложенный Эдвародом Ф. Муром
способ доказательства существования конфигураций, которые Джон У.
Тьюки назвал «Садами Эдема» (рис. 2). Эти конфигурации не могут
возникать в процессе игры, поскольку никакая конфигурация отличного от
них типа не может их породить. «Сады Эдема» возможно задать только в
нулевом поколении, т.е. с самого начала игры. У подобных конфигураций
16
отсутствуют «предшественники», в следствие чего они не могут быть
самовоспроизводящимися.
Алви Р. Смит обнаружил простой способ, позволяющий применить
метод Мура к игре Конуэя. Из теоремы Мура следует, что конфигурация типа
«садов Эдема» должна возникать в игре Конуэя. К сожалению,
доказательство теоремы ничего не говорит о том, как найти «сады Эдема», и
они до сих пор не обнаружены. Конфигурация типа «садов Эдема» в какомто смысле парадоксальна, т.к. она может оказаться в одном случае простой, а
в другом достаточно сложной. Благодаря одной из формул, выведенных
Муром, Смит доказал, что такую конфигурацию всегда можно заключить в
квадрат со стороной в 10 миллиардов клеток. Однако даже этот результат
совсем не облегчает поиски подобной конфигурации.
Рис. 2. «Сады Эдема»
Благодаря созданию «планерного ружья» была открыта возможность
имитации в игре Конуэя машины Тьюринга. Данная машина способна, в
теории, производить все действия, которые только доступны самым
совершенным из современных ЭВМ. «Планеры» можно было бы применять в
качестве «единичных импульсов», целью которых являетсяне только
хранение и передача информации, но и выполнение всех операций,
допускаемых схемой реальной вычислительной машины. Если игра Конуэя
действительно допускает создание машины Тьюринга, то следующим
вопросом было бы создание универсального конструктора, позволяющего
осуществлять нетривиальное самовоспроизведение конфигураций. До сих
пор никому не удалось «построить» машину Тьюринга в пространстве, все
клетки которого могут находится лишь в двух состояниях, а «соседние»
клетки понимаются в смысле Конуэя (то есть должны иметь с данной либо
общую сторону, либо общую вершину). Доказано, что в пространстве, все
клетки которого могут находится в двух состояниях, а «соседство»
понимается в смысле фон Неймана, построить машину Тьюринга
невозможно.
17
1.2 Выбор инструментария
Как и любая другая простая программа, игра «Жизнь» может быть
реализована на большом количестве доступных языков программирования.
Но, т.к. ее реализация должна быть представлена в браузере, то наиболее
подходящим языком в данной ситуации будет JavaScript [7].
JavaScript[7] это мультипарадигменный язык программирования,
которыйподдерживает
объектно-ориентированный,
императивный
и
функциональный стили. Данный языкприменяется как встраиваемый язык
для программного доступа к объектам приложений. С самого началаего
создавали для того, чтобы сделать веб-странички более «живыми».
Программы на этом языке именуются скриптами. В браузере они
подключатся напрямую к HTMLи, по завершению загрузки страницы,
моментально выполняются.
Современный
JavaScript
[7]
–
это
«безопасный»
язык
программирования общего назначения. Поскольку изначально данный язык
был ориентирован на браузеры, то он не предоставляет низкоуровневых
средств работы с памятью и процессором, т.к. в них этого не требуется.
Остальные возможности языка напрямуюзависят от окружения, в котором
JavaScript [7] был запущен. В браузере JavaScript [7] способен делать всё, что
относится к взаимодействию с посетителем, манипуляциям со страницейи, в
какой-то мере, с сервером. Так же он поддерживается всеми
распространенными браузерами ичасто включен в них по умолчанию, а
также, имеет полную интеграцию с HTML/CSS.
Встроенный во все основные браузеры интерпретатор
JavaScript [7]
позволяет запускать любые скрипты на веб-страницах. Данный язык можно
использовать не только в браузерах.По своей сути он является полноценным
языком, программы на котором можно запускать как на сервере, так и в
стиральной машинке, если в ней конечно установлен соответствующий
интерпретатор.
Структурно JavaScript[7] можно представить в виде объединения трех
четко различимых друг от друга частей:
 ядро (ECMAScript),
 объектная модель браузера (BrowserObjectModel, BOM),
 объектная модель документа (DocumentObjectModel, DOM).
При рассмотрении JavaScript[7] в отличных от браузера окружениях,
можно заметить, что объектная модель браузера и объектная модель
документа имеют возможность и вовсе не поддерживаться. Объектную
модель документа иногда рассматривают как отдельную от JavaScript[7]
18
сущность, что согласуется с определением DOMкак независимого от языка
интерфейса документа. В противоположность этому ряд авторов находят
BOM иDOMтесно взаимосвязанными.
ECMAScript не является браузерным языком и в нём не определяются
методы ввода и вывода информации. Это, скорее, основа для построения
скриптовых языков. Спецификация ECMAScript описывает типы данных,
инструкции, ключевые и зарезервированные слова, операторы, объекты,
регулярные выражения, не ограничивая авторов производных языков в
расширении их новыми составляющими.
Объектная модель браузера - браузер-специфичная часть языка,
являющаяся прослойкой между ядром и объектной моделью документа.
Основное предназначение объектной модели браузера — управление окнами
браузера и обеспечение их взаимодействия. Каждое из окон браузера
представляется объектом window, центральным объектом DOM. Объектная
модель браузера на данный момент не стандартизирована, однако
спецификация находится в разработке WHATWGи W3C.
Помимо управления окнами, в рамках объектной модели браузера,
браузерами обычно обеспечивается поддержка следующих сущностей:








управление фреймами,
поддержка задержки в исполнении кода и зацикливания с задержкой,
системные диалоги,
управление адресом открытой страницы,
управление информацией о браузере,
управление информацией о параметрах монитора,
ограниченное управление историей просмотра страниц,
поддержка работы с HTTP cookie.
Объектная модель документа — интерфейс программирования
приложений для HTML и XML-документов. Согласно DOM, документ
(например, веб-страница) может быть представлен в виде дерева объектов,
обладающих рядом свойств, которые позволяют производить с ним
различные манипуляции:





генерация и добавление узлов,
получение узлов,
изменение узлов,
изменение связей между узлами,
удаление узлов.
19
Область применения JavaScript[7] достаточно широка. Он используется
в клиентской части веб-приложений: клиент-серверных программ, в котором
клиентом является браузер, а сервером - веб-сервер, имеющих
распределённую между сервером и клиентом логику. Обмен информацией в
веб-приложениях происходит по сети. Одним из преимуществ такого
подхода является тот факт, что клиенты не зависят от конкретной
операционной системы пользователя, поэтому веб-приложения являются
кроссплатформенными сервисами.
Canvas[8] это элемент HTML 5, предназначенный для создания
растрового двухмерного изображения при помощи скриптов, обычно на
языке JavaScript [7]. Начало отсчета блока находится слева сверху, от него и
строится каждый элемент блока. Размер пространства координат не
обязательно отражает размер фактической отображаемой площади. По
умолчанию его ширина равна тремстам пикселям, а высота ста пятидесяти.
Используются, как правило, для отрисовки графиков для статей и игрового
поля в некоторых браузерных играх. Но также может использоваться для
встраивания видео в страницу и создания полноценного плеера.
Он выглядит как элемент <img>, но его отличие в том, что он не имеет
атрибутов src и alt. Элемент <canvas> имеет только два атрибута - ширину и
высоту. Оба они не обязательны и могут быть выставлены с использованием
свойств DOM. Если атрибуты высоты и ширины не установлены, canvas [8]
будет по умолчанию шириной 300 писелей и в высоту 150 пикселей. Вы так
же можете выставить размеры произвольно в CSS, но во время рендеринга
изображение будет масштабироваться в соответствии с его размером и
ориентацией.
Атрибут id не специфичен для элемента <canvas>, но он может быть
применен по умолчанию в атрибутах HTML, так как он может быть
использован (почти) для любого элемента HTML (так же как класс). Это
всегда отличная идея использовать id, так как это позволяет намного проще
идентифицировать наш элемент в сценарии. Элемент <canvas> может быть
стилизован также, как любое изображение (margin, border, background, и т.
д.). Эти правила, как бы то ни было, фактически не влияют на отрисовку в
canvas [8].
Из-за того, что старые браузеры не поддерживают элемент <canvas>,
идля этого следует предоставить запасное содержимое для отображения
этими браузерами. Это очень просто, надо всего лишь предоставить
альтернативное содержимое внутри элемента <canvas>. Браузеры, которые не
поддерживают <canvas> проигнорируют container и отобразят запасное
содержимое этого тега. Браузеры, которые поддерживают <canvas>
20
проигнорируют запасное содержимое, и просто нормально отобразят canvas
[8].
В отличии от элемента <img>, элемент <canvas>требует
закрывающийся тег (</canvas>). Если этот тег не предоставлен, остаток
документа будет считаться запасным контентом и не будет отображен. Если
запасной контент не нужен, простой <canvas id="foo" ...></canvas>
полностью совместим со всеми браузерами, что поддерживают canvas [8].
Элемент <canvas> в документе создается с фиксированным размером
элемента для рисования, который может иметь один или несколько
контекстов для рендеринга, создавая и манипулируя содержимым для показа.
Разные контексты могут предоставлять разные типы рендеринга, к примеру
WebGl использует 3D контекст основанный на OpenGL ES.Холст изначально
пустой и прозрачный. Первым делом скрипт получает доступ к контексту и
отрисовывает его. Элемент <canvas> имеет метод getContext(), используется
для получения контекста визуализации и ее функции рисования. getContext()
принимает один параметр, тип контекста. Для 2D графики, которая
необходима для создания игры «Жизнь» лучше всего будет использовать
метку "2d".
Данный элемент был выбран для использования, т.к. он очень удобен
при создании нечто подобного, вроде браузерный вариант игры «Жизнь».
Начало отсчета находится в левом верхнем углу, но ее можно сдвигать. Если
нет необходимости перерисовывать холст, но нужно производить
манипуляции с ним, то можно «сфотографировать» весь холст и сохранить в
переменную, и работать уже непосредственно с рисунком. Если же
обновляться должно не все изображение, а только его часть, то можно
стирать определенную зону и рисовать ее заново. Так же можно
манипулировать каждым пикселем, что гораздо упрощает разработку.
21
ГЛАВА 2. РЕАЛИЗАЦИЯ БРАУЗЕРНОЙ ИГРЫ «ЖИЗНЬ».
АНАЛИЗ ТИПОВЫХ КОНФИГУРАЦИЙ
2.1 Реализация браузерной игры «Жизнь»
Прежде чем приступать к разработке программного обеспечения, стоит
определиться, как именно JavaScript [7] будет взаимодействовать с HTML.
Существует два варианта, либо создать отдельный скрипт-файл и
производить все расчеты там, либо встроить скрипт в htmlфайл. Второй
вариант выглядит практичнее в плане количества файлов, но, на этом его
плюсы заканчиваются. Искать ошибки в коде таким образом гораздо
сложнее, нежели проверять файлы по отдельности. В конце концов,
нагромождение кода в общую кучу будет выглядеть не так практично и
красиво, нежели отдельная строчка, интегрирующая JavaSript [7] в вебстраницу. Вставляется же этот скрипт в HTML с помощью тега
<script></script>, что в принципе не должно вызвать каких-либо проблем. Но,
прежде чем использовать этот тег, стоит написать сам html-файл.
Т.к. выбран был вариант с интегрированием скрипта, код-веб
странички не будет представлять из себя чего-то сложного. Важно лишь
правильно написать «тело» программы. Для удобства, нам понадобится три
кнопки: запустить, следующий шаг и очистить поле. Кнопка «Запустить»
будет особенной, т.к. она является своеобразным ключем зажигания. По
нажатию, ее описание будет изменено на «Остановить». Нажав на нее снова,
она примет исходное положение. Прописав нужные теги, а также, создав
рамку с помощью элемента canvas [8], получим первоначальный вид вебстранички (рис. 3). По возможности, после написания основной программы,
можно будет изменить разрешение рамки, которая в дальнейшем станет
игровой областью, где будут происходит все основные действия «Жизни».
Прежде чем приступить к написанию скрипта, необходимо скачать
специализированный редактор, способный поддерживать язык JavaScript [7].
Скрипты, как и html-файлы, можно писать и в обычных текстовых
редакторах. Однако блокнот весьма неудобен для таких манипуляций, т.к. он
не обладает нужными подсказками, выделением важных объектов
соответствующими цветами. Поэтому, в силу своих возможностей, стоит
выбрать какой-либо легкий, а главное, бесплатный редактор кода. Таким
является VisualStudioCode. Он не сложен в освоении и обладает всеми
нужными качествами для разработки простых программ и приложений.
22
Рис. 3. Результат работы «Жизнь.html»
Весь скрипт представляет собой одну большую функцию, которая в
свою очередь также состоит из функций. Первым делом необходимо
получить контекст canvas [8] для рисования. Т.к. контекст будет двумерным,
в скобках ставится значение 2d. Следующим шагом будет запрет
контекстного меню. Это необходимо для того, чтобы реализовать
возможность стирать ненужные «живые» клетки с игровой области по
нажатию правого клика.
var context = canvas.getContext("2d");
document.oncontextmenu=function(e){return false};
Далее идут стандартные настройки, по типу ширины/высоты окна и
клетки. Самой важной частью в этих настройках являются константы Bи L,
которые отвечают за геном рождения и геном выживания соответственно.
Здесь следует разобраться, что же из себя представляют эти геномы.
const B = "000100000";
const L = "001100000";
В данном случае, геном представляет собой массив из девяти чисел-генов,
каждое из которых может принимать значение один или ноль. Ноль означает,
что ген молчит, единица – ген активен. Если ген активен, то поле с
соответствующим числом соседей рассматривается как поле, в котором
клетка может выжить или родиться, в зависимости от генома. Первый
элемент массива, по сути, является нулевым, т.к. он проверяет наличие
23
нулевого соседа. Таким образом, следуя правилам Конуэя, геном выживания
будет соответствовать массиву 001100000. Этот массив означает, что клетка
выживает лишь в том случае, если рядом с ней находится два или три соседа.
Массив 000100000 в свою очередь соответствует геному рождения. По
правилам, рождение происходит лишь в том случае, когда возле клетки
находится ровно три соседа.
Также, следует задать константы для координат курсора мыши,
которые помогут в дальнейшем определять, находится ли курсор в игровой
области или нет. Раз есть координаты, то и должна быть процедура,
обновляющая эти координаты в переменных mouseXи mouseY.
function refreshMouseCoords(e){
var rect = canvas.getBoundingClientRect();
mouseX = e.clientX - rect.left;
mouseY = e.clientY - rect.top;
}
Теперь приступаем к событию нажатия клавиши. При нажатии левой
клавиши мыши, клетки будут рождаться в выбранной области, а при нажатии
правой – умирать, или стираться с рабочей области.
canvas.onmousedown = function(e){
var life;
if (e.which == 1) life = true;
else if (e.which == 3) life = false;
else return;
setCell(e, life);
canvas.onmousemove = function(e) {setCell(e, life);};
};
Для отпущенной клавиши следует написать свою мини-функцию, которая
будет задействована в момент спокойствия, т.е. никаких действий
происходить не будет.
document.onmouseup = function(e){
canvas.onmousemove = null;
};
Никаких сложностей с созданием данной части скрипта возникнуть не
должно, т.к. эти функции достаточно просты в своем создании и не требуют
каких-либо хитрых манипуляций с кодом.
Следующим идет по списку создание тех самых клавиш, которые уже
были заданы в html-файле (рис.3). Как и с обработкой событий мыши,
24
данные функции не вызывают каких-либо проблем при создании. Например,
кнопка «Следующий шаг» будет выглядеть следующим образом:
MainChain.prototype.nextStep = function(){
stopSystem();
step();
};
Самой сложной частью, будет вычислительная, где будут определяться
соседи выбранной клетки. Более наглядно этот код представлен в виде блоксхемы (рис. 4). Эта часть скрипта будет работать до тех пор, пока не
посчитает количество всех соседей на рабочей области. В массивы будут
записаны нужные данные, которые позволят отрисовать по новой игровую
область, меняя местоположение клеток, в зависимости от того, умерла
клетка, родилась или же осталась в своем неизменном состоянии.
Следующей будет функция draw, которая и будет рисовать «живые»
клетки в рабочей области. Пожалуй, она будет одной из наипростейших в
данном скрипте, т.к. в любом языке программирования, в котором имеется
какой-либо графический интерфейс, общая структура построения остается
одной и той же.
function draw(){
context.clearRect(0, 0, w, h);
for (var i = 0; i < n; i++){
for (var j = 0; j < m; j++){
if (cells[i][j]){
context.beginPath();
context.rect(i*cellW, j*cellH, cellW, cellH);
context.closePath();
context.fillStyle = "red";
context.fill();
}
}
}
}
БлагодаряfillStyleвыбратьлюбойцветдляобозначения «живых» клеток. Сама
же отрисовка производится благодаря методу rect. Он рисует квадрат по
координатам массива cells и указанным в самом начале программы ширине и
высоте. По большей своей части они отвечают за размерность не только
клетки, но и игрового поля. Чем меньше размер «организма», тем больше
доска для игры.
Функция generateRandomFieldбудет запускаться сразу по открытию
веб-страницы. Рабочая область моментально заполнится живыми
25
организмами, которые шаг за шагом будут претерпевать различные
изменения, согласно правилам Конуэя.
function generateRandomField(n, m) {
cells = [];
for (var i = 0; i < n; i++) {
cells[i] = [];
for (var j = 0; j < m; j++) {
cells[i][j] = (Math.random() >= 0.5);
}
}
}
Рис. 4. Блок-схема.
26
Последней функцией в данном скрипте будет функция отрисовки сетки
на игровой области.
function drawGrid() {
context.strokeStyle = '#808080';
context.beginPath();
for (var i = 0; i <= n; i++) {
context.moveTo(i * cellW + 0.5, 0.5);
context.lineTo(i * cellH + 0.5, n * cellH);
context.moveTo(0.5, i * cellW + 0.5);
context.lineTo(n * cellH, i * cellH + 0.5);
}
context.stroke();
}
Благодаря данной функции игровая область получит четкую границу для
каждой клетки. Однако, для удобства, стоит все-таки расширить игровую
область, изображенную на рисунке 3. Дляэтоговhtml-файле необходимо
изменить данный тег, а конкретно ширину и высоту<canvasid="canvasCelAut"
width="600" height="600" style="border:3pxsolid #000000;">. Теперь рабочая
область будет выглядеть как изображено на рисунке 5.
Также следует упомянуть, что в данной программе поле является
бесконечным, как в игре «Змейка». Т.е., когда змейка упиралась, допустим, в
левую границу экрана, она выходила из правой. Тоже самое происходит и в
игре жизнь. Если организм уперся в правую границу игровой области, то на
следующем шаге его часть может появится на левой стороне, если
выполнятся условия для зарождения жизни. Это можно увидеть на рисунках
6 и 7. На рисунке 6 показан фрагмент, где «клеточный организм». На
следующем шаге, после проверок условий на жизнь/смерть, а также
рождение новых клеток, образуется новый организм и его правая часть,
которая должна была бы исчезнуть, переходит на левую сторону игровой
области, что как раз и показано на рисунке 7.
27
Рис. 5. Конечный вариант игровой области.
28
Рис. 6. Фрагмент
игровой области. Шаг 1.
Рис. 7. Фрагмент игровой области. Шаг 2.
2.2 Типовые конфигурации
Т.к. игра «Жизнь» существует уже большой промежуток времени, было
создано огромное количество конфигураций. Самыми распространенными на
данный момент являются:
 Планерное ружьё Госпера — первая бесконечно растущая фигура
 Устойчивые фигуры: фигуры, которые остаются неизменными
 Долгожители: фигуры, которые долго меняются, прежде чем
стабилизироваться.
 Периодические фигуры: фигуры, у которых состояние повторяется
через некоторое число поколений
 Двигающиеся фигуры: фигуры, у которых состояние повторяется, но с
некоторым смещением
 Ружья: фигуры, у которых состояние повторяется, но дополнительно
появляется двигающаяся фигура
 Паровозы: движущиеся фигуры, оставляющие за собой следы в виде
устойчивых или периодических фигур (клубы дыма)
29
 Пожиратели: устойчивые фигуры, которые могут
столкновения с некоторыми двигающимися фигурами
 Фигуры, которые при столкновении с некоторыми
дублируются
пережить
фигурами
Большая часть начальных состояний имеет свое уникальное название.
К самым простейшим относятся состояния, которые состоят из трех, четырех
и пяти фишек. Они называются триплет, тетрамино, пентамино
соответственно. Сперва рассмотрим триплет. Такая конфигурация может
выжить лишь только в том случае, когда хотя бы одна фишка граничит с
двумя занятыми клетками. Однако во всех остальных случаях, триплеты
погибают моментально. На рисунке 8 изображены пять триплетов, которые
не погибают на первом ходу,при этом ориентация триплетов, т. е. их
расположение на плоскости, не играет никакой роли.Что касается третьей
конфигурации, то стоит учесть, что любой ряд фишек, расположенный по
диагонали, в конце концов исчезнет. Это происходит из-за того, что с
каждым ходом он теряет фишки, стоящие на концах диагонали. По сути,
любой диагональный ряд, каким бы длинным он не был, всегда будет
распадаться со скоростью света и в конце концов исчезнет.Конфигурация,
под номером четыре, превратиться устойчивую и будет иметь вид квадрата,
размером 2х2 клетки. Такие конфигурации часто называют «любителями
спокойной жизни».Пятая конфигурация носит название «флип-флоп».Флипфлопы возвращаются в исходное состояние спустя каждые два хода.
На рисунке 9 изображена эволюция четырех тетрамино. Первое
тетрамино, квадрат, уже рассматривалось выше.Оставшиеся три
конфигурации также являются любителями спокойной жизни, однако они
превращаются уже не в квадрат, а в улей. При чем, последняя конфигурация
превращается в улей на третьем ходу, а вторая и третья – на втором.Довольно
интересными являются, так называемые, «навигационные огни» или
«светофоры» (рис. 9),которые относятся к типу флип-флопов и, как и ульи,
возникают в игре довольно часто. После девятого хода эта конфигурация
распадается на четыре отдельные «мигалки».
30
Рис. 8. Виды триплетов
Рис. 9. Виды тетрамино
Рис. 10. Навигационные огни
31
Рис. 11. Устойчивые конфигурации
Рис. 12. Пасека
На рисунке 11 изображены двенадцать наиболее часто встречающихся
конфигураций из числа спокойной жизни. Пасека (рис. 12) одна из
устойчивых конфигураций, состоящая из четырех ульев. Чтобы ее получить,
необходимо построить горизонтальный ряд из 7 фишек, который, спустя 14
ходов и превратиться в пасеку. Однако, квадрат, размером 5х5 после первого
же хода переходит в конфигурацию, которая возникает лишь на четвертом
этапе эволюции ряда, состоящего из 7 клеток. Благодаря этому, он
становится пасекой после 11 ходов.
Планер, конфигурация из 5 клеток, – одно из самых интересных
открытий Конуэя. Если проследить за эволюцией больших организмов,
заданных случайным образом, то можно заметить, что некоторые из них,
распадаясь, превращаются в глайдеры. Данная конфигурация примечательна
тем, что каждые два хода планер возвращается в свое изначальное состояние.
Движение данного организма происходит относительно начальной позиции
вправо и вниз ровно на одну клетку. Также стоит упомянуть, что глайдер
движется со скоростью, равной одной четвертой скорости света.
Конуэю известны и другие движущиеся конфигурации, кроме планера,
которые он называет космическими кораблями. На рисунке 12 показаны три
космических корабля, которыепередвигаются со скоростью, равной половине
скорости света, горизонтально слева направо. Во время полета из них
вылетают «искры», которые моментально гаснут при дальнейшем движении
кораблей.
32
Рис. 13. Космические корабли
Одиночные космические корабли не могут занимать в длину больше
шести клеток, если рядом с ними не присутствует эскорта.Иначе, на доске
начинают появляться различные мелкие фигуры, препятствующие движению
корабля. Конуэй обнаружил, что более длинным кораблям, которые он
назвал сверхтяжелыми, необходим эскорт из двух или более кораблей,
размеры которых меньше сверхтяжелого. Данный эскорт не дает возникать
препятствиям на пути сверхтяжёлого корабля. Для самого большого
космического корабля, изображенного на рисунке 14, достаточно двух
эскортирующих кораблей меньшего размера. Для более длинных кораблей
необходима целая флотилия эскортирующих кораблей. Произведя
вычисления для корабля длиной в сто клеток, Конуэй выяснил, что ему
понадобится тридцать два корабля меньшего размера в качестве эскорта.
Рис. 14. Сверхтяжелый космический корабль
33
Следующая конфигурация называется пульсар СР 48-56-72 (рис. 15).
Она периодически восстанавливает себя через каждые три хода. Начальное
состояние пульсара образовано 48 фишками; на втором этапе число фишек
возрастает до 56, а на третьем — до 72, после чего пульсар снова
возвращается в исходное состояние, а число фишек понижается до
48.Пульсар образуется после 32 ходов из элемента гептамино, имеющего вид
растянутой буквы П. Это горизонтальный ряд из пяти фишек, у которого под
первой и последней фишкой располагается ещё по одной фишке.
Рис. 15. Пульсар СР 48-56-72
Конуэй исследовал эволюцию всех горизонтальных рядов из n фишек
вплоть до n = 20. Что происходит при n < 5 уже известно. Ряд, состоящий из
пяти клеток переходит в навигационные огни, из шести клеток исчезает, из
семи клеток, как уже выяснилось, получается пасека, из восьми клеток —
четыре улья и четыре блока, ряд, состоящий из девяти клеток, превращается
в два комплекта навигационных огней, а ряд, насчитывающий в себе десять
фишек, переходит в пентадекатлон — периодически воспроизводящую себя
конфигурацию с периодом, равным пятнадцати. Одиннадцатиклеточный ряд
эволюционирует, превращаясь в две мигалки; ряд из двенадцати фишек
переходит в два улья. Ряд из тринадцати клеток, так же как и из одинадцати,
превращается в две мигалки. Ряды, состоящие из 14 или 15 фишек полностью
исчезают. В свою очередь, если фишек 16, то получается большой набор
навигационных огней, состоящий из восьми мигалок. Эволюция ряда из
семнадцати клеток заканчивается четырьмя блоками; ряды, состоящие из 18
или 19 фишек, полностью исчезают с доски, а эволюция двадцатиклеточного
ряда завершается двумя блоками.
Конуэй также исследовал эволюцию рядов (рис. 16), образованных
пятиклеточными группами, отделенными друг от друга одной свободной
клеткой. Ряд 5-5 после двадцать первого хода превращается в пульсар СР 4856-72. Ряд 5-5-5 переходит в четыре блока и четыре мигалки; в результате
эволюции ряда 5-5-5-5 получаются четыре пасеки и четыре мигалки; ряд 5-55-5-5 заканчивает свои превращения разбросанными по доске планерами и
мигалками в количестве восемь штук каждая. Затем планеры попарно
34
сталкиваются и, разрушаясь, превращаются в восемь блоков. Ряд, состоящий
из шести групп по пяти клеток в каждой (5-5-5-5-5-5), превращается в четыре
мигалки, а эволюция следующего ряда 5-5-5-5-5-5-5, по мнению Конуэя,
представляет «замечательное зрелище, если наблюдать её на экране
вычислительной машины». Конфигурация после 323 ходов стабилизируется,
превратившись в четыре навигационных огня, восемь мигалок, восемь
караваев, восемь ульев и четыре блока, то есть в конфигурацию,
насчитывающую 192 фишки.
Рис. 16. Эволюция рядов
Последующая эволюция начальной конфигурации не утрачивает свою
симметрию,
что способствует
сохранить расположению фишек
вертикальную и горизонтальную оси симметрии, которыми она обладала.
Число фишек достигает максимума (492 фишки) в 283 поколении. Стоит
заметить, что ряды типа n-n-n-... интересны лишь тогда, когда n равно по
крайней мере 5, поскольку при меньших значениях n группы из n фишек не
взаимодействуют друг с другом. Ряды 1-1-1-... и 2-2-2-... сразу же исчезают.
Ряд 3-3-3-... состоит из одних лишь мигалок, а ряд 4-4-4-... на втором ходу
переходит в устойчивый ряд ульев.
Планерное ружье, изображенное на рисунке 1, построила группа
математиков из Массачусетского технологического института. Каждые 30
ходов из ружья вылетает планер. С появлением нового планера, число фишек
на доске увеличивается на 5, в следствие чего популяция начинает
неограниченно расти. При рассмотрении пересекающихся потоков планеров
происходят довольно неожиданные результаты: возникающие конфигурации
могут быть самыми причудливыми и в свою очередь испускать планеры. При
35
пересечении потоков планеров изредка рождается конфигурация, которая
способна поглотить другие ружья в процессе своего расширения. В других
случаях из области, в которой происходит пересечение потоков, вылетают
осколки, которые могут вывести из строя одно или несколько ружей.
Последнее достижение группы математиков из Массачусетского
технологического института, убедительно свидетельствующее об их
виртуозности, — хитроумная комбинация нескольких ружей. В пересечении
создаваемых ею потоков планеров возникает целый завод космических
кораблей легчайшего типа, а каждые 300 ходов происходит даже запуск
одного корабля.
Рис. 17. Планеры
Планерное ружье позволило его создателям совершить и много других
открытий. Например, 13 планеров (рис. 17) при столкновении, рассыпаются
на части, превращаясь постепенно в планерное ружье. Та же группа
исследователей обнаружила пентадекатлон — конфигурацию, способную
«поглотить» сталкивающийся с ней планер.Пентадекатлон может также
отражать планер, изменяя курс последнего на 180°. Расположив друг против
друга два пентадекатлона, можно провести между ними «теннисный матч»:
они будут перекидывать планер, как мяч.
Было открыто много других периодически воспроизводящихся
конфигураций. Одна из них, получившая название палка (Рис. 18), имеет
период 2. Её можно как угодно растягивать. Каждое из двух её состояний
переходит в другое при отражении. Другая была ещё раньше открыта
Конуэем — это так называемый осциллятор Герца (Рис. 19). После каждых
четырёх ходов внутренняя точка перемещается к противоположной стороне
рамки, в результате чего вся фигура «осциллирует» с периодом 8. Третья
конфигурация называется тумблер (Рис. 22), потому что каждые 7 ходов у
36
неё меняются местами верх и низ (она «переключается»). Чеширского кота
(Рис. 21) открыл К. Р. Топкинс из Калифорнии. После шести ходов от кота
остается лишь «улыбка», а «морда» совершенно исчезает. Следующим ходом
«улыбка» тоже уничтожается, и лишь неизменный блок — отпечаток
кошачьей лапы — напоминает о том, что некогда на этом месте находился
кот. Жнейка (рис. 20) движется снизу-вверх по бесконечной диагонали со
скоростью света, осциллируя с периодом, равным 4, и вдоль всего пути
оставляет за собой устойчивые фигуры, символизирующие снопы. «К
сожалению, — пишет изобретатель жнейки, — мне не удалось придумать
«сеятеля» — движущуюся фигуру, которая могла бы засевать поле с той же
скоростью, с которой жнейка его убирает».
Рис. 18. Палка
Рис. 19. Осциллятор Герца
Рис. 21. Чеширский кот
Рис. 20. Жнейка
Рис. 22. Тумблер
Вейнрайт является автором многих любопытных исследований.
Разместив случайным образом 4800 фишек в ячейках квадрата размером
120×120 (с плотностью фишек, равной 1/3), он проследил их эволюцию на
протяжении 450 поколений. Плотность этого первообразного студня, как его
называет Вейнрайт, сильно уменьшилась и стала равняться всего лишь 1/6.
Исчезнут ли все фишки в конце концов или же будут, как утверждает
Вейнрайт, продолжать просачиваться из поколения в поколение с некоторой
минимальной постоянной плотностью — ответ на этот вопрос пока не
37
известен. На протяжении 450 поколений удалось проследить появление 42
«короткоживущих» планеров.
Вейнрайту удалось обнаружить 14 конфигураций, которые после
первого хода превращаются в один или несколько планеров. Например, из
первой фигуры (рис. 23) получается один планер. Буква „Z“ (вторая
конфигурация) после 12 ходов превращается в 2 планера, которые движутся в
противоположных направлениях. Если два планера следуют наперерез друг
другу (третья конфигурация), то после четвёртого хода все фишки с доски
исчезают. Если два лёгких космических корабля движутся опасным курсом,
ведущим к столкновению (последняя фигура), то после седьмого хода доска
оказывается абсолютно пустой, как и в случае столкновения двух планеров.
Рис. 23. Планеры
Вейнрайт, кроме того, экспериментировал с разными бесконечными
полями, заполняя их правильными устойчивыми фигурами. Такие
конфигурации он назвал агарами. Если, например, в агар (рис. 24) поместить
один-единственный «вирус» (то есть одну фишку), причём так, чтобы он
касался вершин четырёх блоков, то агар уничтожит вирус, а через два хода
восстановит свой прежний вид. Если же вирус поместить в клетку так, как
показано на рисунке 24 красным цветом, то начнётся неизбежное разрушение
агара.
Рис. 24. Агар
Вирус постепенно поглотит внутри агара все активные участки,
оставив на поле пустую двусторонне симметричную область, грубо говоря,
восьмиугольной формы (рис. 25). Её граница непрерывно расширяется во все
38
стороны со скоростью света, и не исключено, что это расширение будет
происходить бесконечно долго.
Рис. 25. Результат действий вируса.
Игра «Жизнь» имеет большое количество типовых конфигураций и с
каждым днем их число только растет. Некоторые из них, взаимодействуя
друг с другом, порождают новые конфигурации. Примером тому могут
служить рассмотренные выше тринадцать планеров, образующих при
столкновении друг с другом планерное ружье. Но, самым интересным можно
назвать такое явление, как вирус. Выше рассматривалась такая типовая
конфигурация, как агар. Она может быть бесконечно большой, однако,
поместив всего одну клетку между двумя квадратами горизонтально или
вертикально, происходит разрушение всей конструкции. Поразмыслив над
данным экспериментом, можно прийти к выводу, что любая устойчивая
конфигурация или конфигурация, перешедшая в колебательный режим,
39
уничтожается всего лишь из-за организма, размером в одну клетку. Размер
начальной конфигурации не имеет значения.
Подобный пример приближен к реалиям настоящей жизни. Под
вирусом можно подразумевать «Черную смерть», пандемию чумы,
прошедшую в середине XIV века по Азии и Европе, а устойчивой или
колебательной конфигурацией можно назвать устоявшийся режим жизни
обычных людей того времени. Было достаточно всего одной зараженной
особи, в виде грызуна, которая с течением времени уничтожила большое
количество организмов.
Возможности этой игры настолько огромны, что ее, казалось бы,
можно использовать почти в любой из наук. По сей день она привлекает
внимание ученых, что позволяет модифицировать ее раз за разом. Если
продолжить эти изучения и дальше, то когда-нибудь она охватит весь спектр
точных наук, а возможно и выйдет за эти границы.
40
ЗАКЛЮЧЕНИЕ
Выпускная
квалификационная
работа
посвящена
разработке
программного обеспечения для реализации браузерного варианта игры
«Жизнь». В ходе её выполнения разработан скрипт, позволяющий
представить игру «Жизнь» в виде веб-страницы в браузере. Были решены
следующие задачи:
1. Изучена литература по теме исследования. На основе поставленной
задачи был выбран инструментарий для выполнения работы;
2. На языке JavaScript написан браузерный вариант игры «Жизнь».
Визуализация выполняется на элементе canvas веб-страницы;
3. Произведен анализ типовых конфигураций. Дана классификация
возможных вариантов развития игры.
Работа имеет теоретическое и практическое значение, т.к. с помощью
разработанной программы и самой игры «Жизнь» можно проводить
исследования в различных научных областях.
41
СПИСОК ЛИТЕРАТУРЫ
1. Гарднер М. Математические досуги. Пер. с англ. Ю.А. Данилова. Под ред.
Я. А. Смородинского. М., «Мир», 1972г. 496 стр.
2. Тоффоли Т., Марголус Н. Машины клеточных автоматов: Пер. с англ. М.: Мир, 1991. - 280 стр.
3. Мозговой М. В. Занимательное программирование: Самоучитель. – СПб.:
Питер, 2005. 208 с.
4. Гарднер М. Крестики – нолики: Пер. с англ. - М.: «Мир», 1988. 352 с.
5. Мозговой М. В. Занимательное программирование: Самоучитель. – СПб.:
Питер, 2005. 208 с.
6. Игра «Жизнь» (обзор Гарднера)[Электронный ресурс]. – Режим
доступа:https://life.written.ru/ -Дата доступа 01.06.2018.
7. JavaScript (Wikipedia) [Электронный ресурс]. Режим доступа:
https://ru.wikipedia.org/wiki/JavaScript - Дата доступа 25.05.2018.
8. Базовое использование Canvas [Электронный ресурс]. – Режим доступа:
https://developer.mozilla.org/ru/docs/Web/API/Canvas_API/Tutorial/Basic_usa
ge – Дата доступа 02.06.2018.
42
Приложение
Приложение 1.
life.js
function MainChain(canvas) {
var context = canvas.getContext("2d");
document.oncontextmenu=function(e){return false};
const fps = 2;
const w = canvas.width;
const h = canvas.height;
const n = 50;
const m = 50;
const cellW = w/n;
const cellH = h/m;
var pause = true;
var intervalID;
const B = "000100000";
const L = "001100000";
var mouseX;
var mouseY;
canvas.onmousedown = function(e){
var life;
if (e.which == 1) life = true;
else if (e.which == 3) life = false;
else return;
43
setCell(e, life);
canvas.onmousemove = function(e) {setCell(e,
life);};
};
document.onmouseup = function(e){
canvas.onmousemove = null;
};
function refreshMouseCoords(e){
var rect = canvas.getBoundingClientRect();
mouseX = e.clientX - rect.left;
mouseY = e.clientY - rect.top;
}
var cells;
var cellsBuf = [];
for (var i = 0; i < n; i++) cellsBuf[i] = [];
function generateRandomField(n, m) {
cells = [];
for (var i = 0; i < n; i++) {
cells[i] = [];
for (var j = 0; j < m; j++) {
cells[i][j] = (Math.random() >= 0.5);
}
}
}
44
function setCell(e, life){
refreshMouseCoords(e);
if (mouseX < 0 || mouseX >= w || mouseY < 0 ||
mouseY >= h) return;
var i = Math.floor(mouseX/cellW);
var j = Math.floor(mouseY/cellH);
if (cells[i][j] != life) {
cells[i][j] = life;
draw();
drawGrid();
}
}
MainChain.prototype.clear = function(){
for (var i = 0; i < n; i++)
for (var j = 0; j < m; j++)
cells[i][j] = false;
draw();
drawGrid();
stopSystem();
};
function step() {
tick();
draw();
drawGrid();
}
45
MainChain.prototype.changePauseState = function() {
if (!pause) stopSystem();
else startSystem()
};
MainChain.prototype.nextStep = function(){
stopSystem();
step();
};
function startSystem() {
pause = false;
intervalID = setInterval(step, 1000/fps);
document.getElementById('pause').value =
"Остановить";
}
function stopSystem() {
pause = true;
clearInterval(intervalID);
document.getElementById('pause').value =
"Запустить";
}
function next(i, n) {if (i == (n-1)) return 0; else
return i+1;}
function prev(i, n) {if (i == 0) return n-1; else return
i-1;}
46
function tick(){
for (var i0 = 0; i0 < n; i0++)
for (var j0 = 0; j0 < m; j0++)
cellsBuf[i0][j0] = cells[i0][j0];
for (var i = 0; i < n; i++) {
for (var j = 0; j < m; j++) {
var near = 0;
if (cellsBuf[prev(i, n)] [prev(j, m)])
near++;
if (cellsBuf[prev(i, n)] [j])
near++;
if (cellsBuf[prev(i, n)] [next(j, m)])
near++;
if (cellsBuf[i]
[prev(j, m)])
if (cellsBuf[i]
[next(j, m)])
near++;
near++;
if (cellsBuf[next(i, n)] [prev(j, m)])
near++;
if (cellsBuf[next(i, n)] [j])
near++;
if (cellsBuf[next(i, n)] [next(j, m)])
near++;
if (cellsBuf[i][j])
cells[i][j] = (L[near] == '1');
else
47
cells[i][j] = (B[near] == '1');
}
}
}
function drawGrid() {
context.strokeStyle = '#808080';
context.beginPath();
for (var i = 0; i <= n; i++) {
context.moveTo(i * cellW + 0.5, 0.5);
context.lineTo(i * cellH + 0.5, n * cellH);
context.moveTo(0.5, i * cellW + 0.5);
context.lineTo(n * cellH, i * cellH + 0.5);
}
context.stroke();
}
function draw(){
context.clearRect(0, 0, w, h);
for (var i = 0; i < n; i++){
for (var j = 0; j < m; j++){
if (cells[i][j]){
context.beginPath();
context.rect(i*cellW, j*cellH, cellW,
cellH);
context.closePath();
context.fillStyle = "red";
48
context.fill();
}
}
}
}
generateRandomField(n, m);
drawGrid();
startSystem();
}
49
Приложение 2
Жизнь.html
<!DOCTYPE html>
<html>
<head>
<title>Game of "Life"</title>
<script src="life.js"></script>
</head>
<body>
<canvas id="canvasCelAut" width="600" height="600"
style="border:3px solid #000000;"></canvas><br>
<input id="pause" type="button" name="" style="width: 100px"
onclick="app.changePauseState();return false;"/>
<input type="button" name="" onclick="app.nextStep();return
false;" value="Следующийшаг"/>
<input type="button" name="" onclick="app.clear();return
false;" value="Очиститьполе"/>
<script type="text/javascript">var app = new
MainChain(document.getElementById('canvasCelAut'));</script>
</body>
</html>
50
51
1/--страниц
Пожаловаться на содержимое документа