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

dark256 · 07.01.2011, 02:06

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

Понимаю, что это старо как мир, но в поиске не нашел, а самому писать - в математику лезть ужасно лень

Psycho Tiger · 07.01.2011, 02:07

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

dark256 · 07.01.2011, 02:14

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

Mr.Olegator · 09.01.2011, 10:04

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

Hauts · 09.01.2011, 11:42

dark256, держите!

dark256 · 09.01.2011, 18:12

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

Цитата:

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

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

Котяра · 09.01.2011, 18:35

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

sk65 · 10.01.2011, 04:17

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

dark256 · 10.01.2011, 12:11

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

flashermaster · 20.03.2011, 00:49

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