Патчфинд 3.0

[n3k0nation]

Давненько я не создавал тем на ЗГ ;D

И так друзья, за последний месяц я раздумывал над некоторыми вещами в плане патчфиндинга (для облегчения понимания назовем патчфиндингом - геодату и сам поиск пути, как это и есть на самом деле), я хочу поделиться некоторыми своими мыслями, но уже в рамках l2j реализации. Горячий дискас приветствуется, т.к. я не привык разговаривать сам с собой :)

По следам тем:
алгоритмика патчфиндинга
nCore геодвижек

Так же можно посмотреть эту интересную тему на форуме лыжи (только для залогиненых).

Генерация карты проходимости
Изначально в клиенте есть сами карты формата анреал. Ну хорошо, немного измененные, но все же формат остался тем же. Почему бы нам не взять эти карты и не генерировать геодату по ним без прогрузки самого движка?
Предчувствуя вопросы: да, формат карт хранит лишь ссылки на модели, плюс надо высчитывать разницу высот местности от нуля, для корректного пробега по многоуровневым локациям.
Плюсы способа: совершенно реально узнать проходимость любой точки, а не как сейчас: колонна, а внутри нее пустота, при этом мы какими-то костылями еще и пытаемся определить, что это точка внутри модели, или же тут просто нет нихрена геодаты.
Кстати такой костыль, это основной костяк большинства проблем с прострелами, провалами и другими чудо-действиями. Хотя тут опять же многое зависит от синхронизации клиент-сервер в плане координат и передвижения (что кстати до сих пор "на нуле", как и было, когда я только начал увлекаться л2девом, а это было эдак лет 6 назад). Ну да, я немного вру, у фениксов и балансера были какие-то попытки, но особого успеха они не принесли, хотя стало уже не так криво.
Проблемы способа: размер геодаты будет равен:
(|MAP_MIN_X|+|MAP_MAX_X|) * (|MAP_MIN_Y|+|MAP_MAX_Y|) * (|MAP_MIN_Z|+|MAP_MAX_Z|) * MAX_LAYERS
Это на самом деле достаточно большой размер, особенно если кешировать все в память. Можете посчитать сами. Обычно максимальное количество слоев не превышает 127. Конкретно внутри мы храним 1 байт, который является NSWE точки. Такой формат конечно не совместим с l2j геодатой и _conv.dat, но мы тут частично выигрываем по размеру, т.к. не храним "особенную" высоту для каждой ячейки [лолват, зачем это было вообще сделано? можно было сделать же нормальный формат, в который достаточно легко конвертить _conv.dat, но и тут все криво, да].

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

Ваши предложения господа?


Поиск пути
Изначально у всех игровых обьектов в l2 есть размер, который легко взять из клиента, да и насколько я помню, этот размер храниться даже в l2j, хотя особо там не нужен.
Это дает нам шанс добавить немного эвристики поиску пути, чтобы не было таких косяков, когда мы бежим, допустим в КХ, закрываются двери, а так как просчет пути уже был выполнен, то мы начинаем бежать в дверь. Ну дальше предсказать легко: с координатами творится НЁХ и мы при высокой удаче, можем просто телепортироваться за дверь.
Для начала разберем основные методы эвристического поиска пути, тобишь для самых маленьких, как это делается.
Сама эвристика основана на том, что у каждой точки есть флаг изменения состояния, если состояние точки изменилось, то должны быть уведомлены все слушатели этой точки (т.е. в данном случае, активные пути, в которых состоит эта точка).
В нашем случае, я предлагаю дать всем игровым обьектам, которые могут присутствовать в мире, интерфейс, который будет определять их размер. Таким образом мы сможем иметь примитивную физику столкновений (коллизий), с помощью которой мы сможем оптимально высчитывать путь под ситуации, которые меняются.
Пример: у гнома высота 10, у ушастого педика 30, соответственно гном может пройти, там где ушастый не сможет (в теории; возможно в игре нет таких мест), грубо говоря, это расчет разницы высот текущего слоя и слоя выше, с учетом размера самого обьекта.

P.S: суть этой темы не критиковать текущее положение дел, а как-то рассортировать свои мысли и идеи, плюс обсудить их с другими людьми.
P.P.S: тему буду время от времени обновлять

---------------------------------------------
Если Вы хотите написать: "зачем тебе это надо ТС? пусть все будет как есть", то лучше тыкните мне минус в карму и не пишите такой пост, иначе минус тыкну уже я.

[qweqwe1]

