Улучшение поиска путей в Г2

[avx1024]

Всем привет.
Играл давеча в g2(в2+аб) и что-то стало мне грустно от того что мобы тупые. Заманиваешь его к уступу, чтобы свалился или залезаешь сам и безнаказанно расстреливаешь. Нет конечно это абузы и все дела и их можно не юзать, но текущая система построения маршрутов, как я понял, работает по схеме: "прямой путь из точки А(моб) к точке Б(ГГ/моб)" и сильно страдает от отсутствия какой-либо интеллектуальности.
У меня возник вопрос, а как можно ее улучшить ? Тем более сейчас, когда появился Аст и Юнион, хукать можно все или почти все вызовы в движке и буквально 1 строчкой кода. После гугления на тему ИИ для построения маршрутов, чтения форума и исходников Регота я (на текущем уровне понимания) вижу 2 способа улучшить положение вещей:

Общее решение:
1. Построение навигационного меша из меша локации и вобов.
2. Построение путей на навигационном меше с помощью A* и его вариаций.
3. Доработка логики контроллера построения путей, для сглаживания пути и учета преодоления препятствий(запрыгнуть/облететь/переплыть/спрыгнуть и т.д.)
Решение это довольно трудозатратное, зато результат(в теории) должен быть очень неплохим.

Локальное решение(как в Реготе):
1. Трассировка, для определения можно ли пройти по прямой к целевой точке.
2. Если нельзя, то ищутся 2 ближайших вейпоинта к отправной и конечной точке (к которым можно пройти по прямой) и через алг. поиска пути на графе(Дейкстра или тот же A*) строится маршрут по которому моб и пускается.
3. Естественно нужно будет доработать контроллер, т.к. ГГ или другие мобы двигаются и пути нужно перестраивать.
Решение проще 1, т.к. есть готовые наработки, правда есть и открытые вопросы, ведь Регот написан с 0 и самостоятельно, а есть ли нужный функционал для трассировки(определения колиизий) в движке Г2, х его з.

Интересно мнение сведущих людей. Какие пути решения проблемы с построением путей они видят и есть ли какие-либо наработки по этой теме ?
Я так понимаю какие-то работы в этой области велись, т.к. Gratt выкладывал видео на эту тему(еще во времена AST):

Но почему-то работы не были продолжены.

 

[Gratt]

Но почему-то работы не были продолжены.

Были. Основная сложность только в том, чтобы сесть и довести это до ума.

На самом деле задача несложная, но трудозатратная. Где-то в январе этого года я занимался этой темой и реализовал несколько алгоритмов, которые работали РЕАЛЬНО БЫСТРО. Могу сказать, что алгоритмы делятся на три этапа:
1. Анализ мира. Вообще программе можно было скормить любой меш, который содержал полигоны мира, предназначенные исключительно для ХОДЬБЫ. При отсутствии такого файла алгоритм сам просчитывал все полигоны, пригодные для передвижения и собирал их в группы чанков.
2. Далее можно было произвести запрос нахождения цепи полигонов из А в Б, который брал кратчайший путь по всему полимешу, либо по определенным его группам полигонов (скажем отфильтрованный по материалу дорог, чтобы нпс выбирали исключительно тропы), при чем все это в отдельном потоке, чтобы не просаживать игру.
3. Между промежуточными точками в момент движения NPC должен отрабатывать отдельный высокоточный аналайзер, определяющий физические препятствия (деревья, строения, ящики, двери и тд), кстати именно его концепт на прикрепленном видео.

 

[avx1024]

в момент движения NPC должен отрабатывать отдельный высокоточный аналайзер

А почему был выбран вариант с runtime анализом препятствий ? Ведь все мобы, кроме NPC не двигаются и их можно учесть при определении полигонов пргодных для ходьбы.

Если у меня есть интерес к этой теме, мое участие в доработке этого функционала и релиза в виде плагина для Union или иным способом, обсуждаемо ?

 

[Gratt]

А почему был выбран вариант с runtime анализом препятствий ? Ведь все мобы, кроме NPC не двигаются и их можно учесть при определении полигонов пргодных для ходьбы.

А во что предлагаешь писать инфу о препятствиях?

