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

9

Итак, я понял, как использовать A * для поиска пути, и я могу использовать его в сетке. Тем не менее, мой игровой мир огромен, и у меня есть много врагов, движущихся к игроку, который является движущейся целью, поэтому система сетки слишком медленная для поиска пути. Мне нужно упростить мой график узлов с помощью навигационной сетки.

Я понимаю концепцию «как» работает сетка (нахождение пути через узлы на вершинах и / или центрах ребер многоугольников).

Моя игра использует динамические препятствия, которые процедурно генерируются во время выполнения.

Я не могу понять, как взять самолет с несколькими препятствиями и программно разделить зону прохождения до полигонов для сетки навигации, как показано на следующем рисунке.

навигационная сетка

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

Я использую JavaScript в nodejs, если это имеет значение.

Стивен
источник
1
Динамическое разбиение, которое вы пытаетесь реализовать, будет зависеть от специфики элементов вашей карты. Ваши элементы препятствий полностью состоят из выровненных по сетке прямоугольников, как показано в вашем примере? Повернутые прямоугольники? Нерегулярные полигоны? Или не многоугольники с множеством кривых? Есть ли у вас точечные / полные данные для формы препятствий? Если да, это данные формы в виде треугольников, прямоугольников, исключительно выпуклых многоугольников или сочетания выпуклых и вогнутых многоугольников?
Мэтью Р
@ Matthew Мой мир состоит из преград выпуклого многоугольника, без кривых и без вогнутых многоугольников. Каждое препятствие сохраняется как объект многоугольника с вершинами, представленными векторными объектами.
Стивен
1
Для чего это стоит, я работаю над решением, основанным на этом документе: gradworks.umi.com/3493710.pdf Если я добьюсь успеха, я опубликую свое решение.
Стивен
1
сетка навигации на 100% не говорит вам, можете ли вы куда-то идти или нет, это просто базовая схема проходимых областей, вам все равно нужно проверять столкновения с динамическими объектами, редактировать: почти то, что сказал Рэй
dreta
@Stephen - см. Длинный комментарий .
Мэтью R

Ответы:

3

@Stephen - Длинный комментарий - Эта статья выглядит так, как будто ее стоит прочитать, когда у меня есть время. По сути, я бы предложил нечто вроде алгоритма Хертеля-Мелхорна, который упоминается в статье (ссылку на этот конкретный алгоритм можно найти здесь http://www.bringyou.to/compgeom/ ) с добавлением подразделить стороны карты (внешнюю границу игровой зоны) на некоторое количество времени, чтобы уменьшить появление множества маленьких треугольников, образованных в углах. Эти маленькие треугольники могут быть проблематичными, так как они могут оказаться меньше, чем то, для чего вы выполняете поиск пути. Hertel-Mehlhorn предназначен для сокращения полигонов, образованных треугольным разбиением, если вам интересно больше о триангуляции:http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/PolyPart/polyPartition.htm .

Кроме того, если вы не хотите изобретать велосипед, я думаю, что эта библиотека действительно сделает все, что вам нужно: http://code.google.com/p/polypartition/ . Он преобразует триангуляции и сокращения с помощью одного из нескольких вариантов, включая Hertel-Mehlhorn. Это лицензия MIT, что означает, что ее можно использовать для закрытых и коммерческих проектов, если это является проблемой.

Если вы решите продолжить работу над своей собственной реализацией, я хотел бы увидеть, что вы придумали.

Мэтью Р
источник
1
Отличный ответ, @ Мэтью. И вам обязательно стоит прочитать эту статью! За ним легко следовать, и он объясняет замечательную технику (особенно Приложение A, в котором говорится об обнаружении / генерации меша на основе агентов). Я кодирую версию этого алгоритма для JavaScript, и он идет хорошо. Я опубликую это как ответ, когда это будет сделано.
Стивен
@Stephen хотел бы увидеть эту работу
kevzettler
@Stephen Я тоже ищу версию javascript
Аполо,
6

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

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

Иерархический подход даст на несколько порядков лучшую производительность, в то время как сетка в лучшем случае даст вам небольшое линейное улучшение.

Наивный подход состоит в том, чтобы просто разделить ваш мир на X на более крупные фрагменты, выровненные по сетке, сгенерировать информацию о соединении между ними (например, существует ли путь между порциями 2x1 от 3x1 до 2x2 и каково расстояние среднего пути) ,

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

Шон Миддледич
источник
1
Я должен объяснить далее: моя игра не выровнена по сетке. Я строил сетку в области 800 x 600 пикселей, каждый пиксель составлял один пробел в сетке (я все еще вычислял A *, поэтому я пока не думал о производительности этого). У меня есть препятствия, которые не так просты, как на рисунке выше, я просто пытался проиллюстрировать проблему. Очевидно, что такое игровое поле нужно было пересмотреть, и после некоторого исследования я думаю, что навигационная сетка была бы верным путем.
Стивен
3

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

Обход препятствий может быть решен с помощью поведения руля (используйте обход препятствий). Если при случайном отклонении ваше препятствие настолько велико, что оно заполняет или полностью блокирует движение от одного nav-poly к следующему, то можно каким-то образом проверить этот крайний случай и пересчитать путь между полиом, в котором вы находитесь в данный момент, и тот, от которого ты заблокирован.

Рэй Дей
источник