Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Форум / [Решено]Navigation mesh

[Решено]Navigation mesh

Поделиться
Advanced: Тема повышенной сложности или важная.

Страницы: 1 2 3 4 5 Следующая

LaynosПостоялецwww10 авг. 20166:58#0
Недавно разобрался как генерировать navmesh с помощью блендера. В последствии загорелся идеей сделать демку своими силами... Отсюда и вопросы:

1) почему меш зачастую не соответствует геометрии сцены? Чем выше cell height - тем треугольники navmesh "выше".
Да и вообще не встречал случаев генерации, когда меш полностью соответствовал оригинальной геометрии.

2) а как происходит поиск пути по navmesh, если брать в учёт тот факт, что используется физический движок (bullet physics)?
Так-то для отдания приказов на движение важна ТОЛЬКО геометрия navmesh, но вот в физическом плане важна вся карта (даже те куски, которые navmesh не затронул).
Да и можно ли по отдельность грузить треугольники и тестировать какие-то элементы отдельно? Например "поискать пересечение луча с navmesh", "поискать пересечение луча со сценой"?

3) как всё-таки происходит поиск пути?
Если все точки в одном треугольнике - прямая линия, если вне треугольников - пути нет, если в разных - А*?
Но что делать, если мне не нужен САМЫЙ оптимальный путь и я готов довольствоваться более или менее приемлемым путём? Слышал о подходе с оценками вершин с помощью G и H, но в тонкости вникнуть не смог.

4) (так или иначе связано с 2 и 3 пунктом) как хранить треугольники? И как сконвертировать треугольники из меша именно в такое представление?

Вот тестовая сцена + navmesh сверху:

+ Показать

MrShoorУчастникwww10 авг. 20168:15#1
Laynos
> тем треугольники navmesh "выше".
Что значит выше?

Laynos
> а как происходит поиск пути по navmesh, если брать в учёт тот факт, что
> используется физический движок (bullet physics)?
Буллет не причем. Берутся центры треугольников - это вершины графа. По соседним треугольникам строятся ребра графа. Дальше поиск пути в графе.

Laynos
> как всё-таки происходит поиск пути?
Сначала алгоритмом поиска пути на графе. Может быть астар, может быть дейкстра, может быть волновой алгоритм. Потом путь сглаживается. Сначала "соединяются" центры треугольников, и ищется точка пересечения с ребром. Потом точки пересечения ребер собираются в новый путь. Потом эти точки можно двигать вдоль ребра для кратчайшего пути.

Laynos
> 4) (так или иначе связано с 2 и 3 пунктом) как хранить треугольники?
В виде графа треугольников.

LaynosПостоялецwww10 авг. 20168:24#2
MrShoor
> Что значит выше?
Navmesh не совпадает с оригинальной геометрией. Трегольники могут быть чуть выше/ниже, при наложении navmesh на оригинальный меш сразу будут заметны неровности.

MrShoor
> Берутся центры треугольников - это вершины графа.
А я читал что надо брать вершины треугольников, а не их центры...

MrShoor
> В виде графа треугольников.
Оно-то понятно. Речь о том, как быстро собрать этот граф из обычной модели.
Самый тупой вариант с перебором, по понятным причинам, не пригоден

MrShoorУчастникwww10 авг. 20168:40#3
Laynos
> А я читал что надо брать вершины треугольников, а не их центры...
С центрами граф меньше - ищет быстрее.

Laynos
> Navmesh не совпадает с оригинальной геометрией. Трегольники могут быть чуть
> выше/ниже, при наложении navmesh на оригинальный меш сразу будут заметны
> неровности.
Ну это уже особенности конкретного генератора. Может оптимизирует как чтобы треугольников меньше плодить.

Laynos
> Речь о том, как быстро собрать этот граф из обычной модели.
С помощью хеш таблицы с ключом по ребру. А лучше посмотреть в сторону скрипта экспорта из блендера. Скорее всего там уже собранный граф, только бери да в файл пиши.

LaynosПостоялецwww10 авг. 20168:48#4
MrShoor
> это уже особенности конкретного генератора.
А чем вы пользуетесь? :)
MrShoor
> А лучше посмотреть в сторону скрипта экспорта из блендера. Скорее всего там уже
> собранный граф, только бери да в файл пиши.
Тоже думал об этом, искал. К сожалению, ничего не нашёл... И очень жаль(

MrShoor
> С помощью хеш таблицы с ключом по ребру.
А почему по ребру, как потом этим удобно пользоваться? Если не сложно - можно псевдокодом

MrShoorУчастникwww10 авг. 20169:03#5
Laynos
> А чем вы пользуетесь? :)
Я пользовался руками. Прямо руками делал меш. :) Но рекомендовать не буду, ибо с генератором очевидно проще.

