Патчфинд 3.0
Давненько я не создавал тем на ЗГ ;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: тему буду время от времени обновлять --------------------------------------------- Если Вы хотите написать: "зачем тебе это надо ТС? пусть все будет как есть", то лучше тыкните мне минус в карму и не пишите такой пост, иначе минус тыкну уже я. |
Re: Патчфинд 3.0
Раз уж речь зашла про геодвижок, есть пара вопросов.
В GoE entrance есть потолок, которого нет в геодате (L2J формат). Т.е. есть слои выступов уже в помещении (с водой), есть слой поверхности над локацией. И вот что-то не помню, на птсах с этим проблемы были или нет. По идее два выхода из ситуации - блокировать перемещение вверх по Z, если в воде, если Z поверхности минус Z игрока меньше допустимого значения. Тогда если игрок тыкает в потолок, то может сделать релог и встрять (клиент не даст ткнуть вниз, а наверх выплыть не сможет из-за ограничения). Второй вариант - не блокировать перемещение, игрок не встрянет, но сможет выплыть из помещения на поверхность. Как-то можно решить эту проблему с текущим раскладом (L2J геодата) ? И второй вопрос - с ПТСами не пересекался вообще, беглый поиск не дал результатов - как хранится гео в conv.dat, есть ли потери при конверте в L2J ? По поводу "без прогрузки движка" (если правильно понял мысли автора) - если у объекта есть модифицируемые движком пространственные характеристики (U скриптами или анимацией, например), разве с этим не будет проблем ? Сходу вспоминаются водяные колеса у Хейне, но наверняка есть объекты позаковырестее. |
Re: Патчфинд 3.0
Ну и ладно, буду сам с собой разговаривать :redlol:
На самом деле про размер я немного преврал. Такой размер получится только в максимально плохом случае, так как не все локации имеют многоуровневую структуру, соответственно во многих местах не требуется создавать слои. В любом случае, даже такой вариант, с максимальным размером очень наглядно показывает проблему, которую я описывал. Добавлено через 12 минут Цитата:
Да и по идее в оригинале оно должно выглядеть, как-то так. Проблема в том, что в l2j нет поиска 3D пути (для полетов и плаванья), в данном случае нам нужно делать поправку на 3D'шный поиск пути и опять же высчитывать разницу уровней (слоев) с поправкой на упор, в модель потолка (MAX_Z_FOR_THIS_LAYER - PLAYER_HEIGHT - CONST, где константу нужно подобрать опытным путем, я не думаю, что она будет больше 10), если мы ее превышаем, то попасть в точку назначения нельзя и мы меняем эту точку на ближайшую, на данном слое (чтобы не стоять на месте, если тыкнуть в потолок). Цитата:
Цитата:
|
Re: Патчфинд 3.0
Пожалуй предложу тебе уйти от сравнений в "Lineage" , думай о алгоритме как о методе применения в реальной жизни.
|
Re: Патчфинд 3.0
Цитата:
Реальная модель поиска пути у меня есть, в принципе, как и куча эксперементальных проектов с различными алгоритмами поиска пути, которые никак не связаны ограничениями ладвы, доходя до таких штук: многопоточные эврестические двунаправленные алгоритмы поиска пути в 3D пространстве (привет функциональные языки программирования!), но это так, к слову. Соль этой темы наложить на мою модель патчфинда ограничения ладвы, в условиях выполнения на серверной стороне, плюс более или менее рассортировать свои мысли такой "ограниченной" модели. При этом модель включает не только саму алгоритмику и устройство поиска пути, но и карту проходимости, из которой возможно создание динамической модели цены каждой точки. |
Re: Патчфинд 3.0
Пятничный БАМП.
|
Re: Патчфинд 3.0
Цитата:
Не говоря уже о том, что применительно к л2 такой подход просто не реален. На самом деле, если игрок находится в воде, то ограничивать перемещение нужно по Z макс поверхности воды. Если есть слой потолка ниже Z воды то ясен хрен, что через него "просочиться наверх" нельзя. Цитата:
В л2 нет таких мест, что бы два слоя сходились на такую высоту, что там мог бы пройти гном и не мог пройти ушастый. |
Re: Патчфинд 3.0
Цитата:
http://screenshot.ru/upload/images/2...23/hmkiU8A.png Хотя Вы это и так написали. *slow* Если есть идеи другово подхода, то пишите, т.к. у меня их особо нет для данного случая, то что я думаю - уже описал. Цитата:
Т.е. другими словами, коллизии - нахрен не нужны и фиг с этими дверьми? :D |
Re: Патчфинд 3.0
Цитата:
Цитата:
Двери в разных сборках работают по разному, не знаю как сейчас в л2жсервер, но раньше там пробивалось пересечение прямой с плоскостью двери. В овероподобных двери закрываются по гео. В случае с л2ж ваще не вариант, и даже туда смотреть не хочется. В случае закрытия двери по гео, что мешает раз в N шагов делать речек оставшегося пути? Полностью проблему не решит, но этот кейс и так редкий станет еще реже. Лично у меня при просчете пути в мов двиг возвращается набор точек по которым перс будет идти, по моему в фене так же, но не суть. При этом ничего не мешает проверять NSWE у точки хоть при каждом тике, операция не такая уж и дорогая. |
Re: Патчфинд 3.0
Цитата:
|
Текущее время: 17:30. Часовой пояс GMT +3. |
Powered by vBulletin® Version 3.8.6
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot