Поиск кратчайшего пути
[ Это Сообщение было отредактировано fishca в 2002-02-22 0859 ]
On 2002-02-21 1637, fishca wrote
Помогите, пожалуйста, чайнику, как найти кратчайший путь от одной точки до другой, т.е. есть задача переместить персонажа (просто жирную точку на экране) в другую точку указав ее мышкой на экране.
Кратчайший путь между двумя точками - прямая. Самый простой путь - линейная интерполяция
x = x0*t + (1-t)*x1
y = y0*t + (1-t)*y1
где x0,y0 координаты начала отрезка,
x1,y1 - координаты конца,
t - параметр, при любом t, точка x,y будет на прямой проходящей через x0,y0-x1,y1. При t от 0 до 1 x,y будет на отрезке от x0,y0 до x1,y1.
Достоинством предложенного метода, несомненная простота, недостатком является то, что необходимы операции с вещественными числами. Это можно решить, перейдя к числам с фиксированной точкой.
Есть еще алгоритм Брезенхема, он работает только с целыми числами и крайне быстр, используется для рисования прямых. Тоже достаточно прост, но он больше по объему и комментарии потребуются довольно обширные. Для Ваших нужд я думаю хватит и выше приведённых формул. А если Брезенхем заинтересовал, напишите, я расскажу.
Вот такие дела
http//algolist.by.ru/maths/graphs/shortpath/volna.html