Почему А* не всегда ищет оптимальный путь ? И как поправить ?

← →
Будулай (2005-08-13 01:33) [0]

не особо жертвуя скоростью.

← →
XProger © (2005-08-13 03:48) [1]

Написать Aстар правильно

← →
Будулай (2005-08-13 07:35) [2]

Если ты написал - делись !

← →
XProger © (2005-08-13 07:43) [3]

Делиться не буду, т.к. литературы море - главное желание.
http://delphigfx.mastak.ru/doc/path/path.htm
http://delphigfx.mastak.ru/samples/samp2.rar

← →
grouzd[E]v © (2005-08-13 11:18) [4]

Работающий код - у меня (и, наверное, у Дартмана) в Defence - модуль pathfinding. Качать здесь: code.rpro.ru правда там 8,5 метров. В принципе могу на мыло выслать
ЗЫ спрашивать код - нехорошая тенденция =)

---
... we are walking on a thin line and you better avoid the risk ...

← →
Lakmus (2005-08-13 23:58) [5]

grouzd[E]v

> спрашивать код - нехорошая тенденция =)

а вот открывать код - очень хорошая )

← →
grouzd[E]v © (2005-08-14 00:12) [6]

оффтоп
> а вот открывать код - очень хорошая
а он что, закрыт?

---
... we are walking on a thin line and you better avoid the risk ...

← →
Будулай (2005-08-14 01:31) [7]

Для тех, кто не врубился повторю. Нужнен не алгоритм, а ответ почему он порою ищет не оптимальный путь? Протестируйте свои алгоритмы и сами увидите.

← →
XProger © (2005-08-14 01:39) [8]

Мною написанные А*, в соответствии с данным алгоритмом, всегда находят самый дешёвый путь.

P.S.
Телепаты всё ещё в отпуске...

← →
Xeno © (2005-08-14 08:18) [9]

>Будулай
Хош ответ покажи исходник своего алгоритма,а так XProger прав - Телепаты всё ещё в отпуске...

← →
ViK © (2005-08-14 08:48) [10]

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

← →
boalse © (2005-08-14 09:39) [11]

Я вот тоже не доволен астаром. Написал этот алгоритм по одной очень хорошей статье, точной ссылки сейчас дать не могу, статья у меня на винте. Автор Патрик Лестер (Patrick Lester), какой-то крутой гейммейкер.

Ну так вот что этот алгоритм у меня вытворяет (да и у автора на картинке тоже):

Boalse.narod.ru/AStar.JPG

Зелёная клетка - точка старта, красная - конец, синие клетки - найденный путь, чёрные - препятствие. Если заметили, найденный путь "прилипает" к стенке, а ведь это не самый короткий путь. Оранжеврой линеей я обозначил оптимальное направление. Можно, конечно, применить алгоритм сглаживания пути, но это уже дополнительные тормоза. Я отточил волновой алгоритм, он достаточно быстро летает и находит то, что нужно, но хотелось бы всётаки знать: Астар и вправду находит такой путь, или это я чего-то не так сделал?
XProger, если не сложно, нарисуй такую же фиговину своему астару, чего он покажет?

← →
grouzd[E]v © (2005-08-14 11:40) [12]

> Если ты написал - делись !
> Нужнен не алгоритм, а ответ почему он порою ищет не оптимальный путь?
Это как? =)
А вообще, надо своему такой вариант запихнуть

---
... we are walking on a thin line and you better avoid the risk ...

← →
grouzd[E]v © (2005-08-14 11:53) [13]

Вот че НЕ-мой астар сделал http://grouzdev.nm.ru/ - не мой он т.к. лень свой переписывать под "рисование" =)
Имхо здесь все зависит от цены перемещения - перемещение по диагонали = sqrt(2) * перемещение по прямой

---
... we are walking on a thin line and you better avoid the risk ...

← →
ViK © (2005-08-14 15:11) [14]

Просто твой Астар "не умеет" ходит по диагонали, поэтому и глюки.

В этой статье вроде бы такого нету:
http://delphigfx.mastak.ru/doc/path/path.htm

← →
XProger © (2005-08-14 20:43) [15]

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

P.S.
Телепаты не скоро приедут...

← →
Будулай (2005-08-15 01:30) [16]

> boalse © (14.08.05 09:39) [11]
> Boalse.narod.ru/AStar.JPG

Вот об этой проблеме я и говорил.

← →
XProger © (2005-08-15 01:58) [17]

Будулай, что бы ты не говорил без телепатов или твоего кода мы ничем помочь не сможем...

← →
boalse © (2005-08-15 05:44) [18]

Да, стоимость перемещения по прямой = 10, а по диагонвли = 14. Всё делал как написанно здесь http://blitzetc.nm.ru/03-apr05.htm
Тут куча каких-то статей, нужная называется "Астар для новичков"

есть ещё вопросы?

Ещё вопросы? Хех, ну разве что интересно было бы узнать, как ты воспроизводишь фоновую музыку в своих проектах :)) Вот здесь:
http://delphimaster.net/view/9-1123916645/

еще раз, на всякий случай.

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

двунаправленный поиск с дополнительными оптимизациями имеет скорость ~ O(n*log n) n- глубина поиска. волновой алгоритм гораздо(на порядки) хуже.

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

>программер, который говорит что классики жанра неправы...

Это не только к программерам относится.

Я как-то не подумал поставить равную цену у перемещения по диагонали и в бок. Дома попробую, думаю получится.
Проще не значит лучше. Я могу представить, как работает волновой алгоритм, могу даже во сне его нарисовать, а вот как представить в мозгу работу астара - для меня невообразимо. Хотя... когда-то я и волновой понять не мог.

[23] cyborg
ничего поделать с этим не могу, кащениты всю прошывку своим НЛП попортили.
zis is mai da style nah.

← →
keal (2005-08-16 02:34) [25]

Сначала я тоже был недоволен А*, так путь прижимался к стенке. Потом решил прочитать сам алгоритм :), ссылку на статью не дам, не помню. Суть была в том, что алгоритм обходит препятствия не обтирая их, а обходя чуть подальше.

keal, вокруг стен веса расставлены хорошие ;)

Почему А* не всегда ищет оптимальный путь ? И как поправить ? Найти похожие ветки