Классические алгоритмы генерации лабиринтов. Часть 2: погружение в случайность

ec0af28bf45241ee9de2add7bf33e87b.png

Предисловие


→ Первая часть

Итак. Оценив отклик аудитории Хабра и разобравшись с делами, я принялся за написание второй статьи из цикла. Реакция публики оказалась значительно позитивнее моих предположение, а значит, мы продолжаем разговор на одну из любопытнейших тем процедурной генерации — создание лабиринтов.

В этой части мы поговорим о том, что же такое случайная и псевдослучайная генерации, какие алгоритмы могут дать нам равновероятно ничем не похожие друг на друга лабиринты и в чем их минусы. Героями нашего сегодняшнего приключения станут алгоритм Уилсона и алгоритм Олдоса-Бродера для создания случайного остовного дерева (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 удаляет элемент/поле


Смещение и случайность


Что мы подразумеваем под случайной генерацией? Можем ли мы сказать, что если во втором лабиринте, в отличии от первого, отсутствует две стенки на юге, то они полностью случайны? Или если первый лабиринт имеет на два горизонтальных коридора больше? И да, и нет.

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

f3d239496c1d40658357c3956f3a8f8d.png

a1db2e7f5c4d458c9d12ae5944429de9.png

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

Мы получили случайный результат? Да. Можем ли мы его таковым считать? Ну, по-моему мнению, нет.

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

А что если мы хотим, чтобы смещения вообще не было? Чтобы из, к примеру, 9 не связанных точек графа, каждый раз мы получали совершенно непохожее на остальные остовное дерево? Тогда нам нужно, чтобы каждое из направлений для алгоритма было равноценно. Значит, мы разрешаем проходить по уже пройденным вершинам, следовательно, в каждой итерации цикла будем случайно выбирать одно из четырех направлений вне зависимости от того, были ли мы там или нет. Единственное условие — не выходить за рамки поля.

К слову о термине Uniform Spanning Tree. Мы уже знаем, что такое остовное дерево. Соединив все вершины графа ребрами так, чтобы из любой вершины в другую нельзя было попасть, не пройдя одно и то же ребро дважды, мы получим остовное дерево. Но ведь если вершин в графе более двух, то и вариаций деревьев может быть больше, верно? Так вот, Uniform Spanning Tree — одна равновероятно выбранная вариация остовного дерева в некотором графе.

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

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


ea9699e97af847d8ae245a20212cdcf7.png

c19bf30e7b8341ee817b014c559e7fe2.png

084f655b45044098919550948e35f60a.gif

9f783876affb4a24ba271affe8a3e3ab.gif

Описание

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

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

Проблемой может стать несовершенство генераторов случайных чисел, которые сами могут тяготеть к каким-либо значениям и выдавать их чаще. Но если использовать, к примеру, генератор случайности на основе природного шума (ветра, распада урана), то, пожалуй, вы сможете, наконец, в полной мере насладиться работой алгоритма.

Надо признать, наблюдение за его работой поистине даёт осознание всей тленности и бессмысленности бытия. Чтобы записать гифку с его анимацией, я потратил очень немало времени, так как укладываться в 30 секунд в поле 5×5 он упорно не хотел. Когда оставалось соединить всего одну последнюю непроверенную клетку к остовному дереву, Олдос-Бродер уходил в другой угол и наматывал там круги. Пришлось значительно увеличить скорость анимации и уменьшить поле, чтобы, наконец, он успел обойти все клетки лабиринта.

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

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

  1. Выбрать случайную вершину (клетку). Абсолютно случайную;
  2. Выбрать случайную соседнюю вершину (клетку) и перейти в неё. Если она не была посещена, добавить её в дерево (соединить с предыдущей, убрать между ними стену);
  3. Повторять шаг 2, пока все клетки не будут посещены.

Пример работы
Красным цветом выделено наше текущее положение на поле.

Начинаем с левого верхнего угла. Тут ничего необычного.

a1aac320f9824b96b2af0ec8bc804cfe.png

Случайным образом решаем пойти направо и убрать стенку между двумя клетками. Хорошо, делаем.

e2b91e0cb28f48cba245c224b68ca9b6.png

Неповезло. Наш ГСЧ говорит, чтобы мы пошли обратно, то есть налево.

ce7d988bf95f44c4b875cb039a457ca1.png

А теперь вниз. Попутно соединяем все непосещенные клетки и убираем между ними стены.

a2efc2173bf54fda8c62a6f74d93e2d6.png

Еще раз повезло. Вниз!

886d7ee2c3da4cc4866d421c3013a979.png

Ладно, один возврат назад можно простить.
c44fd51ed98d41ae9c575587cb616499.png

Выбираем пойти направо и убираем стену.

5e304f7388114a0385be2f12f3b8a804.png

А тут нам дважды невезет и мы возвращаемся в самое начало.

366646a0b1e14b17ab1be1cec4591ef1.png
7489e9350cae4a57baa4fe49cde97976.png

Выбор дважды пал пойти направо. Отлично, хоть какое-то разнообразие.

28c1895afb1f4ec2a5fb2fc9c3ee1610.png
e5cd40beb32340a6a2e458efbc5d7ace.png

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

70f8a210c6864405ac08f50d1bdc8c48.png

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

746a792f8bbb45ef8ccfee413d222822.png

Пришло время бесцельно поблуждать, погулять.

f57ca668915746308daa59fbfd7d48ee.png
ff2ecacef0e040e496a2f0db7bc55208.png
1773c797ebd14de9afe28e671186e2c7.png
89be58dbe89f447cadda9f2570176278.png

Возвращаемся к клетке 2–2 и спускамся ниже, убирая стенку.

0a6e215ce75f461eb0cd9533d5c0534a.png

Завершаем нашу проголку и получаем сгенерированный лабиринт.

b01d210a432e4ef791649d70f4d08fc4.png


Плюсы:
  • Отсутствует какое-либо смещение;
  • Лабиринты абсолютно случайны, поэтому невозможно создать определенный алгоритм их решения;
  • Сложность решения для человека;
  • Простая реализация;

Минусы:
  • Скорость. Пока будет генерироваться лабиринт, Вы успеете состариться и умереть;
  • Не позволяет генерировать бесконечные лабиринты;
  • Сильное падение эффективности под конец генерации;

Реализация
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] = {visited = 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()
  return aux.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[iy][ix].visited = 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].visited == false then
      aux.grid[iy-1][ix].bottom_wall = false
      aux.grid[iy-1][ix].visited = 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].visited == false then 
      aux.grid[iy][ix].bottom_wall = false 
      aux.grid[iy+1][ix].visited = true
      unvisited_cells = unvisited_cells - 1 
    end
    iy = iy+1
  end
  elseif dir == "RIGHT" then
    if ix+1 <= aux.width then
     if aux.grid[iy][ix+1].visited == false then 
      aux.grid[iy][ix].right_wall = false
      aux.grid[iy][ix+1].visited = true
      unvisited_cells = unvisited_cells - 1 
    end
    ix = ix+1
  end
  elseif dir == "LEFT" then
    if ix-1 >= aux.sx then
     if aux.grid[iy][ix-1].visited == false then
      aux.grid[iy][ix-1].right_wall = false
      aux.grid[iy][ix-1].visited = true
      unvisited_cells = unvisited_cells - 1 
    end
    ix = ix-1
    end
  end
  end
