Методи генерації та проходження лабіринтів

Abstract

Метою кваліфікаційної роботи є дослідження методів генерації лабіринтів та пошуку шляхів, а також їх порівняльний аналіз. Розглянуто підходи на основі алгоритму бінарного дерева, методу Олдоса-Бродера та алгоритму Еллера для генерації лабіринтів, та пошук у ширину, алгоритм Дейкстри та метод А* для вирішення задачі пошуку шляху. Передбачено створення застосунку, що дозволить користувачу генерувати лабіринт за одним із обраних алгоритмів і знаходити шлях за допомогою реалізованих методів. Для розробки програмного застосунку використовуються ігровий двигун Unity та мова програмування C#. У ході виконання кваліфікаційної роботи реалізовано застосунок, який генерує лабіринт одним з обраних методів та виконує пошук найкоротшого шляху у лабіринті усіма реалізованими алгоритмами водночас. Лабіринт генерується з заданим параметром розмірності, а знайдений шлях аналізується за часом, витраченим на його пошук. Проведено порівняльний аналіз алгоритмів генерації та вирішення лабіринтів.