При построении Н-пути для обхода препятствий используется алгоритм Н-слежения, а при построении Р-пути – Р-слежение.

При отрицательном направлении Р-слежения двоичный код приоритетного направления опреднляется соотношением

,

а при положительном

.

Если направление с высшим приоритетом запрещено, то выбирается первое возможное направление с низшим приоритетом. Определяемое соотношением

,

где n – двоичный код чисел из последовательности 1, 2, …,8.

Суммирование по модулю 8 выполняется при отрицательном направлении слежения, вычитание – при положительном.

Важным моментом является определение элемента, в котором заканчивается обход препятствий и начинается построение пути в оптимальном направлении (по прямой к элементу d_b ). Если в нужный момент не прекратить обход препятствий, то неизбежно зацикливание пути вокруг препятствий. Элемент пути, в котором прекращается обход препятствий, назовем элементом спуска. На рисунке 2 элементом спуска является элемент 19. Здесь приведен путь в лабиринте, построенный согласно этой методике от элемента d_a к элементу d_b . От элемента d_a до элемента 1, который является элементом встречи, выполняется построение пути согласно этапу 1. Обход препятствий начинается от элемента встречи 1 в отрицательном направлении (этап 2) и заканчивается элементом спуска 19. От элемента спуска 19 до конечного элемента пути выполняется
этап 1.

Для определения элемента спуска пути предлагается следующий алгоритм:

a) определяем двоичный код угла поворота вектора перехода относительно вектора Z’ из соотношения

;

причем суммирование выполняется при отрицательном направлении обхода препятствий, вычитание – при положительном.

b) В каждом элементе излома проверяем значение двоичного кода a_k и направление построения пути в наилучшем направлении. Если a_k ³0 и направление обхода препятствий совпадает с наилучшим направлением построения пути, то элемент d_k будет элементом спуска. В противном случае d_k не является элементом спуска.

Этап 3. Минимизация длинны пути сводится к построению выпуклого контура, описанного вокруг первоначального пути. Если нет возможности получить выпуклый контур из-за наличия препятствий, то строится сглаженный контур, т.е. контур, имеющий меньшую длину, чем первоначальный.

Находим все элементы спуска первоначального пути и разбиваем его на отдельные участки, разграниченные элементами спуска. Последовательно минимизируем все участки пути.

1) Находим все элементы излома соответствующего участка пути, и если имеется не более одного излома, то он не подлежит минимизации если элементов излома два и более, то минимизация заключается в том, что строится новый путь L_н (d_a , d_j ) пути L(d_a , d_j ), где d_j - элемент излома пути, самый близкий к конечному элементу.

2) Построенный вновь подпуть L_н (d_a , d_j ) сравнивается по длине с путем L(d_a , d_j ), и если новый путь меньше, то L(d_a , d_j ) заменяется на L_н (d_a , d_j ).

3) Минимизация повторяется для следующего элемента излома, самого близкого к d_j , и до тех пор, пока на L_н (d_a , d_j ) или L(d_a , d_j ) останется один элемент излома.

Осуществляется минимизация обоих первоначально построенных путей, полученных при положительном (левом) и отрицательном (правом) обходе группы препятствий, из которых выбирается минимальный
(рисунок 3).

2. Волновой алгоритм трассировки.

Дискретное поле платы разбивают на три множества, описываемых с помощью булевых матриц:

С – множество элементов поля, требующих соединения между собой (на рисунке 4 множество , где i=0, 1, 2, 3);

Р – множество элементов поля, запрещенных для трассировки (на рисунке 4,а(б) это множество закрашено черным);

S – множество свободных элементов поля платы.

Требуется, используя элементы множества S, соединить элементы множества С в одну цепь, не пересекающую Р.

Процесс нахождения минимального пути состоит из двух этапов:

- Распространение волны от источника до встречи с одним из приемников;

- Определение пути от источника к приемнику.

В качестве источника выбирается один из элементов множества С, все остальные элементы являются приемниками. Обозначим через R_k множество элементов волны на шаге k и назовем его k-фронтом волны, тогда R_{k +1} принадлежит Н-окрестности R_k .

На каждом шаге расширения делается проверка пересечения фонта волны с приемником. Как только какой-либо элемент приемника будет включен в волну, процесс распространения волны завершается, и от ближайшего к источнику элемента приемника начинается построение пути.

Для построения волны используются матрицы распространения волн в горизонтальном (R_k ’), и вертикальном (R_k ) направлении и матрицы точек поворота с вертикального направления на горизонтальное (M_k ) и с горизонтального направления на вертикальное (M_k ’), где

;

;

.

На рисунке 5, а - г приведены соответственно матрицы R_k , R_k ’, M_k , M_k ’, построенные для k=12. Источником является фрагмент С₀ . Для наглядности в клетках, занятых волной, указывается номер шага, на котором достигнута эта точка.