Какие методы используются в видеоиграх для создания бесконечных лабиринтов?

Некоторые методы, которые используются в видеоиграх для создания бесконечных лабиринтов:

• Алгоритм Эллера. habr.com cyberleninka.ru Позволяет построчно создавать связные лабиринты без циклов. habr.com Для генерации лабиринта неограниченной высоты достаточно хранить в памяти только пару последних строк. habr.com
• Генерация лабиринта на таблице. tproger.ru Поле изначально разбивается на прямоугольные «большие» клетки, образуя таким образом таблицу. tproger.ru Далее в каждой такой ячейке случайным образом появляется комната случайного размера, не превосходящая размеров ячейки. tproger.ru Затем комнаты объединяются коридорами. tproger.ru
• Генерация лабиринта с использованием клеточного автомата. cyberleninka.ru Сначала всё поле заполняется случайным образом стенами (для каждой клетки случайным образом определяется, будет ли она свободной или непроходимой). tproger.ru Затем несколько раз происходит обновление состояния карты в соответствии с условиями, похожими на условия рождения/смерти в «Жизни». tproger.ru
• Рекурсивный метод (алгоритм случайного прохода). cyberleninka.ru Если размерность генерируемого лабиринта небольшая, то можно использовать этот метод. cyberleninka.ru Он предполагает простейшее построение случайного прохода с использованием дополнительных построений таких же случайных ходов, продолжающееся до тех пор, пока не будет заполнено всё пространство, выделяемое под лабиринт. cyberleninka.ru