Сегодня написал генерацию локации по планарному графу. Это первый шаг к автоматической генерации локаций. Поясню.

Планарный граф — это граф, который может быть нарисован на плоскости без пересечений рёбер. Я определяю базовые локации (вэйпоинты), как окружности с центрами в вершинах графа. Рёбра графа определяют пути, по которым можно перемещаться от одного вэйпоинта до другого. Такой граф описывает структуру локации. После того, как граф задан, нужно определить контуры стенок локации. Для этого вначале ищутся контуры графа (в математике они называются гранями, но я уже привык к контурам).

Что такое контур графа? Любой планарный граф разделяет плоскость на несколько областей, ограниченных его рёбрами. Одна из областей — внешняя, бесконечная, её мы тоже учитываем. Если представить, что каждое ребро графа — это пара направленных отрезков, смотрящих в противоположные стороны, то каждую из областей можно ограничить контуром из направленных отрезков — таким, что эта область лежит, например, справа от каждого из них. Причём таким способом будут перечислены все направленные отрезки графа.

Кстати, для связного планарного графа верна любопытная формула Эйлера: число вершин — число рёбер + число граней (контуров) = 2. Ещё один интересный факт о плоских графах — теорема о четырёх цветах: грани графа можно раскрасить четырьмя цветами так, что соседние грани не будут иметь один и тот же цвет (соседние — имеющие общее ребро). Но это так, лирическое отступление в красоту теории. :)

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