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

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

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

Cupper
Статья конкретно о A*, но если интересно посмотри на статью о A* в Game Programming Gems 3. Там 3-4 очень рульнъх статьи, одна о тактическом A*, где путь старается уворачиватся от огня и встречами с противником.

#16
19:54, 19 янв 2004

Zemedelec
С тактикой все просто. Надо лишь пометить область как Варзону и задать высокий коэффициент стоимости прохода.
Остальное, спасибо, посмотрю.

#17
8:53, 20 янв 2004

Zemedelec
а где взять Game Programming Gems 3? есть в электр. виде?

#18
13:39, 20 янв 2004

_moadib
У меня нет.

#19
20:31, 26 янв 2004

Мда.
Печальная картина.
Хоть статья и называется "принципы работы", сами принципы работы автор понимает неверно.
Если написать опущенные в приведённом коде функции согласно вербальным указаниям - получится абсолютно неработоспособный алгоритм, проводящий прямую линию от начальной точки к конечной (на примере плоского 8-ми связанного грида).
Принципы работы изложенны настолько невнятно, что придётся рассказать его заново.

Итак, А* - это реализация взвешенного волнового алгоритма, где для быстрого поиска пограничных узлов с наименьшим весом (именно наименьшим весом, а не наименьшим "расстоянием до конечного пункта"), применяется список этих узлов, формируемый на этапе обработки предыдущих узлов.
Итак, реально в алгоритме существует только один основной список - open.
Причём это не "список необработанных узлов", а список узлов пограничной области волнового алгоритма.
Список close абсолютно необязателен и даже вреден с точки зрения производительности.
Всё его предназначение - определение того, обрабатывался узел или нет.
Гораздо эффективнее реализовать такую проверку на свойствах узла (я имею в виду, что конструкция if(pNode->m_bIsProcessed) работает несколько быстрее чем if(search(closed.begin(),closed.end(),pNode)). Для исключения операции сравнения также можно заранее проинициализировать все узлы весом в условную бесконечность).
Далее, мы берём начальный узел с весом ноль и записываем всех его соседей в открытый список с весами перехода в них из текущего узла.
Список далее обрабатывается в порядке наименьшего веса (именно это основа волнового алгоритма, а беря наименьшее расстояние до конечного пункта, мы просто выстраиваем цепочку в направлении конечного пункта вплоть до его достижения, не взирая на стоимость пути).
Обрабатывая очередной текущий узел, мы так же добавляем всех его соседей в открытый список, за исключением случаев, когда узел уже обработан, и его, полученный на предыдущем этапе, вес не меньше полученного текущего.
Всё.

#20
4:01, 27 янв 2004

Помоему, ето называется поиск в ширину.

#21
10:04, 27 янв 2004

По моему тоже. 8)

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

#22
12:44, 27 янв 2004

Psych
Ето скорее Дийкстра, так как все же обрабатъвается узел с наименьшим весом.

had
Наличие closed списка обязательно в той или другой форме.
А если конкретно об оптимизации, то в AI Game Programming Wisdom 1 есть очень конкретная статья, которая разсматривает довольно оптимизированнъй A*, с кучей таблицами, модифицированнъми списками и closed листом в виде копии картъ проходимости.

#23
18:34, 27 янв 2004

had
хех.
Соглашусь только с тем, что в комментариях к коду не совсем правильно назвал критерий. Это действительно не расстояние, а стоимость пути, от него, как правило, зависящая. Но тем не менее придираться к этому не стоило, это не принципиально.
PS:
> получится абсолютно неработоспособный алгоритм
алгоритм абсолютно работоспособный (проверенно электроникой)

#24
18:38, 27 янв 2004

IROV..
>мож я вообще баран.. но зачем список.. создавать.. когда можно обычной очередью управится..
Можно и очередью. Но лучше binary heap.

#25
1:27, 26 фев 2004

Кстати, оценка расстояния до финиша - это, в данном случае,  удачный выбор эвристической функции, которая, собственно и отличает А* от поиска вширину.

#26
10:11, 26 фев 2004

Очень охота заметить, что скажем на неровном ландшафте (или когда тяжесть пути очень зависит от характеристик данной клетки/тайла, т.е. путь по прямой от точки А до точки Б может бъть X, а может бъть и 30*Х (из-за неровностей по пути), тогда A* довольно плох и пользовать его смъсла особого нету из за накладнъх расходов в самом алгоритме, т.е. так или иначе расползется везде, лучше волну.

#27
13:02, 26 фев 2004

Zemedelec
Может быть ты и прав, но в А* можно добавить ЛОД практически без усложнения алгоритма.

#28
13:45, 26 фев 2004

Cupper
А что мешает добавить тот-же LOD к волне?

#29
13:52, 26 фев 2004

Zemedelec
Помоему это сильно усложнит алгоритм. Ведь нужно уметь использовать одновременно и обычный режим и ЛОД.
Хотя я запросто могу ошибаться.

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

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