Поиск пути в играх

[Волгоградец]

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

[CrazyFlasher]

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

[iNils]

http://algolist.manual.ru/maths/graphs/shortpath/

[Волгоградец]

Спасибо, CrazyFlasher и iNils!