Алгоритм завоювання для стохастичного заповнення двовимірних дискретних решіток зв’язаними областями - Красніков , Влад Валерійович; Ситнікова, Поліна Едуардівна (Автоматизовані системи управління та прилади автоматики, 2025)
Запропоновано новий алгоритм, що дозволяє розв’язати розповсюджену проблему генерації змістовних стохастичних зв’язаних областей для двовимірних дискретних полів. Проведено дослідження, в ході якого сформульовано відповідну чітку задачу, ілюстровану прикладом у вигляді створення ігрового поля для модифікованої версії класичної задачі N-Queens. Задача полягає у реалізації алгоритму, який дозволив би створювати будь яке поле площею N x N, де N > 0, задається вручну. Поле повинно процедурно заповнюватись зв’язними областями. Проведено аналіз існуючих алгоритмів та підходів, які зазвичай використовуються у процедурній генерації у сумісних індустріях. Серед таких розглянуто: градієнтний шум Перліна; клітинні автомати; хвильова заливка і випадкове блукання. Зроблено висновки, що ці алгоритми у їхній класичній репрезентації не підходять для процедурного створення ігрового поля для обраної задачі, тому у дослідженні запропоновано новий алгоритм, який є похідним від алгоритму випадкового блукання. Цей алгоритм полягає у створенні агентів, які в даному випадку є ферзі на шахівниці. Кожен агент рухається по черзі, але можливість ходу і вибір ортогонального напряму задається за допомогою додаткових критеріїв, таких як: формула пропуску ходу, пріоритет нічийних клітин над власними, пріоритет клітин ближчих до краю поля і неможливість заходити на чужі поля. Алгоритм реалізовано з використанням мови програмування С#. В роботу програми було також додано можливість зробити декілька генерацій поспіль і порахувати метрики для отриманих фігур на матрицях. Для дослідження успіху запропонованого алгоритму було використано такі метрики: середня витягнутість, середня прямокутність, середня зубчастість контуру, максимальна витягнутість, максимальна прямокутність і мінімальна зубчастість контуру. Було також пораховано метрику ефективності алгоритму щодо його складності тобто (кількість кроків агентів поділена на площу решітки). Для розрахунку ефективності та збору метрик було проведено по тисячі експериментів зі значеннями розміру поля N x N, де N = 8, 12, 20. Результати роботи довели, що алгоритм працює, виконує поставлену задачу і є ефективним.