Войти
ПрограммированиеФорумИгровая логика и ИИ

Принцип работы алгоритма поиска пути Астар (A*). (Комментарии к статье) (4 стр)

Страницы: 1 2 3 4 5 6 Следующая »
#45
0:16, 29 фев 2004

Cupper
А сам Open список как поддерживаеш? Какой структурой даннъх?

#46
12:07, 1 мар 2004

Zemedelec
Binary Heap, по принципу как здесь.
_moadib ссылку давал.

#47
12:52, 1 мар 2004

Cupper
Говорят списком бъстрее, но не простъм.
Имееш 15 (к примеру) елементов где содержатся самъе лучшие кандидатъ + сам список.
Въборка лучшего кандидата из етого буффера, если он пустой - то тогда он заполняется из списка. При вставке елемента, сначала он вставляется в буффер, если в буффере все елементъ лучше (т.е. последний, так как буффер - сортирован), то елемент просто занисится в список.
Ето говорят что бъстрее, так как операции по удалению и вставке елемента не симетричнъ, как ето предполагает heap, там все logN.

#48
13:11, 1 мар 2004

Zemedelec
хм...
на выходных попробую. Спасибо.

#49
13:43, 1 мар 2004

Zemedelec

Зетс райт ! Называется "ведерный" кажется метод ...... Давно изучен и дает лучшие скоростные характеристики.

#50
18:32, 10 июня 2004

2 All
1) Сходил на ссылку данную  _moadib (http://www.policyalmanac.org/games/aStarTutorial.htm)
Там в описании, закрытый список больше не посещаеться, а используеться только как хранилише родителя.
А в статье Cupper'а идет постоянное обращение к закрытому списку на предмет переноса в открытый, от сюда вопрос где засада для не Cupper'овского варианта (пример (возможно в картинке) когда нужно переоткрыть закрытый узел т.к. сколько не пробовал не придумал)?
2) Странно, но есть стандартный способ определения посещения узла и наличие его в закрытом или открытом списке, почему о нем никто не говорит ? затраты на один узел max 32bit(для супер маняков) БЕЗ ПРЕДВАРИТЕЛЬНОЙ ИНИЦИАЛИЗАЦИИ. время определения O(1). Время отлинковки из 2-ву направленого списка O(1) , остается только время добавления в открытый список и вуаля ;))

p.s.
Очень хотелось бы узнать ответ на мой первый вопрос.
p.p.s.
Может это уже никто не читает, ну да ладно для истории оставлю ;)

#51
11:32, 15 июня 2004

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

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

#52
11:52, 15 июня 2004

iancen
2) ето когда вместо булевого флага пользуем скажем номер pathfind-а или что-то такое? А не отжирает ли ето слишком много памяти?

Cupper
На карте с разнъми типами ландшафта, и особенно когда въсота играет роль в оценочной функции, то A* работает довольно плохо. Ибо евристику надо сделать для наихудшего случая, а если он очень плох - тогда все ето медленно превращяется в волну, только в медленную... :)

#53
14:04, 15 июня 2004

2 Zemedelec
1) Ответ понятен (чисто теоритически), хотя конечно жаль что без картинки.
2) Да, по номеру pathfind, но если учесь факт что оптимальное выравнивание данных 32bit, то нормально. Но при этом на переполнение уходит ~26 дней, можно и 16bit при 1000 обращениях в сек. хватит на 32 секунды до переинициализации, что тоже можно отнести к практически O(1). В любом случае этот вариант во всех случаях лучше всяких битовых массивов(на каждом обращении нужно чистить память numNodes/32 + обращение для проверки) и т.д.

Прошло более 6 лет
#54
21:32, 6 мая 2011

полагаю всем участникам дискуссии, а так же автору будет интересна эта ветка
http://www.gamedev.ru/code/forum/?id=147231

#55
19:08, 18 авг 2011

Сделал свою воду, затем почитав понял, что реализовал Дейкстру, а оттуда до Астара рукой подать.

Думал как уменьшить число проверяемых узлов в сетке, придумал такую эвристику:

g = distance
h = max(dx, dy)
f = h

Мне кажется, что она будет искать как-то так:

 _______    O
  O O O|    O
  O O O|  O
  O O O O
  O
O

Кружочки - это закрытые узлы.

Сейчас сижу на списках, хочу записывать их сразу отсортировано, чтобы без поиска обойтись. Мне кажется это будет куда экономнее, чем каждый раз сортировать, т.к. весь экшн происходит у головы списка. Не знаю когда доделаю, вот и запостил :)
Кто-нибудь мог бы проверить такую эвристику если не сложно? Ну или сказать, что она не будет работать.

#56
21:43, 18 авг 2011

Хмм, что-то как-то коряво наверное, на горизонталях/вертикалях будет в обе стороны идти, или наугад, в зависимости от в глубину или в ширину. Может типа так как-то:

g = distance
h = max(dx, dy)
h += min(dx, dy) * 0.001
f = h
#57
5:22, 19 авг 2011

Омг, ну и параша =Д вопрос снят

#58
19:08, 20 авг 2011

Итак, а теперь серьезно:

Я реализовал сортировочный список, теперь сделал и двоичной кучей.
Производительность двоичной кучи вышла ниже в 8-9 раз, т.е практически на порядок. Из-за чего это может быть?
Обе версии ищут в глубину.

1) Вынимаю корень, закрываю, обмениваю с концом и heapify для него.
2) Затем его вертикальных/горизонтальных соседей проверяю, если они не открыты и не закрыты, то закрываю или открываю, добавляю в конец и всплываю его.
3) Если ячейка уже в открытом списке, то если g лучше, считаю новый h. Меняю значение ячейки в куче на новое и всплываю его.
4) Затем тоже самое для диагональных соседей.

Вот и все, что делает куча.
На шаге 3 Была проблема с поиском конкретной ячейки в куче и я стал хранить в ячейке еще и её индекс в куче, т.е во всех операциях с деревом, переставляемым элементам я этот индекс обновляю.
Возможно тормозит из-за этого, и вообще, как эту проблему другим способ решить?
Кучей вообще так нужно в Астаре пользоваться?

P.S. В куче я храню ссылки на объекты ячеек, а не их индексы в списке. Подумал, что  heap[n] будет лучше list[heap[n]]

#59
15:23, 29 сен 2011

desss
> Производительность двоичной кучи вышла ниже в 8-9 раз, т.е практически на
> порядок. Из-за чего это может быть?
из-за того, что надо СТЛ юзать. std::multimap<> в помощь

Страницы: 1 2 3 4 5 6 Следующая »
ПрограммированиеФорумИгровая логика и ИИ

Тема в архиве.