Пройди свой путь в ширину: библиотеки для графов из инди-игры TESTAMENT
Рассказываем о библиотеке для создания графов при разработке игр. Также объясняем, зачем нужны графы и как применять их в геймдеве.
888 открытий3К показов
Знаете, почему математики не любят направленные нецикличные графы? Потому что если они совершать ошибку, они не смогут вернуться.
С чего все началось
Графы – это не только математический объект, но и важный инструмент программистов. Они используются в играх, визуализации данных, социальных сетях и других серьезных проектах. Если вы не знаете, как работать с графами, то вы не программист. Конкретно раскладка графа в плоскости – задача не тривиальная. Но что делать, если вы хотите решить эту задачу легковесно и быстро?
Когда я начал работать над своим пет-проектом TESTAMENT, мне нужно было генерировать и отображать произвольные графы. Я хотел, чтобы локации были в виде простых шагов-событий, соединенных между собой. Примерами могут послужить проекты Slay The Spire, Cult of the Lamb, Darkest Dungeon и другие. Исследовав вопрос, я увидел, что существующие библиотеки слишком тяжелые и сложные для моих нужд.
- QuickGraph – развитая библиотека, которая активно используется в промышленных системах. Наверное, самым мастодонт среди всех библиотек, которые я знаю.
- GraphShape – форк и последующая переработка заброшенного GraphSharp. Куча алгоритмов раскладки. И скупая документация, кажется, для галочки.
- Microsoft Automatic Graph Layout – мощное решение от лидера рынка корпоративных решений.
- YWorks – красивое коммерческое решение.
Все эти штуки наверняка могут отобразить граф супер эффективным и академически правильным способом. Но тогда, возможно, код работы с графами станет наибольшей частью кодовой базы моего небольшого проекта. Я понял, что мне нужно простое и легковесное решение для небольших инди-игр, которое будет работать быстро и без лишних сложностей. Так я попробовал сделать набросок своего алгоритма раскладки и, о чудо, вышло быстро и дало неплохой результат. В этой статье я расскажу о моем наборе библиотек, который поможет вам создавать случайные графы и раскладывать их в плоскости с минимальными усилиями.
Какими будут мои графы:
- Графы направленные. По сути – деревья.
- Графы нецикличные.
- Может быть несколько стартовых узлов.
- Предполагается один финишный узел.
- Из одного узла может выходить несколько ребер в разные соседние узлы.
- Один узел может принимать несколько ребер от разных соседних узлов.
- Все узлы одинакового размера.
- Подойдет вариант визуализации, когда граф просто вытянут в линию. Возможно даже, такой вариант наиболее предпочтителен. Чтобы игрок проходил от начала (слева) до конца (направо).
При генерации:
- Всегда должно быть несколько стартовых улов.
- В определенный момент несколько узлов графа должны входить в один узел.
- В определенный момент один узел должен разветвляться на строго определенное количество узлов.
- Нужно полностью контроллировать, какими могут быть следущие узлы.
Минимальные графы
Моя библиотека предоставляет единственный интерфейс для работы с графами IGraph
- AddNode – добавляет узел в граф.
- ConnectNodes – соединяет два узла ребром.
- GetAllNodes – возвращает все узлы графа.
- GetNext – возвращает узлы, соединенные с указанным узлом.
Самая простая и наивная реализация для ориентированных графов – DirectedGraph.
Пример использования. Введем свой тип данных. У меня в игре это, например, граф локаций. Локации можно описать примерно так.
Создадим простой нецикличный граф вроде такого. Игрок должен начать бой. Затем у него есть выбор – легкий или сложный путь. И награда в конце.
Раскладка графа
Алгоритм
Давайте разберемся, как нарисовать этот граф! Я буду работать только с направленным нецикличным графом, чтобы упростить задачу. Итоговый граф будет визуализирован слева направо. Так же – для простоты.
Сначала получаем все корневые узлы и группируем их в нулевой уровень. Затем рекурсивно повторяем этот процесс для соседних узлов, выполняя обход графа в ширину.
BFS (Breadth First Search) – выполняет обход поуровнево: сначала проходит по всем ближайшим от начальной точки вершинам, потом спускается глубже
Получается массив массивов.
Далее нам нужно выдать координаты каждому узлу. Для получения x-координаты просто перемножаем уровень на ширину узла. Для получения y-координаты нам нужно индекс узла умножить на высоту узла. А так же нужно выровнять узел по центру по высоте.
Для этого считаем отступ, который добавляем к y-координате. Отступ считается, как половина разницы между высотой графа и суммарной высотой всех узлов в уровне. А высота графа – это суммарная высота уровеня с самым большим количеством узлов.
Но тут есть нюанс. По контракту, граф не гарантирует порядок соседних узлов в методе GetNext()
.
Для того, чтобы “сгладить” эту проблему, выполним следующую доработку:
- Назначаем вес корневым узлам. Вес назначается по порядку.
- Для каждого соседнего узла считаем вес, как среднее всех весов узлов, которые входят.
- Упорядочиваем узлы по весу в рамках одного уровня.
- Рекурсивно повторяем для всех уровней.
Весь алгоритм в UML:
Реализация
Библиотека содержит реализацию этого алгоритма. Разберем, как раскатать этот граф в плоскости.
Визуализатор возвращает набор объектов типа IGraphNodeLayout<TNodePayload>
с данным для отображения каждого узла.
- Node – ссылка на исходный узел графа.
- Position – это целочисленные координаты (X, Y), где нужно отрисовать узел.
- Size – это размер узла. Сейчас значения для всех узлов будут одинаковыми.
Пример конфига для визуализатора:
Графы в линию – это конечно решение, но не для крутой игры. Поэтому были добавлены пост-процессоры раскладки графов, чтобы добавить некоторый хаос в граф.
- RetryTransformLayoutPostProcessor – Выполняет произвольную трансформацию узла графа и валидирует изменения. Если изменения не валидны, то повторяет трансформацию. Идея в том, чтобы случайно подвигать узлы графа. Но если узел после перемещения начинает пересекать другие узлы, то попробовать выбрать другую случайную позицию.
- RepeatPostProcessor – Повторяет указанный набор постпроцессоров указанное число раз. Идея в том, чтобы если нам не удалось выбрать подходящую позицию для первых узлов (которые ближе у корню), то мы попробуем еще раз.
- PushHorizontallyPostProcessor – Расталкивает все узлы по горизонтали на указанное значение. Этот процессор нужен, чтобы заранее дать простор для случайных перемещений по горизонтали. Таким образом, по горизонтали будет разное расстояние между узлами.
- RotatePostProcessor – Поворачивает граф на указанный угол в радианах вокруг начала координат. В начале координат будет самый первый корень. В моей игре я поворачиваю на случайный угол от 0 до Pi. По соображениям Ui/UX. Чтобы для игрока движение по графу все еще было слева-направо сверху-вниз.
Вот как это используется у меня:
Собственно, главная сцена. Исказим стройный граф!
Генерация графов
Генерация графов – это настоящее творчество. Чтобы локации были интереснее, мне нужно создать уникальные и интересные графы. Чтобы игроку каждый раз было интересно планировать новый маршрут. Но чтобы было больше контроля над локацией, нужно использовать какие-то шаблонные решения. Развивая эту идею, можно создать шаблон основных путей графа. По сути, это будет тоже направленный граф, только более высокого порядка. Алгоритм работы прост: мы обходим граф путей, материализуем шаблоны в конкретные узлы и соединяем начальные и конечные узлы ребрами. Поехали!
Реализация
Для генерации используется эта библиотека.
Все начинается с создания путей. Чтобы создать путь, нужно создать экземпляр GraphWay
. Путь – это набор шаблонов, которые являются реализаций интерфейса IGraphTemplate
.
Пример:
Далее формируем граф путей
И, наконец, создаем граф по шаблону.
Далее worldGraph
можно визуализировать так, как я рассказал в статье выше.
Резюме
Я знаю, что код не идеален. Сейчас он решает очень узкую задачу. Но этот код используется в игре TESTAMENT. Для работы с локациями (о чем была статья), для дерева навыков и рецептов крафта. А если потребуется более серьезная работа с графами, лучше использовать один из инструментов выше.
Тем не менее, я бы хотел получить обратную связь, разумную критику и предложения по улучшению. Я надеюсь, мои библиотеки помогут другим независимым разработчикам в их небольших проектах. Я готов помочь и дать советы по использованию библиотек. А если вы хотите что-то доработать – я буду только рад и тоже готов помочь разобраться! Так что давайте сделаем этот код круче вместе!
888 открытий3К показов