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

Необязательный контекст

В процессе работы над второй частью своей MMOZPG я пришёл к выводу, что стоит снабдить игру большим... нет, БОЛЬШИМ количеством скиллов. Жанр ZPG предполагает автокаст, так что скиллы не обязаны быть радикально разными, как в полноценной RPG, достаточно разделить их на категории по типу скилла, раскидать расход маны, эффективность и уровень, а затем навесить на них разные названия и картинки. Полученные таким образом скиллы полностью соответствуют требованиям жанра и при этом весьма разнообразны. Суммарно на первое время я ограничился 450 скиллами(по 50 на каждый из 9 классов), но встал вопрос выдачи разнообразия между разными доменами(школами) магии. Персонажи разных доменов, но одного класса должны иметь немного разную схему прогрессии, то есть саму форму дерева, а также немного разное содержание этого дерево. С этим вводными я и приступил к задаче.

Первичная выборка

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

  1. Создаётся пустой список скиллов класса;
  2. Из общего списка класса достаётся случайный невзятый скилл;
  3. Если скиллов этого типа и уровня менее трёх, добавляем его в список;
  4. Возвращаемся в пункт 2 до тех пор, пока хотя бы в каждой паре тип/уровень не будет хотя бы одного скилла. В случае, если это невозможно (например, скилл призыва есть только один на весь класс и тот на четвёртом уровне), повторяем до тех пор, пока не будет по одному скиллу каждого уровня и по одному каждого типа (уровень и тип теперь раздельный критерий);
  5. Выборка готова.

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

Формирование древа

Взяв список скиллов с предыдущего этапа мы достаём оттуда скилл нулевого уровня. Он гарантированно там есть, он открыт по-умолчанию и он является корнем всего дерева.
Далее мы формируем правила наследования. Какой скилл в принципе может быть дочерним от какого (без жёсткой привязки, так как по результатам первичной выборки у нас может не быть обязательного родителя). Правила следующие:

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

  1. Скиллы сортируются по уровню, от младшего к старшему;
  2. В древе размещается скилл нулевого уровня;
  3. Берётся самый младший по уровню скилл;
  4. Проверяются типы его возможных родителей. Если любой тип присутствует в древе, родителем становится самый старший скилл этого типа.
  5. Если родительские типы не представлены в дереве, родителем становится любой скилл, подходящий по уровню, даже если он не подходит по типу.
  6. Если в массиве "самых старших" по собственному типу скилла уровень ниже, записать в него текущий скилл;
  7. Возвращаться к пункту 3 до истощения массива;
  8. Древо построено.

Визуализация дерева

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

  1. Узлы(скиллы) делятся по слоям в зависимости от уровня наследования;
  2. Слои проходятся по возрастанию;
  3. Узлы в пределах слоя расставляются по вертикали в зависимости от глубины слоя и количества детей узла (чем больше детей тем дальше от центра слоя);
  4. Дочерние узлы расставляются относительно центра родительского узла.
  5. От каждого дочернего узла бросаются три линии - по горизонтали от узла до середины расстояния между ним и родителем, по вертикали от этой точки до горизонтали родителя, по горизонтали от этой точки до родителя.
  6. Линии и узлы красятся в цвет домена, к которому относится персонаж.

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

Результат

Ниже представлены конечные деревья навыков для следопыта Тьмы и следопыта Света. С вышеупомянутыми наложениями :)

Следопыт Тьмы


Следопыт Света

Послесловие

Благодарю за прочтение. Открыт для обсуждения и критики.