Если у меня есть интерес к этой теме, мое участие в доработке этого функционала и релиза в виде плагина для Union или иным способом, обсуждаемо ?

А твоими сильными сторонами являются программирование, математика или daedalus? Иначе не очень понимаю чем именно ты хочешь посодействовать.

 

[avx1024]

А во что предлагаешь писать инфу о препятствиях

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

А твоими сильными сторонами являются программирование, математика или daedalus?

Я 5+ лет программирую на плюсах за деньги, если по трудовой. Если хочешь, можешь провести собеседование или выдать ТЗ.

 

[Gratt]

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

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

Я 5+ лет программирую на плюсах за деньги, если по трудовой. Если хочешь, можешь провести собеседование или выдать ТЗ.

Да делать мне нечего По диалогу сразу понятно все станет. Вот, в дискорде меня найдешь: Gratt#2112

 

[Trazege]

Осмелюсь спросить - есть сподвижки по данному вопросу или желание умерло вместе с возможностями?

 

[avx1024]

Ого, сам мастер пишет в мою тему(пишу без сарказма, т.к. играю в твои моды с 2009 года).
Подвижки есть и даже 1 версия альфы есть. Но там хренова туча вопросов над которыми предстоит покумекать и еще больше работы.
1 версия появилась в ноябре 2020 года и там мобы на ура ищут пути, но не умеют прыгать ,а соединить Rbt с новым механизмом я посчитал беспереспективным занятием, т.к. приходится жертвовать либо корректным поиском путей, либо прыжками, в той или иной степени.. Далее я засел за дорабокой прыжков и карабканий, чем сейчас и занимаюсь. Не хочу давать сроков, но по прикидкам я закончу тех. доработки для прыжков через 3-4 недели, а затем еще 3-4 недели займет склейка нового механизма и движка. Плюс еще можно добавить 30-40% времени на решение непредвиденного и изучения движка, т.к. не все мне еще ясно.
Итого чере 2-3 мес., может немного быстрее, появится полноценная 1 версия. И повторюсь, это будет только альфа, т.к. еще нужно будет решить вопрос с обработкой муверов, лестниц и дверей, к коему я вообще не приступал. И сам плагин не будет работать на 1-ядерном ЦПУ ибо движок не потянет(нужно хотя бы 2 лог. ядра, гипертрединг от Интела или аналогичное от Амд) и ram памяти он будет жрать в районе 250-300 Мб.
Как будет готово я выложу альфу под ванильную Г2 с подробным описанием.

 

[Trazege]

Очень ждём! Поиск пути - на мой взгляд самая реальная проблема мобья в игре.

 

[avx1024]

Итак, пора резюмировать что есть на текущий момент. Чтобы не быть Львом Толстым на словах приложу пару видео из старого плагина, который начал работать в начале ноября прошлого года. Там нет прыжков и корабканий, что и можно увидеть на видео.
1. Ирдорат.


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

2. Хоринис


Опять-таки мобы не перепрыгивают препятствие, а оббегают.

Именно это поведение мне не понравилось и я посчитал что его объединение со старым алгоритмом будет беспереспективно, т.к. пока моб где-то не застрянет, нельзя понять что нужно использовать новый алгоритм для поиска пути. Итого получилось бы что мобы время от времени где-то буксуют и потом начинают оббегать. И так я решил сделать пасфаиндинг и с классическим перемещением и с прыжками. Это было ошибкой, т.к. я не представлял объем работ и необходимый бэкграунд для оного, хотя Рубикон уже перейден.
Не буду подробно расписывать технологию на данном этапе, это будет после релиза альфы. Кратко это навигационный меш, как в unreal и unity. Для расчета навмеша и работы с ним используется проект recastvavigation(к слову он и используется в unreal), который пришлось существенно дорабатывать, особенно часть для построения путей (Detour), да и с RecastDemo приходится возиться очень много, которое используется для визуализации и отладки. Вот скриншоты с RecastDemo, теперь движок так "видит" пространство по которому можно ходить. Также на скриншотах есть визуализация расчетов алгоритмов для прыжков и карабканий, над которыми я и работал последние 7 месяцев.



