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

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

Страницы: 1 2 3 4 5 6 Следующая »
#60
21:03, 30 сен 2011

Меня всегда интересовало, ведь A* на выходе даёт нам идеально короткий путь к обьекту, при том учитывая и стоимость перехода по ребру, и стоимость нахождения на вершине графа. Собственно, в играх то это зачем??? Там требуется лишь найти путь, причём желательно оптимальный, но не идеальный, плюс, не всегда надо указывать стоимости вершин и переходов, а учитывать нужно только расстояние до следущих вершин. Поэтому я считаю, что алгоритмом Дейкстры в играх вполне можно ограничиться. Лично у меня вообще поиск в глубинуXD. И ещет кстати, вполне неплохо, тоесть и погрешность в оптимальности есть, и всё о чём я говорил.

#61
0:20, 1 окт 2011

Sgw32
> едь A* на выходе даёт нам идеально короткий путь к обьекту, при том учитывая и
> стоимость перехода по ребру, и стоимость нахождения на вершине графа.
> Собственно, в играх то это зачем??? Там требуется лишь найти путь, причём
> желательно оптимальный, но не идеальный, плюс, не всегда надо указывать
> стоимости вершин и переходов, а учитывать нужно только расстояние до следущих
> вершин. Поэтому я считаю, что алгоритмом Дейкстры в играх вполне можно
> ограничиться.
Это Дейкстра всегда дает идеально короткий путь к объекту, а А* от эвристики зависит.

#62
0:37, 1 окт 2011

Обоим два.
Особенно улыбнуло про не идеальный, но оптимальный путь. Читайте терминологию.

#63
1:01, 1 окт 2011

GeniusIsme
Не веришь, что А* может давать неоптимальный путь? Вот пример:
http://www.gamedev.ru/flame/forum/?id=152038&page=2#m27

#64
9:31, 1 окт 2011

Это не А*. Следующий.

#65
10:23, 1 окт 2011

Вобщето там астар =).  Да. Зависит от эвристики.

#66
12:38, 1 окт 2011

GeniusIsme
Вообще-то эта картинка http://ru.wikipedia.org/wiki/Алгоритм_поиска_A*, только дорожка дорисована.
Гении такие гении.

#67
13:09, 1 окт 2011

Пририсована дорожка? Отлично! А звездочку стереть не забыли? Учите матчасть.

#68
13:42, 1 окт 2011

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

#69
14:41, 1 окт 2011

kipar
Если эвристика "несоответствующая" - то это не А*. В А* есть условия на эвристику: что она "оптимистическая", т. е. всегда предполагает, что между данными точками можно пройти не медленней, чем на самом деле.

#70
23:07, 1 окт 2011

Chipmunk
> Если эвристика "несоответствующая" - то это не А*. В А* есть условия на
> эвристику: что она "оптимистическая", т. е. всегда предполагает, что между
> данными точками можно пройти не медленней, чем на самом деле.
если грубо, admissible эвристика -> g(begin, end) > h(begin, end)
в противном случае, А* может выдавать неоптимальные маршруты(пути)

#71
10:22, 21 окт 2011

Здравствуйте.

Пишу программу для нахождения пути из т. А в т. Б на карте, с последующей детализацией пути в 3D. Возник вопрос. Для карт размеров 800*1000 пикселей, скажем, есть необходимость оптимизировать алгоритм? Я иммею ввиду, что для такой карты такого размера получу ли огромное время просчета и большие затраты по памяти?
Просто пришла мысль, что нужно сначала работать не с точками(пикселями), а областями(квадратами), чтобы отсечь побольше вариантов прохода.
Или же я загоняюсь, и стоит взять обычную реализацию?

Прошу высказать мнение, и ,если возможно, какие -либо советы.

#72
10:33, 21 окт 2011

moeviv,
На карте в 1024 на 1024 астар сильно тормозит.  Чтоб этого не было нужно делить всю карту на  части по 128 на 128.  + В самом алгоритме нужно оптимизировать открытый/закрытый список.  Там много всего в алгоритме можно соптимизировать.

#73
11:20, 21 окт 2011

А можно чуть подробней о 128 на 128. Как я понял нужно сначала найти по каким малым областям я пойду, и работать далее только с ними. Или я что-то не так понимаю?

#74
11:56, 21 окт 2011

moeviv
могу порекомендовать вот эту библиотеку http://www.gamedev.ru/code/forum/?id=148004
или micropather

поддерживает веса тайлов и разные типы полей
что касается оптимизации - хз, может и не понадобится

> А можно чуть подробней о 128 на 128. Как я понял нужно сначала найти по каким
> малым областям я пойду, и работать далее только с ними. Или я что-то не так
> понимаю?
да, определяешь множество блоков по которым нужно пройти твоему персу
а в рамках одного блока определяешь как дойти до следующего блока

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

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