1. Предварительный поиск маршрута
Предварительный поиск маршрута осуществляется перед началом построения алгоритма разделения ячеек, чтобы сократить затраты времени и ресурсов на работу алгоритма если задача поиска маршрута не является слишком сложной, с большими свободными областями и малым количеством запрещенных точек.
Рассмотрим шаги алгоритма предварительного поиска маршрута:
1) Определить разницу координат между qт и q0;
2) Изменяем разницу координат так, чтобы свести её к нулю по каждой координате в соответствии со следующими приоритетами шага:
2.1) Изменить (+/-) три координаты xyz за один шаг;
2.2) Изменить две координаты за шаг xy || xz || yz за шаг;
2.3) Изменить одну координату x || y || z за шаг;
3) Проверяем условия:
3.1) Если выбранный в соответствии с приоритетом шаг сделать невозможно из-за помехи в виде запрещенной точки, то приоритет шага понижается. Если приоритет достиг минимума (2.3) и все равно на пути находится препятствие, то производится попытка обойти препятствие (если первоначально задано значение радиуса обхода R) происходит «ощупывание» - проверка соседних областей на наличие возможности обойти препятствие и продолжить путь к qт путем уменьшения разности координат.
3.1.1) Если такая точка найдена, то совершим S шагов (их количество задается предварительно) в этом направлений и продолжаем движение к qт путем уменьшения разности координат.
3.1.2) Если значение радиуса проверено и дальнейший путь не найден, то переходим к алгоритму разделения ячеек.
3.2) Если по одной или двум из координат разница сведена к нулю, то соответственно приоритеты 2.1 и 2.2 не рассматриваются. Если все разницы сведены к нулю, то qт достигнута, иначе переходим к шагу 2.
Рассмотрим небольшой пример (рис. 3). Пусть задан радиус обхода R=1 и количество шагов S=1.
Первый шаг позволяет изменить две координаты за шаг. Сделать следующий шаг в направлении qт мешает запрещенная точка. Попробуем обойти препятствие используя радиус обхода. В одном из случаев возможен обход препятствия. Сделав шаг S в этом направлении вернемся к изменению разницы координат. Совершим следующий и последний шаг в направлении qт и она будет достигнута без применения алгоритма разделения ячеек.
Рисунок 3 – Пример работы алгоритм предварительного поиска с обходом препятствия для двумерного случая
Рассмотрим пример для трехмерного случая, в котором не задан радиус обхода препятствия (рис. 4).
Рисунок 4 - Пример работы алгоритм предварительного поиска без радиуса обхода препятствия для трехмерного случая
Для достижения qт в соответствии с алгоритмом предварительного поиска необходимо сделать шаг из q0 вправо и вниз, только вправо или только вниз. Любому изменению в этих направлениях мешают запрещенные точки (рис. 5). Радиус обхода предварительно не был задан, поэтому алгоритм предварительного поиска не может построить маршрут и происходит переход к следующему шагу алгоритма разделения ячеек.
Рисунок 5 - Пример работы алгоритм предварительного поиска без радиуса обхода препятствия для трехмерного случая
Если же радиус обхода был задан, например R=1 и количество шагов S=1, то алгоритм предварительного поиска смог выбраться из тупика и построить маршрут (рис. 6).
Рисунок 6 - Пример работы алгоритм предварительного поиска с обходом препятствия для трехмерного случая