Кое-что о графах

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

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

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

Предположим, у нас есть три уровня: Москва, Амстердам и Париж. Произвольно проведем направленные связи между ними следующим образом: из Москвы можно попасть в Амстердам, из Амстердама в Москву и Париж, а из Парижа в Амстердам. Упрощенно это можно записать следующим образом:

Moscow: Amsterdam
Amsterdam: Paris, Moscow
Paris: Amsterdam

Это и будет текстовым форматом графа строк-идентификаторов.

Напишем класс направленного графа элементов произвольного типа:

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

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

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

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

В итоге клиентский вызов будет таким:

var str = "Moscow: Amsterdam \n Amsterdam: Moscow, Paris \n Paris: Amsterdam";
var graph = ParsingUtil.ParseStringGraph(str);

Затем можно делать с полученным графом что угодно. Например, в диалоговой системе можно было бы задать формат q_questionId и a_answerId для идентификаторов вопросов и ответов, а сами идентификаторы были бы ключами в одной большой экселевской табличке с переводами для локализаций. Тогда один граф был бы одним диалогом. Если же дополнительно связать идентификаторы с JSON-строками, можно задать какие угодно свойства для них и даже парсить в полиморфный граф при необходимости.

A single golf clap? Or a long standing ovation?

By clapping more or less, you can signal to us which stories really stand out.