Нужна помощь с гео (LostWorld)

[pvpgate 11]

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

Теперь подробности
У меня в сборке персонаж довольно странно взамодействует с гоедатой, когда речь заходит о поиске пути:
Вот так оббегает у меня углы (если расстояние от угла до стартовой и финишной точки более 3 ячеек геодаты (ДИАГОНАЛЬНЫЙ ПОИСК В ПРИМЕРАХ ОТКЛЮЧЕН ДЛЯ УПРОЩЕНИЯ. С НИМ ПРОИСХОДИТ ТО ЖЕ САМОЕ, ТОЛЬКО УГЛЫ В НАЧАЛЕ И КОНЦЕ СРЕЗАЮТСЯ ПО ДИАГОНАЛЕ):

Персонаж делает крюк, пытаясь находится на растоянии 2(в третем) ячейки геодаты от стен.
На картинке схематично показан алгоритм работы поиска пути из моего геодвижка (волновй алгоритм, по логике путь должен лежать вдоль стен по возрастанию цифр)
Если расстояние от угла до старта и финиша 3 и менее ячеек путь находится корректно:

Если расстояние от угла до начала более 3 ячеек, а до конца 3 ячейки, то до угла персонаж будет держаться на расстоянии 2 ячеек, а после на расстоянии одной ячейки:

Если расстояние от угла до начала более 3 ячеек а до конца 2, то первую часть пути персонаж будет держаться на расстоянии 2 ячеек, а потом вплотную к стене:

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


Вплотную к стене подбежать можно, и бежать вдоль нее тоже (если не задействован поиск пути)
В архиве прилагаю свой геодвижок + creature (на всякий случай): http://rgho.st/67LhC5X9V
Ниже описание методов которые я разобрал:

geoMove.findMovePath() //собственно вызывается при поиске пути
PathFind.findPath()  //вызывается в методе выше, отдает лист точек path
PathFind.handleNode() //в зависимости от типа ячейки (и того включен ли диагональный поиск) выбирает ближайшие ячейки вокруг
PathFind.handleNeighbour() //вызывается методом handleNode(), проставляет для ячеек значение пути и т.д.
PathFind.tracePath() //после того как handleNeighbor достиг точки назначения начинает с конца в начало восстанавливать путь, выбирая для каждой ячейки "родительскую"
GeoNegine.MoveList() // проверяет лист path из FindPath() на возможность пройти по нему, возвращает лист точек (если все впорядке - идентичный path, судя по всему)

Буду безмерно благодарен за любые подсказки. Если кто ткнет носом в конкретное место с меня отдельное спасибо, ну и на пиво рублей 500 (вряд ли конечно будет серьезным мотиватором, но чем могу...)

Изменено 24 июля, 2018 пользователем pvpgate

[gawric 49]

не пробовал в коде вывести цифру конечного веса пути? он же где-то должен перебирать каким путем лучше добежать до точки.

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

[pvpgate 11]

12 часов назад, gawric сказал:

не пробовал в коде вывести цифру конечного веса пути? он же где-то должен перебирать каким путем лучше добежать до точки.

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

не совсем. Он использует волновой алгоритм, начиная от начальной точки он для всех соседних точек проставляет путь = пути от предыдущей +1 (в случае с диагональю - ~1.4, но для тестов я отключил диагональный поиск). Если соседняя точка уже занята (ей проставлено значение пути от другой точки) он сравнивает это значение с тем, которое может записать. Если он может записать меньшее значение - перезаписывает. Кроме того для каждой след. точки предыдущая (из которой в нее проставлено значение) записывается как родительская (parent). Таким образом волна распространяется от начальной точки во все стороны пока не окажется что очередная точка это точка финиша. После этого, начиная от финишной точки, выбирается ее "родительская" точка, для нее - ее родительская, и так пока не упремся в стартовую точку. На этом путь считается проложенным. Сейчас начал логировать путь в методе GeoMove.findMovePath() и отрисовывать его, впринципе все то же самое выходит, только путь строится до середины геоноды, поэтому возникает такой "хвост" в конце (справа на скрине)

К сожалению мне туговато дается java без особого опыта в программировании, так что пока не слишком получается логировать на всех этапах, т.к. лог забивается поиском пути для всех ресающихся мобов, а в методе findMovePath() в качестве агрумента передается игрок и можно отрисовывать только для isPlayable()...

Изменено 2 августа, 2018 пользователем pvpgate

[gawric 49]

14 часов назад, pvpgate сказал:

не совсем. Он использует волновой алгоритм, начиная от начальной точки он для всех соседних точек проставляет путь = пути от предыдущей +1 (в случае с диагональю - ~1.4, но для тестов я отключил диагональный поиск). Если соседняя точка уже занята (ей проставлено значение пути от другой точки) он сравнивает это значение с тем, которое может записать. Если он может записать меньшее значение - перезаписывает. Кроме того для каждой след. точки предыдущая (из которой в нее проставлено значение) записывается как родительская (parent). Таким образом волна распространяется от начальной точки во все стороны пока не окажется что очередная точка это точка финиша. После этого, начиная от финишной точки, выбирается ее "родительская" точка, для нее - ее родительская, и так пока не упремся в стартовую точку. На этом путь считается проложенным. Сейчас начал логировать путь в методе GeoMove.findMovePath() и отрисовывать его, впринципе все то же самое выходит, только путь строится до середины геоноды, поэтому возникает такой "хвост" в конце (справа на скрине)

К сожалению мне туговато дается java без особого опыта в программировании, так что пока не слишком получается логировать на всех этапах, т.к. лог забивается поиском пути для всех ресающихся мобов, а в методе findMovePath() в качестве агрумента передается игрок и можно отрисовывать только для isPlayable()...

на сколько я знаю у каждого объекта игрок или моб есть свой ID, почему бы просто в поиске не сделать проверку только по определенному игроку или мобу, а все остальное отбросить?

[gawric 49]

14 часов назад, pvpgate сказал:

 

Изменено 3 августа, 2018 пользователем gawric

[pvpgate 11]

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

[gawric 49]

Только что, pvpgate сказал:

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

ну возможно кто-то тоже встанет на таком вопросе, может отписать ответ?

[pvpgate 11]

5 часов назад, gawric сказал:

ну возможно кто-то тоже встанет на таком вопросе, может отписать ответ?

Алгоритм поиска пути как я и описывал - волновой. Но вот "вес" или расстояние для каждой следующей точки считается не просто как расстояние до предыдущей +1, а немного сложнее. В методе PathFind.traverseCost() расстояние увеличивается не на 1 а на 3 если точка вокруг которой ищется точка непроходима в одну из сторон

n.nswe != NSWE_ALL

 

а также увеличивается на 2 если точка вокруг которой ищется соседняя точка соседствует с непроходимой в одну из сторон точкой

getHeightAndNSWE(n.x + 1, n.y, n.z);
if(hNSWE[1] != NSWE_ALL || Math.abs(n.z - hNSWE[0]) > 16){ return 2f; }

getHeightAndNSWE(n.x - 1, n.y, n.z);
if(hNSWE[1] != NSWE_ALL || Math.abs(n.z - hNSWE[0]) > 16){ return 2f; }

getHeightAndNSWE(n.x, n.y + 1, n.z);
if(hNSWE[1] != NSWE_ALL || Math.abs(n.z - hNSWE[0]) > 16){ return 2f; }

getHeightAndNSWE(n.x, n.y - 1, n.z);
if(hNSWE[1] != NSWE_ALL || Math.abs(n.z - hNSWE[0]) > 16){ return 2f; }

 

ну и если расстояние по z > 16 тоже, но это наверно разумно оставить.
Однако, выпилив все эти условия понадобится переписывать pathClean() и намного тщательнее относиться к качеству геодаты. Может придется кое что изменить в диагональном поиске пути еще, посмотрим...

[PointerRage 132]

Если отключать увеличенный вес точек, которые граничат с непроходимыми элементами графа, то можно получить интересный кейс с диагональными точками, которые могут участвовать в конечном пути:

ooToo
oTxxx
oTxxx

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

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

 

И да, если серьезно, то вес точки -- это одно, а эвристика -- другое. Не следует путать теплое с мягким.