Класичні алгоритми генерації лабіринтів. Частина 1: Вступ



Передмова
На написання статті мене спонукало практично повна відсутність матеріалів російською мовою про алгоритми генерації лабіринтів. На Хабре, з того, що взагалі є по темі, можна відзначити дві статті: раз і два. Цінність і користь з яких несе лише друга. У першій – просто переклад формального алгоритму та невелика його пояснення. Що, звичайно, непогано, але дуже бідно і не викликає бажання вивчати тему далі.

Якщо моя стаття Вам сподобається, я продовжу писати про різних алгоритмах. Ми розглянемо два найбільш примітивних і простих випадку – генерація двійкового дерева і Сайдвиндер, який, по своїй суті, просто трохи змінена версія двійкового дерева з одним помітним плюсом. ОБЕРЕЖНО ТРАФІК.

Дам одну пораду – не підглядайте в код до тих пір, поки ви не напишіть свою реалізацію. Ви отримаєте набагато більше задоволення і користі від виправлення помилок і пошуку помилок, ніж якщо просто переведете з однієї мови на іншу.

Серйозно. Прислухайтеся до поради. Ви, вірно, витратите більше часу, але воно коштує варто. У мене, наприклад, із-за пари помилок з'явився дуже забавний генератор «інопланетних» текстів, який можна використовувати в різних Sci-Fi іграх для створення тексту. Сподіваюся, Ви вивчаєте тему для себе і нікуди не поспішайте.

P. S.:

Я буду використовувати термін «зміщення», припускаючи англійська bias. Тобто пристрасть до алгоритму спрямованості в яку-небудь сторону. Наприклад, праве зсув – алгоритм генерує лабіринти з довгими правими проходами.

Розмальовка лабіринтів відбувається щодо відстані від крайнього лівого кута поля до певної клітини. Чим далі від початкової координати – тим темніше буде колір.

Ідеальний лабіринт – такий лабіринт, в якому одна клітина пов'язана з іншою одним єдиним шляхом. Інакше кажучи, остовне дерево.

Про LuaКоли я тільки починав закопуватися в тему лабіринтів, я не припускав, що в підсумку буду писати статтю і вибрав мову, на якому у мене є можливість не витрачати занадто багато часу на рендер і архітектуру і займатися виключно логікою. В результаті, між C++ і Lua, вибір припав на Lua і Love2D.

Не варто переживати, якщо Ви з Луа незнайомі. Незнання мови ніяк не завадить Вам зрозуміти реалізацію, завдяки простоті синтаксису. Якщо Ви хоча б трохи вмієте програмувати, 80% коду не викличе у Вас проблем з розумінням. Решта 20% — specific language, про які я завжди буду писати спочатку статті, пояснюючи їх роботу.

Перше, що мені слід сказати:
Lua має лише одну структуру даних – таблиці – асоціативний масив, при допомозі якого ми створюємо потрібні нам структури. Наприклад, класи, безлічі, звичайні масиви, стаки, черги тощо. Звертатися до них ми може або з допомогою рядкових-ключів, або з допомогою індексів.
Так само, таблиці не обмежують нас у зберіганні тільки одного типу даних в одному об'єкті і працюють подібно структурам в C/C++. Такий код абсолютно коректний:

ourStructure = {}
ourStructure["BeautyKey"] = 42
ourStructure[42] = "UltimateAnswer"
ourStructure[1] = false

Присвоювання nil видалить поле:
ourStructure[42] = nil


Друге:
Lua не має прихованого механізму копіювання таблиць. Код, наведений нижче, не буде копіювати і створювати нового об'єкта SomeNewArray, він лише копіює в нього посилання на об'єкт SomeArray, і, отже, буде змінювати його точно так само, як якщо Ви передасте значення через неконстантную посилання чи вказівник на C/C++:

someArray = {}
someArray[1] = 42
someArray[2] = "ReferencesTest"
someNewArray = someArray 
someNewArray[1] = "42 Is Gone, Now Only the Garbage-String here"


І третє, для тих, хто добре знайомий з Lua:
Так, я знаю, що в деяких місцях код надмірний. І те, що в деяких місцях все можна було б спростити метаметодами теж. Слід враховувати те, що код писався в першу чергу для того, щоб розібратися з алгоритмами, а не для використання в реальному проекті. До того ж, відсутність надлишку специфічних для мови функцій дозволяє викладати код в тому вигляді, в якому він є, без нагромаджень коментарів.


Алгоритм двійкового дерева






Опис:

Перший і найпростіший алгоритм у розумінні, який я розгляну. Його суть полягає в тому, щоб прокласти шлях у випадковому напрямку з кожної клітини поля: в моїй реалізації або наверх, або вправо (залежить від вибраного Вами зміщення). Ми розглядаємо тільки 1 клітку за одиницю часу, отже, ми можемо генерувати лабіринти нескінченного розміру, зберігаючи лише кінцевий результат (лабіринт) без необхідності зберігати якусь побічну інформацію.

Такий спосіб генерації має два побічних ефекти:

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

