Алгоритм генерации волн врагов в рогалике

в 20:15, , рубрики: Godot, алгоритм, волны, генерация, математическое ожидание, рогалик, формулы

Привет!

Недавно в ранний доступ в Steam вышла наша игра Clayers: Prologue. Это рогалик в глиняном стиле, где нужно подбирать и смешивать цвета, чтобы убивать врагов. В этой статье разберём наш подход к генерации волн с учётом сложности противников.

Немного об игре

Алгоритм генерации волн врагов в рогалике - 1

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

  • Основные цвета: красный, жёлтый, синий (дропаются с врагов).

  • Сложноцветные: оранжевый, фиолетовый, зелёный (не дропаются с врагов).

Убийство одноцветного врага

Убийство одноцветного врага

Оранжевый получается из красного и жёлтого, зелёный — из синего и жёлтого, фиолетовый — из синего и красного. При выстреле смешанной пулей расходуется по 0,5 объёма пули из каждого бака с краской.

Сложноцветный враг

Сложноцветный враг

Алгоритм

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

  1. Задаём предельное количество врагов и общую сложность волны.

  2. Исходя из текущего набора ресурсов (объём красок для выстрелов), рассчитываем сложность убийства каждого противника.

  3. В цикле добавляем разных врагов, пока суммарная сложность пачки не приблизится к целевому значению. Например, сначала жадно выбираем самого лёгкого врага, учитывая цвет и тип, а затем корректируем выбор для разнообразия игрового опыта.

Первый и третий пункты достаточно очевидны, поэтому основное внимание в статье уделим формуле сложности врага.

Формула сложности следующего врага в волне

1. Вероятность попадания нужным цветом

Для начала определим вероятность того, что игрок при выстреле попадёт краской определённого цвета.

 C_{t a r g e t} - text { количество ресурса краски цвета врага }  C_{other} - text { количество ресурса других цветов } p -text {вероятность выстрелить правильным цветом}P_{text {hit}}(color)=begin{cases}0, & C_{t a r g e t}<=0 \ 1, & C_{text {target }} > 0 text { и } C_{text {other }}=0 \ p, &C_{text {target }} > 0 text { и } C_{text {other }}>0, color=enemy.color \  1-p, &C_{text {target }} > 0 text { и } C_{text {other }}>0, color neq enemy.color end{cases}

p можно вычислить как среднее по забегам игроков.

2. Функция урона выстрела

Функция урона зависит от цвета пули и врага. В нашем случае враг получает тройной урон, если цвет пули совпадает с его цветом:

D(color)=begin{cases}3, & color=enemy.color \ 1, & color neq enemy.colorend{cases}

3. Мат. ожидание урона

Можно вычислить математическое ожидание урона для n-го выстрела по каждому цвету, так как мы имеем дело с дискретной случайной величиной.

Eleft[D_nright]=sum_c P_{h i t}(c) cdot D(c)

4. Максимальный возможный урон

Чтобы определить, хватит ли ресурсов для ликвидации врага, необходимо вычислить максимальный возможный урон D_{max}

 C_{max} - text { максимальный объем краски среди цветов } D_{max }=sum_{n=1}^{C_{max }} Eleft[D_nright]

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

5. Вероятность убийства врага

Зная максимальный уронD_{max}и здоровье врага HP врага, вычисляем вероятность гарантированного убийства:

 HP - text {количество здоровья врага } P_{text {kill }}=begin{cases}1, & D_{max } geq H P \ 0, &  D_{max } < H P end{cases}

6. Коэффициент ресурсной сложности врага

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

K_{text {res }}=frac{C_{text {min }}}{C_{text {total }}}

Где C_{total} — общее количество краски у игрока.

7. Итоговая сложность убийства врага

S_{k i l l}=1/K_{text {dodge }} cdot K_{text {res }}^{P_{text {kill }}}

Где K_{dodge} - коэффициент уклонения врага (учитывает возможность его убить без стрельбы, например, для взрывающихся врагов типа Камикадзе).

При этом K_{dodge} >=1, и 0< 1/K_{dodge} <=1

Возвести K_{res} в степень P_{kill} важно, чтоб "заединичить" K_{res}^{P_{kill}}. Если P_{kill}=0, то не хватит ресурсов убить врага.

0<K_{text {res }}^{P_{text {kel }}} leq 1

В итоге предел S_{kill} дает нам верхнюю границу, необходимую для подсчета сложности волны.

Итог

В результате у нас получился простой и стабильный алгоритм, который:

  • Обеспечивает сбалансированную сложность волн.

  • Учитывает ресурсную сложность и вероятность убийства врага.

  • Позволяет варьировать состав врагов для разнообразия геймплея.

Теперь нам не нужно вручную контролировать разнообразие врагов в волнах — можно просто наслаждаться процессом! Надеемся, что статья была интересной. Оцените волны в игре, предлагайте свои идеи по улучшению алгоритма и задавайте вопросы. За крутые идеи и пожелания можем скинуть ключик!

Автор: dlrxxx

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js