Класичні алгоритми генерації лабіринтів. Частина 2: занурення у випадковість



Передмова
частина Перша

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

У цій частині ми поговоримо про те, що ж таке випадкова і псевдослучайная генерації, які алгоритми можуть дати нам рівноймовірно нічим не схожі один на одного лабіринти і в чому їх мінуси. Героями нашого сьогоднішнього пригоди стануть алгоритм Вілсона і алгоритм Олдоса-Бродера для створення випадкового остовного дерева (Uniform Spanning Tree). ОБЕРЕЖНО ТРАФІК.

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

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

Про LuaВ алгоритмі Вілсона, і, можливо, в деяких інших, про які я буду писати, для вибору випадкової ще не відвіданого клітини використовується функція next (table [, index]). Її опис з офіційної документації Lua:
Дозволяє програмі отримати всі поля таблиці. Перший параметр – це таблиця, другий – індекс у таблиці. next повертає наступний індекс в таблиці і відповідного йому значення. Якщо другий параметр nil, next повертає початковий індекс і пов'язане з ним значення. При виклику останнього індексу, або з nil в порожній таблиці, next повертає nil. Якщо другий параметр відсутній, він інтерпретується як nil. Зокрема, Ви можете використовувати next(t) для перевірки порожня таблиця, чи ні.
Отже, замість того, щоб вибирати клітку з допомогою math.random і перевіряти, чи оброблена вона або використати зв'язку стек-клітин разом з хеш-таблицею для відстеження місця розташування в ньому, можна використовувати лише одну хеш-таблицю, ключі в якій будуть захэшироваными координатами і брати елементи з неї з допомогою next.

key = next(cellsHash, nil)
local start_x, start_y = aux.deHashKey(key)
cellsHash[key] = nil — Нагадаю, присвоювання nil видаляє елемент/поле


Зміщення і випадковість
Що ми розуміємо під випадкової генерацією? Чи можемо ми сказати, що якщо в другому лабіринті, на відміну від першого, відсутній дві стінки на півдні, то вони повністю випадкові? Або якщо перший лабіринт має на два горизонтальних коридору більше? І так, і ні.

Говорячи про випадковості в лабіринтах, ми повинні чітко усвідомлювати, що маємо на увазі. Давайте подивимося на результат роботи алгоритму двійкового дерева:





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

Ми отримали випадковий результат? Так. Чи можемо ми його таким вважати? Ну, на мою думку, немає.

Проблема в зсуві (bias), яке багато в чому визначає «випадковість». Алгоритми, які за визначенням повинні створювати випадкові лабіринти, в підсумку створюють схожі. Якщо «схожість» яскраво виражена, як у двійковому дереві, ми говоримо, що такий лабіринт легко вирішується. Якщо ж при порівнянні декількох лабіринтів нам важко однозначно сказати, до чого тяжіє алгоритм, ми говоримо, що такий лабіринт вирішується складніше. Для знаходження зсув, нам потрібно порівняти кілька результатів генерації і побудувати статистичну модель, за якої б ми могли написати більш розумний пошук шляху або самим, «більш розумно» вирішувати лабіринти такого типу. Наприклад, ми можемо сказати, що алгоритм двійкового дерева має в n разів більше горизонтальних проходів, ніж вертикальних. Значить, можна буде врахувати дані і прискорити процес знаходження виходу.

А що якщо ми хочемо, щоб зміщення взагалі не було? Щоб, приміром, 9 не пов'язаних точок графа, кожен раз ми отримували зовсім несхоже на інші остовне дерево? Тоді нам потрібно, щоб кожен з напрямків для алгоритму було рівноцінно. Значить, ми дозволяємо проходити вже пройдених вершин, отже, в кожній ітерації циклу будемо випадково вибирати один з чотирьох напрямків незалежно від того, чи ми там, чи ні. Єдина умова – не виходити за межі поля.

До речі про термін Uniform Spanning Tree. Ми вже знаємо, що таке остовне дерево. Поєднавши всі вершини графа ребрами так, щоб з будь-якої вершини в іншу не можна було потрапити, не пройшовши одне і те ж ребро двічі, ми отримаємо остовне дерево. Але адже якщо вершин у графі більше двох, то і варіацій дерев може бути більше, вірно? Так от, Uniform Spanning Tree – одна рівноймовірно обрана варіація остовного дерева в деякому графі.

І так. Ми хочемо абсолютно випадкові, абсолютно несхожі один на одного лабіринти, і навіть готові пожертвувати швидкістю. Тоді давайте познайомимося з алгоритмами Олдоса-Бродера і Вілсона.

