Алгоритми вивчення структури лабіринтів та дослідження ефективності їх застосування
DOI: 10.31673/2412-9070.2024.034851
Анотація
У статті розглядаються лабіринти в контексті задачі їх створення та проходження для застосування в ігровій іт-індустрії. Наводяться базові відомості про лабіринти, їх основні різновиди та структури, наводиться математична модель ідеального лабіринту. Досліджуються та вирішуються питання, пов’язані з вибором параметрів оцінки ефективності їх роботи, безпосередньо аналіз алгоритмів, проєктування тестового додатку на мові Java та аналіз отриманих результатів. Під час оцінки ефективності проаналізовано декілька алгоритмів дослідження структури за параметрами швидкості роботи та надано рекомендації по обраню найоптимальнішого з представлених.
Ключові слова: лабіринт; ідеальний лабіринт; пошук в глибину; пошук в ширину; алгоритм Тремо; Java; програма; алгоритм заповнення глухих кутів.
Список використаної літератури
1. Yerry Soepriyantoa, Akhmad Fakharuddina, Sihkabudena, Eka Pramono Adia. Development of Maze Game on Interactive Whiteboard for Fine Motor Learning // Advances in Social Science, Education and Humanities Research. 2017. vol. 118. Р. 651.
2. Maze Classification [Електронний ресурс]. URL: https://www.astrolog.org/labyrnth/algrithm.htm
3. Introduction to Algorithms, Second Edition / Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein // MIT Press and McGraw-Hill, 2001. Р. 594–611.
4. Jamis Buck. Mazes for Programmes. Code your own twisty little passages. The Pragmatic Bookshelf.
5. A Comprehensive and Comparative Study of Maze-Solving Techniques by Implementing Graph Theory / Adil M. J. Sadik, Maruf A. Dhali, Hasib M. A. B. Farid [et al.] // Department of Electrical and Electronic Engineering. 2010. p. 52–53.
6. Maze-solving algorithm [Електронний ресурс]. URL: https://en.wikipedia.org/wiki/Maze-solving_algorithm