2. Два порожніх коридору по сторонах лабіринту. Коли алгоритм «прокапывается» до кінця рядка/стовпця, йому не залишається вибору, окрім як продовжити шлях в одному єдиному напрямку, створюючи порожні «кордону».

До речі, назву не просто так збігається зі структурою даних. Результат його роботи – випадкове двійкове дерево, в якому з кожної клітини (вершини) є рівно 1 шлях у напрямку до кореня (батьківської вершини), і, відповідно, рівне 1 шлях до будь-якої іншої клітці. Як наслідок, будь-яка клітина має не більше 3 з'єднань зі своїми сусідами.

Формальний алгоритм (для північно-східного зміщення):

  1. Вибрати початкову клітинку;
  2. Вибрати випадкове напрямок для прокладання шляху. Якщо сусідня клітка в цьому напрямку виходить за межі поля, прокопати клітку в єдино можливому напрямку;
  3. Перейти до наступного клітці;
  4. Повторювати 2-3 до тих пір, поки не будуть оброблені всі клітини;
Приклад роботиЗелене – розглянута поточна клітка, червоне – фронт, клітини, в які можна переміститися.

Починаємо з координати (0;0). Нагору в цьому ряду піти не можемо, так як інакше вийдемо за межі лабіринту. Йдемо вправо до упору, по дорозі зносячи всі стіни.





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



Кидаємо монетку і вибираємо… Верх. Прибираємо стіну і переходимо до наступної клітці.


Відмінно. Випадок підказує нам йти направо. Прибираємо стіну і переміщаємося в наступну клітину.







Вибору у нас немає, наліво піти не можемо, значить, прибираємо стіну зверху і йдемо на наступний ряд.





Монета переконує нас піти направо. Що ж, слухаємося. Прибираємо стіну і переходимо до слеудующей клітці.





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







Плюси:
  • Проста реалізація;
  • Висока швидкість роботи;
  • Можливість генерувати нескінченні лабіринти;
Мінуси:
  • Низька складність малюнка;
  • Сильний зсув по діагоналі;
  • Відсутність тупиків по зсуву;
  • Одноманітність згенерованих лабіринтів;
Реалізація

local mod = {}
local aux = {}

aux.width = false
aux.height = false
aux.sx = false
aux.sy = false
aux.grid = false

function aux.createGrid (rows, columns)
local MazeGrid = {}

for y = 1, rows do 
MazeGrid[y] = {}
for x = 1, columns do
MazeGrid[y][x] = {bottom_wall = true, right_wall = true} -- Wall grid
end
end 
return MazeGrid
end

-- Binary Tree North-East variant 
function mod.createMaze(x1, y1, x2, y2, grid)
aux.width, aux.height, aux.sx, aux.sy = x2, y2, x1, y1
aux.grid = grid or aux.createGrid(aux.height, aux.width)
aux.binarytree()
aux return.grid
end

function aux.binarytree() 
for y = aux.sy, aux.height do 
for x = aux.sx, aux.width do
if y ~= aux.sy then 
if math.random(0, 1) == 0 then 
if x ~= aux.width then 
aux.grid[y][x].right_wall = false
else
aux.grid[y-1][x].bottom_wall = false
end
else
aux.grid[y-1][x].bottom_wall = false
end
else
if x ~= aux.width then 
aux.grid[y][x].right_wall = false 
end
end
end
end
end

return mod


Алгоритм «Sidewinder»






Опис:

Алгоритм з неперекладним назвою Sidewinder по своїй роботі дуже схожий на алгоритм двійкового дерева, в тому відмінності, що в ньому немає характерного зміщення по діагоналі, одного порожнього коридору і клітини ми розглядаємо не окремо, а множинами. Лабіринти виходять з переважно вертикальним або горизонтальним зміщенням (в залежності від реалізації), з відсутністю тупиків у їх напрямку. У порівнянні зі своїм більш примітивним побратимом, зсув не так помітно і більше схоже на «спіраль», яка плавно змінює вертикальні і горизонтальні коридори.

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

Для прикладу: 9 клітин першого ряду можна поділити на три множини, між якими розташовані стіни. Кожне безліч другого ряду буде прокопувати шлях до одного з трьох «блоків» вище. Третій ряд прокладе шлях до «блоків» другого. І так до кінця поля. У підсумку, у нас вийдуть 3 розгалужені, ізольовані один від одного вертикальні області, що не підходить для ідеального лабіринту, в якому з кожної точки поля є рівно 1 шлях у будь-яку іншу.

Формальний алгоритм (для стандартного зміщення):

  1. Вибрати початковий ряд;
  2. Вибрати початкову клітинку ряду і зробити її поточної;
  3. Ініціалізувати порожня множина;
  4. Додати поточну клітку в безліч;
  5. Вирішити, прокладати шлях направо;
  6. Якщо проклали, то перейти до нової клітці і зробити її поточною. Повторити кроки 3-6;
  7. Якщо не проклали, вибираємо випадкову клітку безлічі і прокладаємо звідти шлях наверх. Переходимо на наступний ряд і повторюємо 2-7;
  8. Продовжувати, поки не буде оброблений кожний ряд;