В посте выше я писал что сделаю альфу за 2-3 мес., но тут я ошибся. Во-первых мне не хватает бэкграунда по алгебре и геометрии, во-вторых отсутствует практический опыт в вычислительной геометрии. Так например для реализации просчета прыжков мне понадобилась новая подсистема collision detection, оригинальная не устраивает т.к. написана под 1 поток(нашпигована глобальными и статическими переменными), самое главное она медленная, мне нужны были несколько сотен неносекунд для запросов типа ray-triangle intersection по произвольной области и меша и не более 1 мкс для запросов типа obb-triangle intersection. Сам просчет геометрических примитивов(narrow phase) использует стандартные алгоритмы, а вот в broad phase подсистемы различаются. В оригинале - bsp tree + octo tree, я же пока остановился на xz grid + bvh with sah, ну и sse 1.0 для критических частей. Хотя даже быстрая детекция коллизий не решила проблемы со скоростью и пришлось делать кэш вычислений, который и дал приемлимые скорости для обсчета путей. (Раньше для дистанция с прыжками требовалось 10-30 мс, для 1 пути, что даже с учетом объединения результатов для нескольких мобов было неприемлемо, теперь это 1-2 мс. Т.е. ускорение в 10-20 раз, в некоторых случаях до 100 раз). Обратная сторона кэша это потребление памяти, которой всего чуть менее 3Гб. Сам кэш ест немного (10-40 Мб, в зависимости от настроек), но эта цифра умножается как минимум на 3, т.к. для разных мобов приходится использовать разный навмеш(сейчас мобы разбиваются на 3 класса, можно и больше но вырастет потребление памяти).
В общем если вернуться к подсчету временных затрат, только на collision detection у меня ушло 3.5 мес. чтобы проверить разные струтктуры и их комбинации и получить устраивающие меня цифры.

Из работ для выпуска альфа-версии осталось сделать:
1. Правки геометрических алгоритмов прыжков(около недели работы по 10-12 часов в день)
2. Контроллер пасфаиндинга с учетом нормального режима и прыжков (около 2-х. месяцев, но может и быстрее, т.к. там в основном логика и вычислительной геометрии уже не много)
3. Отлов серьезных багов в пасфаиндинге и просто падений (от пары дней до пары месяцев, но скорее всего 2 +/- недели).
Да, сама посистема поиска путей состоит их 3-х плагинов, 1 выгружает меш из движка в .obj формате, 2 - строит навмеш по .obj, 3 - сам плагин и утилиты RecastDemo для визуализации и отладки, ее интрефейс можно увидеть на скриншотах. В будущем нужно будет объеденить 2 и RecastDemo.

Я написал этот пост так как у меня накопилось дел которые нужно решать по жизни и полноценно совмещать работу, разработку пасфаиндинга и собственно социальную деятельность я уже не могу (порой приходится на разработку тратить по 16 часов в сутки, с учетом работы). Так что беру перерыв на 3 месяца, а после приступлю к реализации намеченного в п. 1-3. Хотя конечно полный перерыв взять не получится , т.к. буду уделять время и вычислительной геометрии и линалу, засосало меня все это как-то.

 

[KirTheSeeker]

Я написал этот пост так как у меня накопилось дел которые нужно решать по жизни и полноценно совмещать работу, разработку пасфаиндинга и собственно социальную деятельность я уже не могу (порой приходится на разработку тратить по 16 часов в сутки, с учетом работы). Так что беру перерыв на 3 месяца, а после приступлю к реализации намеченного в п. 1-3. Хотя конечно полный перерыв взять не получится , т.к. буду уделять время и вычислительной геометрии и линалу, засосало меня все это как-то.

Удачи с делами и терпения в разработке.

 

[Test Level]

Ладно орки, но варги-то с какого перепугу разумными стали? Видео напомнило Risen, где монстрюки через пол локации к тебе бегут.

 

[Trazege]

Удачи и терпения! Вещь чрезвычайно востребованная. Насчёт алгебры и геометрии рекомендую проконсультироваться с Граттом. Он шарит в этом хорошо.

 

[Trazege]

Как обстоят дела с плагином? Есть ли надежда что он увидит таки мир?

 

[avx1024]