Алгоритм Олдоса-Бродера







Опис

Пам'ятайте я говорив, що алгоритм двійкового дерева самий простий у розумінні? Так от, я лукавив. Він дійсно простіше в реалізації, так як там ми маємо справу завжди тільки з одним напрямком і c одним розглядаються поруч, але в примітивності і «дурниці» алгоритм Олдоса-Бродера пішов далеко вперед. Весь його сенс полягає в тому, щоб безцільно блукати по полю в надії наткнутися на вершину створюваного остовного дерева і приєднати ще одну, а потім знову випадково вибрати точку в лабіринті і гуляти, поки не потрапимо в одну із з'єднаних.

Олдос-Бродер позбавлений якого-небудь зміщення. Зовсім. Всі лабіринти, отримані з його допомогою, абсолютно випадкові і не схожі один на одного. Алгоритм не має переваг по спрямованості, заплутаності або ще яким-небудь характеристиками. Результуючі лабіринти випадкові і рівноймовірні.

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

Треба визнати, спостереження за його роботою воістину дає усвідомлення всієї тлінність і безглуздості буття. Щоб записати діфку з його анімацією, я витратив дуже багато часу, так як укладатися в 30 секунд у полі 5×5 він вперто не хотів. Коли залишалося з'єднати всього одну останню неперевірену клітку до остовному дереву, Олдос-Бродер йшов в інший кут і намотував там круги. Довелося значно збільшити швидкість анімації і зменшити поле, щоб, нарешті, він встиг обійти всі клітини лабіринту.

Його створили два незалежних дослідників, які вивчали рівноймовірні варіанти остовных дерев: Девід Олдос, професор Каліфорнійського університету Берклі та Андрій Бродер, вчений, нині працює в Google. Однозначно сказати, в якій сфері дані дослідження були б корисні, важко. Однак, крім лабіринтів, алгоритм часто спливає у роботах математичної ймовірності, що, втім, не дивно, враховуючи принцип його роботи.

