ПрограммированиеСтатьиОбщее

Генетические алгоритмы в разработке игр.

Автор:

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

EVOLV | Генетические алгоритмы в разработке игр.

Уровень подготовки:
Если за плечами уже есть змейка и тетрис - читаем смело. Если нет, ничего страшного, расширяем кругозор.
Также желательны базовые знание LUA для понимания кода.

Итак поехали!

Теоретическая часть.

Наверняка многие уже не раз слышали про генетические алгоритмы и с чем их едят.
Что далеко ходить, у нас даже есть небольшая статья в разделе термины Генетический алгоритм.

Но сегодня разговор не о теоретической, а практической стороне вопроса, как все это безобразие можно пустить в дело.

Для начала попробую простыми словами рассказать, что же из себя представляет этот хитрый алгоритм.

Если максимально упрощенно генетический алгоритм - ничто иное, как подбор коэффициентов для решения уравнения.
Вся соль кроется в способе подбора этих параметров, тут то мы и вспоминаем про название алгоритма.
Представим искомые коэффициенты как гены и вспомним, как работает эволюция.
Еще в далекие времена Дарвин говорил про естественный отбор, что всегда выживает самый приспособленный. Вот так же и у нас.

алгоритм до неприличия прост:
1-создаем новое поколение популяции
2-отбираем самых приспособленных, остальных удаляем
3-из оставшихся выводим(селекционируем) новое поколение и снова пункт 2
И все это происходит до тех пор, поке не будет найдено решение задачи.

Простой пример: уравнение X + Y = 100, здесь X и Y можно представить как гены.

Создаем 4 особи со случайным набором ген:
( X = 2, Y = 2 )
( X = 20, Y = 2 )
( X = 30, Y = 50 )
( X = 22, Y = 44 )

Проверяем приспособленность, для этого считаем насколько переменные приближают нас к решению уравнения:
| 2 + 2 | / 100 =  0.04
| 20 + 2 | / 100 =  0.22
| 30 + 50 | / 100 =  0.8
| 22 + 44 | / 100 =  0.66

На основе лучшей пары создаем следующее поколение, также добавляем в него и лучших особей из предыдущего.
У нас крайне простой случай, у каждой особи всего по 2 гена.
Скрещиваем ( X1, Y1 ) и ( X2, Y2 ) и получаем в итоге ( X1, Y2 ) и ( X2, Y1 )

новое поколение:
( X = 30, Y = 50 )    родитель 1
( X = 22, Y = 44 )    родитель 2
( X = 30, Y = 44)    потомок 1
( X = 22, Y = 50)    потомок 2

И казалось бы, вот уже мы скачем верхом на эволюционном процессе и все задачи нам по плечу, но не все так просто.
На данном примере видно, что уже через 1 итерацию - новых генов взять неоткуда, а из старых уже найдена лучшая комбинация.
Решения достигнуто не было, и система работает без изменений.
Тут то нам на помощь приходят мутации, они не такие красивые как скажем в сталкере, но зато очень даже эффективные.

Суть мутации проста: добавить новых генов при формировании следующей популяции.
Будь это совершенно новая особь или изменение случайных генов потомка, уже детали реализации.   

Но, как говорится и это еще не все! При большом количестве генов система порой приходит к равновесию, так и не найдя решения.
И даже мутации из за малого удельного веса не спасают ситуацию.

В качестве аналогии можно привести новичка, пришедшего в большую компанию.
У него горят глаза, полно энергии, идей, инновационные технологии.
Он кричит: “Я знаю как правильно, как нам улучшить компанию, достигнуть успеха, даже есть опыт”
А с другой стороны - бывалые дяди, которые всю жизнь тут трудятся и знают, как делать дела.
У них связи, авторитет, они сидят на откатах и не хотят ничего менять.
И они ему говорят: “Ты кто такой ваще, ты нам мать что ли, че учить то нас вздумал, уйди,
не мешай работать” А дальше система либо его ломает, либо он уходит.

И чтобы эволюция не буксовала на месте - нужны встряски. Как с динозаврами например.
Как только происходит застой ( появился стабильный генотип ), всей системе нужна встряска.
Удаление большей части популяции или даже полностью всей и создание недостающих особей со случайным набором генов.

Опять же аналогия с компанией.
Большие компании поделили рынок поровну и всем достается понемногу, рынок не развивается.
И тут приходят стартапы, состоящие из тех самых молодчиков с горящими глазами.
Конечно только один из ста в итоге останется на плаву, а остальные потонут, но тот кто сможет - сорвет куш.

Итак ребятишки, давайте подведем итог, что же сегодня мы узнали.
Для работы генетического алгоритма нужны следующие вещи:
-описать решение задачи набором параметров( генов ) назовем это описание особью.
-определить критерии успешности особи( мера правильности решения задачи )
-провести эволюционный отбор при помощи 3х методов: скрещивание, мутация и встряска.

Практическая часть.

Формулы и циферки эт конечно хорошо, но как говорится ближе к телу.
Есть задача, с которой часто встречаются, как разработчики, так и игроки, а именно расчет билда.

Для простоты примем, что игра пошаговая.
Есть монстр, у него нет хп и мы будем измерять максимально урон, который герой может нанести пока не погибнет.
Каждые 3 хода монстр атакует игрока, с 20% шансом крита.

Есть игрок со следующими параметрами: шкалы здоровья и силы, реген здоровья и силы, атака и защита.
Также у игрока есть экипировка, которая влияет на параметры.

В качестве генов здесь будет выступать экипировка, что и в каком слоте находится у героя.