Как обстоят дела с плагином? Есть ли надежда что он увидит таки мир?

Неисповедимы пути готические. Хотя хрустальный шар говорит что в 21 году не увидит точно !
Да, я опять вернулся к разработке, сейчас занимаюсь дверями, лестницами, муверами и лавой. Если точнее, то я только начал этот процесс и сейчас разбираюсь с движком, чтобы выгрузить их меш.

P.S. Вообще пауза благотворно сказалась на разработке. Я стал скатываться в шлифование отдельных частей(типа collision detection), которые не приближали к конечному результату. На текущий момент чтобы получить 1 работающую версию нужно сделать 6 вещей:
1. Доработку по переходам между сушей и водой + мелочевка с флагами.
2. Собсно муверы с лестницами и дверями
3. Перевести разработку под винду. 1 версия плагина(с которой видео) ессно под вин, но вся разработка с алгоримами, генерацией навмеша и визуализацией под линкусом. (В утилите визуализации рендеринг на opengl, за пол дня у меня не получилось завести его под VS, так придется засеть за это более обстоятельно.)
4. Доработать генерацию навмеша, чтобы можно было области размечать в виз. редакторе.
5. Поправить интерфейсы прыжков под новую версию (по мере обретения бэкграунда приходит понимание проблем в старых версиях, но тут ничего не сделать). Вообще сейчас алгоритмы 2 версии и они весьмо бодро работают по корректности и скорости, первая версия плагина выйдет на них.
6. Сам плагин, который все соединит и подстроит под интерфейс Rbt в движке.

Не хочу давать сроков, т.к. ошибусь все равно. Можно лишь отметить самые затратные по времени этапы, это 2 и 6, т.к. нужно будет много времени тратить на изучение движка и отлов багов. Ну и все зависит от моей загруженности, т.к. я не могу работать по 16 часов в сутки, точнее могу но не долго.

 

[Trazege]

Неисповедимы пути готические. Хотя хрустальный шар говорит что в 21 году не увидит точно !
Да, я опять вернулся к разработке, сейчас занимаюсь дверями, лестницами, муверами и лавой. Если точнее, то я только начал этот процесс и сейчас разбираюсь с движком, чтобы выгрузить их меш.

P.S. Вообще пауза благотворно сказалась на разработке. Я стал скатываться в шлифование отдельных частей(типа collision detection), которые не приближали к конечному результату. На текущий момент чтобы получить 1 работающую версию нужно сделать 6 вещей:
1. Доработку по переходам между сушей и водой + мелочевка с флагами.
2. Собсно муверы с лестницами и дверями
3. Перевести разработку под винду. 1 версия плагина(с которой видео) ессно под вин, но вся разработка с алгоримами, генерацией навмеша и визуализацией под линкусом. (В утилите визуализации рендеринг на opengl, за пол дня у меня не получилось завести его под VS, так придется засеть за это более обстоятельно.)
4. Доработать генерацию навмеша, чтобы можно было области размечать в виз. редакторе.
5. Поправить интерфейсы прыжков под новую версию (по мере обретения бэкграунда приходит понимание проблем в старых версиях, но тут ничего не сделать). Вообще сейчас алгоритмы 2 версии и они весьмо бодро работают по корректности и скорости, первая версия плагина выйдет на них.
6. Сам плагин, который все соединит и подстроит под интерфейс Rbt в движке.

Не хочу давать сроков, т.к. ошибусь все равно. Можно лишь отметить самые затратные по времени этапы, это 2 и 6, т.к. нужно будет много времени тратить на изучение движка и отлов багов. Ну и все зависит от моей загруженности, т.к. я не могу работать по 16 часов в сутки, точнее могу но не долго.

Вы сделали мой день, коллега. Спасибо за отличные новости! Просто занят сейчас балансировкой боевки мобов и постоянно ловлю себя на мысли - насколько важен этот плагин.

 

[avx1024]

