Я работаю над поиском пути для игры в жанре RTS, где я строю навигационную сетку из игровой сетки.
Я написал алгоритм, похожий на Marching Squares, который создает и упрощает границы между пешеходными и недоступными областями карты. Теперь у меня есть «сетка», состоящая только из ребер. Мне нужно триангулировать эту сетку, чтобы окончательная триангуляция содержала начальные края, а затем я могу удалить непроходимые области, чтобы создать дыры в навигационной сетке. Например, мне нужно сделать это ...
Треугольники обозначают области на карте, по которым можно ходить. Дыры представляют собой непроходимые области, такие как горы или здания. Сетку можно рассматривать как 2D, так как высота значения не имеет. Очевидно, это очень упрощенный случай. Сетка навигации в игре будет состоять из тысяч вершин и множества дыр, но я могу разбить ее на более мелкие части для динамического обновления.
Я рассмотрел алгоритмы ограниченной триангуляции Делоне, которые сначала создают триангуляцию Делоне точек, а затем удаляют все треугольники, которые пересекают ограниченные ребра, а затем повторно триангулируют удаленные треугольники.
Для моих целей это кажется немного избыточным. Моя сетка не обязательно должна быть Делоне, и она полностью состоит из ограниченных краев, поэтому я бы хотел по возможности пропустить дополнительные триангуляции. Есть ли лучший алгоритм для этого? Я искал и искал, и смог найти только ограниченные алгоритмы Делоне. Или, может быть, я ошибаюсь, и лучше всего подойдет алгоритм Делоне с ограничениями?
Раньше я выполнял поиск пути навигационной сетки с нуля, но мне никогда не приходилось создавать навигационную сетку самостоятельно. Алгоритмы триангуляции для меня в новинку. Любое понимание?
