![](https://habrastorage.org/files/f95/53e/b6f/f9553eb6f4a3413481f66a89a8759e9d.png)
Предисловие
На написание статьи меня сподвигло практически полное отсутствие материалов на русском языке про алгоритмы генерации лабиринтов. На Хабре, из того, что вообще есть по теме, можно отметить две статьи: раз и два. Ценность и пользу из которых несет лишь вторая. В первой – просто перевод формального алгоритма и небольшое его пояснение. Что, конечно, неплохо, но очень скудно и не вызывает желания изучать тему дальше.
Если моя статья Вам понравится, я продолжу писать о различных алгоритмах. Мы рассмотрим два самых примитивных и простых случая – генерация двоичного дерева и Сайдвиндер, который, по своей сути, просто чуть измененная версия двоичного дерева с одним заметным плюсом. ОСТОРОЖНО ТРАФИК.
Дам один совет – не подглядывайте в код до тех пор, пока вы не напишите свою реализацию. Вы получите гораздо больше удовольствия и пользы от исправления багов и поиска ошибок, чем если просто переведете с одного языка на другой.
Серьезно. Прислушайтесь к совету. Вы, верно, потратите больше времени, но оно стоит стоит. У меня, например, из-за пары ошибок появился очень забавный генератор «инопланетных» текстов, который можно использовать в различных Sci-Fi играх для создания текста. Надеюсь, Вы изучаете тему для себя и никуда не спешите.
P.S.:
Я буду использовать термин «смещение», предполагая английский bias. Т.е. пристрастие алгоритма к направленности в какую-либо сторону. Например, правое смещение – алгоритм генерирует лабиринты с длинными правыми проходами.
Раскраска лабиринтов происходит относительно расстояния от крайнего левого угла поля до некоторой клетки. Чем дальше от начальной координаты – тем темнее будет цвет.
Идеальный лабиринт – такой лабиринт, в котором одна клетка связана с другой одним единственным путем. Иначе говоря, остовное дерево.
Про Lua
Когда я только начинал закапываться в тему лабиринтов, я не предполагал, что в итоге буду писать статью и выбрал язык, на котором у меня есть возможность не тратить слишком много времени на рендер и архитектуру и заниматься исключительно логикой. В итоге, между C++ и Lua, выбор пал на Lua и Love2D.
Не стоит переживать, если Вы с Луа незнакомы. Незнание языка никак не помешает Вам понять реализацию, благодаря простоте синтаксиса. Если Вы хотя бы немного умеете программировать, 80% кода не вызовет у Вас проблем с пониманием. Остальные 20% — language specific, про которые я всегда буду писать вначале статьи, объясняя их работу.
Первое, что мне следует сказать:
Lua имеет лишь одну структуру данных – таблицы – ассоциативный массив, при помощи которого мы создаем нужные нам структуры. К примеру, классы, множества, обычные массивы, стаки, очереди и тому подобное. Обращаться к ним мы может либо с помощью строчных-ключей, либо с помощью индексов.
Так же, таблицы не ограничивают нас в хранении только одного типа данных в одном объекте и работают подобно структурам в C/C++. Такой код абсолютно корректен:
Присваивание nil удалит поле:
Второе:
Lua не имеет скрытого механизма копирования таблиц. Код, приведенный ниже, не будет копировать и создавать нового объекта SomeNewArray, он лишь скопирует в него ссылку на объект SomeArray, и, следовательно, будет изменять его точно так же, как если Вы передадите значение через неконстантную ссылку или указатель в C/C++:
И третье, для тех, кто хорошо знаком с Lua:
Да, я знаю, что в некоторых местах код избыточен. И то, что в некоторых местах всё можно было бы упростить метаметодами тоже. Следует учитывать то, что код писался в первую очередь для того, чтобы разобраться с алгоритмами, а не для использования в реальном проекте. К тому же, отсутствие избытка специфических для языка функций позволяет выкладывать код в том виде, в котором он есть, без нагромождений комментариев.
Не стоит переживать, если Вы с Луа незнакомы. Незнание языка никак не помешает Вам понять реализацию, благодаря простоте синтаксиса. Если Вы хотя бы немного умеете программировать, 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:
Да, я знаю, что в некоторых местах код избыточен. И то, что в некоторых местах всё можно было бы упростить метаметодами тоже. Следует учитывать то, что код писался в первую очередь для того, чтобы разобраться с алгоритмами, а не для использования в реальном проекте. К тому же, отсутствие избытка специфических для языка функций позволяет выкладывать код в том виде, в котором он есть, без нагромождений комментариев.
Алгоритм двоичного дерева
![](https://habrastorage.org/files/1b0/5e0/f47/1b05e0f47a7942389eef48eec6fea19e.png)
![](https://habrastorage.org/files/77e/0e3/dcd/77e0e3dcd78748ee86a7969bc104645e.png)
![](https://habrastorage.org/files/35c/76c/92a/35c76c92a18c4d318dc415cde6443dec.gif)
![](https://habrastorage.org/files/df9/1e6/2a0/df91e62a01d6467985ece549f8919c90.gif)
Описание:
Самый первый и самый простой алгоритм в понимании, который я рассмотрю. Его суть заключается в том, чтобы проложить путь в случайном направлении из каждой клетки поля: в моей реализации либо наверх, либо вправо (зависит от выбранного Вами смещения). Мы обрабатываем только 1 клетку за единицу времени, следовательно, мы можем генерировать лабиринты бесконечного размера, сохраняя лишь конечный результат (лабиринт) без необходимости хранить какую-либо побочную информацию.
Такой способ генерации имеет два побочных эффекта:
1. Лабиринты обладают сильным диагональным смещением и отсутствием тупиков в его направлении. Посмотрите на скриншоты выше и Вы увидите, что каждый из коридоров стремится к правой верхней клетке, и, как итог, имеет ровно один путь к ней, и нигде на пути нет тупика:
2. Два пустых коридора по сторонам лабиринта. Когда алгоритм «прокапывается» до конца строки/столбца, ему не остается выбора, кроме как продолжить путь в одном единственном направлении, создавая пустые «границы».
К слову, название не просто так совпадает со структурой данных. Результат его работы – случайное двоичное дерево, в котором из каждой клетки (вершины) есть ровно 1 путь по направлению к корню (родительской вершине), и, соответственно, ровно 1 путь к любой другой клетке. Как следствие, любая клетка имеет не более 3 соединений со своими соседями.
Формальный алгоритм (для северо-восточного смещения):
- Выбрать начальную клетку;
- Выбрать случайное направление для прокладывания пути. Если соседняя клетка в этом направлении выходит за границы поля, прокопать клетку в единственно возможном направлении;
- Перейти к следующей клетке;
- Повторять 2-3 до тех пор, пока не будут обработаны все клетки;
Пример работы
Зеленое – текущая рассматриваемая клетка, красное – фронт, клетки, в которые можно переместиться.
Начинаем с координаты (0;0). Наверх в этом ряду пойти не можем, так как иначе выйдем за границы лабиринта. Идем вправо до упора, по пути снося все стены.
![](https://habrastorage.org/r/w1560/files/2ca/dc9/d72/2cadc9d7214045acaeee915e30f7fa23.png)
![](https://habrastorage.org/r/w1560/files/6f2/d9b/e11/6f2d9be110f7482d949940c8e5f13e06.png)
Всё, тупик. Идти некуда. Перемещаемся на следующий ряд и видим, что теперь есть возможность пойти наверх и вправо.
![](https://habrastorage.org/r/w1560/files/63a/67c/2dc/63a67c2dc1f24f7eacdd387bd82cd0e8.png)
Кидаем монетку и выбираем… Верх. Убираем стену и переходим к следующей клетке.
![](https://habrastorage.org/r/w1560/files/5b9/63e/8cd/5b963e8cdb04457e8647e70269103aee.png)
Отлично. Случай подсказывает нам идти направо. Убираем стену и перемещаемся в следующую клетку.
![](https://habrastorage.org/r/w1560/files/f44/ad9/f98/f44ad9f9855043f49b0cb70a6cb482b7.png)
![](https://habrastorage.org/r/w1560/files/880/f69/003/880f69003276475dac6f3c444f388238.png)
![](https://habrastorage.org/r/w1560/files/daf/a13/6ac/dafa136acebb41f79ffa9a9f7ba496ee.png)
Выбора у нас нет, налево пойти не можем, значит, убираем стену сверху и идем на следующий ряд.
![](https://habrastorage.org/r/w1560/files/f17/559/c5a/f17559c5a797438bbd28d39874403e95.png)
![](https://habrastorage.org/r/w1560/files/1b0/ce0/82f/1b0ce082f5e0410ab00fab729bd9ea1b.png)
Монета убеждает нас пойти направо. Что же, слушаемся. Убираем стену и переходим к слеудующей клетке.
![](https://habrastorage.org/r/w1560/files/c06/086/b41/c06086b41af94896abc16bc13f5e45c7.png)
![](https://habrastorage.org/r/w1560/files/596/3dc/b56/5963dcb567344522bbc274d3fce17be6.png)
Прокатившись метр, наш несчастный кусок металла падает и говорит, что пора идти наверх. Сносим стену, шагаем к следующей клетке, и, так как она крайняя в этом ряду, убираем стену сверху. Лабиринт закончен.
![](https://habrastorage.org/r/w1560/files/322/cbb/810/322cbb810a4142e3acb57dda8bf91603.png)
![](https://habrastorage.org/r/w1560/files/263/6f5/ad2/2636f5ad26b14b4bb95f1e2a4ebe6a59.png)
![](https://habrastorage.org/r/w1560/files/210/119/4f5/2101194f5abc40d69cd70dcd629cbec7.png)
Начинаем с координаты (0;0). Наверх в этом ряду пойти не можем, так как иначе выйдем за границы лабиринта. Идем вправо до упора, по пути снося все стены.
![](https://habrastorage.org/files/2ca/dc9/d72/2cadc9d7214045acaeee915e30f7fa23.png)
![](https://habrastorage.org/files/6f2/d9b/e11/6f2d9be110f7482d949940c8e5f13e06.png)
Всё, тупик. Идти некуда. Перемещаемся на следующий ряд и видим, что теперь есть возможность пойти наверх и вправо.
![](https://habrastorage.org/files/63a/67c/2dc/63a67c2dc1f24f7eacdd387bd82cd0e8.png)
Кидаем монетку и выбираем… Верх. Убираем стену и переходим к следующей клетке.
![](https://habrastorage.org/files/5b9/63e/8cd/5b963e8cdb04457e8647e70269103aee.png)
Отлично. Случай подсказывает нам идти направо. Убираем стену и перемещаемся в следующую клетку.
![](https://habrastorage.org/files/f44/ad9/f98/f44ad9f9855043f49b0cb70a6cb482b7.png)
![](https://habrastorage.org/files/880/f69/003/880f69003276475dac6f3c444f388238.png)
![](https://habrastorage.org/files/daf/a13/6ac/dafa136acebb41f79ffa9a9f7ba496ee.png)
Выбора у нас нет, налево пойти не можем, значит, убираем стену сверху и идем на следующий ряд.
![](https://habrastorage.org/files/f17/559/c5a/f17559c5a797438bbd28d39874403e95.png)
![](https://habrastorage.org/files/1b0/ce0/82f/1b0ce082f5e0410ab00fab729bd9ea1b.png)
Монета убеждает нас пойти направо. Что же, слушаемся. Убираем стену и переходим к слеудующей клетке.
![](https://habrastorage.org/files/c06/086/b41/c06086b41af94896abc16bc13f5e45c7.png)
![](https://habrastorage.org/files/596/3dc/b56/5963dcb567344522bbc274d3fce17be6.png)
Прокатившись метр, наш несчастный кусок металла падает и говорит, что пора идти наверх. Сносим стену, шагаем к следующей клетке, и, так как она крайняя в этом ряду, убираем стену сверху. Лабиринт закончен.
![](https://habrastorage.org/files/322/cbb/810/322cbb810a4142e3acb57dda8bf91603.png)
![](https://habrastorage.org/files/263/6f5/ad2/2636f5ad26b14b4bb95f1e2a4ebe6a59.png)
![](https://habrastorage.org/files/210/119/4f5/2101194f5abc40d69cd70dcd629cbec7.png)
Плюсы:
- Простая реализация;
- Высокая скорость работы;
- Возможность генерировать бесконечные лабиринты;
Минусы:
- Низкая сложность рисунка;
- Сильное смещение по диагонали;
- Отсутствие тупиков по смещению;
- Однообразность сгенерированных лабиринтов;
Реализация
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»
![](https://habrastorage.org/files/2ef/18c/13a/2ef18c13aaaf42e8834a61e827bc6046.png)
![](https://habrastorage.org/files/b7d/851/357/b7d851357374412cbb4aeb2d2f035389.png)
![](https://habrastorage.org/files/f76/e47/074/f76e4707441c42c7bc85c79554a14d65.gif)
![](https://habrastorage.org/files/d8b/680/72a/d8b68072a6b6471393d288fa5e6fd38f.gif)
Описание:
Алгоритм с непереводимым названием Sidewinder по своей работе очень похож на алгоритм двоичного дерева, в том отличии, что в нём нет характерного смещения по диагонали, одного пустого коридора и клетки мы рассматриваем не по отдельности, а множествами. Лабиринты получаются с преимущественно вертикальным или горизонтальным смещением (в зависимости от реализации), с отсутствием тупиков в их направлении. В сравнении со своим более примитивным собратом, смещение не так заметно и больше похоже на «спираль», которая плавно сменяет вертикальные и горизонтальные коридоры.
Что касается побочных эффектов, то Sidewinder создает только один пустой коридор на одной стороне, вместо двух. Начиная создание множеств с первого ряда поля, у нас отсутствует возможность прокопать путь наверх, так как мы находимся в самом крайнем вертикальном положении и попытка пойти выше приведет к выходу за границы поля. Но и если мы будем организовывать множества без выхода по вертикали, мы создадим несколько изолированных друг от друга областей.
Для примера: 9 клеток первого ряда можно поделить на три множества, между которыми расположены стены. Каждое множество второго ряда будет прокапывать путь к одному из трех «блоков» выше. Третий ряд проложит путь к «блокам» второго. И так до конца поля. В итоге, у нас получатся 3 разветвленные, изолированные друг от друга вертикальные области, что не подходит для идеального лабиринта, в котором из каждой точки поля есть ровно 1 путь в любую другую.
Формальный алгоритм (для стандартного смещения):
- Выбрать начальный ряд;
- Выбрать начальную клетку ряда и сделать её текущей;
- Инициализировать пустое множество;
- Добавить текущую клетку в множество;
- Решить, прокладывать ли путь направо;
- Если проложили, то перейти к новой клетке и сделать её текущей. Повторить шаги 3-6;
- Если не проложили, выбираем случайную клетку множества и прокладываем оттуда путь наверх. Переходим на следующий ряд и повторяем 2-7;
- Продолжать, пока не будет обработан каждый ряд;
Пример работы
Красные клетки – члены множества.
Мы начинаем с первого ряда и видим, что выше нас – выход за пределы поля. Сносим все стены и идем сразу во второй ряд, создаем пустое множество.
![](https://habrastorage.org/r/w1560/files/102/2a3/a9e/1022a3a9e3384f01aa161bdbe30fd2c1.png)
![](https://habrastorage.org/r/w1560/files/68e/627/bae/68e627bae0ea4d8a85d03fb9392349ee.png)
Так, а вот тут интереснее. Давайте добавим в множество первые две клетки ряда.
![](https://habrastorage.org/r/w1560/files/6e7/bf4/5aa/6e7bf45aaf70424c86e24ed85b01d80c.png)
Выбираем одну из этих клеток и убираем относящуюся к ней верхнюю стенку в первый ряд.
![](https://habrastorage.org/r/w1560/files/e43/067/e32/e43067e32c744bb6a3150f4a149063a1.png)
Обнуляем множество, добавляем в нее следующую клетку ряда.
![](https://habrastorage.org/r/w1560/files/932/2c2/060/9322c206053248d1a39c6c4c12393d40.png)
В этот раз ни с кем не объединяем, просто прокладываем путь наверх прямо из этой единственной клетки.
![](https://habrastorage.org/r/w1560/files/040/566/9c7/0405669c718c4cfa88b9f771ef0a39a6.png)
Повторяем наши действия. Обнуляем множество, переходим в следующую клетку, добавляем её… А так как она осталась последней в ряде, то так же убираем стену сверху и идем в ряд ниже.
![](https://habrastorage.org/r/w1560/files/335/4d7/4d3/3354d74d31b54681860ac490874f0574.png)
![](https://habrastorage.org/r/w1560/files/867/90f/66c/86790f66c8c1433aae695925843ae65d.png)
А теперь сразу объединяем три первые клетки в одно множество.
![](https://habrastorage.org/r/w1560/files/85a/332/6ab/85a3326ab79147b19435da9e0f64a641.png)
Случайно выбираем клетку, в нашем случае, вторую и убираем стену сверху к предыдущему ряду.
![](https://habrastorage.org/r/w1560/files/2cd/3d9/2cd/2cd3d92cd8bc4846ab8185275e5e99b6.png)
Ну, тут у нас опять нет выбора, убираем стену наверху и идем на ряд ниже.
![](https://habrastorage.org/r/w1560/files/660/b8d/a55/660b8da559ba4e3fb9eec20894d8839d.png)
![](https://habrastorage.org/r/w1560/files/ae3/348/21f/ae334821ff984b7dbc47404afa5c724c.png)
На этот раз, самую перваую клетку мы сделаем единственной. Убираем стену к предыдущему ряду и идем дальше, в следующую клетку.
![](https://habrastorage.org/r/w1560/files/993/b8e/d5d/993b8ed5d3824143bb8a41400eecfa67.png)
![](https://habrastorage.org/r/w1560/files/484/db2/b85/484db2b855d748e8a62d21f888e8a91a.png)
Предположим, что захотели в конце объединить три клетки.
![](https://habrastorage.org/r/w1560/files/e37/8cc/6ae/e378cc6ae1704d97b5e6d276510460b1.png)
И снова нам приглянулась средняя клетка из множества, из которой и убираем стену наверх. Всё, наш лабиринт готов.
![](https://habrastorage.org/r/w1560/files/ee5/c1f/8dc/ee5c1f8dcdb8411e9de155bd198f2be2.png)
Мы начинаем с первого ряда и видим, что выше нас – выход за пределы поля. Сносим все стены и идем сразу во второй ряд, создаем пустое множество.
![](https://habrastorage.org/files/102/2a3/a9e/1022a3a9e3384f01aa161bdbe30fd2c1.png)
![](https://habrastorage.org/files/68e/627/bae/68e627bae0ea4d8a85d03fb9392349ee.png)
Так, а вот тут интереснее. Давайте добавим в множество первые две клетки ряда.
![](https://habrastorage.org/files/6e7/bf4/5aa/6e7bf45aaf70424c86e24ed85b01d80c.png)
Выбираем одну из этих клеток и убираем относящуюся к ней верхнюю стенку в первый ряд.
![](https://habrastorage.org/files/e43/067/e32/e43067e32c744bb6a3150f4a149063a1.png)
Обнуляем множество, добавляем в нее следующую клетку ряда.
![](https://habrastorage.org/files/932/2c2/060/9322c206053248d1a39c6c4c12393d40.png)
В этот раз ни с кем не объединяем, просто прокладываем путь наверх прямо из этой единственной клетки.
![](https://habrastorage.org/files/040/566/9c7/0405669c718c4cfa88b9f771ef0a39a6.png)
Повторяем наши действия. Обнуляем множество, переходим в следующую клетку, добавляем её… А так как она осталась последней в ряде, то так же убираем стену сверху и идем в ряд ниже.
![](https://habrastorage.org/files/335/4d7/4d3/3354d74d31b54681860ac490874f0574.png)
![](https://habrastorage.org/files/867/90f/66c/86790f66c8c1433aae695925843ae65d.png)
А теперь сразу объединяем три первые клетки в одно множество.
![](https://habrastorage.org/files/85a/332/6ab/85a3326ab79147b19435da9e0f64a641.png)
Случайно выбираем клетку, в нашем случае, вторую и убираем стену сверху к предыдущему ряду.
![](https://habrastorage.org/files/2cd/3d9/2cd/2cd3d92cd8bc4846ab8185275e5e99b6.png)
Ну, тут у нас опять нет выбора, убираем стену наверху и идем на ряд ниже.
![](https://habrastorage.org/files/660/b8d/a55/660b8da559ba4e3fb9eec20894d8839d.png)
![](https://habrastorage.org/files/ae3/348/21f/ae334821ff984b7dbc47404afa5c724c.png)
На этот раз, самую перваую клетку мы сделаем единственной. Убираем стену к предыдущему ряду и идем дальше, в следующую клетку.
![](https://habrastorage.org/files/993/b8e/d5d/993b8ed5d3824143bb8a41400eecfa67.png)
![](https://habrastorage.org/files/484/db2/b85/484db2b855d748e8a62d21f888e8a91a.png)
Предположим, что захотели в конце объединить три клетки.
![](https://habrastorage.org/files/e37/8cc/6ae/e378cc6ae1704d97b5e6d276510460b1.png)
И снова нам приглянулась средняя клетка из множества, из которой и убираем стену наверх. Всё, наш лабиринт готов.
![](https://habrastorage.org/files/ee5/c1f/8dc/ee5c1f8dcdb8411e9de155bd198f2be2.png)
Плюсы:
- Возможность генерировать бесконечные лабиринты;
- Только 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 и прочие шутеры в только-только зарождающемся жанре использовали такие алгоритмы для генерации уровней, по некоторым слухам.
Поэтому, если Вам понравилась статья, тема, и Вы хотите видеть их дальше – то, пожалуйста, напишите об этом в комментарии. Так же, буду очень рад любой критике, как в техническом плане, так и в лингвистическом и стилистическом.