Давненько я не создавал тем на ЗГ ;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: тему буду время от времени обновлять
---------------------------------------------
Если Вы хотите написать: "зачем тебе это надо ТС? пусть все будет как есть", то лучше тыкните мне минус в карму и не пишите такой пост, иначе минус тыкну уже я.