Алгоритм поиска пути

[dark256]

Допустим есть поле N на M клеток. На нем некоторые клетки помечены как "препятствия".
Никто не кинется алгоритмом рассчета пути юнита из точки А в точку В, с учетом обхода препятствий и других юнитов? :) Понимаю, что это старо как мир, но в поиске не нашел, а самому писать - в математику лезть ужасно лень :)

[Psycho Tiger]

Поищите по запросу "Аstar" (А*)

[dark256]

Ага. Спасибо! В целом идея ясна. Задача - животрепещущая, как я и предполагал.
Подожду, может все-таки кто-нибудь поделится исходником.

[Mr.Olegator]

Немного не понимаю, что ты хочешь... Столкновения "объекта" с препятствиями что ли?

[Hauts]

dark256, держите (http://coolisee.com/2010/05/21/poisk-puti-pathfinding/)!

[dark256]

ВАУ! Спасибище!!!

Немного не понимаю, что ты хочешь... Столкновения "объекта" с препятствиями что ли?

Пройти из точки А в точку Б. Если на дороге стоит не именно препятствие, а такой же юнит, то обход оного. Как я понимаю - это частный случай того же самого алгоритма?

[Котяра]

Вообще это довольно сложная задача и описываются алгоритмами d-star, т.е. алгоритмами a-star c динамически изменяемыми параметрами проходимости. В общем случае решение зависит от множества факторов. Для каждых случаев описываем свои эвристики. Не зря во многих играх на такие случаи забивают.

[sk65]

Незнаю может поможет
http://xitri.com/2008/09/22/simple-engine-flash-game-top-view.html

[dark256]

Здорово! Спасибо!

[flashermaster]

попробуй http://script3.blogspot.com/2010/04/star-path-finding-algorthim-in.html
мощьное решение с дополнительной опцией "сглаженного пути"
вдобавок попробуй мою модификацию (добавлил поиск в 4x направленях)
http://www.megaupload.com/?d=CL3MRX3U