end

return mod


Алгоритм Уилсона


fe2112abacea4afda1fac350bfcfd689.png

45f26fd105dd4306a844d8a1146fecd8.png

fc9db99b62154bfb995b6489e342caed.gif

19851da13b5f42518e8fde188c816df5.gif

Описание

Поздравляю, мы, наконец, добрались до чего-то посерьезнее. Алгоритм Уилсона значительно сложнее всех предыдущих как в реализации, так и в понимании. Цель Уилсона, как и у своего более глупого напарник Олдоса-Бродера — генерация равновероятного случайного остовного дерева. И хотя принцип работы в чем-то схож, детали сильно различаются.

В основе алгоритма по-прежнему лежит равновероятный случайный выбор стороны перемещения в лабиринте (графе), с двумя важными отличиями:

Перемещаясь по полю мы «запоминаем» все вершины, в которых побывали до момента нахождения вершины остовного дерева. Как только мы натыкаемся на уже добавленную вершину, мы присоединяем получившийся подграф (ветвь) к нашему генерируемому дереву. Если создается цикл в подграфе, то удаляем его. Под циклом я подразумеваю соединение какой-либо вершины, которая уже находится во временном подграф с ним же, но в другой точке. Иначе говоря, не должно быть вершин, у которых больше 2 ребер. Если не понимаете сейчас, не страшно — дальше на примере работы наглядно увидите.

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