Раз уж речь зашла про геодвижок, есть пара вопросов.

В GoE entrance есть потолок, которого нет в геодате (L2J формат). Т.е. есть слои выступов уже в помещении (с водой), есть слой поверхности над локацией. И вот что-то не помню, на птсах с этим проблемы были или нет. По идее два выхода из ситуации - блокировать перемещение вверх по Z, если в воде, если Z поверхности минус Z игрока меньше допустимого значения. Тогда если игрок тыкает в потолок, то может сделать релог и встрять (клиент не даст ткнуть вниз, а наверх выплыть не сможет из-за ограничения). Второй вариант - не блокировать перемещение, игрок не встрянет, но сможет выплыть из помещения на поверхность. Как-то можно решить эту проблему с текущим раскладом (L2J геодата) ?

И второй вопрос - с ПТСами не пересекался вообще, беглый поиск не дал результатов - как хранится гео в conv.dat, есть ли потери при конверте в L2J ?

По поводу "без прогрузки движка" (если правильно понял мысли автора) - если у объекта есть модифицируемые движком пространственные характеристики (U скриптами или анимацией, например), разве с этим не будет проблем ? Сходу вспоминаются водяные колеса у Хейне, но наверняка есть объекты позаковырестее.

[n3k0nation]

Ну и ладно, буду сам с собой разговаривать :redlol:

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

Добавлено через 12 минут

В GoE entrance есть потолок, которого нет в геодате (L2J формат). Т.е. есть слои выступов уже в помещении (с водой), есть слой поверхности над локацией. И вот что-то не помню, на птсах с этим проблемы были или нет. По идее два выхода из ситуации - блокировать перемещение вверх по Z, если в воде, если Z поверхности минус Z игрока меньше допустимого значения. Тогда если игрок тыкает в потолок, то может сделать релог и встрять (клиент не даст ткнуть вниз, а наверх выплыть не сможет из-за ограничения). Второй вариант - не блокировать перемещение, игрок не встрянет, но сможет выплыть из помещения на поверхность. Как-то можно решить эту проблему с текущим раскладом (L2J геодата) ?

Делать дополнительный непроходимый слой, который находится от модели потолка до слоя, который выше. Это если без особых костылей.
Да и по идее в оригинале оно должно выглядеть, как-то так. Проблема в том, что в l2j нет поиска 3D пути (для полетов и плаванья), в данном случае нам нужно делать поправку на 3D'шный поиск пути и опять же высчитывать разницу уровней (слоев) с поправкой на упор, в модель потолка (MAX_Z_FOR_THIS_LAYER - PLAYER_HEIGHT - CONST, где константу нужно подобрать опытным путем, я не думаю, что она будет больше 10), если мы ее превышаем, то попасть в точку назначения нельзя и мы меняем эту точку на ближайшую, на данном слое (чтобы не стоять на месте, если тыкнуть в потолок).

И второй вопрос - с ПТСами не пересекался вообще, беглый поиск не дал результатов - как хранится гео в conv.dat, есть ли потери при конверте в L2J ?

Нет, потерь почти нет. Теряется только некоторая часть мета-информации, если честно не помню, что в ней храниться.

По поводу "без прогрузки движка" (если правильно понял мысли автора) - если у объекта есть модифицируемые движком пространственные характеристики (U скриптами или анимацией, например), разве с этим не будет проблем ? Сходу вспоминаются водяные колеса у Хейне, но наверняка есть объекты позаковырестее.

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

[Deazer]

Пожалуй предложу тебе уйти от сравнений в "Lineage" , думай о алгоритме как о методе применения в реальной жизни.

[n3k0nation]

Пожалуй предложу тебе уйти от сравнений в "Lineage" , думай о алгоритме как о методе применения в реальной жизни.

Это уже было в теме "Патчфинд 2.0" ;D
Реальная модель поиска пути у меня есть, в принципе, как и куча эксперементальных проектов с различными алгоритмами поиска пути, которые никак не связаны ограничениями ладвы, доходя до таких штук: многопоточные эврестические двунаправленные алгоритмы поиска пути в 3D пространстве (привет функциональные языки программирования!), но это так, к слову.
Соль этой темы наложить на мою модель патчфинда ограничения ладвы, в условиях выполнения на серверной стороне, плюс более или менее рассортировать свои мысли такой "ограниченной" модели.
При этом модель включает не только саму алгоритмику и устройство поиска пути, но и карту проходимости, из которой возможно создание динамической модели цены каждой точки.

[n3k0nation]

