Поиск пути
 

Как осуществляется поиск пути в рпг,ртс, квестах всяких? Я вот немного посмотрел ресурсы на эту тему - есть алгоритм а*... вроде легкий... но подходит только для карты, представленной в виде массива... а какие алгоритмы поиска применять в 3д играх, изометрии? А* похоже, весьма затратен даже при немногочисленных объектах, "ищущих путь"... а если их достаточно много? Можно ли поиск длинного пути разбить на несколько мелких? И как заранее понять, насколько он продолжителен, если он еще не высчитан?

Ответ: Поиск пути
 

В современных играх используют навмеш. Еще есть иерархический поиск путей.

Ответ: Поиск пути
 

спасибо, можно более подробно?

Ответ: Поиск пути
 

Вероятно сможешь найти что-то полезное
https://developer.valvesoftware.com/...igation_Meshes
http://www.dtf.ru/articles/read.php?id=46788

Ответ: Поиск пути
 

спасибо, а ты сам как, разбираешься в поиске пути? Просто нашел один пример a*, вроде как быстрый, только разобраться надо...

Ответ: Поиск пути
 

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

Минусы:
- Многопоточность, из нее куча вытекающих нюансов
- Сложность ( хотя, я думаю это несложно)

Надеюсь, я сейчас не натупил как мудакъ))
В случае чего, ругайте матом и бейте ногами

Ответ: Поиск пути
 

да я понимаю, конечно, а* это медленно... но я нашел вроде как более-менее быстрый пример поиска пути по сравнению с другими... ну а как например во всяких rogue like реализуется поиск пути для множества "объектов"? Например, в dwarf fortress?

Ответ: Поиск пути
 

Мне кажется что-то вроде а*, только запросы на поиск пути обрабатываются менеджером, ставящим их в очередь по некоторому приоритету, и они считаются за фрейм по 2-3 тшуки. Думаю так

Ответ: Поиск пути
 

а что, даже так какая-никакая экономия достигается... спасибо, буду пробовать...

А вот еще - пути при следовании из одной и той же начальной точке к одной и той же конечной получаются всегда одинаковыми? Или это зависит от выбора формулы расчета эвристического расстояния? Думаю, если перед началом поиска задавать формулу случайно, разности в производительности не будет?

Ответ: Поиск пути
 

Я кстати когда то заботился об этом очень сильно.
Если в вашем случае приходится обрабатывать Астар в каждом цикле(кадре) то лучше расчитывать не от старта к финишу, а наоборот. При этом не придется обрабатывать все соседние 'клетки' на цену пути, достаточно будет довести путь до финиша и предпоследняя 'клетка' станет указателем для движения. В большинстве случаев такой способ в разы сократит время на поиск.
Конечно можно закритиковать такой способ навязывая идеал в том что Астар должен расчитыватся полностью и один раз(к примеру если вам требуется расчитать короткий путь от Челябинска до Саранска), но в игре где обстановка меняется постоянно классический Астар проиграет.

Это примерные показатели затронутых клеток для расчета пути за один цикл. На самом деле их пути будут равны.

Ответ: Поиск пути
 

ого, наверно, сработает, надо же только начало на конец и наоборот поменять, так?

Ответ: Поиск пути
 

Все верно! Возьми стандартный Астар, заставь его считать от финиша к старту. Отбрось расчет стоимости пути, т.е. соседи должны оцениватся только на дальность к старту.

Один немаловажный момент. Если в игре есть динамические препятствия, к примеру юниты, то занятой клеткой нужно считать клетку куда 'идет' объект, а не действительное положение объекта. Так же нужно учитывать что ни один объект не должен передвигатся со скоростью больше одной клетки за цикл.

Также можешь подшаманить код что бы 'поиск пути' обрабатывался только когда объект приблизился на растояние к направляющей клетке, меньшей его скорости или при смене позиции финиша.

Ответ: Поиск пути
 

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

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

насчет скорости перемещения - думаю с этим проблем не возникнет...

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

Ответ: Поиск пути
 

В А* стоимость расчитывается по кол-ву шагов + растояния до цели, если считаешь от финиша к старту количество шагов учитывать не нужно. Сделай на практике выведи результаты и все станет ясным.

Пойми за счет того что твой поиск пути обрабатывается каждый цикл, не учитывая стоимость шагов и + от финиша к старту, у тебя все равно выходит тот же кратчайший путь с меньшими вычислениями.

Ответ: Поиск пути
 

прости, я чего-то не врубаюсь...я не знаю, правильно ли но я так делаю: от стартовой точки выбираю какую-нибудь соседнюю, которая не занята, и путь до которой короче... затем считаю уже ее соседей и так до тех пор пока очередь не дойдет до конечной... не знаю, я правильно делаю? Вот так считаю путь - F = G + H, где G - расстояние от текущей "родительской" точки до этой, H - оценочное расстояние от текущей(родительской) точки, до конечной... не знаю, это вообще астар?