Ну вот, заходишь сделать юбилейный пост, а твоего потенциального заказчика забанили. Впрочем оставим лирику.
С предыдущего списка сделаны пункты 1, 2, 4 + еще мнго чего, но правки в основном технического характера, так что в красивых картинках их не покажешь. Плюс ко всему, по мере реализации одного пункта, в список доработок добавляется еще 3-4, но то пойдет на следующие итерации.
Из самого важного:
1. Переработана bvh струтктура для хранения меша, чтобы можно было обрабатывать изменения мира, при активации муверов. Это, в свою очередь, благотворно сказалось на количестве потребляемой памяти. Т.к. если раньше меш каждого воба дублировался и добавлялся к мешу мира, то теперь в мировом меше хранится только AABB этого воба(6 прямоугольников - 12 треугольников), в котором хранятся ссылки на сам меш воба.
Итого на популярных локах выходит:
a. Ванильный Хоринис - 43 Мб
b. Хоринис из АБ-НБ(последней версии) - 75 МБ
c. Архолос - 125 МБ
(Это цифры самого меша, кэши и навмеш идут отдельно)
Причем "компиляция" меша делалась с упором на скрость collision detection, если ей пожертвовать то можно еще 10-15% памяти сэкономить.

2. По мере реализации 1 пукта и функционала для дверей-лестниц, добавил функционал для разметки областей меша и простановки кастомных флагов. Вообще на эту идею меня навели разговоры с Граттом, про построение пути по полигонам с определенным флагом(чтобы НПС в обычных ситуациях выбирали одни полигоны, например дороги и игнорировали другие, например лес). Я подумал что было бы интересно добавить разметки областей и установку им определенных флагов, например жилая/нежилая территория. На это поведение можно накрутить скриптовую логику, что слабые монстры не приближаются к полигонам с флагом "жилая территория", а области нарисовать у ворот города, ферм. Итого не получится заманивать монстров для убийства в города. (Да-да это фича для ноудезеров из АБ-НБ ). Ну и вообще разное поведение можно придумать с флагами, главное это управление вынести в скрипты.
Собственно процесс разметки и результат:

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

3. Самая тяжелая доработка, заняла у меня 3+ месяца. По дефолту при генерации намеша задается радиус агента и его величина используется как отступ при генерации навмеша, чтобы при передвижении мобы не застревали в краях меша, особенно на поворотах. Такой же отступ берется при генерации на уступах, т.е. если до края скалы меньше заданного радиуса, то навмеша там не будет. В общем это нормальное поведение, но движок Готики позволяет мобу стоять, если 50+ % его bbox'a будет на меше и даже меньше если опора под цетнром бокса (хождение по канатам). И получается что Рекаст не умел генерить навмеш на узких участках, а жертвовать радиусом, занижая его, так себе затея. В общем пришлось досканально разбираться в первой четверти процесса генерации и перерабатывать его. Итого теперь меш можно генерить на переладинах, мачтах и т.д.

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

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

4. Работа с полигонами жидкости, в 1 очередь водой (с лавой сложнее и отчасти проще, ее обработки пока не будет). Как известно в игре есть три вида передвижения по воде, a - как по суше, b - анимация тормознутого калича и c - плавание. И в зависимости от глубины мобы могут использовать те или иные виды прыжков и карабкания. В оригинале этого всего не было и нужно было длработать. Да и еще 1 важная штука, при переходе из воды на сушу, этот переход может не сработать если наклон полигонов, которые оказываются под мобом или игроком будут больше максимального, пригодного для хождения. Что в конечном счете приводит к тому что моб гребет на 1 месте и не может залезть на берег (наверняка все видели такую ситуацию). В итоге я сделал генерацию водяных полигонов под все типы передвижения + с обработкой мест непригодных для хождения.

1 - суша; 2 - вода по которой можно ходить как по суше; 3 - каличная вода; 4 - плавание; 5 - в этом месте переход на сушу не возможен и там попросту не генерируется навмеш. Теперь можно составлять лоцманские карты водоемов Хориниса.

5. Кое какие доработки с генерацией граней полигонов, для корректного просчета карабкания, ну и еще много всего по мелочи.