Пятничный БАМП.

[rage]

Делать дополнительный непроходимый слой, который находится от модели потолка до слоя, который выше. Это если без особых костылей.

Это самый, огромный костыль и есть! Похоже те, кто писал гео-двиг в л2ж так и рассуждали
Не говоря уже о том, что применительно к л2 такой подход просто не реален.

На самом деле, если игрок находится в воде, то ограничивать перемещение нужно по Z макс поверхности воды. Если есть слой потолка ниже Z воды то ясен хрен, что через него "просочиться наверх" нельзя.

Да и по идее в оригинале оно должно выглядеть, как-то так. Проблема в том, что в l2j нет поиска 3D пути (для полетов и плаванья), в данном случае нам нужно делать поправку на 3D'шный поиск пути и опять же высчитывать разницу уровней (слоев) с поправкой на упор, в модель потолка (MAX_Z_FOR_THIS_LAYER - PLAYER_HEIGHT - CONST, где константу нужно подобрать опытным путем, я не думаю, что она будет больше 10), если мы ее превышаем, то попасть в точку назначения нельзя и мы меняем эту точку на ближайшую, на данном слое (чтобы не стоять на месте, если тыкнуть в потолок).

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

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

[n3k0nation]

Это самый, огромный костыль и есть! Похоже те, кто писал гео-двиг в л2ж так и рассуждали
Не говоря уже о том, что применительно к л2 такой подход просто не реален.

На самом деле, если игрок находится в воде, то ограничивать перемещение нужно по Z макс поверхности воды. Если есть слой потолка ниже Z воды то ясен хрен, что через него "просочиться наверх" нельзя.

Сама вода должна играть меньший приоритет, чем многослойность. Пример.



Хотя Вы это и так написали. *slow* Если есть идеи другово подхода, то пишите, т.к. у меня их особо нет для данного случая, то что я думаю - уже описал.

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

Мы же говорим, приоритетно, про джаву и там нет 3D поиска пути. Да, в воде текущий поиск пути справляется, но достаточно сесть на виверну и полетать по проблемным местам.
Т.е. другими словами, коллизии - нахрен не нужны и фиг с этими дверьми?

[rage]

Сама вода должна играть меньший приоритет, чем многослойность. Пример.



Хотя Вы это и так написали. *slow* Если есть идеи другово подхода, то пишите, т.к. у меня их особо нет для данного случая, то что я думаю - уже описал.

Какие могут быть еще идеи? Уперся в потолок "не плыви", уперся в Z max воды тоже "не плыви". Это простейший кейс, тут никакой супер логики не нужно. Вернее плыви но не выше Z max которая в данном случае либо слой потолка либо воды.

Мы же говорим, приоритетно, про джаву и там нет 3D поиска пути. Да, в воде текущий поиск пути справляется, но достаточно сесть на виверну и полетать по проблемным местам.
Т.е. другими словами, коллизии - нахрен не нужны и фиг с этими дверьми?

Коллизии между чем и чем? С полетами тоже все более-менее на нормальных движках

Двери в разных сборках работают по разному, не знаю как сейчас в л2жсервер, но раньше там пробивалось пересечение прямой с плоскостью двери. В овероподобных двери закрываются по гео.
В случае с л2ж ваще не вариант, и даже туда смотреть не хочется.
В случае закрытия двери по гео, что мешает раз в N шагов делать речек оставшегося пути? Полностью проблему не решит, но этот кейс и так редкий станет еще реже.

Лично у меня при просчете пути в мов двиг возвращается набор точек по которым перс будет идти, по моему в фене так же, но не суть. При этом ничего не мешает проверять NSWE у точки хоть при каждом тике, операция не такая уж и дорогая.

[n3k0nation]

Двери в разных сборках работают по разному, не знаю как сейчас в л2жсервер, но раньше там пробивалось пересечение прямой с плоскостью двери. В овероподобных двери закрываются по гео.
В случае с л2ж ваще не вариант, и даже туда смотреть не хочется.
В случае закрытия двери по гео, что мешает раз в N шагов делать речек оставшегося пути? Полностью проблему не решит, но этот кейс и так редкий станет еще реже.

Лично у меня при просчете пути в мов двиг возвращается набор точек по которым перс будет идти, по моему в фене так же, но не суть. При этом ничего не мешает проверять NSWE у точки хоть при каждом тике, операция не такая уж и дорогая.

Зачем это делать, если можно использовать за основу эвристику? Ее реализацию я описал в начале топика: использование событийной архитектуры.