|
С# Средство разработки на платформе .Net |
25.03.2013, 23:17
|
#1
|
Нуждающийся
Регистрация: 25.11.2012
Сообщений: 83
Написано 2 полезных сообщений (для 2 пользователей)
|
Поиск пути
Как осуществляется поиск пути в рпг,ртс, квестах всяких? Я вот немного посмотрел ресурсы на эту тему - есть алгоритм а*... вроде легкий... но подходит только для карты, представленной в виде массива... а какие алгоритмы поиска применять в 3д играх, изометрии? А* похоже, весьма затратен даже при немногочисленных объектах, "ищущих путь"... а если их достаточно много? Можно ли поиск длинного пути разбить на несколько мелких? И как заранее понять, насколько он продолжителен, если он еще не высчитан?
|
(Offline)
|
|
26.03.2013, 00:43
|
#2
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Ответ: Поиск пути
В современных играх используют навмеш. Еще есть иерархический поиск путей.
|
(Offline)
|
|
26.03.2013, 11:14
|
#3
|
Нуждающийся
Регистрация: 25.11.2012
Сообщений: 83
Написано 2 полезных сообщений (для 2 пользователей)
|
Ответ: Поиск пути
спасибо, можно более подробно?
|
(Offline)
|
|
26.03.2013, 13:03
|
#4
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Ответ: Поиск пути
|
(Offline)
|
|
Эти 3 пользователя(ей) сказали Спасибо pax за это полезное сообщение:
|
|
27.03.2013, 12:05
|
#5
|
Нуждающийся
Регистрация: 25.11.2012
Сообщений: 83
Написано 2 полезных сообщений (для 2 пользователей)
|
Ответ: Поиск пути
спасибо, а ты сам как, разбираешься в поиске пути? Просто нашел один пример a*, вроде как быстрый, только разобраться надо...
|
(Offline)
|
|
27.03.2013, 12:17
|
#6
|
Задрот
Регистрация: 24.07.2009
Адрес: Ивановская область, г. Кинешма
Сообщений: 1,574
Написано 407 полезных сообщений (для 863 пользователей)
|
Ответ: Поиск пути
Сообщение от wppt
спасибо, а ты сам как, разбираешься в поиске пути? Просто нашел один пример a*, вроде как быстрый, только разобраться надо...
|
а стар нифига не быстрый, лишь для единичного случая, и тот приходится неплохо порезать по итерациям.
Есть вариант лучше - иерархический а стар, тот ищет путь сначала по большим областям, постепенно сужая область поиска.
Но повторюсь - все это дело крайне медленно. Есть конечно выход - замутить поисковик пути (как наиболее ресурсоемкую задачу) в отдельном процессе, при возможности выделить на него целое ядрышко CPU. Вот так наверно будет круто.
Плюсы:
- Асинхронно
- Поиск одновременно дохрена путей
- Не затрагивает главный процесс (логику \ графику)
Минусы:
- Многопоточность, из нее куча вытекающих нюансов
- Сложность ( хотя, я думаю это несложно)
Надеюсь, я сейчас не натупил как мудакъ))
В случае чего, ругайте матом и бейте ногами
|
(Offline)
|
|
27.03.2013, 20:08
|
#7
|
Нуждающийся
Регистрация: 25.11.2012
Сообщений: 83
Написано 2 полезных сообщений (для 2 пользователей)
|
Ответ: Поиск пути
да я понимаю, конечно, а* это медленно... но я нашел вроде как более-менее быстрый пример поиска пути по сравнению с другими... ну а как например во всяких rogue like реализуется поиск пути для множества "объектов"? Например, в dwarf fortress?
|
(Offline)
|
|
27.03.2013, 21:18
|
#8
|
Задрот
Регистрация: 24.07.2009
Адрес: Ивановская область, г. Кинешма
Сообщений: 1,574
Написано 407 полезных сообщений (для 863 пользователей)
|
Ответ: Поиск пути
Сообщение от wppt
да я понимаю, конечно, а* это медленно... но я нашел вроде как более-менее быстрый пример поиска пути по сравнению с другими... ну а как например во всяких rogue like реализуется поиск пути для множества "объектов"? Например, в dwarf fortress?
|
Мне кажется что-то вроде а*, только запросы на поиск пути обрабатываются менеджером, ставящим их в очередь по некоторому приоритету, и они считаются за фрейм по 2-3 тшуки. Думаю так
|
(Offline)
|
|
28.03.2013, 12:21
|
#9
|
Нуждающийся
Регистрация: 25.11.2012
Сообщений: 83
Написано 2 полезных сообщений (для 2 пользователей)
|
Ответ: Поиск пути
а что, даже так какая-никакая экономия достигается... спасибо, буду пробовать...
А вот еще - пути при следовании из одной и той же начальной точке к одной и той же конечной получаются всегда одинаковыми? Или это зависит от выбора формулы расчета эвристического расстояния? Думаю, если перед началом поиска задавать формулу случайно, разности в производительности не будет?
|
(Offline)
|
|
02.04.2013, 21:50
|
#10
|
ПроЭктировщик
Регистрация: 02.06.2011
Адрес: Набережные Челны
Сообщений: 103
Написано 27 полезных сообщений (для 91 пользователей)
|
Ответ: Поиск пути
Я кстати когда то заботился об этом очень сильно.
Если в вашем случае приходится обрабатывать Астар в каждом цикле(кадре) то лучше расчитывать не от старта к финишу, а наоборот. При этом не придется обрабатывать все соседние 'клетки' на цену пути, достаточно будет довести путь до финиша и предпоследняя 'клетка' станет указателем для движения. В большинстве случаев такой способ в разы сократит время на поиск.
Конечно можно закритиковать такой способ навязывая идеал в том что Астар должен расчитыватся полностью и один раз(к примеру если вам требуется расчитать короткий путь от Челябинска до Саранска), но в игре где обстановка меняется постоянно классический Астар проиграет.
Это примерные показатели затронутых клеток для расчета пути за один цикл. На самом деле их пути будут равны.
|
(Offline)
|
|
03.04.2013, 11:18
|
#11
|
Нуждающийся
Регистрация: 25.11.2012
Сообщений: 83
Написано 2 полезных сообщений (для 2 пользователей)
|
Ответ: Поиск пути
ого, наверно, сработает, надо же только начало на конец и наоборот поменять, так?
|
(Offline)
|
|
03.04.2013, 19:53
|
#12
|
ПроЭктировщик
Регистрация: 02.06.2011
Адрес: Набережные Челны
Сообщений: 103
Написано 27 полезных сообщений (для 91 пользователей)
|
Ответ: Поиск пути
Все верно! Возьми стандартный Астар, заставь его считать от финиша к старту. Отбрось расчет стоимости пути, т.е. соседи должны оцениватся только на дальность к старту.
Один немаловажный момент. Если в игре есть динамические препятствия, к примеру юниты, то занятой клеткой нужно считать клетку куда 'идет' объект, а не действительное положение объекта. Так же нужно учитывать что ни один объект не должен передвигатся со скоростью больше одной клетки за цикл.
Также можешь подшаманить код что бы 'поиск пути' обрабатывался только когда объект приблизился на растояние к направляющей клетке, меньшей его скорости или при смене позиции финиша.
|
(Offline)
|
|
03.04.2013, 21:20
|
#13
|
Нуждающийся
Регистрация: 25.11.2012
Сообщений: 83
Написано 2 полезных сообщений (для 2 пользователей)
|
Ответ: Поиск пути
вообще я не знаю, что тебе ответить, т.к. хотел сделать игру с пошаговым и реалтайм режимами(по раундам, как в D&D-подобных рпг)...
да и еще немного непонятно, зачем отбрасывать расчет стоимости, ведь все таки ищется кратчайший путь... или имеется в виду то, что учитывать надо стоимость не от текущей родительской клетки до той, которая проверяется на текущем шаге алгоритма, а от родительской клетки до проверяющейся?
насчет скорости перемещения - думаю с этим проблем не возникнет...
насчет пересчета пути - также стоит пересчитывать путь, если поменялось состояние одной из клеток, входящих в путь(например, она стала занята )
|
(Offline)
|
|
03.04.2013, 22:33
|
#14
|
ПроЭктировщик
Регистрация: 02.06.2011
Адрес: Набережные Челны
Сообщений: 103
Написано 27 полезных сообщений (для 91 пользователей)
|
Ответ: Поиск пути
В А* стоимость расчитывается по кол-ву шагов + растояния до цели, если считаешь от финиша к старту количество шагов учитывать не нужно. Сделай на практике выведи результаты и все станет ясным.
Пойми за счет того что твой поиск пути обрабатывается каждый цикл, не учитывая стоимость шагов и + от финиша к старту, у тебя все равно выходит тот же кратчайший путь с меньшими вычислениями.
|
(Offline)
|
|
04.04.2013, 11:53
|
#15
|
Нуждающийся
Регистрация: 25.11.2012
Сообщений: 83
Написано 2 полезных сообщений (для 2 пользователей)
|
Ответ: Поиск пути
прости, я чего-то не врубаюсь...я не знаю, правильно ли но я так делаю: от стартовой точки выбираю какую-нибудь соседнюю, которая не занята, и путь до которой короче... затем считаю уже ее соседей и так до тех пор пока очередь не дойдет до конечной... не знаю, я правильно делаю? Вот так считаю путь - F = G + H, где G - расстояние от текущей "родительской" точки до этой, H - оценочное расстояние от текущей(родительской) точки, до конечной... не знаю, это вообще астар?
|
(Offline)
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 13:47.
|