Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   forum.boolean.name > Программирование игр для компьютеров > С#

С# Средство разработки на платформе .Net

Ответ
 
Опции темы
Старый 25.03.2013, 23:17   #1
wppt
Нуждающийся
 
Регистрация: 25.11.2012
Сообщений: 83
Написано 2 полезных сообщений
(для 2 пользователей)
Поиск пути

Как осуществляется поиск пути в рпг,ртс, квестах всяких? Я вот немного посмотрел ресурсы на эту тему - есть алгоритм а*... вроде легкий... но подходит только для карты, представленной в виде массива... а какие алгоритмы поиска применять в 3д играх, изометрии? А* похоже, весьма затратен даже при немногочисленных объектах, "ищущих путь"... а если их достаточно много? Можно ли поиск длинного пути разбить на несколько мелких? И как заранее понять, насколько он продолжителен, если он еще не высчитан?
(Offline)
 
Ответить с цитированием
Старый 26.03.2013, 00:43   #2
pax
Unity/C# кодер
 
Аватар для pax
 
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений
(для 5,323 пользователей)
Ответ: Поиск пути

В современных играх используют навмеш. Еще есть иерархический поиск путей.
__________________
Blitz3d to Unity Wiki
(Offline)
 
Ответить с цитированием
Старый 26.03.2013, 11:14   #3
wppt
Нуждающийся
 
Регистрация: 25.11.2012
Сообщений: 83
Написано 2 полезных сообщений
(для 2 пользователей)
Ответ: Поиск пути

спасибо, можно более подробно?
(Offline)
 
Ответить с цитированием
Старый 26.03.2013, 13:03   #4
pax
Unity/C# кодер
 
Аватар для pax
 
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений
(для 5,323 пользователей)
Ответ: Поиск пути

Вероятно сможешь найти что-то полезное
https://developer.valvesoftware.com/...igation_Meshes
http://www.dtf.ru/articles/read.php?id=46788
__________________
Blitz3d to Unity Wiki
(Offline)
 
Ответить с цитированием
Эти 3 пользователя(ей) сказали Спасибо pax за это полезное сообщение:
Лit}{Ъ (06.05.2013), HolyDel (26.03.2013), Wegox (27.03.2013)
Старый 27.03.2013, 12:05   #5
wppt
Нуждающийся
 
Регистрация: 25.11.2012
Сообщений: 83
Написано 2 полезных сообщений
(для 2 пользователей)
Ответ: Поиск пути

спасибо, а ты сам как, разбираешься в поиске пути? Просто нашел один пример a*, вроде как быстрый, только разобраться надо...
(Offline)
 
Ответить с цитированием
Старый 27.03.2013, 12:17   #6
Reizel
Задрот
 
Аватар для Reizel
 
Регистрация: 24.07.2009
Адрес: Ивановская область, г. Кинешма
Сообщений: 1,574
Написано 407 полезных сообщений
(для 863 пользователей)
Ответ: Поиск пути

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

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

Надеюсь, я сейчас не натупил как мудакъ))
В случае чего, ругайте матом и бейте ногами
(Offline)
 
Ответить с цитированием
Старый 27.03.2013, 20:08   #7
wppt
Нуждающийся
 
Регистрация: 25.11.2012
Сообщений: 83
Написано 2 полезных сообщений
(для 2 пользователей)
Ответ: Поиск пути

да я понимаю, конечно, а* это медленно... но я нашел вроде как более-менее быстрый пример поиска пути по сравнению с другими... ну а как например во всяких rogue like реализуется поиск пути для множества "объектов"? Например, в dwarf fortress?
(Offline)
 
Ответить с цитированием
Старый 27.03.2013, 21:18   #8
Reizel
Задрот
 
Аватар для Reizel
 
Регистрация: 24.07.2009
Адрес: Ивановская область, г. Кинешма
Сообщений: 1,574
Написано 407 полезных сообщений
(для 863 пользователей)
Ответ: Поиск пути

Сообщение от wppt Посмотреть сообщение
да я понимаю, конечно, а* это медленно... но я нашел вроде как более-менее быстрый пример поиска пути по сравнению с другими... ну а как например во всяких rogue like реализуется поиск пути для множества "объектов"? Например, в dwarf fortress?
Мне кажется что-то вроде а*, только запросы на поиск пути обрабатываются менеджером, ставящим их в очередь по некоторому приоритету, и они считаются за фрейм по 2-3 тшуки. Думаю так
(Offline)
 
Ответить с цитированием
Старый 28.03.2013, 12:21   #9
wppt
Нуждающийся
 
Регистрация: 25.11.2012
Сообщений: 83
Написано 2 полезных сообщений
(для 2 пользователей)
Ответ: Поиск пути

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

А вот еще - пути при следовании из одной и той же начальной точке к одной и той же конечной получаются всегда одинаковыми? Или это зависит от выбора формулы расчета эвристического расстояния? Думаю, если перед началом поиска задавать формулу случайно, разности в производительности не будет?
(Offline)
 
Ответить с цитированием
Старый 02.04.2013, 21:50   #10
Izunad
ПроЭктировщик
 
Аватар для Izunad
 
Регистрация: 02.06.2011
Адрес: Набережные Челны
Сообщений: 103
Написано 27 полезных сообщений
(для 91 пользователей)
Ответ: Поиск пути

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

Это примерные показатели затронутых клеток для расчета пути за один цикл. На самом деле их пути будут равны.
(Offline)
 
Ответить с цитированием
Старый 03.04.2013, 11:18   #11
wppt
Нуждающийся
 
Регистрация: 25.11.2012
Сообщений: 83
Написано 2 полезных сообщений
(для 2 пользователей)
Ответ: Поиск пути

ого, наверно, сработает, надо же только начало на конец и наоборот поменять, так?
(Offline)
 
Ответить с цитированием
Старый 03.04.2013, 19:53   #12
Izunad
ПроЭктировщик
 
Аватар для Izunad
 
Регистрация: 02.06.2011
Адрес: Набережные Челны
Сообщений: 103
Написано 27 полезных сообщений
(для 91 пользователей)
Ответ: Поиск пути

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

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

Также можешь подшаманить код что бы 'поиск пути' обрабатывался только когда объект приблизился на растояние к направляющей клетке, меньшей его скорости или при смене позиции финиша.
(Offline)
 
Ответить с цитированием
Старый 03.04.2013, 21:20   #13
wppt
Нуждающийся
 
Регистрация: 25.11.2012
Сообщений: 83
Написано 2 полезных сообщений
(для 2 пользователей)
Ответ: Поиск пути

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

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

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

насчет пересчета пути - также стоит пересчитывать путь, если поменялось состояние одной из клеток, входящих в путь(например, она стала занята )
(Offline)
 
Ответить с цитированием
Старый 03.04.2013, 22:33   #14
Izunad
ПроЭктировщик
 
Аватар для Izunad
 
Регистрация: 02.06.2011
Адрес: Набережные Челны
Сообщений: 103
Написано 27 полезных сообщений
(для 91 пользователей)
Ответ: Поиск пути

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

Пойми за счет того что твой поиск пути обрабатывается каждый цикл, не учитывая стоимость шагов и + от финиша к старту, у тебя все равно выходит тот же кратчайший путь с меньшими вычислениями.
(Offline)
 
Ответить с цитированием
Старый 04.04.2013, 11:53   #15
wppt
Нуждающийся
 
Регистрация: 25.11.2012
Сообщений: 83
Написано 2 полезных сообщений
(для 2 пользователей)
Ответ: Поиск пути

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


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


Часовой пояс GMT +4, время: 14:09.


vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com