Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2006.01.22;
Скачать: CL | DM;

Вниз

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

 
Будулай   (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
Тут куча каких-то статей, нужная называется "Астар для новичков"


 
XProger ©   (2005-08-15 06:31) [19]

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


 
boalse ©   (2005-08-15 06:59) [20]

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


 
Zer0 ©   (2005-08-15 10:15) [21]

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

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

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

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


 
boalse ©   (2005-08-15 10:38) [22]

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

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

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


 
cyborg ©   (2005-08-15 15:29) [23]


> [21] Zer0 ©   (15.08.05 10:15)

Мда, как хорошо начиналось а потом:
ленитсо разбиратсо программер чоткое


 
Zer0 ©   (2005-08-15 16:38) [24]

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


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

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


 
XProger ©   (2005-08-16 03:41) [26]

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



Страницы: 1 вся ветка

Текущий архив: 2006.01.22;
Скачать: CL | DM;

Наверх




Память: 0.53 MB
Время: 0.029 c
14-1135641619
PHOTOSHOP
2005-12-27 03:00
2006.01.22
[PHOTOSHOP] Как найти цвет, которого нет?


8-1123675869
dDan
2005-08-10 16:11
2006.01.22
Очистить канву PaintBox а


2-1136301660
dera
2006-01-03 18:21
2006.01.22
Как переменной типа интегер присвоить случайное число от 0 до 10


6-1129030407
Tonich
2005-10-11 15:33
2006.01.22
FTP


4-1131791080
oSa
2005-11-12 13:24
2006.01.22
Как отключить службы в ОС Виндоус ХП