Laynos
> Тоже думал об этом, искал. К сожалению, ничего не нашёл... И очень жаль(
А что там искать то? Бери да пиши, в блендере консоль есть, ищи свой объект, смотри его структуру, экспортируй.

Laynos
> А почему по ребру, как потом этим удобно пользоваться? Если не сложно - можно
> псевдокодом

Я не знаю на каком языке тебе надо, но для C# это будет:
struct triangle {
  vec3 pt[3];
}
struct edge {
  vec3 pt[2];
}
List<triangle>; //просто список треугольников, вершины графа
Dictionary<edge, List<int> >; //ключ - ребро треугольника, значение - список индексов треугольников в вышеописанном списке, и имеющих данное ребро

LaynosПостоялецwww10 авг. 20169:09#6
MrShoor
Вас понял, спасибо. Но разве во время поиска по словарю не будет проблем из-за точности float?

MrShoor
> Я пользовался руками. Прямо руками делал меш. :) Но рекомендовать не буду, ибо
> с генератором очевидно проще.
Прям хардкор, хе-хе :)

MrShoorУчастникwww10 авг. 20169:13#7
Laynos
> Вас понял, спасибо. Но разве во время поиска по словарю не будет проблем из-за
> точности float?
Если у тебя треугольники ссылались на абсолютно одинаковые вершины - то не будет.

Laynos
> Прям хардкор, хе-хе :)
Ну как то так. Не скажу, что это сильно сложнее, если у тебя уровень одним большим мешем.

LaynosПостоялецwww10 авг. 20169:18#8
MrShoor
> Ну как то так. Не скажу, что это сильно сложнее, если у тебя уровень одним
> большим мешем.
Согласен. В общем-то, я планирую (в розовых мечтах) завести RTS-игру.
А вы можете подсказать как спроецировать меш на другой меш?

Тобишь у меня есть два меша:
1 - сама карта
2 - plane, который я хорошенько разделил на много мелких треугольников

Вот хотелось бы второй меш спроецировать на первый, а потом вручную убрать ненужные кусочки.
В вашем подходе есть несомненное преимущество: человек контролирует расположение и размеры треугольников... Иногда генерировать сложнее (если не брать особо сложные меши, конечно).

Да и информация об этом поможет мне, к слову, также пофиксить сгенерированный меш, насильно "притулив" его к оригинальной геометрии

P.S. Я использую всё тот же Blender

MrShoorУчастникwww10 авг. 20169:23#9
Laynos
> А вы можете подсказать как спроецировать меш на другой меш?
Я не то что бы гуру блендера. Так что подсказать не могу. Подозреваю что там должен быть какой то модификатор. Я у себя делал так, копировал весь уровень, а потом просто выделял и прибивал все ненужные треугольники руками.

Laynos
> Да и информация об этом поможет мне, к слову, также пофиксить сгенерированный
> меш, насильно "притулив" его к оригинальной геометрии
А зачем? Там такие большие погрешности?

LaynosПостоялецwww10 авг. 20169:24#10
MrShoor
> А зачем? Там такие большие погрешности?
Иногда довольно ощутимые
MrShoorУчастникwww10 авг. 20169:30#11
Laynos
> Иногда довольно ощутимые
Ну тогда хрен знает. Ничего не подскажу по генератору. Может кто другой подскажет.
DampireПостоялецwww10 авг. 201610:27#12
Laynos
Объясни дураку, зачем его прижимать к геометрии? Навмеш описывает возможный путь для агента. Агент может ходить по ступенькам и соответственно эти ступеньки проще описать плейном под углом. Прижимай агента к физической геометрии, если он у тебя не летающий, а на навмеше строй путь. Остальное - невообразимая глупость.

Правка: 10 авг. 2016 10:28

LaynosПостоялецwww10 авг. 201610:40#13
Dampire
> Объясни дураку, зачем его прижимать к геометрии? Навмеш описывает возможный
> путь для агента. Агент может ходить по ступенькам и соответственно эти
> ступеньки проще описать плейном под углом. Прижимай агента к физической
> геометрии, если он у тебя не летающий, а на навмеше строй путь. Остальное -
> невообразимая глупость.
А если подойти к вопросу с другой стороны: зачем мне его НЕ прижимать?
Я планирую скомбинировать navmesh и физическую корректность передвижений.

navmesh - вспомогательная структура для поиска пути. А там уже я решаю как и когда объекту надо развернуться, ускориться и т.п.
Каждый раз при изменении положения объекта все треугольники navmesh, на которых стоит объект (+ запас, чтобы другие объекты о него не цеплялись), признаются непроходимыми.

AntonioModerПостоялецwww10 авг. 201610:50#14
Laynos
> 1) почему меш зачастую не соответствует геометрии сцены? Чем выше cell height -
> тем треугольники navmesh "выше".
> Да и вообще не встречал случаев генерации, когда меш полностью соответствовал
> оригинальной геометрии.
Ты в курсе что генерируется с учетом размеров Агента?
Вот тебе "точное соответствие геометрии", только генератить он будет очень долго:
blenderNavmesh | [Решено]Navigation mesh

Правка: 10 авг. 2016 10:51

Страницы: 1 2 3 4 5 Следующая

/ Форум / Программирование игр / Игровая логика и ИИ

2001—2017 © GameDev.ru — Разработка игр