Итого до первой конечной точки с альфа релизом остается 3 пункта:
a. Переработать алгоритмы карабкания и прыжков + поправить физику движка. Сообщением выше я писал что поправлю только интерфейсы, но проще будет сделать все разом, т.к. навмеш сильно изменился. Да и старые алгоритмы я бы назвал 2.5d, а не 3d. Забавно смотреть на старые подходы(например прыжки вниз), как я считал-пересчитывал точки приземления, с учетом величины наклона полигона и прочей ерундой, вместо того чтобы просто решить квадратное уравнение с вектором скорости, ускорения и полигоном приземления.
b. Нужно превести проект на Винду(как я писал выше, повозиться с рендериногом на opengl) + порефакторить код, т.к. кода нового уже под 20К и будет еще больше, и попадаются то глупые ошибки с утечкой памяти, то дублирование кода, то еще чего что можно при правильном подходе избежать и не тратить время на отладку.
c. Сам плагин. Собственно 1 версия без прыжков есть, вместе с ней есть понимание интерфейса и работы RobustTrace'a, который я и заменяю, так что основа уже имеется, что прилично сократит время.
По времени, хочется надеяться что успею к концу этого года, но обещать ничего не могу (да, я только про альфу говорю пока).
За сим все.

P.S. Один теоретический вопрос. Почему в движке меш хранится с инверсией по z координате ? Если его просто выгрузить то он окажется отзеркален в противоположную сторону, например на Ирдорате нос корабля будет на проем в скалах(откуда приплыли), а не на грот. Я это понял давно и просто инвертирую его при выгрузке, что кстати не правильно, т.к. приходится и коодинаты пути инвертировать при передаче из плагина в движок, что лишняя трата ЦПУ времени. Правильнее инвертировать при рендеринге. Но это поправимо и будет поправлено, интересно именно почему так сделано ?

 

[MaGoth]

Почему в движке меш хранится с инверсией по z координате

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

 

[SuperDave500]

Я забыл, насколько плохи пути для NPC в Готике 2. Увидев эту ветку, я вернулся и поигрался с пути. Мне стало грустно. Пожалуйста, продолжайте эту столь необходимую работу!

 

[AlchimikSalandril]

Ну вот, заходишь сделать юбилейный пост, а твоего потенциального заказчика забанили. Впрочем оставим лирику.
С предыдущего списка сделаны пункты 1, 2, 4 + еще мнго чего, но правки в основном технического характера, так что в красивых картинках их не покажешь. Плюс ко всему, по мере реализации одного пункта, в список доработок добавляется еще 3-4, но то пойдет на следующие итерации.
Из самого важного:
1. Переработана bvh струтктура для хранения меша, чтобы можно было обрабатывать изменения мира, при активации муверов. Это, в свою очередь, благотворно сказалось на количестве потребляемой памяти. Т.к. если раньше меш каждого воба дублировался и добавлялся к мешу мира, то теперь в мировом меше хранится только AABB этого воба(6 прямоугольников - 12 треугольников), в котором хранятся ссылки на сам меш воба.
Итого на популярных локах выходит:
a. Ванильный Хоринис - 43 Мб
b. Хоринис из АБ-НБ(последней версии) - 75 МБ
c. Архолос - 125 МБ
(Это цифры самого меша, кэши и навмеш идут отдельно)
Причем "компиляция" меша делалась с упором на скрость collision detection, если ей пожертвовать то можно еще 10-15% памяти сэкономить.

2. По мере реализации 1 пукта и функционала для дверей-лестниц, добавил функционал для разметки областей меша и простановки кастомных флагов. Вообще на эту идею меня навели разговоры с Граттом, про построение пути по полигонам с определенным флагом(чтобы НПС в обычных ситуациях выбирали одни полигоны, например дороги и игнорировали другие, например лес). Я подумал что было бы интересно добавить разметки областей и установку им определенных флагов, например жилая/нежилая территория. На это поведение можно накрутить скриптовую логику, что слабые монстры не приближаются к полигонам с флагом "жилая территория", а области нарисовать у ворот города, ферм. Итого не получится заманивать монстров для убийства в города. (Да-да это фича для ноудезеров из АБ-НБ ). Ну и вообще разное поведение можно придумать с флагами, главное это управление вынести в скрипты.
Собственно процесс разметки и результат:
Посмотреть вложение 107384

Посмотреть вложение 107385

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

