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

11

Я пытаюсь найти решение этой проблемы. Я пытаюсь построить навигационную сетку в формате сетки вершин, привязанных к координатам x, y, расположенным в виде квадратов для трехмерного пространства. Но у меня возникают проблемы, пытаясь найти способ сделать это.

Я попытался заглянуть в библиотеку Recast. Это довольно надежный метод, но он явно замедляется с большими картами и открытым пространством. Я также не знаю, как они генерируют вершины и ребра для мирового пространства с помощью карты высот.

Моей следующей мыслью было сделать то, что делал Unreal Engine 3.

https://udn.epicgames.com/Three/NavigationMeshReference.html

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

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

Мои основные проблемы ... это не кажется оптимальным. Не думая об этом, при оценке процесс O (N ^ 3) для многослойного уровня. Который может стать довольно противным.

И последний бит для автоматического создания прямоугольных групп этих квадратов. Я не совсем уверен, как это сделать. Реализация Unreal разделяет их по склонам. Тем не менее, я пытаюсь сохранить формат сетки. Так что это не совсем необходимо. Проблема все еще остается при создании больших прямоугольных плиток, чтобы разделить процесс поиска пути на основе плитки. Плитка не может быть ни слишком большой, ни слишком маленькой.

Итак, вопросы ...

Каким был бы эффективный способ создать эту опоясанную навигационную сеть? И какой будет хороший способ создания плиток?

moonshineTheleocat
источник
Когда вы ожидаете создать сетку? Время компиляции, время загрузки или в реальном времени? Мы боролись с этой же проблемой и в итоге решили, что для нашего сценария это избыточно (генерация времени загрузки в нисходящем шутере без перекрывающихся путей), мы решили использовать подход, основанный на четырех деревьях. Это сработало достаточно хорошо для нас. Поэтому я думаю, что я спрашиваю, действительно ли это вам нужно, или какое самое простое решение, которое соответствует вашим начальным требованиям, потому что это может занять много времени. Если вам удастся найти хорошее решение, я бы хотел услышать, как вы его исправили.
Нильс
@Niels Я планирую предварительно построить, а затем загрузить его в игру.
moonshineTheleocat
Тогда потребление времени не должно быть слишком большим первоначальным недостатком, так как игрок не будет ждать этого. Вы всегда можете оптимизировать после того, как у вас что-то получится.
Нильс
Насколько велик ваш уровень? Мы использовали recast в больших играх, и у нас не было проблем - вам просто нужно настроить значения времени и т. Д.
Стивен,
Я думаю, что вам не хватает "решетки" бит. Что не совсем то же самое, что и плитки, которые использует reast. Я пытаюсь понять, как переназначить reast, чтобы сделать такую ​​вещь. Но это был в основном кошмар.
СамогонТелеокат

Ответы:

1

Основной трехмерный мир может быть представлен навигационной сеткой, которая может быть удобно встроена в большинство игровых движков. Актер может путешествовать по краям многоугольников.

Это было бы простым решением. Есть много алгоритмов для поиска пути и генерации навигационной сетки.

Я хотел бы поделиться тем, что я прочитал некоторое время назад.

Example01

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

Example02

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

Что касается вопроса, я бы порекомендовал вам проверить ответ Кромстера в списке алгоритмов генерации navmesh.

Также ознакомьтесь с AI Systems of Left 4 Dead, частью которого являются примеры. Еще много интересных тем

Удачи.

suvam0451
источник
0

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

Джо Шмоэ
источник
Хорошая идея, но не жизнеспособная для конечных целей. Мне нужно поддерживать большой мир и позволять ИИ перемещаться с одной стороны континента на другую. Это много выполнимо, но мне нужно иметь фиксированную навигационную сетку, чтобы генерировать более высокие узлы.
СамогонТелеокат
0

Это проблема, которую я видел везде. Хитрость заключается в «разделении интересов». «Скажи что?», Я слышал, вы думаете. То, что отображается на экране, НЕ является «структурой данных». Важно держать визуальные элементы отдельно от данных для создания визуальных элементов. Это всегда будет «будущим» вашей игрой, когда будут выпущены новые версии программного обеспечения.

Создайте структуру данных (она же модель), которая будет представлять ваш игровой мир. Затем создайте «представление» модели структуры данных. Если вы хотите изменить мир с сетки шахматной доски на гексагональную сетку, структура данных (модель) останется прежней, но дисплей «раскрасит» (отобразит) другой вид.

PBMCube
источник
4
Хотя разделение проблем действительно является хорошей практикой в ​​целом, этот ответ в настоящее время освещает детали, специфичные для ответа на вопрос (т. Е. Как создать подходящую модель нахождения сетки на основе сетки из заданного набора геометрии мира). Вы совершенно правы, что какой бы ни была эта модель, она, вероятно, должна быть отделена от данных, используемых для рисования уровня, но для ответа на вопрос нам все еще нужен метод для генерации этой модели поиска пути.
DMGregory
-2

Сделайте двойной массив. И затем, если объект / объекты являются непроходимыми, есть метод, чтобы сообщить массиву, что позиция не проходима. Когда ИИ пытается двигаться, он смотрит на двойной массив и проверяет его на проходимость.

Питер Дж
источник
4
Метод для заполнения этого массива является сложной частью. ;)
DMGregory