Генерація та рішення лабіринту за допомогою методу пошуку в глибину по графу, savepearlharbor
Це перша з декількох запланованих статей, присвячених генерації і рішенням лабіринтів.
У цій статті мова піде про найпростіший у реалізації алгоритмі генерації «ідеального» лабіринту і його застосуванні для пошуку шляху.
Ми розглянемо алгоритм, заснований на бектрекінге, що дозволяє створювати лабіринти без циклів, що мають єдиний шлях між двома точками. Алгоритм не найшвидший, досить вимогливий до ресурсів, у порівнянні з алгоритмом Ейлера або Круськала, але дуже простий у реалізації і дозволяє створювати гіллясті лабіринти з дуже довгими тупиковими відгалуженнями.
Зацікавлених - прошу під кат.
У російськомовному інтернеті дуже мало інформації по алгоритмам генерації лабіринтів, що і стало причиною для написання цієї статті.
Приклади коду на мові Сі, а також повний вихідний код проекту на GitHub доступні під ліцензією GNU GPLv3.
Посилання на англомовні ресурси і проект ви знайдете в кінці статті.
опис алгоритму
Зауваження: передбачається, що спочатку у кожної клітини є стінки з усіх чотирьох сторін, які відокремлюють її від сусідніх клітин.
1. Зробіть початкову клітку поточної і відзначте її як відвідану.
2. Поки є невідвідані клітини
1. Якщо поточна клітина має невідвіданих «сусідів»
1. Проштовхніть поточну клітку в стек
2. Виберіть випадкову клітку з сусідніх
3. Приберіть стінку між поточною кліткою і обраної
4. Зробіть обрану клітку поточної і відзначте її як відвідану.
2. Інакше якщо стік не порожній
1. Висмикніть клітку з стека
2. Зробіть її поточної
3. Інакше
1. Виберіть випадкову невідвідування клітку, зробіть її поточною і відзначте як відвідану.
Ви, мабуть, помітили що при виконанні умови 3, готовий лабіринт найімовірніше матиме ізольовану область.
Ця умова включено в алгоритм як виняток, на практиці при нормальній роботі алгоритму і правильних вихідних даних, воно не виконується ніколи.
Реалізація
Як уже сказано вище, передбачається, що при початку роботи алгоритму всі клітини відділені стінками.
Ілюстрація роботи алгоритму
0.
1.
2.1.
2.2.
2.1.
2.
Програмний код
Приступаємо до найцікавішого.
Почнемо діяти по порядку і спочатку сгенерируем початкову матрицю, з якої буде працювати алгоритм.
Для зручності домовимося, що всі типи клітин задані в перерахуванні.
Тепер, коли всі приготування зроблені, можна приступати до генерації.
Структури значно спростять життя при обміні інформацією між функціями.
Уривок коду, який відповідає за генерацію:
Як видно, реалізація алгоритму проста і абстрактна від теорії, як то кажуть, «впорається навіть дитина».
Щоб не перевантажувати статтю, код функцій, використовуваних у вищенаведеному уривку, під спойлером.
Функція getNeighbours повертає масив невідвіданих сусідів клітини
Функція removeWall прибирає стінку між двома клітинами:
Спочатку обчислюється значення різниці координат другої і першої точок. Очевидно, значення може бути або негативне, або позитивне, або 0.
Треба знайти такі координати xy, щоб при додаванні їх з координатами першої точки виходили координати стінки.
Так як ми точно знаємо, що вектор різниці між координатами стінки і першій точці дорівнює або (| 1 | 0) або (0, | 1 |), ми можемо цим скористатися.
Таким чином, аддітів для x координати при xDiff! = 0 буде дорівнює xDiff / | xDiff |, при xDiff = 0, нулю. Для y відповідно.
Отримавши аддитиви для x і y, ми легко обчислюємо координати стінки між першою і другою клітинами і призначаємо клітку по цих координатах відвідується.
Отже, тепер у нас є генератор лабіринтів, який може будувати заплутані лабіринти, розмір яких обмежений тільки розміром оперативної пам'яті.
У підсумку, ми можемо отримати щось таке:
Лабіринти. Обережно, трафік!
Генерація працює, тепер справа за малим: знайти в такому лабіринті вихід.
І все ще сильніше спрощується, так як нам більше не треба прибирати стінки.
Алгоритм пошуку шляху бектрекінгом:
1. Зробіть початкову клітку поточної і відзначте її як відвідану.
2. Ще не знайдений вихід
1. Якщо поточна клітина має невідвіданих «сусідів»
1. Проштовхніть поточну клітку в стек
2. Виберіть випадкову клітку з сусідніх
3. Зробіть обрану клітку поточної і відзначте її як відвідану.
2. Інакше якщо стік не порожній
1. Висмикніть клітку з стека
2. Зробіть її поточної
3. Інакше виходу немає
Подивимося що вийшло:
Вирішені лабіринти. Трафік!
Червоним позначено шлях, блакитним - відвідані клітини.
100 × 100
Ось і все, що потрібно для найпростішої реалізації генератора випадкових лабіринтів.
Для тих, хто зацікавився, повні вихідні тексти проекту на GitHub: Maze Generator and Solver (offscreen rendering)
OSMesa підтримують не всі драйверами на unix-based, а на системі Windows не підтримується зовсім. так що бажаючим, кому не пощастило з ОС / залізом, можу запропонувати ознайомитися з суміжним проектом: Maze Generator and Solver
В обох проектах реалізовані одні й ті ж алгоритми, але перший малює в пам'яті і виводить послідовність png-зображень, а другий на екрані.
Збірка cd build # 038; # 038 ;. / configure # 038; # 038; make, якщо незручно, в папці src є файл-проект QtCreator'a.