Article

Article

disabolic

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


Первоначальная цель состояла в том, чтобы избавиться от необходимости ручного создания и редактирования карт, которые существовали в виде html страниц, содержащие в себе названия комнат и связи между ними в текстовом формате. Если взглянуть на это более глобально, то становится очевидно, что поддержка карт в актуальном состоянии в соответствии с их оригиналами (xml файлы с информацией о конкретной зоне) не является возможным, не говоря уже об отображении карт с учетом динамических изменений во время игры.


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


Еще раз прочитав название документа, можно заметить, что речь идет про ориентированные графы. Граф (дискретная математика) - это совокупность объектов и связей между ними. Объекты рассматриваются как вершины или узлы графа, а связи - как ребра. В свою очередь ориентированный граф - это граф, ребрам которого присвоено направление. Именно ориентированным графом и является карта в мире Dreamland. Если говорить о конкретном представлении, то в роли вершин выступают комнаты со своим уникальным номером, а в роли ребер - переходы (выходы) из одной комнаты в другую.


Но чтобы было возможным отрисовать на экране карту, которая бы выглядела структурно правильно, необходимо просчитать для каждой из комнат координаты в 3х-мерной системе координат. Связи между комнатами имеют направление (север, юг, восток, запад, вверх, вниз). Каждое из этих направлений указывает на пространственное смещение одной комнаты относительно другой в 3х-мерном пространстве в рамках лишь одной из координатных осей. Например, если из комнаты 1 подняться вверх в комнату 2, при смещении Δz по оси z, координата z(2) для второй комнаты будет высчитываться следующим образом: z(2) = z(1) + Δz. 


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


|Алгоритм обхода графа для карт Dreamland'a|


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


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


P.S. Пруфов пока нет, но всему свое время.

Report Page