Алгоритм Уилсона, как и Олдос-Бродер, генерирует абсолютно случайные лабиринты без какого-либо смещения. Алгоритм не имеет предпочтений по направленности, запутанности или ещё каким-либо характеристикам. К сожалению, для получения наилучших результатов следует использовать аппаратные генераторы случайных чисел, которые не имеют предпочтений в числах.

Сам алгоритм был опубликован Дэвидом Уилсоном в 1996 году в своей работе о генерации равновероятных случайных остовных деревьев. Как и прежде, кроме лабиринтов, материалы всплывают на различных сайтах посвященных математической вероятностям. Более того, мне довелось наткнуться на несколько интересных публикаций, касательно Uniform Spanning Tree и алгоритма Уилсона в частности. Если в одной их них описывается больше сам алгоритм, то в другой в целом само понятие и математическая основа остовных деревьев.

Если читателям будет интересно, возможно, я напишу часть 2a, где приведу сами работы и их частичный перевод. Основная причина, почему я избегаю математического обоснования здесь — мои статьи направлены на новичков и людей, которым программирование интереснее сухой математики.

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

  1. Выбрать случайную вершину, не принадлежащую остовному дереву и добавить её в дерево;
  2. Выбрать случайную вершину, не принадлежащую остовному дереву и начать обход графа (лабиринта), пока не придём в уже добавленную вершину дерева; Если образуется цикл, удалить его;
  3. Добавить все вершины получившегося подграфа в остовное дерево;
  4. Повторять шаги 2–3, пока все вершины не будут добавлены в остовное дерево.

Пример работы
Зеленом выделена первая вершина дерева. Красным — создаваемая ветвь (подграф).

Традиционно, нужно попасть в левый верхний угол. Начинаем строить ветвь с координаты 3–2.

c324b8deba6f4996ab3866c51bd5841d.png
5aa6ed046a904094b02e77299de117a6.png
e9c8e646af564a42bbb391fbe263044b.png
9d0aa3572d9d4ebc9483ebe54d7ed78f.png

Вот сейчас интересный и важный момент. Алгоритм решает пойти наверх, тем самым замкнув ветвь в координате 2–2.

6e291e72f05d4efd93f4e063d257ab16.png

Удаляем получившийся цикл и начинаем с 2–2 строить заново.

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

Отлично, алгоритм решил пойти наверх и тем самым присоединился к основному дереву. Убираем стены на пути и выбираем следующую клетку.

cd8bd58fbd6846d1aae7ae15c1bf1c09.png
e6d4ca3a24e2461584be977381686509.png

Вновь, коснулись созданного недавно дерева, убрали стены и начали заново.

4261dc57b9084c1dbeb905097579ceb7.png
04ea12a6f46746faa4813364e4c971b1.png
c635193455cc466093e603659759686e.png
d9e76e1a00c54539bb8899abd02d2e97.png

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

77e48264497e4585a9b1952193e091c2.png

Соединились с деревом, очистили от стен путь. Продолжили наше путешествие в новой клетке.

d47ea0f88e2844a6b36bd675c6f0c455.png
c6a96e39f6404038b4b11d3abd0f64d6.png
447f45059d6c47b1934ed29ae8cd571d.png

Снова соединились с основным деревом, убрали стены, закончили лабиринт.

cbbb04de6f1846159b398eb68c8ead9c.png


Плюсы:
  • Отсутствует какое-либо смещение;
  • Лабиринты абсолютно случайны, поэтому невозможно создать определенный алгоритм их решения;
  • Сложность решения для человека;
  • Нет бессмысленного блуждания;
  • Скорость по сравнению с Олдос-Бродером в разы больше;

Минусы:
  • Непростая реализация;
  • Падения скорости в начале генерации;
  • Большие требования к памяти, чем у Олдос-Бродера;

Реализация
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] = {visited = 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()
return aux.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.visited == 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.visited = 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[iy][ix].visited 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].visited = 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)

© Habrahabr.ru