Маршрутный алгоритм имеет две разновидности :
Основанный на вычислении расстояния между точками.
Основанный на рекурентном соотношении.
Маршрутный алгоритм получил свое название, потому что
осуществляет одновременно и формирование фронта и прокладывание трассы.Источником волны на каждом шаге является конечный элемент участка трассы проложенной на предыдущих шагах.
Маршрутный алгоритм основанный на вычислении расстояния между точками.
Работа алгоритма начинается от начального элемента. При этом вокруг начального элемента рассматривается 8-ми элементная окрестность. От каждого элемента окрестности до конечного элемента оценивается длинна пути. При этом расстояние между точками вычислется по формуле:
D=|Xi-XB|+|Yi-YB|
где (Xi,Yi) - Координаты точки окрестности. (XВ,YВ)- Координаты конечного элемента.
Таким образом вычисляется восемь значений из которых выбирается минимальное. Элемент от которого расстояние оказалось минимальным выбирается в качестве элемента трассы. Вокруг него снова рассматривается 8-ми элементная окрестность. Процесс продолжается до тех пор пока не будет достигнут конечный элемент. Если на пути встречается препятствие в виде запрещенного элемента, то обход препятствия осуществляется исходя из интуиции разработчика. При этом задаются направления обхода препятствия.
Маршрутный алгоритм основанный на рекурентном соотношении.
Маршрутный алгоритм можно построить на основе следующего рекурентного соотношения:
y(x) = 2y(x + h) + y(x + 2h) + d
Где x,y(x) - абсцисса и ордината элемента занимаемого трассой на данном шаге.
(x + h) - ордината элемента занимаемого трассой на предыдущем шаге.
(x + 2h) - ордината элемента отстоящего от вычисляемого на 2 шага.
h - величина изменения абциссы на каждом шаге.
d (delta) - это функция определяющая вид трассы. Если
d=0 то строится прямолинейная трасса, если
d=const то строится параболическая трасса.
Ордината очередного элемента трассы вычисляется по рекурентной формуле, а абсцисса трассы вычисляется по формуле :
D=Xn=Xn-1+h
Знак "+" или "-" в рекурентной формуле выбирается исходя из того откуда начинается построение трассы, из начального элемента
"+", и соответственно из конечного "-".
По этой формуле чтобы вычислить 3-й элемент трассы необходимо знать два предыдущих. Первым элементом является исходный элемент
A(XA,YA), тогда ордината второго элемента вычисляется по формуле :
Y(X)=Y(XA)+ ((Y(XA)-Y(XB))/(XA-XB))*h
Если на пути встретится запрещенный элемент его обход осуществляется исходя из интуиции разработчика.
Главным достоинством маршрутного алгоритма является простота, а также возможность движения по диагонали.
|
