MasterToma добавил(а) новый ресурс:
[C1] PathMaker - PathMaker для C1
Узнать больше об этом ресурсе...
[C1] PathMaker - PathMaker для C1
Узнать больше об этом ресурсе...
Последнее редактирование модератором:
PathMaker 1.0.16.0
- Автор темы MasterToma
- Дата начала
Привет, наконец-то добрался до генерации path-node'ов для С1. Из известных мне ликов, первый PathMaker.exe был для С4, по-этому я базировался на нем.
Принцип генерации path-node'ов - расчет вершин, и связей между ними, т.е. такая компиляция гео-даты - все варианты, откуда куда можно пройти, а если нельзя, то как добраться до следующей вершини (то, что в L2J делается в рантайме, в PTS сделано на этапе подотовки геодаты. Оно и понятно, в рантайме геодата практически не меняется (исключения - двери, ламающиеся стены и проч). Коллизии с другими существами берутся под внимание уже в рантайме.
Различия С1-С4 генераторов
1. Гео-движок С1 и С4 немного отличаются (в С4 меньше шансов застрять в углах или прилипнуть к стенам). Соответственно, С4 PathMaker.exe (который использует геодвижок для тестов "перемещения") генерит немного другой граф,
чем С1 (с учетом фиксов на прилипания и углы)
2. В С1 не было SuperPoint'ов (были way-points вместо них), соотв. С1 этого не поддерживает, в отличие от С4
3. В С1 заложили размер геодаты 30х26, на вырост. И если сам гео-движок был оптимизирован в плане памяти и выделял RAM только на загруженные зоны, специфика PathMaker такова, что он работал по всем клеткам. Т.е. С1 PathMaker отжирал чуть больше RAM, и чуть дольше итерировался (хотя пустые зоны быстро пропускал)
4. Формат логов был немного изменен в С4.
Различия С4-HFx64 генераторов
1. Максимальная зона Y увеличилась на +1
2. Гео-алгоритм не менялся (MD5 для pathnode.bin на полном сете из гео-зон давал тот же результат что и С4)
3. Логи стали более информативны, хотя для рядового админа они все равно ни о чем.
4. х64 - значит можно грузить больше гео в RAM. + незначительные приимущества, связанные с х64 тулсэтом.
Еще существует какой-то хекснутый "PathMaker - Fixed (Load all Geo) C4", пока не понял, что именно там "пофикшено"
Как всем вам известно, мои работы не несут абсолютно никакой практической пользы, скорее академическую. Это больше похоже на новости плана "ученые вычислили, что видимая часть вселенной существует 100500 миллиардов лет". Однако, в случае с PathMaker его оказалось прям таки очень легко адаптировать аж под HF x64 (константу изменить и тулсет настроить). Алгоритм корейцев зубодробительный, множество сверток графов для оптимизаций, так что я думаю, его как написали в далеком 2002м (для С0 же), так с того момента и не меняли (изменение в геодвиге на рубеже С4 не в счет, геодвиг != PathMaker).
Принцип генерации path-node'ов - расчет вершин, и связей между ними, т.е. такая компиляция гео-даты - все варианты, откуда куда можно пройти, а если нельзя, то как добраться до следующей вершини (то, что в L2J делается в рантайме, в PTS сделано на этапе подотовки геодаты. Оно и понятно, в рантайме геодата практически не меняется (исключения - двери, ламающиеся стены и проч). Коллизии с другими существами берутся под внимание уже в рантайме.
Различия С1-С4 генераторов
1. Гео-движок С1 и С4 немного отличаются (в С4 меньше шансов застрять в углах или прилипнуть к стенам). Соответственно, С4 PathMaker.exe (который использует геодвижок для тестов "перемещения") генерит немного другой граф,
чем С1 (с учетом фиксов на прилипания и углы)
2. В С1 не было SuperPoint'ов (были way-points вместо них), соотв. С1 этого не поддерживает, в отличие от С4
3. В С1 заложили размер геодаты 30х26, на вырост. И если сам гео-движок был оптимизирован в плане памяти и выделял RAM только на загруженные зоны, специфика PathMaker такова, что он работал по всем клеткам. Т.е. С1 PathMaker отжирал чуть больше RAM, и чуть дольше итерировался (хотя пустые зоны быстро пропускал)
4. Формат логов был немного изменен в С4.
Различия С4-HFx64 генераторов
1. Максимальная зона Y увеличилась на +1
2. Гео-алгоритм не менялся (MD5 для pathnode.bin на полном сете из гео-зон давал тот же результат что и С4)
3. Логи стали более информативны, хотя для рядового админа они все равно ни о чем.
4. х64 - значит можно грузить больше гео в RAM. + незначительные приимущества, связанные с х64 тулсэтом.
Еще существует какой-то хекснутый "PathMaker - Fixed (Load all Geo) C4", пока не понял, что именно там "пофикшено"
Как всем вам известно, мои работы не несут абсолютно никакой практической пользы, скорее академическую. Это больше похоже на новости плана "ученые вычислили, что видимая часть вселенной существует 100500 миллиардов лет". Однако, в случае с PathMaker его оказалось прям таки очень легко адаптировать аж под HF x64 (константу изменить и тулсет настроить). Алгоритм корейцев зубодробительный, множество сверток графов для оптимизаций, так что я думаю, его как написали в далеком 2002м (для С0 же), так с того момента и не меняли (изменение в геодвиге на рубеже С4 не в счет, геодвиг != PathMaker).
Уже третий человек спрашивает на чем именно я базировался. Ответы задаются не спроста, в сети ходит около 5 шаренных PathMaker'ов.
Вот
Вот
Вы не можете просматривать ссылку пожалуйста воспользуйтесь следующими ссылками Вход или Регистрация
, чем они разнятся, и какой для каких хроник использовать.
Тов. ТС, а чем вы занимаетесь? может проекты там какие, али новые хроники? или неужто только ц1 некрофилите?
Все просто.
С1 мне не нужен мне нужен как минимум С4, а в планах ГФ (движок уже обкатан, стабилен, и детские болезни с багами пофикшены в основном).
Насколько мне известно, ни у кого, кроме корейцев, не было исходников ГФ или хотя бы С4. Декомпильнуть с нуля С4 на 100% (как у меня С1) очень сложно по следующим причинам
Кто-то пазлы собирает, кто-то сериалы смотрит.
Насколько мне известно, ни у кого, кроме корейцев, не было исходников ГФ или хотя бы С4. Декомпильнуть с нуля С4 на 100% (как у меня С1) очень сложно по следующим причинам
- С4/ГФ собирался новым тулсетом, с более агрессивными опциями компилятора для оптимизаций и доп. проверок (stack smashing, overflow cookies, address decryption и тд). Элементарные вещи компилятор так завернет, что не докопаешься
- х64 - более сложные инструкции (хотя код исходный тот же)
- Специфика гейм-дева - очень тяжело тестировать. Поэтому если что-то работает, они это не меняют. NCSoft пишет новые методы методом копи-пасты для расширения функционала. Я смотрел как-то на ГОД - там вся инфраструктура от С1 осталась, только логи добавили. Фиксы если и были - то точечные.
- С Л2 сервере НЕ было рефакторинга. По крайней мере до GF (в GD лоадер вынесли, гео подправили, но это отдельная история) - это С1 кодовая база + точечные фиксы старого + новый функционал
- В новых хрониках очень много функционала, но код весь связан между собой. Т.е. чтобы сделать что-то работостособное, надо восстановить ВСЮ бинарку.
- Максимально чистый АСМ, так как компилятор MS Visual Studio 6 был настолько убогий, что с++ код переводил в асм как есть. Результат - отлично читающаяся IDA
- Минимум фич (С0 -> С1 и С1->С4 большая разница), значит быстрее можно закончить всю бинарку, быстрее начать тестировать, меньше скоуп работ и тд
- Многие тулзы достались нам ТОЛЬКО от С0. Они работают с С0-С1 кодовой базой, значит для их переноса на новые хроники и так надо было бы копать эту базу.
- Дальше - портирование. У меня уже есть разобраные полностью С4 L2Auth L2LogD и так на 20% CacheD. Просто открыть две ИДЫ (с1 и с4) и механически переносить слева направо... Очень четко видны изменения в коде, а так же легко детектится мусор новых компиляторов и х64 сборки
Кто-то пазлы собирает, кто-то сериалы смотрит.
Для @sergebaz , и всех остальных, которые просили от меня "формулы" по геодате.
Выкладываю алгоритм работы PathMaker'а. Он не изменялся со времен С1 до GD как минимум. MD5 чек-сумма файла pathnode.bin с моего (С1) и GD PathMaker'а та же самая, индексы только с GF-H5 изменились, так как там 27-y добавился. В новых хрониках не видел, не знаю.
Мужики, запилитемне дверь уже его под L2J-подобные!
Думаю, формат геодаты не надо объяснять, он открыт, но все же: Гео-зона состоит из клеток 16х16 единиц, клетка - это минимальная дискретная единица карты с клиента. Итак,
1. Цикл по каждой клетке, ищем первую клетку, которая имеет закрытый проход в одну сторону
2. Начинаем делать два траверса вдоль припятствия (по и против часовой стрелок). Вы в пещеры ходили? Стену надо держать левой или правой рукой (руку не менять!!). Зачем два траверса? Потому что персонаж может хотеть на юго-восток (см рисунок) или северо-восток (этот траверс на самом крупном плане пропущен, но виден на среднем плане)
3. Идем вдоль препятствия, пока не дойдем до клетки, которая позволит двигаться в ту же сторону (Восток в нашем случае), но уже на открытой местности, т.е. соседние направления тоже открыты). Ура, вы нашли два пути, как обойти препятствие с востока, двигаясь на юго и северо-восток.
4. Теперь у вас есть "змейка" клеток. Вы "скомпилировали" геодату, переведя из формата "клетки" в пространственный формат "вершины и ребра" (Nodes - links), т.е. получили информацию как из одной вершины добраться до другой в целом мире LineageII. Каждая вершина имеет от 0 до 8 братьев, к которым можно через нее добраться по ребрам (право-лево, верх-низ, диагонали).
5. Эта информация используется A-* алгоритмом поиска пути
БОльшую часть из него делает PathMaker, избавляя run-time от множества расчетов (по сути, строит синие точки, которые на gif'ке выше обозначают препятствие, и варианты обхода синих точек).
6. Run-time получает 2 точки (А -> В). Через хитрожопую look-up table получает две пространственные вершины (Node). Через вычитание векторов (привет, 5ый класс) получает направление. Зная направление, движится по вершинам, от А к В, используя ее ребра для перемещения. Когда попадает в нужную вершину, просто прокладывает прямой путь до точки В. Путь построен.
Оптимизации:
PathMaker оптимизирует путь, смердживая до 20 клеток в одну PathNode'у.
PS: @kick, измени плз название темы на [C1-С4] PathMaker, так как он совместим с С4 полностью
Выкладываю алгоритм работы PathMaker'а. Он не изменялся со времен С1 до GD как минимум. MD5 чек-сумма файла pathnode.bin с моего (С1) и GD PathMaker'а та же самая, индексы только с GF-H5 изменились, так как там 27-y добавился. В новых хрониках не видел, не знаю.
Мужики, запилите
Думаю, формат геодаты не надо объяснять, он открыт, но все же: Гео-зона состоит из клеток 16х16 единиц, клетка - это минимальная дискретная единица карты с клиента. Итак,
1. Цикл по каждой клетке, ищем первую клетку, которая имеет закрытый проход в одну сторону
2. Начинаем делать два траверса вдоль припятствия (по и против часовой стрелок). Вы в пещеры ходили? Стену надо держать левой или правой рукой (руку не менять!!). Зачем два траверса? Потому что персонаж может хотеть на юго-восток (см рисунок) или северо-восток (этот траверс на самом крупном плане пропущен, но виден на среднем плане)
3. Идем вдоль препятствия, пока не дойдем до клетки, которая позволит двигаться в ту же сторону (Восток в нашем случае), но уже на открытой местности, т.е. соседние направления тоже открыты). Ура, вы нашли два пути, как обойти препятствие с востока, двигаясь на юго и северо-восток.
4. Теперь у вас есть "змейка" клеток. Вы "скомпилировали" геодату, переведя из формата "клетки" в пространственный формат "вершины и ребра" (Nodes - links), т.е. получили информацию как из одной вершины добраться до другой в целом мире LineageII. Каждая вершина имеет от 0 до 8 братьев, к которым можно через нее добраться по ребрам (право-лево, верх-низ, диагонали).
5. Эта информация используется A-* алгоритмом поиска пути
БОльшую часть из него делает PathMaker, избавляя run-time от множества расчетов (по сути, строит синие точки, которые на gif'ке выше обозначают препятствие, и варианты обхода синих точек).
6. Run-time получает 2 точки (А -> В). Через хитрожопую look-up table получает две пространственные вершины (Node). Через вычитание векторов (привет, 5ый класс) получает направление. Зная направление, движится по вершинам, от А к В, используя ее ребра для перемещения. Когда попадает в нужную вершину, просто прокладывает прямой путь до точки В. Путь построен.
Оптимизации:
PathMaker оптимизирует путь, смердживая до 20 клеток в одну PathNode'у.
PS: @kick, измени плз название темы на [C1-С4] PathMaker, так как он совместим с С4 полностью
А где-то можно почитать, или имеется в виду L2J?
Еще интересно, как это дело работает в многоуровневых локациях, когда фактически клетка может быть под клеткой. Что-то вроде приведения в одну плоскость происходит?
L2J формат немного отличается от PTS, как в плане файлов так и в плане структур данных. Формат файлов геодаты от PTS можно посмотреть в PTS -> L2J конвертерах, их полно валяется. По поводу структур данных - я делал детальное его описание, но под заказ, так сказать, не для паблика.
Переход между уровнями осуществляется в специальном типе сектора (не путать с секцией). Выглядит это примерно так - если для текущей x-y клетки есть другие уровни по Z - рекурсивно начинаем траверс с этой клетки. Для уровня есть трешхолд в 32 единицы (типа ступеньки, они могут быть до 30 - это персонаж еще может перепрыгнуть, а вот 33+ - это непроходимое препятствие)
MasterToma обновил(а) ресурс [C1] PathMaker новой записью:
x_26 support (GF+)
Узнать больше об этом обновлении...
x_26 support (GF+)
Узнать больше об этом обновлении...
@MasterToma, а не разбирали случайно формат хранения инфы в pathnode.bin?
Я в старших хронах нашел промежуточный pathnode.txt и исходя из мысли, что PathMaker64.exe до бита одинаковый в ХФ и 287 слитом, могу предположить, что это актуально для обеих хроник.
В pathnode.txt я вижу графы, с координатами узлов и списком потомков.
Т.е можно предположить, что эта инфа хранится и pathnode.bin, но в бинарном виде.
Я в старших хронах нашел промежуточный pathnode.txt и исходя из мысли, что PathMaker64.exe до бита одинаковый в ХФ и 287 слитом, могу предположить, что это актуально для обеих хроник.
В pathnode.txt я вижу графы, с координатами узлов и списком потомков.
Код:
--- Section(168448,-96256) Count(15) ---
13239601 : (168664 -96056 2328) (8) - 13239602 13239617 13239603 13238266 13239604 13238267 13239605 13238268
13239602 : (168648 -96056 2304) (8) - 13239603 13239617 13239604 13238266 13239605 13238267 13239607 13238268
13239603 : (168632 -96056 2280) (8) - 13239604 13239617 13239605 13238266 13239607 13238267 13239608 13238268
13239604 : (168616 -96056 2264) (8) - 13239605 13239617 13239607 13238266 13239608 13238267 13239609 13238268
13239605 : (168600 -96056 2240) (8) - 13239607 13239617 13239608 13238266 13239609 13238267 13239610 13238268
13239606 : (168680 -96088 2376) (8) - 13239604 13239601 13239605 13239602 13239607 13239603 13239614 13239616
13239607 : (168584 -96056 2216) (8) - 13239608 13239617 13239609 13238266 13239610 13238267 13239611 13238268
13239608 : (168568 -96056 2192) (8) - 13239609 13239617 13239610 13238266 13239611 13238267 13239612 13238268
13239609 : (168536 -96056 2160) (8) - 13239610 13238266 13239611 13238267 13239612 13238268 13239613 13238269
13239610 : (168520 -96056 2144) (8) - 13239611 13238266 13239612 13238267 13239613 13238268 13239615 13238269
13239611 : (168504 -96056 2120) (8) - 13239612 13238266 13239613 13238267 13239615 13238268 13238259 13238269
13239612 : (168488 -96056 2096) (8) - 13239613 13238266 13239615 13238267 13238259 13238268 13238260 13238269
13239613 : (168472 -96056 2072) (8) - 13239615 13238266 13238259 13238267 13238260 13238268 13238261 13238269
13239614 : (168552 -96088 2216) (8) - 13239612 13239609 13239613 13239610 13239615 13239611 13238259 13239617
13239615 : (168456 -96056 2048) (8) - 13238259 13238266 13238260 13238267 13238261 13238268 13238262 13238269Т.е можно предположить, что эта инфа хранится и pathnode.bin, но в бинарном виде.
Так и есть. Оригинальный PathMaker.exe от С4 тоже при генерации выкитывает в текстовом виде - это для дебага видимо, или для какой-то диагностики. А в бине хранится тоже самое, но в бинарном формате, как вы и сказали.
@MasterToma, спасибо. Как я понял, веса он не хранит, а только использует при генерации графов, а в реалтайме там уже не A*, а Дейкстра.
@MasterToma, вообщем разобрал я бинарь pathnode.bin этот, подгрузил данные из него и чутка визуализировал. Пока не складывается в моей голове пазл, зачем это все нужно, как наши корейские друзья это используют и в чем преимущество, по сравнению с рантайм обсчетом по данным из геодаты напрямую, кроме сомнительной выгоды по CPU(очень сомнительной).
Видос прикладываю, возможно есть у кого-то мысли по этому поводу.
Хотя вот на многослойных блоках траектория явно получше, чем мой алгоритм считает.
@MasterToma, вообщем разобрал я бинарь pathnode.bin этот, подгрузил данные из него и чутка визуализировал. Пока не складывается в моей голове пазл, зачем это все нужно, как наши корейские друзья это используют и в чем преимущество, по сравнению с рантайм обсчетом по данным из геодаты напрямую, кроме сомнительной выгоды по CPU(очень сомнительной).
Видос прикладываю, возможно есть у кого-то мысли по этому поводу.
Хотя вот на многослойных блоках траектория явно получше, чем мой алгоритм считает.
Последнее редактирование модератором:
Видимо, чтобы не считать в рантайме то, что можно посчитать заранее.
На тысячах игроков и мобов, на процессорах времен л2, это не так уж и мало.
Это в целом нормальная практика, вытаскивать из рантайма подобное, особенно если это не дает сильный оверхед по памяти.
Я понимаю это, но считать там все считает и почти тоже самое. Я сейчас смотрю код алгоритма поиска пути в ПТСке и вижу там ровно такие же обсчеты в рантайме, для большей части пути.
Вот условно "явофицированый" метод(мне так проще его воспринимать, чтобы не переключаться в голове с плюсов на яву и обратно), можешь посмотреть сам.
Если так, то тоже интересно. Последний раз, когда я заглядывал в код жабы тыщу лет назад, там был тупой поиск пути по сетке, даже без кеширования графа.
Сетка это тот же граф, просто с намного большим количеством нод, которые на практике не нужны, так как большинство из них связаны с соседями. Интерес представляют только ноды рядом с препятствиями.
Как я вижу цель PathNode - просто уменьшить количество перебираемых нод для поиска пути.
Вы не можете просматривать ссылку пожалуйста воспользуйтесь следующими ссылками Вход или Регистрация
- здесь есть интерактивная карта в самом начале статьи, которую можно редактировать, там явно видно различие в сложности поиска пути для сетки и графа.Если сейчас в жабах что-то подобное реализовано, то действительно, смысла в дополнительных механизмах не много.
