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

Abstract

В статті розглянуто променевий алгоритм пошуку шляху, який в теорії графів застосовується для пошуку шляху між вершинами зв`язного графу. На практиці він використовується для вирішення цілого ряду прикладних задач. Застосовуючи променевий алгоритм пошуку шляху знаходять та будують маршрути від початкової точки до місця призначення у картах та навігаторах на місцевості, при проєктуванні електронних плат мікроконтролерів, в логістиці, картографії, комп`ютерних іграх. Використання штучного інтелекту у безпілотних транспортних засобах актуалізувало застосування променевого алгоритму пошуку шляху, як швидкий і маловитратний спосіб побудови маршрутів в режимі реального часу і в ситуації динамічних змін поточних сценаріїв руху. Особливостями променевого алгоритму пошуку шляху є направлений пошук вздовж вибраних променів, рух променів з обох вершин у напрямку один до одного, побудова шляху від вершини перетину взаємонаправлених променів. Запропоновано застосувати променевий алгоритм пошуку шляху для гексагональних комірок. Характерною особливістю гексагональних комірок є їх шестизв`язна симетрія та найнижче співвідношення периметра до площі серед інших багатокутників (і квадрата в тому числі). Застосовуючи променевий алгоритм пошуку шляху на гексагональних комірках буде збільшено можливі напрямки поширення променю з 4-х до 6-ти. Дослідження поля гексагональних комірок здійснюється у напрямку руху променю, залежно від початкових передумов, що визначаються різницею координат початкової комірки і комірки призначення, до якою моє бути прокладено шлях. Оскільки під час аналізу координат комірок вибираються і аналізуються координати не всіх комірок, а тільки ті, що розміщені на шляху променю, променевий алгоритм пошуку шляху матиме кращу швидкодію під час реалізації, ніж хвильовий алгоритм. Недоліком променевого алгоритму пошуку шляху є те, що не завжди можна знайти шлях між визначеними комірками, хоча варіанти шляху можуть існувати. Також запропоновано представлення поля гексагональних комірок у виді зв`язного графу та перетворення у двовимірну матрицю, для кращої обробки програмними засобами, та для виявлення непрохідних комірок, якщо такі присутні.