Как я могу создать навигационную сетку для мозаичной сетки?

18

На самом деле я еще не начал программировать для этого, но я хотел посмотреть, как бы я поступил так или иначе.

Скажем, у меня есть сетка плиток, все одного размера, некоторые из них можно перемещать, а некоторые нет. Как мне создать навигационную сетку из полигонов из этой сетки?

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

Росс Хейс
источник
2
Технически сетка в значительной степени эквивалентна навигационной сетке. Я подозреваю, что вы на самом деле спрашиваете способ оптимизировать сетку и объединить смежные квадраты.
Kylotan
@Kylotan Да, это именно то, что я имел в виду, просто способ объединить смежные полигоны.
Росс Хейс

Ответы:

28

Вот один из методов, которые я придумал, когда делал navmesh для игры RTS. Обратите внимание, что это доморощенный, сторонние инструменты не использовались, мне потребовалось около 3 недель, чтобы внедрить и исправить ошибку:

  1. Используйте алгоритм Марширующих квадратов , чтобы преобразовать плитки препятствий в контуры . Обратите внимание, что края карты тоже являются контуром, и их также необходимо включить.
  2. Уменьшите количество точек на контурах, используя алгоритм Дугласа-Пекера (фиолетовые линии на нижнем рисунке)
  3. Кормить все точки в Делоне триангуляцию (чтобы получить наиболее однородные треугольники)
  4. Добавьте дополнительные точки в пустые области и вдоль краев карты (чтобы получить более равномерную навигацию)
  5. Проверьте вдоль контуров препятствий и переверните полигоны, произведенные Делоне, чтобы соответствовать контурам. - Часто Делоне может размещать треугольники (серые), не соответствующие вашим контурам (красные), тогда вам нужно их обнаружить и перевернуть. Соединяя их обратно в многоугольник, разделите их вдоль контуров и сделайте триангуляцию вручную введите описание изображения здесь
  6. Обрезать внутренние препятствия - удалите полигоны, которые находятся внутри препятствий (розовые на картинке выше)
  7. Заполните данные о соединении между оставшимися треугольниками и вершинами, как вам нужно - это ваша навигационная сеть.

Результат:

тайлмап навмеш

Кромстер говорит, что поддерживает Монику
источник
1

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

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

wolfdawn
источник
1
Это не то, как обычно реализуются навигационные сетки. Цель навигационной сетки (и, я полагаю, причина, по которой спрашивающий даже задал здесь свой вопрос) состоит в том, чтобы оптимизировать граф до минимально необходимого количества полигонов (обычно треугольников), которые охватывают наиболее полезные пробелы, чтобы уменьшить количество как шаги, необходимые для поиска правильного пути, и объем памяти, необходимый для определения сетки. Необработанная реализация потребляет на тонну больше памяти и тратит драгоценное время на обработку ИИ.
Гургадурген
Ты прав. Конечно, децимация (сокращение полигонов) является разумной и желательной оптимизацией. Просто когда вы читаете вопрос опера, вы чувствуете, что он просто хочет превратить сетку в график.
волчий рассвет