Идеально было бы:
1.) Код A
2.) Код на базе первого но уже JPS
3.) Я открываю в редахторе, и вижу различия, и начию догонять как работает алгоритм, и что мне нужно с делать в моем случае, что бы мой работающий A начал работать в режиме JPS
1.) Код A
2.) Код на базе первого но уже JPS
3.) Я открываю в редахторе, и вижу различия, и начию догонять как работает алгоритм, и что мне нужно с делать в моем случае, что бы мой работающий A начал работать в режиме JPS
был код не могу разобрать как он работает, хзхзхз
>solution.png (168Кб, 1802x1802)
Ха, а лабиринт то оче лёгкий, все тупиковые ответвления совсем коротенькие. Для любого днище алгоритма не составит труда пройти.
Я занимался пасфайндингом всё лето.
У тебя на картинке летающий объект в твоём случае это просто вид сверху, но для моей игры - это случай летающего объекта, на который не действует гравитация. Вот что сделал я, для того, чтобы моя самонаводящаяся ракета срезала углы.
Я ищу путь А* алгоритмом.
Когда путь найден, я записываю все найденные ноды в двумерный массив path. По x идёт номер нода, по y - вся информация о нём. В моём случае объекту необходимо знать ещё и каким способом попасть из одного нода в сосдений - прыжком, шагом, залезанием по лестнице, телепортацией, спрыгиванием с платформы и т.д. Но в твоём случае это не важно.
Когда ракета достигает очередного путевому нода "my_node", она делает проверку:
есть ли коллизия на путь к следующему ноду "my_node+1" или нет. Если коллизии нет - она выбирает следующий нод "my_node+2" и делает такую же проверку. Когда ракета находит такой нод, что между ней и ним есть коллизия по прямой линии, она возвращается к предыдущему ноду и делает его следующей путевой точкой, выкидывая из путь все остальные точки. Вот и всё.
Если ты хочешь сразу создать путь со срезами:
сначала создай полный путь.
затем пройдись по созданному пути подобным алгоритмом, записывая в отдельный массив путевые точки, которые ты не выкинул.
Вот этот отдельный массив и станет твоим путём.
У тебя конкретная задача какая?
В некоторых кейсах жпс будет сосать у обычного стара, в некоторых - прирост будет копеечный, а если у тебя агентов много или нод слишком дохуя - то тут вообще другим заниматься надо.
Хорошо, конкретная задача в следующем.
Дано:
Игра, где есть исходный код который использует A для зон 32х32 для поиска пути (сделано так, что бы не жрало дохрена ресурсов), используется B Bheap, и прочие оптимизации для максимального быстродействия А алгоритма.
Но вот незадача, максимальный размер карты 512х512 нод, в среднем карты по 300-400.
A в единичном случае отрабатывает довольно шустренько (на глаз), но при задействовании несольких десятков юнитов - проц уходит на 80-90% загрузки из-за как понимаете огромного класстера обрабатываемой информации (проход по всем открытым нодам, добавление в закрытые, проверки занята ли точка, добавления в heap, и так далее). Ну вы поняли.
на 32х32 зонах эти вычисления вообще не заметны, а вот на 512х512 начинается дикий пиздец.
И вот этот пиздец похуй как (самое простое решение - самое лучшее) нужно решить.
Т.е. загрузку проца необходимо снизить любой ценой с 90% до 2-3%, поэтому выбор пал на Jump Point Search.
Почему?
Потому что локации это не лабиринты, а города, где частенько между нодами по 50-60 клеток свободных, которые можно скипнуть, и получить перформанс.
Я пользовался тестером уже с готовой либой и приложением для своих локаций, результаты меня более чем порадовали.
Для мелких дистанций я все так же буду использоваться свой работающий А, а вот для больших нужно что-то нормальное, без лишнего мозгоебания и препроцессинга и так далее.
Поэтому и прошу помощи, так как не понимаю сути и механики JPS, если бы понимал - уже давно бы реализовал.
почему сделан лимит в 32х32 для АStar?
Этот алгоритм используется игровыми НПЦ, мобами, и так далее азличными юнитами, которые дальше чем 32х32 видить физически не могут.
Я же увеличил намеренно лимиты, что бы можно было ходить и строить пути за гранью видимости, и это ахуенно работает, но жрет сука ресурсов дохуя.
>между нодами по 50-60 клеток свободных
Думаю тебе стоит изменить свои ноды. Разбей карту на прямоугольники, внутри которых там можешь двигаться по прямой.
На пике могло бы быть 256 нодов-квадратов, но может быть и 9 нодов-прямоугольников.
Да, к одному ноду может прилегать не 8, а гораздо больше нодов. При создании нода запиши количество соседей в информацию о ноде, чтобы не искать максимально возможное число соседей.
Да, тебе придётся в грани записать параметры стенки, соединяющей два нода.
Да, при создании путевых точек тебе придётся выбрать оптимальную точку на линии, соединяющей ноды.
Но ты получишь большой выигрыш в производительности.
10 получилось, а не 9. Но не суть.
>внутри которых ты можешь двигаться по прямой, не встречая препятствий.
> при задействовании несольких десятков юнитов - проц уходит на 80-90%
Они у тебя каждый шаг путь ищут, что ли? Если тебе действительно нужно постоянно искать путь - запрети им искать его пока они не достигнут своей следующей путевой точки.
Тут действительно тебе достаточно нодой делать не тайл, а участок улицы. 10-15 нпц "внутри" ноды спокойно разойдутся тупым стирингом, если захочешь 100500 нпц - доебашишь векторфилды на каждую ноду ко всем соседним.
Жпс был бы смысл юзать, если бы у тебя город был размером с реальный. Но если для твоих целей его достаточно с нодой в тайл, и ты это точно застестил - то не еби мозги и юзай конечно.
А вот тебе ссылочка, как искать путь внутри нодов.
http://digestingduck.blogspot.ru/2010/03/simple-stupid-funnel-algorithm.html
нет, не каждый, а раз где-то в 10 клеток после перемещения (карта 500х500 клеток) и динамически изменяется, кто-то другой может стать на клетку, ранее не занятая клетка, может стать не проходимой, и так далее, поэтому чеки каждый раз необходимо делать.
Код реализовал, буста перформанса не наблюдаю существенного, но решение лабиринтов и сложных локаций стало быстрее в разы.
Но когда дохуя юнитов на карте (монстров \ нпц) которые используют алгоритм для перемещения - то тут такая же хуйня в плане использования ресурсов (правда в 2-3 раза меньше, но да похуй).
Заместо обновления Binary Heap, и тыканья в кучу и так далее, появились лишние действия с проверками клеток.
Т,е. поменялось шило на мыло немного, но алгоритм действительно работает, и работает ЛУЧШЕ чем А* во всех случаях которые мне необходимы.
Осталось дело за малым - профилирование, и решение проблем с довольно тяжелыми функциями которые дохуилярд раз чекают клетки.
Всем спасибо, не ожидал от двача адекватов, за что отдельная благодарочка.
Но когда дохуя юнитов на карте (монстров \ нпц) которые используют алгоритм для перемещения - то тут такая же хуйня в плане использования ресурсов (правда в 2-3 раза меньше, но да похуй).
Заместо обновления Binary Heap, и тыканья в кучу и так далее, появились лишние действия с проверками клеток.
Т,е. поменялось шило на мыло немного, но алгоритм действительно работает, и работает ЛУЧШЕ чем А* во всех случаях которые мне необходимы.
Осталось дело за малым - профилирование, и решение проблем с довольно тяжелыми функциями которые дохуилярд раз чекают клетки.
Всем спасибо, не ожидал от двача адекватов, за что отдельная благодарочка.
разбей перемещаемое пространство на регионы, регионы на подрегионы, сократи количество нод объединив туннели в одну большую ноду, хули ты. можешь ещё этот паттерн прямых линий при поиске А* использовать, скипая сразу несколько тайлов на открытом пространстве. в конце концов ебани навмеш.
Как я понимаю что такое JPS:
(если что-то не так - разъясните)
- Это оптимизация и надстройка над A
- Надстройка заключается в скипанье добавления нод в кучу \ массив \ похуй куда в зависимости где хранятся ноды.
- за счет этого скипанья, достигается хорошая производительность, потому что не нужно каждый новый раз обсчитывать каждое направление \ клетку и искать стоимость пути и находить самый минимальный.
Если не правильно понимаю - объясните пожалуйста, что это, и как вы это понимаете своими словами, не ссылками на какую- то хуйню вроде хабра, а своими словами. Прочитал кучу литературы, статей, оф. доков, но нихуя так и не понял (пока).
Идеально было бы на примере кода (похуй какого) посмотреть что да как, что бы в дифф загнать и посмотреть разницу в имплементации.
Если кто-то переделывал свой A в JPS - дайте знать, и подскажите что в общих чертах нужно сделать. У меня все.
P.S. grid, карта 500x500 (x0, y0 -> x1, y1)
Поэтому для меня JPS жизненно необходим. Ибо из A уже выжаты все соки, но с имплементацией и понимание JPS все туго пока...