Непристойно простий алгоритм генерації лабіринтів

Технології 10 січня 2025

Простенький алгоритм генерації ідеальних лабіринтів у звичайному двомірному просторі. Nuff said, інше під катом.

Пошук і розчарування
1. Передбачуваність
2. Споживання пам "яті
3. Недосконалість алгоритму
Ідея і реалізація
Власне, алгоритм

Пошук і розчарування

Почну без зайвих подробиць і прелюдій - мені в ході моєї студентської життєдіяльності знадобився алгоритм генерації прямокутного лабіринту. З молитвою на грішних устах я з головою занурився в нескінченні надра гугла і накопав ось цю статтю. Алгоритм був простий і зрозумілий, він давав необхідні мені ідеальні, не циклічні лабіринти (з будь-якої точки лабіринту можна потрапити в будь-яку іншу його точку, причому тільки одним шляхом), але через свої мізерні на той момент пізнання в програмуванні, я затягнув повноцінну реалізацію на півроку. Так вийшло. І, відверто кажучи, розчарувався в результаті. Алгоритм видавав більш-менш цікаві лабіринти при розмірності менше 20, проте десь з цього рубежу почалися проблеми.

1. Передбачуваність

Як я не намагався, потрапити з лівого верхнього кута лабіринту в правий верхній можна було тільки пройшовшись по двох нижніх рівнях. Що давало деякі можливості, начебто зробити їх чимось на зразок широкого коридору, але мені це було не потрібно.

2. Споживання пам "яті

Алгоритм я писав на старому доброму Pascal, який запускав через емулятор DOSBox. Це обмежувало мою оперативну пам'ять 64-кілобайтним обрубком. Оскільки лабіринт я зберігав у масиві структур, які включали в себе три байтових змінних, то створення лабіринту розмірністю більше 150х150 без залучення динамічної пам'яті було проблемним.

3. Недосконалість алгоритму

Так вже вийшло, що алгоритм розглядав не всі можливі варіанти розвитку подій, що призводило до появи різних небажаних артефактів.

Після усвідомлення цих трьох пунктів, я вирішив відмовитися від цього алгоритму і створити свій.

Ідея і реалізація

Отже, мені потрібен був ідеальний і не циклічний лабіринт. Попередній алгоритм мав на увазі зведення стін у порожньому приміщенні, тому я вирішив піти іншим шляхом, а саме - прокопувати дороги в суцільному грунті. Робити це буде невелика «землерийка», яка буде для нас залишатися двомірними координатами. Але який алгоритм керуватиме рухами «землерийки»? Ніякої! «Землерийку» по нашому неосяжному підземеллю буде ганяти Великий Корейський Рандом.

Власне, алгоритм

Позначимо 1 як прохід і 0 як стіну. Початкові умови - двомірний масив, заповнений нулями. Розмірність масиву - будь-які непарні числа. Вважаємо, що лівий верхній кут стіни має координати (1; 1). Координати «землерийки» завжди парні, пересувається вона, відповідно, тільки стрибками довгою в два елементи масиву.

Випадковим чином вибираємо точку приземлення «землерийки» - генеруємо випадкові ненульові координати. Точці приземлення присвоюється значення 1.
Випадково вибираємо один з напрямків - верх, низ, ліво, право.
Якщо після стрибка в обраному напрямку ми опинимося в зовнішній стіні або в проході, то повернутися до попереднього пункту. Інакше - стрибаємо в зазначеному напрямку. Присвоюємо значення 1 клітині, в яку приземлилися і через яку перестрибнули.
Якщо після приземлення ми не можемо зробити стрибок (потрапляння в глухий кут), то ми випадково генеруємо координати. Інакше - переходимо до другого пункту.
Повторюємо пункт вище до тих пір, поки в зазначених координатах не буде прохід.

Все до непристойності просто. Рано чи пізно ми зациклимося в останніх двох пунктах. Перериванням алгоритму може бути або лічильник, або проста перевірка - якщо в кожній комірці з парними координатами знаходиться 1, то алгоритм можна сміливо переривати.

Переваги: