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

RussDragon 23 января в 14:16 21,6k


Предисловие


На написание статьи меня сподвигло практически полное отсутствие материалов на русском языке про алгоритмы генерации лабиринтов. На Хабре, из того, что вообще есть по теме, можно отметить две статьи: раз и два. Ценность и пользу из которых несет лишь вторая. В первой – просто перевод формального алгоритма и небольшое его пояснение. Что, конечно, неплохо, но очень скудно и не вызывает желания изучать тему дальше.

Если моя статья Вам понравится, я продолжу писать о различных алгоритмах. Мы рассмотрим два самых примитивных и простых случая – генерация двоичного дерева и Сайдвиндер, который, по своей сути, просто чуть измененная версия двоичного дерева с одним заметным плюсом. ОСТОРОЖНО ТРАФИК.

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

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

P.S.:

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

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

Идеальный лабиринт – такой лабиринт, в котором одна клетка связана с другой одним единственным путем. Иначе говоря, остовное дерево.

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

Не стоит переживать, если Вы с Луа незнакомы. Незнание языка никак не помешает Вам понять реализацию, благодаря простоте синтаксиса. Если Вы хотя бы немного умеете программировать, 80% кода не вызовет у Вас проблем с пониманием. Остальные 20% — language specific, про которые я всегда буду писать вначале статьи, объясняя их работу.

Первое, что мне следует сказать:
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()
  return aux.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()
  return aux.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 и прочие шутеры в только-только зарождающемся жанре использовали такие алгоритмы для генерации уровней, по некоторым слухам.

Поэтому, если Вам понравилась статья, тема, и Вы хотите видеть их дальше – то, пожалуйста, напишите об этом в комментарии. Так же, буду очень рад любой критике, как в техническом плане, так и в лингвистическом и стилистическом.
Проголосовать:
+68
Сохранить: