[Из песочницы] Разработка симулятора эволюции одноклеточных организмов «The strongest survives»
В данном посте я расскажу о своем опыте написания игры-симулятора эволюции одноклеточных организмов на прямоугольной плоскости. Кроме разработки алгоритмов симулятора, речь пойдет о проблемах с которыми я столкнулся при разработке данного проекта на C#, а также о его портировании для работы в браузере. В конце статьи будет ссылка на готовую к игре версию и на все исходники. Если я вас заинтересовал — прошу под кат.
Вдохновение
Перед тем как мы приступим — я хочу коротко рассказать о тех проектах, которые вдохновили меня на написание данного симулятора. Первую аналогию вы могли провести еще по скриншоту в шапке поста, ведь мой проект внешне довольно сильно похож на игру «Жизнь», придуманную математиком Джоном Конвем в 1970 году. Еще больше меня вдохновили вот эта и эта статьи других хаброюзеров. Чтоб не гонять уважаемого читателя по ссылкам, коротко опишу о чем идет речь в данных статьях: первая — модификация игры Конвея с добавлением туда естественного отбора, а вторая — моделирование разумной жизни на базе нейронных сетей.
Определение требований
Писать еще один клон игры «Жизнь» я не хотел, да и идея естественного отбора мне настолько понравилась, что я решил сконцентрироваться именно на эволюции. Название пришло само собой — «The strongest survives».
Вот требования, которые я ставил себе при разработке:
- разработать симулятор эволюции, в котором будет множество видов организмов — клеток;
- добавить несколько объектов для взаимодействия клеток с ними (еда, яд, мертвы клетки);
- сделать симуляцию производительной в первую очередь, чтоб можно было быстро увидеть результат за большой период;
- симуляция должна как можно более соответствовать реальной жизни;
- должна быть возможность изменения условий обитания организмов.
В TSS клетки имеют много показателей, от которых зависит их следующее состояние. Они могут анализировать окружающую обстановку и принимать на основе этих данных решения, которые помогут им выжить. На их приоритеты при осмотре окрестностей влияют модификаторы, записанные в геноме. Например, есть параметр агрессия. Когда клетка видит другую клетку с чужеродным геномом, то она прибавляет к стремлению двигаться в ту сторону этот модификатор (агрессию). То же самое с голодом, коллективностью, тягой к яду и тягой к мертвым клеткам. После расчетов выбирается сторона с наибольшей суммой модификаторов.
Основные правила игры:
- вселенная игры имеет свою единицу времени — тик;
- каждая клетка имеет определенный уровень энергии, убывающий во время каждого тика;
- главная цель клетки — выжить и размножиться. Для этого ей нужно собрать как можно больше энергии;
- все клетки имеют максимальный возраст;
- клетки могут иметь разный геном, который влияет на их стратегию выживания, при этом их физические возможности равны;
- во время каждого тика каждая клетка может сделать один шаг в одну из 4-х выбранных сторон. При выборе направления шага, в зависимости от находящегося на новом месте объекта, произойдет какое-то событие. Если там пустое место — она просто туда переместится, если там еда, яд, или мертвая клетка — она получит их уровень энергии и тоже переместиться туда. Если же там живая клетка — она останется на месте и, в зависимости от того, какая там клетка произойдет определенное событие. Если там клетка с таким же геномом, то обе получат энергию, если с другим геномом — данная клетка заберет у нее часть энергии.
Клетка может сделать один ход раз в тик. Точнее, она осматривает площадь вокруг, как это показано на картинке и выбирает приоритетное направление: вверх, вниз, влево, вправо или стоять на месте.
Также клетка может размножиться. Размножение происходит делением, один раз за тик, если у клетки достаточно энергии. При этом, рядом должно быть пустое пространство, где создается новая клетка с таким же геномом, либо клетка с мутировавшим геномом. При этом ее уровень энергии делиться поровну между родительской и дочерней клетками. Требуемый для размножения уровень энергии определяет пользователь, но модификатором к нему выступает параметр «репродуктивность». Этот параметр храниться в геноме. Чем он выше — тем меньше энергии нужно клетке для размножения.
Как-то так представлял себе я эту игру, в то время. В целом, что-то подобное и получилось.
Суть геймплея
Геймплей заключается в том, что пользователю предоставляется редактор констант вселенной, в котором он может изменять условия обитания организмов и наблюдать за тем, как они приспосабливаются. Звучит не очень впечатляюще, но здесь довольно много значений, доступных игроку (около 30), меняя которые можно получить множество уникальных вариаций результата. Подробней о каждой константе вы можете почитать в мануале в папке с игрой или под спойлером.
Mutation_Enable — позволяет включить или отключить мутацию клеток при размножении.
Mutation_AttackChildrenMutantsOfFirstGeneration — если это свойство отключено, то клетки не могут атаковать своих потомков первого поколения, когда те мутируют.
Mutation_AttackParentIfCellIsYouMutant — если это свойство отключено, то мутировавшие клетки не могут атаковать своих предков первого поколения.
Mutation_ChangedValuesAtOne — показывает сколько раз изменяются значения, отвечающие за поведение клеток, при каждой мутации. Например, если значение 10, то 10 раз будет выбрано и изменено на 1 случайное свойство клетки, отвечающее за поведение. Может быть от 1 до 200.
Mutation_ChancePercent — шанс мутации при размножении.
CellAge_Max — максимальный возраст клетки.
CellAge_AdultCell — возраст взрослой клетки. У клеток-детей уровень агрессии не выше CellGenome_Child_Aggression и они не могут размножаться.
EnergyLevel_CreatingCell — уровень энергии у клеток, при их генерации на старте.
EnergyLevel_NeededForReproduction — уровень энергии, при котором клетка может размножиться. Может варьироваться из-за CellGenome_ReproductionRange.
EnergyLevel_MaxForCell — максимальный уровень энергии, которую может накопить клетка.
EnergyLevel_DeadCell — уровень энергии, получаемый от мертвых клеток.
EnergyLevel_DefFood — уровень энергии, получаемый от еды.
EnergyLevel_PoisonedFood — уровень энергии, получаемый от яда.
EnergyLevel_MovesFriendly — уровень энергии, получаемый клеткой, когда к ней движется родственник или она движется к нему. Как правило он намного меньше чем уровень энергии обычной еды. Способствует созданию колоний.
EnergyLevel_MovesAggression — показывает сколько энергии отнимает клетка у чужеродных клеток при нападении.
CellsCount_MaxWithOneType — максимальное количество клеток на поле с одинаковым геномом.
CellGenome_Child_Aggression — уровень агрессии у клеток-детей.
CellsCount_MaxAtField — максимальное количество клеток на поле.
EnergyEntropyPerSecond — уровень энергии, который теряет клетка при каждом тике.
Special_FoodCountForTick — количество еды, генерируемое при каждом тике вселенной.
Special_PoisonCountForTick — количество яда, генерируемое при каждом тике вселенной.
CellGenome_HungerRange — диапазон значений голода при генерации клетки.
CellGenome_AggressionRange — диапазон значений агрессии при генерации клетки.
CellGenome_ReproductionRange — диапазон значений репродуктивности при генерации клетки. Чем выше значение, тем меньше энергии нужно клетке для размножения.
CellGenome_FriendlyRange — диапазон значений коллективности при генерации клетки.
CellGenome_PoisonRange — диапазон значений влечения к яду при генерации клетки. Обычно отрицателен.
CellGenome_CorpseRange — диапазон значений влечения к мертвым клеткам при генерации клетки.
Так выглядит этот редактор в веб версии.
А в версии под Windows можно еще и редактировать место, где генерируется еда или яд.
Разработка и результат
В результате нескольких месяцев разработки, я написал 4 версии своей игры. Первые две — для тестирования и отладки логики вселенной симулятора, третья — релизная версия под Windows, четвертая — версия для браузеров. Сейчас я быстро пробегусь по первым двум и уже потом буду рассказывать об особенностях основных версий.
Версия на WindowsForms
Это первая рабочая версия моей программы. В данной версии еще не реализовано большей части игровой логики и она имеет много багов. Рендеринга тут нет, все выводится в текстовое поле в виде символов. Такой вот текстовый вывод работал очень медленно (1–2 тика в секунду), но, все же, есть в нем что-то ламповое.
Версия в текстовой консоли
Как ни странно — вторая версия программы. Ее я писал для лабораторных. В этой и последующих версиях игровая логика идентична.
Версия на WPF
На эту версию я потратил больше всего времени, но она и является наиболее проработанной. Рендеринг фреймов здесь занимает 20–30 мс и не зависит от размеров поля, да и сам тик обрабатывается довольно быстро. Пользователь может создавать огромное игровое поле (хоть 2000×2000 ячеек). Есть возможность просматривать информацию о каждой клетке, просто кликнув на нее.
Демонстрация работы программы.
При написании данной версии своего проекта мне пришлось решить множество проблем. Самые запоминающиеся решения я опишу здесь.
1) Ручной рендеринг. Так как я решил писать велосипед — я делал отрисовку без движка, используя стандартные средства WPF для отрисовки примитивов. Но это позволило мне максимально оптимизировать отрисовку именно под свою программу.
Когда я только начал делать отрисовку — вся канва перерисовывалась с нуля при каждом фрейме, что очень било по производительности. Но потом я написал алгоритм, который хранил прошлый кадр в буфере и при отрисовке нового — закрашивал места, где были объекты, но теперь нет, а на месте, где они появились — рисовал объект. Не знаю насколько быстро это работало бы на движке, но здесь производительность выросла в разы и перестала зависеть от размеров поля.
Отсутствие движка также упростило портирование под браузер, там я использовал тот же алгоритм.
Но в этом способе есть и минусы — часто возникают помехи на изображении, особенно это заметно в WPF версии.
2) Динамический редактор классов. Чтоб не переделывать по сто раз форму, на которой отображались поля редактирования настроек вселенной, я использовал рефлексию и написал динамический редактор, который читал поля передаваемого объекта (в данном случае — объект с настройками) и строил форму для их редактирования.
Вот так выглядел этот редактор в версии WPF.
Веб версия
Через некоторое время после написания WPF версии мне захотелось портировать ее под браузер. Результат вы можете увидеть в шапке статьи, либо, лично перейдя на сайт и попробовав.
Я немного знал Javascript, но мне совсем не хотелось переписывать полторы тысячи строк кода игровой логики на нем. Но выход нашелся — я решил использовать Bridge.NET, открытый компилятор C# в Javascript. Да, дорогой читатель, ты все правильно понял — теперь мы пишем под браузер на C#. Благодаря этому компилятору я смог использовать язык, который хорошо знал. Оставалось только переписать рендеринг и остальной код, связанный с отображением. По причине Javascript лени, веб версия менее функциональна, чем версия под Windows, но служит неплохой демонстрацией работы симулятора.
Справедливо отметить, что мне, все же, очень пригодились знания Javascript и HTML из-за особенностей работы браузеров.
Итоги
При разработке данного проекта я сильно подтянул свои навыки в программировании в целом. На данный момент все версии игры доступны на этом сайте tss-game.cc.ua. Если вы сами хотите приступить к разработке или просто посмотреть код — вот мой гитхаб, тут вы можете найти все версии моей программы с обширными комментариями. Надеюсь, вам было интересно читать о моем опыте, возможно, эта статья вдохновит и вас на что-то подобное, как меня вдохновили другие статьи в свое время.
Комментарии (10)
vlreshet
2 мая 2017 в 17:34
+1↑
↓
Жаль что нельзя вставлять комментарии в комментарии. Сюда вот этот идеально подошёл бы :)2 мая 2017 в 17:51
0↑
↓
Можно картинкой. А вообще — тут статья гораздо более качественная.
Rastishka
2 мая 2017 в 17:56
–1↑
↓
Ох если бы студенты, я почти 1 в 1 такое в школе писал на бейсике, только параметров меньше было.2 мая 2017 в 18:08
0↑
↓
Ахах, так и есть.
2 мая 2017 в 17:41
+4↑
↓
Согласно описанию, перемещение каждого объекта («клетки») зависит от текущего состояния «мира», без учёта перемещения других объектов. Из этого [неявно] следует, то объекты перемещаются по очереди. Если да, то как определяется очерёдность? Если нет, то как решается проблема конфликтов перемещения (когда два или больше объектов перемещаются на одно и то же место)?2 мая 2017 в 18:00
0↑
↓
И ещё: если они действительно перемещаются по очереди, то это не есть двухмерный клеточный автомат и сходство с игрой Конвея чисто внешнее.2 мая 2017 в 18:08
+1↑
↓
Абсолютно верно. Я и не позиционировал свою игру как клеточный автомат. У меня они действительно перемещаются по очереди. Но, ради более справедливой работы, эта очередь постоянно перемешивается в случайном порядке.
2 мая 2017 в 18:23
+2↑
↓
Как-то очень медленно. Не пробовали профайлером тыкать?2 мая 2017 в 18:27
0↑
↓
Не пробовал. Вы про рендеринг?2 мая 2017 в 19:54 (комментарий был изменён)
0↑
↓
В целом. Всё как-то очень печально бегает.
Сравните с поделием конкурирующих студентов (10 мб) на Java, запущенном на унылом Core2 Quad(тут должен быть смайлик, но НЛО заставляет говорить, что мне они надоели:)
