Преобразование сетки в график для навигации ⇐ C#

[Anonymous]

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

Всем привет!

Я работаю над многопользовательской игрой, для которой требуется, чтобы сервер мог выполнять поиск пути для объектов, управляемых сервером. Сервер представляет собой простое приложение C#, а клиент использует игровой движок Unity. Использование Unity на сервере не вариант. Кроме того, я хотел бы полностью избегать нативных библиотек.

Я уже исследовал Detour для поиска пути, и хотя у них есть порты C#, я бы предпочел иметь собственную реализацию фактического бита поиска пути; поскольку процесс достаточно прост, и я бы хотел, чтобы он был адаптирован к моим потребностям, чтобы он хорошо сочетался с существующими компонентами на сервере.

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

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

Единственные данные, которые я могу извлечь из API Unity — это индексы вершин и треугольников сгенерированной сетки, поэтому мне нужно будет заново построить свой собственный граф. Моя первая реализация просто создавала узел для каждого треугольника, и если этот треугольник разделял две другие точки с другим треугольником, чтобы создать связь между ними, образуя края моего графа.

Хотя это отлично работает для большинства сеток, этого не хватает, потому что кажется, что Unity выбрасывает сетки, которые могут иметь соединения (ребра) между областями (многоугольниками), даже если они не имеют общих двух вершин. Вот пример наложения Unity созданной навигационной сетки на геометрию моего уровня (Unity объединяет треугольники в выпуклые многоугольники, а мой код — нет, однако проблема все равно существует в любом случае)




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

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

Код: Выделить всё

if (sharedVertexCount == 2)
connectPolygons()
else if (sharedVertexCount == 1)
Vector3[] parallelLine = findParallelLineSharedByBothPolygons()
if (parallelLine != null)
Vector3 otherPoint = getUnsharedPointInLine(parallelLine)
if (isPointInLine(parallelLine, otherPoint))
connectPolygons()

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

В любом случае должно найти более простое решение; однако я не нашел в Интернете ничего, что указывало бы мне в этом направлении... поэтому я спрашиваю вас, ребята, могу ли я что-нибудь сделать, чтобы эффективно превратить сгенерированную навигационную сетку в граф связанных полигонов. Либо помощь с моей реализацией isPointInLine, либо указание мне в направлении более разумного алгоритма будут оценены вне слов.

Подробнее здесь: https://stackoverflow.com/questions/216 ... navigation