Рух у випадковому напрямку

Якщо перешкода невелика і опукла, то об’єкт швидше за все зможе її обійти, рухаючись від неї, і намагаючись рухатись навмання в іншому напрямку доти, доки досягне не цілі. На рис. 9.1 показано роботу цього алгоритму.

Тут і далі сірим кружечком позначено рухомий об’єкт, білим – ціль руху, а чорними квадратами – перешкоди.

Проблеми виникають тоді, коли перешкоди досить великі або коли вони увігнуті, як показано на рис. 9.2. Об’єкт може здійснити чимало спроб, перш ніж правильний шлях буде знайдено, або правильного шляху не буде знайдено взагалі. На щастя, за допомогою наступного методу об’єкт успішно долає подібні перешкоди.

Метод відслідковування меж перешкод

Якщо перешкода досить велика і не має опуклої форми, то після зіткнення із нею можна спробувати її обійти, прямуючи за видимими

обрисами доти, доки напрямок на ціль не буде блокуватися цією перешкодою. На рис. 9.3, а і 9.3, б показано, як цей алгоритм вирішує проблеми, з котрими не може впоратись алгоритм руху у випадковому напрямку.

a б

Рис. 9.3. Метод відслідковування обрисів перешкод

Основною перевагою наведених вище алгоритмів є те, що вони не потребують апріорної інформації про всі перешкоди, розміщені на шляху до цілі. Обхід перешкод відбувається по мірі їх виникнення, що знижує вимоги до пам’яті для таких алгоритмів. З другого боку, бачимо, що знайдені траєкторії не оптимальні за довжиною. У такому разі єдиний розумний підхід – це планування всього шляху перед початком переміщень. Такі алгоритми відомі під загальною назвою методи обходу зв’язних графів.Крім того,ці методи дозволяють вирішувати проблему пошуку оптимальної траєкторії з урахуванням різної «вартості» руху за різними елементами карти.

9.3. Метод «пошуку в ширину»

Найбільш простим алгоритмом серед методів обходу зв’язних графів – це метод «пошуку в ширину» (breadth-first search). Принцип його роботи такий: починаючи з першого вузла (положення), цей ал-

горитм перевіряє спочатку всі вузли, що межують з ним, потім всі вузли в двох кроках від нього, потім у трьох кроках, і так далі доти, доки цільового вузла (положення) не буде знайдено. Зазвичай всі необстежені сусідні вузли вміщуються у список «відкритих» вузлів, який є стеком типу «першим зайшов, першим вийшов» (FIFO, first-in-first-out).Алгоритм цього методу такий:

functionBreadthFirstSearch : Boolean;var

n, n', s : node; Open : queue;

Begin

s.parent := nil; // s is a node for the start push s on Open

whileOpen is not emptydo beginpop node n from Open

ifn is a goal nodethen begin(9.1)construct path

result := true; // success exit;

End;

foreach successor n' of ndo begin ifn' has been visited already,

then continue;n'.parent := n; push n' on Open

end;end;

result := false; // no path found

End

На рис. 9.4 показано результат роботи алгоритму (9.1).

Бачимо, що алгоритм дійсно знаходить шлях обходу перешкод і цей шлях гарантовано оптимальний (найкоротший) за умови, що рух усіма дозволеними елементами карти має однакову «вартість». Проте є декілька проблем, пов’язаних з алгоритмом «пошуку в ширину». По-перше, пошук здійснюється в усіх напрямках, замість того, щоб проводити його за напрямком до цілі. По-друге, не всі кроки мають однакову довжину. Перехід на сусідній елемент по діагоналі довший, ніж перехід під прямим кутом.

Рис. 9.4. Робота алгоритму«пошуку в ширину»

Одне з можливих поліпшень такого алгоритму полягає в тому, що пошук ведеться одночасно від початкового положення до цілі та від цілі до початкового положення. Результат роботи такої модифікації подано на рис. 9.5.

Рис. 9.5. Двонапрямлений пошук у ширину

Подібні методи поліпшення можуть використовуватись і для інших алгоритмів пошуку.

9.4. Метод «пошуку в глибину»

Логічною альтернативою методу «пошуку в ширину» став метод «пошуку в глубину» (depth-first search), за якого пошук ведеться переважно в бік віддалення від розглядуваного вузла, а не в бік пошуку в сусідніх до нього вузлах. Очевидно, що в цьому випадку потрібні додаткові умови припинення такого процесу, наприклад, за досягнення заданої глибини пошуку.

З погляду реалізації цей алгоритм відрізняється від методу «пошуку в ширину» (9.1) лише тим, що замість черги FIFO використовують чергу типу «останній зайшов, перший вийшов» (LIFO, last-in-first-out).