руки:
меч1( атака 5, требует силы 5 )
меч2( атака 4, требует силы 3 )
меч3( атака 8, требует силы 10 )
щит1( защита 3, требует силы 2  )
щит2( защита 5, требует силы 3  )

туловище:
доспех1( защита 5, атака -2 )
доспех2( защита 3, атака 0 )
доспех3( защита 1, реген здоровья 1 )

голова:
шлем( защита 2 )
шапка силы( реген силы 1 )
шапка здоровья( реген здоровья 1 )

макс здоровье 500
макс сила 100
реген здоровья 0
реген силы 5
атака 1
защита 1

Монстр атакует за раз на 25 единиц, во время крита на 45, шанс крита 20%.
Игрок атакует каждый ход, когда хватает силы.

Кодить все это дело будем на луа. Почему, да это быстро и весело :)

Для начала пропишем параметры персонажа, монстра и экипировки.

+ Входные данные

Теперь когда с входными данными закончено - идем дальше.
Первым делом нам нужно сгенерировать особь( то есть создать случайный билд )

Для этого напишем небольшую функцию:

+ CreateRandomBuild()

Копируем параметры заданные по умолчанию в  новый билд)
Дальше устанавливаем в слоты  экипировку.
Здесь вместо готовой таблицы устанавливаем ссылку на исходную таблицу и генерируем в ее пределах случайный индекс.
Это нам понадобится для селекции.
Перед тем как вернуть созданный билд, добавляем параметры из экипировки в параметры самого билда.
Это делается небольшой функцией:

+ SetEquipmentToBuild( Build )

Теперь нужен способ скрещивания особей, так как гены у нас, это просто индексы массива,
то скрещивание будет представлять из себя случайный выбор гена у одной из особей родителей.
Ну и чтоб ускорить эволюцию немного, одна из особей( доминантная ) будет иметь больший шанс( 6 из 10 ) передать свои гены.

+ CrossingBuils( Build1, Build2 )

Также во избежание вырождения популяции добавим шанс мутации ( 2 из 10 )
В нашем случае мутация - случайное изменение одного из генов( слота экипировки )
Добавляем параметры экипировки к билду и готово!

Еще нам понадобится функция оценки жизнеспособности билда, пишем:

+ TestBattle( Build )

Оценивать будем по максимальному нанесенному урону, также не лишним будет знать - сколько на это потребовалось шагов.

На каждом шаге мы делаем следующие вещи:
-Если достаточно энергии - атакуем.
-Если ход кратный трем, получаем урон от монстра( с 20% шансом крита ).
-Проводим регенерацию здоровья и энергии.
-Проверяем, вдруг билд получился круче монстра, ограничивая все это дело 10000 итераций.

В итоге  возвращаем нанесенный урон и продолжительность битвы.

Итак все приготовления сделаны и пришло время окунуться в увлекательный мир генетических алгоритмов. Вы готовы дети!?

А вот и сам генетический алгоритм, подгреб к нашему празднику невежества и знаний:

+ GenTest()

Создаем таблицу и заполняем случайными билдами. Размер популяции был выбран в 16 особей.
Далее вся популяция проходит проверку боем и сортируется по нанесенному урону.

Переходим к селекции. Гены лучшей половины популяции переходят в следующее поколение.
После чего начинаем скрещивать успешную половину с теми, кто отбор так и не прошел, в этот же момент может происходить мутация.

В итоге мы получаем количество особей, что было в начале. И опять бой, селекция, бой…
Казалось бы все этом может длиться вечно, но на небольшом количестве генов лучшая комбинация находится довольно быстро,
поэтому у нас стоит ограничение в 50 циклов. После чего можно подводить итоги.

Для запуска всего этого мракобесия осталось только взвести рандомизатор по текущему времени и запустить симуляцию.

math.randomseed( os.time() ) 
GenTest()

Сохраняем , запускаем, затаив дыхание ждем результата.

И вуаля! Видим, что самый хороший билд это: два вторых меча, доспех номер 3 и шапка жизни :)

Запустив симуляцию еще несколько раз подряд - видно что, этот билд является стабильным, но все же иногда есть небольшие отклонения.
Это получается за счет небольшого количества поколений и рандома связанного с критическими атаками монстра.
При увеличении количества поколений до 500 - билд получается всегда один и тот же.
Поэтому для балансировки важно правильно подобрать количество итераций.

Вот сводный график 3х запусков моделирования. Зависимость нанесенного урона от поколения особей.
EVOLV_gr | Генетические алгоритмы в разработке игр.
Высокий старт всех случаев обусловлен тем, что это результаты лучшей особи первого поколения.
Основная часть эволюции происходит в течении первых 20 циклов, после уже видна стабилизация.

Снизив количество поколений до 10, можно увидеть и другие жизнеспособные варианты.
Что интересно, в них ни разу не было щитов, а значит они нуждаются в ребалансе.
Та же при помощи этого алгоритма можно определить среднее время жизни монстра,
а если немного переделать, то появится возможность сталкивать билды друг с другом.

Выводы.
Подводя итог, у нас получилось за небольшое время сделать довольно гибкий инструмент для балансировки игры,
который поможет проверить, работают ли все как задумано, или есть места которые стоит поправить.

Правда в примере не был использован механизм встряски, из за малого количества генов, его эффект был бы просто незаметен.
Надеюсь  еще расскажу вам об этом, но это уже будет совсем другая история.

А пока всего хорошего и спасибо за рыбу :)

20 марта 2018 (Обновление: 31 дек 2018)

Комментарии [63]