Приклад роботиЧервоні клітини – члени множини.
Ми починаємо з першого ряду і бачимо, що вище нас – вихід за межі поля. Зносимо всі стіни і йдемо відразу в другий ряд, створюємо порожній безліч.





Так, а ось тут цікавіше. Давайте додамо в безліч перші дві клітини ряду.



Вибираємо одну з цих клітин і прибираємо відноситься до неї верхню стінку в перший ряд.



Обнуляем безліч, додаємо в неї наступну клітину ряду.



Цього разу ні з ким не об'єднуємо, просто прокладаємо шлях наверх прямо з цієї єдиної клітини.



Повторюємо наші дії. Обнуляем безліч, переходимо в наступну клітину, додаємо її… А так як вона залишилася останньою у низці, то так само прибираємо стіну зверху і йдемо в ряд нижче.





А тепер відразу об'єднуємо три перші клітини в одне безліч.



Випадково вибираємо клітку, в нашому випадку, другу і прибираємо стіну зверху до попереднього ряду.



Ну, тут у нас знову немає вибору, прибираємо стіну вгорі і йдемо на ряд нижче.





На цей раз, саму перваую клітку ми зробимо єдиною. Прибираємо стіну до попереднього ряду і йдемо далі, в наступну клітину.





Припустимо, що захотіли в кінці об'єднати три клітини.



І знову нам сподобалася середня клітка з безлічі, з якої і прибираємо стіну наверх. Все, наш лабіринт готовий.


Плюси:

  • Можливість генерувати нескінченні лабіринти;
  • Тільки 1 порожній коридор;
  • Більш складний малюнок, на відміну від алгоритму двійкового дерева;
Мінуси:

  • Більш заплутана реалізація;
  • Відсутність тупиків по зсуву;
  • Сильне вертикальне зміщення;
Реалізація
local mod = {}
local aux = {}

aux.width = false
aux.height = false
aux.sx = false
aux.sy = false
aux.grid = false

function aux.createGrid (rows, columns)
local MazeGrid = {}

for y = 1, rows do 
MazeGrid[y] = {}
for x = 1, columns do
MazeGrid[y][x] = {bottom_wall = true, right_wall = true}
end
end 
return MazeGrid
end

function mod.createMaze(x1, y1, x2, y2, grid)
aux.height, aux.width, aux.sx, aux.sy = y2, x2, x1, y1
aux.grid = grid or aux.createGrid(y2, x2)
aux.sidewinder()
aux return.grid
end

function aux.sidewinder()
local cx = aux.sx --[[ cx – координата початку множини з x. У нас немає потреби створювати окремий масив для сета, так як його елементи завжди розташовуються строго в ряд ]]
for y = aux.sy, aux.height do
for x = aux.sx, aux.width do 
if y ~= aux.sy then
if math.random(0, 1) == 0 and x ~= aux.width then
aux.grid[y][x].right_wall = false
else 
aux.grid[y-1][math.random(cx, x)].bottom_wall = false

if x ~= aux.width then
cx = x+1
else 
cx = aux.sx
end
end
else 
if x ~= aux.width then 
aux.grid[y][x].right_wall = false 
end
end
end
end
end

return mod


Епілог
Сподіваюся, Вам сподобалася стаття і Ви почерпнули нові знання про примітивною процедурної генерації лабіринтів. Я вибрав два найбільш простих у реалізації та роботі алгоритму, щоб новачкам було простіше «помацати» тему і зрозуміти, чи вони хочуть вивчати її далі. Мені важливо знати, чи цікаві такі статті людям на Хабрахабре і чи варто продовжувати їх писати. Для читачів у мене є ще мінімум 9 класичних алгоритмів, які варто розглянути. Якісь представляють із себе випадкове блукання по полю, як, наприклад, алгоритм Прима або Вілсона, які вимагають більше ресурсів для роботи, так як працюють з графами, наприклад, Еллер і Крускал, а якісь витримують золоту середину. Але і це не кінець – у мене в рукаві є такі речі, як: полярні (круглі) лабіринти, генерація лабіринтів на різній сітці (гекси, трикутник тощо), маскінг лабіринтів написи і форми, 2.5 Д лабіринти і 3Д, теорія лабіринтів, статистичне порівняння алгоритмів, комбіновані алгоритми генерації. Зрештою, у нас є ще безліч варіацій типів лабіринтів. Наприклад, зараз ми розглядаємо ідеальні алгоритми, в яких з кожної точки є рівно один шлях у будь-яку іншу. Але ж є ще й ті, які дозволяють одній клітці мати кілька шляхів для будь-якої іншої! Наприклад, Quake, Doom і інші шутери в тільки-тільки зароджується жанрі використовували такі алгоритми для генерації рівнів, за деякими чутками.

Тому, якщо Вам сподобалася стаття, тема, і Ви хочете бачити далі – то, будь ласка, напишіть про це в коментарі. Так само, буду дуже радий будь-якої критики, як в технічному плані, так і в лінгвістичному і стилістичному.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.