Я работаю над поиском путей для игры в RTS, где я создаю навигационную сетку из сетки игры.Самый быстрый алгоритм триангуляции с отверстиями?
Я написал алгоритм, похожий на Marching Squares, который создает и упрощает границы между доступными и неустойчивыми областями карты. Теперь у меня есть «сетка», состоящая только из краев. Мне нужно триангулировать эту сетку, чтобы конечная триангуляция содержала исходные ребра, а затем я могу удалить непригодные области для создания дыр в навигационной сетке. Например, мне нужно это сделать ...
Треугольники представляют проходимую области карты. Отверстия представляют собой неприемлемые области, такие как горы или здания. Сетку можно рассматривать как 2D, так как высота не имеет значения. Это, очевидно, очень упрощенный случай. Навигационная сетка в игре будет состоять из тысяч вершин и множества отверстий, но я могу разбить ее на меньшие куски для динамического обновления.
Я посмотрел на ограниченные алгоритмы триангуляции Делоне, которые сначала создают триангуляцию Delaunay точек, а затем удаляют любые треугольники, которые пересекают ограниченные ребра, а затем повторно триангулируют удаленные треугольники.
Это кажется немного излишним для моих целей. Моя сетка не обязательно должна быть Delaunay, и она полностью состоит из ограниченных краев, поэтому я бы хотел пропустить дополнительные триангуляции, если это возможно. Есть ли лучший алгоритм для этого? Я посмотрел и посмотрел, и мне удалось найти ограниченные алгоритмы Делоне. Или, может быть, я ошибаюсь, и лучший алгоритм Delaunay был бы лучше?
Я уже делал навигацию по поиску путей с нуля, но мне никогда не приходилось создавать навигационную сетку. Алгоритмы триангуляции новы для меня. Любое понимание?
Поскольку у вас нет специальных запросов по треугольникам, более простой подход, например [многоугольная триангуляция] (http://en.wikipedia.org/wiki/Polygon_triangulation), лучше использовать, чем Delaunay. – Ante
Я посмотрел на метод Ушного обрезания, который, кажется, немного медленнее, чем триангуляция Делоне, но потребовал бы, чтобы я сортировал свои вершины в циклах, верно? –
Теперь я понимаю, что у вас только края. В каждом случае вам нужно будет соединять и ориентировать края, найти часть внутри какой-либо другой части (знать, что это отверстие или нет), а затем триангулировать многоугольник с отверстиями. Отверстия можно удалить, добавив 2 одинаковых края из отверстия в границу полигона или другое отверстие. Ушные обрезки - простой метод и с разбиением пространства (дерево BSP, квадратное дерево, ...) оно быстрее, чем O (n^2). – Ante