3. Самая тяжелая доработка, заняла у меня 3+ месяца. По дефолту при генерации намеша задается радиус агента и его величина используется как отступ при генерации навмеша, чтобы при передвижении мобы не застревали в краях меша, особенно на поворотах. Такой же отступ берется при генерации на уступах, т.е. если до края скалы меньше заданного радиуса, то навмеша там не будет. В общем это нормальное поведение, но движок Готики позволяет мобу стоять, если 50+ % его bbox'a будет на меше и даже меньше если опора под цетнром бокса (хождение по канатам). И получается что Рекаст не умел генерить навмеш на узких участках, а жертвовать радиусом, занижая его, так себе затея. В общем пришлось досканально разбираться в первой четверти процесса генерации и перерабатывать его. Итого теперь меш можно генерить на переладинах, мачтах и т.д.
Посмотреть вложение 107386

Естественно предполагается что по этим местам мобы смогут бегать/прыгать и всяко использовать в построении пути.
Побочным эффектом оказалось что можно генерить навмеш даже на канатах.
Посмотреть вложение 107387

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

4. Работа с полигонами жидкости, в 1 очередь водой (с лавой сложнее и отчасти проще, ее обработки пока не будет). Как известно в игре есть три вида передвижения по воде, a - как по суше, b - анимация тормознутого калича и c - плавание. И в зависимости от глубины мобы могут использовать те или иные виды прыжков и карабкания. В оригинале этого всего не было и нужно было длработать. Да и еще 1 важная штука, при переходе из воды на сушу, этот переход может не сработать если наклон полигонов, которые оказываются под мобом или игроком будут больше максимального, пригодного для хождения. Что в конечном счете приводит к тому что моб гребет на 1 месте и не может залезть на берег (наверняка все видели такую ситуацию). В итоге я сделал генерацию водяных полигонов под все типы передвижения + с обработкой мест непригодных для хождения.
Посмотреть вложение 107388
1 - суша; 2 - вода по которой можно ходить как по суше; 3 - каличная вода; 4 - плавание; 5 - в этом месте переход на сушу не возможен и там попросту не генерируется навмеш. Теперь можно составлять лоцманские карты водоемов Хориниса.

5. Кое какие доработки с генерацией граней полигонов, для корректного просчета карабкания, ну и еще много всего по мелочи.

Итого до первой конечной точки с альфа релизом остается 3 пункта:
a. Переработать алгоритмы карабкания и прыжков + поправить физику движка. Сообщением выше я писал что поправлю только интерфейсы, но проще будет сделать все разом, т.к. навмеш сильно изменился. Да и старые алгоритмы я бы назвал 2.5d, а не 3d. Забавно смотреть на старые подходы(например прыжки вниз), как я считал-пересчитывал точки приземления, с учетом величины наклона полигона и прочей ерундой, вместо того чтобы просто решить квадратное уравнение с вектором скорости, ускорения и полигоном приземления.
b. Нужно превести проект на Винду(как я писал выше, повозиться с рендериногом на opengl) + порефакторить код, т.к. кода нового уже под 20К и будет еще больше, и попадаются то глупые ошибки с утечкой памяти, то дублирование кода, то еще чего что можно при правильном подходе избежать и не тратить время на отладку.
c. Сам плагин. Собственно 1 версия без прыжков есть, вместе с ней есть понимание интерфейса и работы RobustTrace'a, который я и заменяю, так что основа уже имеется, что прилично сократит время.
По времени, хочется надеяться что успею к концу этого года, но обещать ничего не могу (да, я только про альфу говорю пока).
За сим все.

P.S. Один теоретический вопрос. Почему в движке меш хранится с инверсией по z координате ? Если его просто выгрузить то он окажется отзеркален в противоположную сторону, например на Ирдорате нос корабля будет на проем в скалах(откуда приплыли), а не на грот. Я это понял давно и просто инвертирую его при выгрузке, что кстати не правильно, т.к. приходится и коодинаты пути инвертировать при передаче из плагина в движок, что лишняя трата ЦПУ времени. Правильнее инвертировать при рендеринге. Но это поправимо и будет поправлено, интересно именно почему так сделано ?

несмотря на бан очень ждем! Ибо в отличии от местных банщиков вы реально делаете огромную и нужную работу.