Формальний алгоритм:

  1. Вибрати випадкову вершину (клітку). Абсолютно випадкову;
  2. Вибрати випадкову сусідню вершину (клітину) і перейти до неї. Якщо вона не була відвідана, додати її в дерево (з'єднати з попередньою, прибрати між ними стіну);
  3. Повторювати крок 2, доки всі клітини не будуть відвідані.
Приклад роботиЧервоним кольором виділено наше поточне положення на полі.

Починаємо з лівого верхнього кута. Тут нічого незвичайного.



Випадковим чином вирішуємо піти направо і прибрати стінку між двома клітинами. Добре, робимо.



Неповезло. Наш ГВЧ каже, щоб ми пішли назад, тобто наліво.



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



Ще раз пощастило. Вниз!



Гаразд, один повернення назад можна пробачити.


Вибираємо піти направо і прибираємо стіну.



А тут нам двічі невезет і ми повертаємося в початок.




Вибір двічі впав піти направо. Відмінно, хоч якась різноманітність.




Спускаємося нижче і прибираємо стіну.



А ось тут ми хоч і переміщаємося в сусідню клітку, стіну не прибираємо, так як вони вже в одному і тому ж дереві.



Настав час безцільно поблукати, погуляти.






Повертаємося до клітки 2-2 і спускамся нижче, прибираючи стінку.



Завершуємо нашу проголку і отримуємо згенерований лабіринт.



Плюси:

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

  • Швидкість. Поки буде генеруватися лабіринт, Ви встигнете постаріти і вмерти;
  • Не дозволяє генерувати нескінченні лабіринти;
  • Сильне падіння ефективності під кінець генерації;
Реалізація
local mod = {}
local aux = {}

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

aux.dirs = {"UP", "DOWN", "LEFT", "RIGHT"}

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

for y = 1, rows do 
MazeGrid[y] = {}
for x = 1, columns do
MazeGrid[y][x] = {відвідали = false, bottom_wall = true, right_wall = true}
end
end 
return MazeGrid
end

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(y2, x2)
aux.aldous_broder()
aux return.grid
end

function aux.aldous_broder()
local unvisited_cells = aux.width * aux.height
local ix = math.random(aux.sx, aux.width)
local iy = math.random(aux.sy, aux.height)

aux.grid[iv][ix].відвідали = true
unvisited_cells = unvisited_cells - 1

while unvisited_cells ~= 0 do
local dir = aux.dirs[math.random(1, 4)]

if dir == "UP" then
if iy-1 >= aux.sy then
if aux.grid[iy-1][ix].відвідали == false then
aux.grid[iy-1][ix].bottom_wall = false
aux.grid[iy-1][ix].відвідали = true 
unvisited_cells = unvisited_cells - 1 
end
iy = iy-1
end
elseif dir == "DOWN" then
if iy+1 <= aux.height then 
if aux.grid[iy+1][ix].відвідали == false then 
aux.grid[iv][ix].bottom_wall = false 
aux.grid[iy+1][ix].відвідали = true
unvisited_cells = unvisited_cells - 1 
end
iy = iy+1
end
elseif dir == "RIGHT" then
if ix+1 <= aux.width then
if aux.grid[iv][ix+1].відвідали == false then 
aux.grid[iv][ix].right_wall = false
aux.grid[iv][ix+1].відвідали = true
unvisited_cells = unvisited_cells - 1 
end
ix = ix+1
end
elseif dir == "LEFT" then
if ix-1 >= aux.sx then
if aux.grid[iv][ix-1].відвідали == false then
aux.grid[iv][ix-1].right_wall = false
aux.grid[iv][ix-1].відвідали = true
unvisited_cells = unvisited_cells - 1 
end
ix = ix-1
end
end
end
end

return mod


Алгоритм Вілсона






Опис

Вітаю, ми, нарешті, дісталися до чогось серйознішого. Алгоритм Вілсона значно складніше всіх попередніх як реалізації, так і в розумінні. Мета Вілсона, як і у свого дурного напарник Олдоса-Бродера – генерація рівноймовірного випадкового остовного дерева. І хоча принцип роботи в чомусь схожий, деталі сильно розрізняються.

В основі алгоритму як і раніше лежить равновероятный випадковий вибір сторони переміщення в лабіринті (графі), з двома важливими відмінностями:

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

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

Алгоритм Вілсона, як і Олдос-Бродер, генерує абсолютно випадкові лабіринти без будь-якого зміщення. Алгоритм не має переваг по спрямованості, заплутаності або ще яким-небудь характеристиками. На жаль, для отримання найкращих результатів слід використовувати апаратні генератори випадкових чисел, які не мають переваг в числах.

Сам алгоритм був опублікований Девідом Вілсоном у 1996 році в своїй роботі по генерації рівноймовірно випадкових остовных дерев. Як і раніше, крім лабіринтів, матеріали спливають на різних сайтах присвячених математичної імовірностей. Більше того, мені довелося натрапити на кілька цікавих публікацій, щодо Uniform Spanning Tree і алгоритму Вілсона зокрема. Якщо в одній з них описується більше сам алгоритм, то в інший в цілому саме поняття і математична основа остовных дерев.

Якщо читачам буде цікаво, можливо, я напишу частина 2a, де наведу самі роботи та їх частковий переклад. Основна причина, чому я уникаю математичного обґрунтування тут – мої статті спрямовані на новачків і людей, яким програмування цікавіше сухий математики.

Формальний алгоритм:

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

Традиційно, потрібно потрапити в лівий верхній кут. Починаємо будувати гілку з координати 3-2.






Ось зараз цікавий і важливий момент. Алгоритм вирішує піти вгору, тим самим замкнувши гілку в координаті 2-2.



Видаляємо вийшов цикл і починаємо з 2-2 будувати заново.


habrastorage.org/files/e9c/8e6/46a/e9c8e646af564a42bbb391fbe263044b.png

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




Знову, торкнулися створеного нещодавно дерева, прибрали стіни і почали наново.






Замкнулися, прибрали цикл, продовжили з 2-3 заново.



З'єдналися з деревом, очистили від стін шлях. Продовжили нашу подорож в новій клітині.





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



Плюси:

  • Відсутнє будь-яке зміщення;
  • Лабіринти абсолютно випадкові, тому неможливо створити певний алгоритм їх вирішення;
  • Складність рішення для людини;
  • Немає безцільного блукання;
  • Швидкість порівняно з Олдос-Бродером в рази більше;
Мінуси:

  • Непроста реалізація;
  • Падіння швидкості на початку генерації;
  • Великі вимоги до пам'яті, ніж у Олдос-Бродера;
Реалізація
local mod = {}
local aux = {}

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

aux.dirs = {"UP", "DOWN", "LEFT", "RIGHT"}

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

for y = 1, rows do 
MazeGrid[y] = {}
for x = 1, columns do
MazeGrid[y][x] = {відвідали = false, bottom_wall = true, right_wall = true}
end
end 
return MazeGrid
end

local function saveGridState()
local temp = {}
for yk, yv in pairs(aux.grid) do
temp[yk] = {}
for xk, xv in pairs(yv) do 
temp[yk][xk] = {bottom_wall = aux.grid[yk][xk].bottom_wall, right_wall = aux.grid[yk][xk].right_wall}
end
end
return temp
end

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(y2, x2)
aux.wilson()
aux return.grid
end

function aux.hashKey(x, y)
return x * aux.height + (y - 1)
end

function aux.deHashKey(value)
return math.floor(value/aux.height), value%aux.height + 1
end

function aux.hashCells(grid)
local vtable = {}
for yk, yv in pairs(grid) do
for xk, xv in pairs(yv) do
if xv.відвідали == false then
vtable[aux.hashKey(xk, yk)] = xv
end
end
end
return vtable
end

function aux.wilson()
local cellsHash = aux.hashCells(aux.grid) -- Вершини, що не знаходяться в дереві

local dirsStack = {} -- Скл напрямків
local dsHash = {}
local dsSize = 0

-- Створюємо дерево
local key, v = next(cellsHash, nil)
v.відвідали = true
cellsHash[key] = nil

while next(cellsHash) do -- Поки є необроблені вершини, працює
key = next(cellsHash, nil) -- Отримуємо ключ і по ньому координати клітини
local start_x, start_y = aux.deHashKey(key)
local ix, iy = start_x, start_y

while not aux.grid[iv][ix].відвідали do -- Ходимо, поки не знайдемо відноситься до дерева клітку
local dir = aux.dirs[math.random(1, 4)]
local isMoved = false

key = aux.hashKey(ix, iy)

if dir == "UP" and iy-1 >= aux.sy then iy = iy - 1 isMoved = true
elseif dir == "DOWN" and iy+1 <= aux.height then iy = iy + 1 isMoved = true
elseif dir == "LEFT" and ix-1 >= aux.sx then ix = ix - 1 isMoved = true
elseif dir == "RIGHT" and ix+1 <= aux.width then ix = ix + 1 isMoved = true end

if isMoved then -- Якщо ми можемо рухатися, тоді перевіряємо на цикли
if dsHash[key] then -- Видалення циклів
dirsStack[dsHash[key]].dir = dir

for i = dsHash[key]+1, dsSize do
local x, y = aux.deHashKey(dirsStack[i].hashref)
dsHash[dirsStack[i].hashref] = nil
dirsStack[i] = nil
dsSize = dsSize - 1
end
else
local x, y = aux.deHashKey(key) - Додавання в стак напрямків
dsSize = dsSize + 1
dsHash[key] = dsSize
dirsStack[dsSize] = {dir = dir, hashref = key}
end
end

end

for i = 1, dsSize do -- Проквапывание шляху
aux.grid[start_y][start_x].відвідали = true
cellsHash[aux.hashKey(start_x, start_y)] = nil
aux.grid[start_y][start_x].point = false
local dir = dirsStack[i].dir

if dir == "UP" then
aux.grid[start_y-1][start_x].bottom_wall = false
start_y = start_y - 1

elseif dir == "DOWN" then
aux.grid[start_y][start_x].bottom_wall = false
start_y = start_y + 1

elseif dir == "LEFT" then
aux.grid[start_y][start_x-1].right_wall = false
start_x = start_x - 1

elseif dir == "RIGHT" then 
aux.grid[start_y][start_x].right_wall = false
start_x = start_x + 1
end
end

dsHash, dirsStack, dsSize = {}, {}, 0 -- Обнулення стака напрямків
end
end

return mod



Епілог:
Підсумовуючи все вище сказане, варто зазначити, що хоча ми і дісталися до більш складних алгоритмів і розібралися з деякими новими (для когось) поняттями графів, головні труднощі ще попереду. Неочевидно заплутані алгоритми Еллера, Краскала і Прима, засновані виключно на роботі з графами і деревами, готують нам непрості, нехай і цікаві публікації. Однак, перш ніж приступати до їх написання, слід поглянути на алгоритми пошуку з поверненням і щось під назвою «Зловити&Вбити», чия робота по генерації лабіринту сильно відрізняється від всіх інших. Натяк на тему наступній статті я дав.

Що ще. У коментарях до попередньої частини, деякі люди питали чи скидали свої алгоритми генерації, що було вкрай цікаво і радісно. Якщо Ви коли-то реалізовували створення лабіринтів своїм вигаданим способом і можете його зараз згадати – прошу, поділіться. Може бути, з вашого дозволу, в якій-небудь із статей я напишу і про нього. Взагалі, я радий будь-яким цікавим історіям і спогадами по темі. Не важливо, чи згадуєте Ви, як лабіринти малювали в тетраді в школі або на комп'ютері в університеті.

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

0 коментарів

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