Боковое примечание: я не уверен, что этот вопрос относится к сайту обмена стеками разработки игр, но я чувствую, что он принадлежит здесь, поскольку, хотя контекст представляет собой игру, сам алгоритм, который я пытаюсь реализовать, довольно независим от приложения. Кроме того, я не ищу технику высокого уровня, так как чувствую, что уже установил ее, а вместо этого ищу более конкретную помощь в решении определенной проблемы. Так или иначе, на вопрос:
Всем привет!
Я работаю над многопользовательской игрой, которая требует, чтобы сервер мог выполнять поиск пути для объектов, контролируемых сервером. Сервер представляет собой прямое приложение 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, либо указание мне в направлении более разумного алгоритма будут оценены без слов.
