Алгоритм завоювання для стохастичного заповнення двовимірних дискретних решіток зв’язаними областями
DOI:
https://doi.org/10.30837/0135-1710.2025.185.070Ключові слова:
алгоритм завоювання, стохастичне заповнення, двовимірна дискретна решітка, зв’язні областіАнотація
Запропоновано новий алгоритм, що дозволяє розв’язати розповсюджену проблему генерації змістовних стохастичних зв’язаних областей для двовимірних дискретних полів. Проведено дослідження, в ході якого сформульовано відповідну чітку задачу, ілюстровану прикладом у вигляді створення ігрового поля для модифікованої версії класичної задачі N-Queens. Задача полягає у реалізації алгоритму, який дозволив би створювати будь яке поле площею N x N, де N > 0, задається вручну. Поле повинно процедурно заповнюватись зв’язними областями.
Проведено аналіз існуючих алгоритмів та підходів, які зазвичай використовуються у процедурній генерації у сумісних індустріях. Серед таких розглянуто: градієнтний шум Перліна; клітинні автомати; хвильова заливка і випадкове блукання.
Зроблено висновки, що ці алгоритми у їхній класичній репрезентації не підходять для процедурного створення ігрового поля для обраної задачі, тому у дослідженні запропоновано новий алгоритм, який є похідним від алгоритму випадкового блукання.
Цей алгоритм полягає у створенні агентів, які в даному випадку є ферзі на шахівниці. Кожен агент рухається по черзі, але можливість ходу і вибір ортогонального напряму задається за допомогою додаткових критеріїв, таких як: формула пропуску ходу, пріоритет нічийних клітин над власними, пріоритет клітин ближчих до краю поля і неможливість заходити на чужі поля.
Алгоритм реалізовано з використанням мови програмування С#. В роботу програми було також додано можливість зробити декілька генерацій поспіль і порахувати метрики для отриманих фігур на матрицях. Для дослідження успіху запропонованого алгоритму було використано такі метрики: середня витягнутість, середня прямокутність, середня зубчастість контуру, максимальна витягнутість, максимальна прямокутність і мінімальна зубчастість контуру. Було також пораховано метрику ефективності алгоритму щодо його складності тобто (кількість кроків агентів поділена на площу решітки).
Для розрахунку ефективності та збору метрик було проведено по тисячі експериментів зі значеннями розміру поля N x N, де N = 8, 12, 20. Результати роботи довели, що алгоритм працює, виконує поставлену задачу і є ефективним.
Посилання
Sinha, R., Kaur, N., Gupta, S., Thakur, P. (2025). N-Queen Problem Solution Using Modified Genetic Algorithm. In: Bajaj, A., Sreedhar, S., Abraham, A. (eds) Bio-Inspired Computing. IBICA 2023. Lecture Notes in Networks and Systems, vol. 1230. Springer, pp. 201–210.
Perlin K. (1985) An Image Synthesizer. ACM SIGGRAPH Computer Graphics, vol. 19, no. 3, pp. 287–296, https://doi.org/10.1145/325334.325247
Кудінов І. П., Ягодкін Д. (2025). Алгоритми процедурної генерації шуму Перліна. Зб. тез наук. доп. здобувачів вищої освіти Бердян. держ. пед. ун ту, Запоріжжя, Україна, трав. 2025, с. 127-130. https://doi.org/10.5281/zenodo.15548937
Kopel, M., Maciejewski, G. (2020). Comparison of Procedural Noise-Based Environment Generation Methods. In: Nguyen, N.T., Hoang, B.H., Huynh, C.P., Hwang, D., Trawiński, B., Vossen, G. (eds) Computational Collective Intelligence. ICCCI 2020. Lecture Notes in Computer Science, vol 12496. Springer, Cham. pp 878–887.
Wu Z., Mao Y., Li Q. (2021). Procedural Game Map Generation using Multi leveled Cellular Automata by Machine Learning, in Proc. ISAIMS 2021, Chongqing, China, Oct. 2021, https://doi.org/10.1145/3500931.3500962
Fellows M. R., Rosamond F. A., da Silva M. D., Souza U. S. (2021). A Survey on the Complexity of Flood Filling Games. Discrete Appl. Math., vol. 304, pp. 233–246, Dec. 2021, https://doi.org/10.1016/j.dam.2021.09.029
Popp S., Dornhaus A. (2023). Ants Combine Systematic Meandering and Correlated Random Walks when Searching for Unknown Resources. iScience, vol. 26, no. 2, 2023, Art. no. 105916, https://doi.org/10.1016/j.isci.2022.105916
