| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Почему А* не всегда ищет оптимальный путь ? И как поправить ?
Будулай © (2005-08-13 01:33:00)не особо жертвуя скоростью.
XProger (2005-08-16 03:41:00) [1]keal, вокруг стен веса расставлены хорошие ;)
keal (2005-08-16 02:34:00) [2]Сначала я тоже был недоволен А*, так путь прижимался к стенке. Потом решил прочитать сам алгоритм :), ссылку на статью не дам, не помню. Суть была в том, что алгоритм обходит препятствия не обтирая их, а обходя чуть подальше.
Zer0 (2005-08-15 16:38:00) [3][23] cyborg
ничего поделать с этим не могу, кащениты всю прошывку своим НЛП попортили.
zis is mai da style nah.
cyborg (2005-08-15 15:29:00) [4]
> [21] Zer0 © (15.08.05 10:15)
Мда, как хорошо начиналось а потом:
ленитсо разбиратсо программер чоткое
boalse (2005-08-15 10:38:00) [5]>программер, который говорит что классики жанра неправы...
Это не только к программерам относится.
Я как-то не подумал поставить равную цену у перемещения по диагонали и в бок. Дома попробую, думаю получится.
Проще не значит лучше. Я могу представить, как работает волновой алгоритм, могу даже во сне его нарисовать, а вот как представить в мозгу работу астара - для меня невообразимо. Хотя... когда-то я и волновой понять не мог.
Zer0 (2005-08-15 10:15:00) [6]еще раз, на всякий случай.
A* - это модификация алгортима дейикстры - поиска наидешевейшего пути по графу (который является оптимальнымдля любых графов, для тех кто незнает что означает слово оптимальный - тоесть лучше уже не придумать для общего случая).
модификация заключается в добавлении эвристической составляющей, которая позволяет во многих случаях значительно уменьшить зону поиска. для правильной работы алгоритма на прямоугольной сетке коэффициенты/веса в общем уравнении стоимости нужнопроводить исследования.
если коэффициенты заданы не грамотно - то поиск будет пратически неоптимальным.
хорошо подобранные коэффициенты позволяют значительно сократить размеры области поиска при этом найденый путь будет в большинстве случаев подоптимальным.
двунаправленный поиск с дополнительными оптимизациями имеет скорость ~ O(n*log n) n- глубина поиска. волновой алгоритм гораздо(на порядки) хуже.
вобщем не надо ленитсо, а нужно RTFM и разбиратсо.
программер, который говорит что классики жанра неправы, как минимум должен привести чоткое алгоритмическое/математическое доказательство. не смог - автоматически призанл себя криворуким и безбашенным.
boalse (2005-08-15 06:59:00) [7]Ещё вопросы? Хех, ну разве что интересно было бы узнать, как ты воспроизводишь фоновую музыку в своих проектах :)) Вот здесь:
http://www.delphimaster.ru/cgi-bin/forum.pl?id=1123916645&n=9
XProger (2005-08-15 06:31:00) [8]есть ещё вопросы?
boalse (2005-08-15 05:44:00) [9]Да, стоимость перемещения по прямой = 10, а по диагонвли = 14. Всё делал как написанно здесь http://blitzetc.nm.ru/03-apr05.htm
Тут куча каких-то статей, нужная называется "Астар для новичков"
XProger (2005-08-15 01:58:00) [10]Будулай, что бы ты не говорил без телепатов или твоего кода мы ничем помочь не сможем...
Будулай (2005-08-15 01:30:00) [11]
> boalse © (14.08.05 09:39) [11]
> Boalse.narod.ru/AStar.JPG
Вот об этой проблеме я и говорил.
XProger (2005-08-14 20:43:00) [12]boalse, стоимость перемещения по диагонали у тебя отличается от перемещения по горизонтали/вертикали скорее всего, и как ты вес точки оцениваешь?
P.S.
Телепаты не скоро приедут...
ViK (2005-08-14 15:11:00) [13]Просто твой Астар "не умеет" ходит по диагонали, поэтому и глюки.
В этой статье вроде бы такого нету:
http://delphigfx.mastak.ru/doc/path/path.htm
grouzd[E]v (2005-08-14 11:53:00) [14]Вот че НЕ-мой астар сделал http://grouzdev.nm.ru/- не мой он т.к. лень свой переписывать под "рисование" =)
Имхо здесь все зависит от цены перемещения - перемещение по диагонали = sqrt(2) * перемещение по прямой
---
... we are walking on a thin line and you better avoid the risk ...
grouzd[E]v (2005-08-14 11:40:00) [15]> Если ты написал - делись !
> Нужнен не алгоритм, а ответ почему он порою ищет не оптимальный путь?
Это как? =)
А вообще, надо своему такой вариант запихнуть
---
... we are walking on a thin line and you better avoid the risk ...
boalse (2005-08-14 09:39:00) [16]Я вот тоже не доволен астаром. Написал этот алгоритм по одной очень хорошей статье, точной ссылки сейчас дать не могу, статья у меня на винте. Автор Патрик Лестер (Patrick Lester), какой-то крутой гейммейкер.
Ну так вот что этот алгоритм у меня вытворяет (да и у автора на картинке тоже):
Boalse.narod.ru/AStar.JPG
Зелёная клетка - точка старта, красная - конец, синие клетки - найденный путь, чёрные - препятствие. Если заметили, найденный путь "прилипает" к стенке, а ведь это не самый короткий путь. Оранжеврой линеей я обозначил оптимальное направление. Можно, конечно, применить алгоритм сглаживания пути, но это уже дополнительные тормоза. Я отточил волновой алгоритм, он достаточно быстро летает и находит то, что нужно, но хотелось бы всётаки знать: Астар и вправду находит такой путь, или это я чего-то не так сделал?
XProger, если не сложно, нарисуй такую же фиговину своему астару, чего он покажет?
ViK (2005-08-14 08:48:00) [17]Я видел какой-то исходник данного алгоритма, и там был глюк с очисткой поля, т.е. вначале рисуешь лабиринт, нажимаешь кнопочку "поиск" и он тебе находит оптимальный путь, далее нажимаешь кнопочку "очистить" на экране поле очищается, но в памяти это лабиринт остается, и поэтому второй раз алгоритм работает неправильно.
Xeno (2005-08-14 08:18:00) [18]>Будулай
Хош ответ покажи исходник своего алгоритма,а так XProger прав - Телепаты всё ещё в отпуске...
XProger (2005-08-14 01:39:00) [19]Мною написанные А*, в соответствии с данным алгоритмом, всегда находят самый дешёвый путь.
P.S.
Телепаты всё ещё в отпуске...
Будулай (2005-08-14 01:31:00) [20]Для тех, кто не врубился повторю. Нужнен не алгоритм, а ответ почему он порою ищет не оптимальный путь? Протестируйте свои алгоритмы и сами увидите.
| |
Страницы: 