Хабрахабр

[Перевод] Лабиринты: классификация, генерирование, поиск решений

Лабиринт может использовать по одному элементу из каждого класса в любом сочетании. Лабиринты в целом (а значит, и алгоритмы для их создания) можно разбить по семи различным классификациям: размерности, гиперразмерности, топологии, тесселяции, маршрутизации, текстуре и приоритету.

Существуют следующие типы: класс размерности по сути определяет, сколько измерений в пространстве заполняет лабиринт.

Существуют следующие типы: классификация по гиперразмерности соответствует размерности объекта, двигающегося через лабиринт, а не самого лабиринта.

Есть следующие типы: класс топологии описывает геометрию пространства лабиринта, в котором тот существует как целое.

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

От связан с типами проходов в пределах геометрии, определённой в описанных выше категориях. классификация по маршрутизации — это, вероятно, наиболее интересный аспект в генерации лабиринтов.

Текстура — это не просто параметры, которые можно включать или выключать. классификация по текстуре описывает стиль проходов при различной маршрутизации и геометрии. Вот несколько примеров переменных:

Обычно при генерации это сводится только к разнице в алгоритмах, а не к заметным отличиям лабиринтов, но всё равно это полезно учитывать. эта классификация показывает, что процессы создания лабиринтов можно разделить на два основных типа: добавляющие стены и вырезающие проходы. Один и тот же лабиринт часто генерируется обоими способами:

Это только те типы лабиринтов, которые я создавал сам. описанное выше ни в коем случае не является исчерпывающим списком всех возможных классов или элементов внутри каждого класса. Заметьте, что почти каждый тип лабиринта, в том числе и лабиринты с особыми правилами, можно выразить в виде ориентированного графа, в котором будет конечное количество состояний и конечное количество вариантов выбора в каждом состоянии, и это называется

Вот несколько других классификаций и типов лабиринтов: .

Вот список обобщённых алгоритмов для создания различных классов лабиринтов, описанных выше:

  • Начинаем с внешней стены и случайным образом добавляем касающийся её фрагмент стены. Идеальный: для создания стандартного идеального лабиринта обычно необходимо «выращивать» его, обеспечив отсутствие петель и изолированных областей. Если вы добавляете сегмент стены, оба конца которого отделены от остального лабиринта, то это создаст несоединённую стену с петлёй вокруг, а если добавить сегмент, оба конца которого касаются лабиринта, то это создать недостижимую область. Продолжаем случайным образом добавлять в лабиринт сегменты стен, но проверяем, что каждый новый сегмент касается с одного конца существующей стены, а его другой конец находится в ещё несозданной части лабиринта. Это метод добавления стен; почти аналогично ему вырезание проходов, при котором части проходов вырезаются таким образом, чтобы существующего прохода касался только один конец.

  • Я создаю их за четыре этапа: (1) начинаю с внешней стены, (2) обхожу лабиринт и добавляю отдельные сегменты стены, касающиеся каждой вершины стены, чтобы в лабиринте не было открытых комнат или небольших стен-«столбов», (3) обхожу все возможные сегменты стен в случайном порядке, добавляя стену там, где она не создаст тупика, (4) или запускаю процедуру удаления изолированных областей в конце, чтобы лабиринт был правильным и имел решение, или поступаю умнее на этапе (3) и делаю так, чтобы стена добавлялась только тогда, когда она не может привести к изолированной области. Плетёный: для создания лабиринта без тупиков по сути нужно добавлять в лабиринт сегменты стен случайным образом, но делать так, чтобы каждый новый добавляемый сегмент не приводил к созданию тупика.

  • Это превращает каждый тупик в U-образный поворот, и у нас получится одномаршрутный проход, начинающийся и заканчивающийся в начале исходного лабиринта, который будет следовать по тому же пути, как и перемещение вдоль стены исходного лабиринта. Одномаршрутный: один из способов создания случайного одномаршрутного лабиринта — создать идеальный лабиринт, закрыть выход, чтобы остался только один вход, а затем добавлять стены, разделяющие каждый проход на две части. Можно добавить небольшие хитрости, чтобы начало и конец не всегда находились друг рядом с другом: при создании идеального лабиринта мы никогда не будем добавлять сегменты, соединяющиеся с правой или нижней стенами, поэтому получившийся лабиринт будет иметь простое решение, следующее вдоль стены. Новый одномаршрутный лабиринт будет иметь удвоенный относительно исходного идеального лабиринта размер. В результате получится одномаршрутный лабиринт, начинающийся в правом верхнем углу и заканчивающийся в левом нижнем. Поставим вход в правом верхнем углу, и после разбиения пополам для создания одного маршрута удалим правую и нижнюю стены.

  • Разреженный:

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

  • 3D: трёхмерные лабиринты и лабиринты большей размерности можно создавать точно так же, как стандартный двухмерный идеальный лабиринт, только из каждой ячейки можно случайным образом двигаться в шесть, а не в четыре ортогональные ячейки. Из-за дополнительных размерностей в этих лабиринтах обычно используется вырезание проходов.
  • В монохромном растровом изображении переплетённый лабиринт можно представить четырьмя строками на проход (двух строк на проход достаточно для стандартного идеального лабиринта): одна строка для самого прохода, а остальные три строки недвусмысленно показывают, когда другой соседний проход идёт под ним, а не просто образует тупик рядом с первым проходом. Переплетённый: переплетённые лабиринты по сути создаются как идеальные лабиринты с вырезанием проходов, только при вырезании проходов мы не всегда ограничены существующим проходом, потому что у нас есть возможность пройти под ним и всё равно сохранить идеальность лабиринта. что можно продолжить вырезание, находясь под ним; так можно избежать тупиков, расположенных прямо под другими проходами. Ради эстетичности перед вырезанием под уже готовым проходом можно заглядывать вперёд, чтобы убедиться. Также после вырезания под проходом можно инвертировать соседние с пересечением пиксели, чтобы новые проходы проходили над старыми, а не под ними.

  • Выбираем пиксель, который уже поставлен как стена, выбираем ещё одну случайную локацию, и «стреляем» или начинаем рисовать стену в сторону второй локации. Crack: Crack-лабиринты по сути создаются как идеальные лабиринты с добавлением стен, только в них нет отчётливой тесселяции, за исключением случайного расположения пикселей. Завершаем работу, если какое-то время не можем добавить новых значимых стен. Однако нужно останавливаться, не доходя до уже существующих стен, чтобы не создать изолированности. Это делает лабиринт очень похожим на поверхность листа, то есть по сути это фрактальный лабиринт. Учтите, что случайные локации для рисования могут находится в любом месте лабиринта, поэтому по лабиринту будет проходить несколько прямых линий и множество пропорционально меньших стен; количество стен ограничено только пиксельным разрешением.

  • Например, для треугольного дельта-лабиринта с соединяющимися треугольными ячейками: (1) есть сетка, в которой количество ячеек в каждой следующей строке увеличивается на две. Омега: для лабиринтов в стиле «омега» необходимо задать некую сетку, способ соединения ячеек друг с другом и привязку к экрану вершин, окружающих каждую ячейку. смотрил ли треугольник вверх или вниз). (2) Каждая ячейка соединяется с ячейками, соседними с ней в этом ряду, за исключением третьего прохода, который соединён с соответствующей ячейкой строкой выше или ниже, в зависимости от того, нечётный или чётный этот столбец (т.е. Можно заранее отрисовать все стены на экране и вырезать в лабиринте проходы, или хранить в памяти некий изменяемый массив и рендерить всё после завершения. (3) Каждая ячейка использует математику треугольников, чтобы определить, где отрисовывать его на экране.

  • Хотя стандартный 3D-лабиринт состоит из дерева проходов через сплошную площадь, гиперлабиринт состоит из дерева полос или лиан, проходящих по открытой площади. Гиперлабиринт: гиперлабиринт — это 3D-среда, похожая на обратную версию стандартного трёхмерного не-гиперлабиринта, в котором блоки становятся открытыми пространствами, и наоборот. Если каждая лиана соединяется с верхней или нижней частью, то гиперлабиринт будет иметь хотя бы одно простое решение. Для создания гиперлабиринта мы начинаем со сплошных верхней и нижней граней, а затем выращиваем извилистые лианы из этих граней для заполнения пространства между ними, чтобы усложнить прохождение отрезка прямой между этими двумя гранями. Если ни одна лиана не соединяется и с верхней, и с нижней частями (что создаст непроходимый столбец), то пока в верхней и нижней частях нет петель лиан, которые заставляют их неразрывно соединяться друг с другом подобно цепи, гиперлабиринт будет оставаться решаемым.

  • Лабиринт на поверхности куба — это всего лишь шесть квадратных частей лабиринта. Planair: Planair-лабиринты с необычной топологией обычно создаются как массив из одного или нескольких лабиринтов или частей лабиринтов, в которых определён способ соединения краёв друг с другом. Когда создаваемая часть доходит до края, то она перетекает в следующую часть и в правый край.

  • Шаблон:

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

  • Ниже представлен список конкретных алгоритмов. Существует множество способов создания идеальных лабиринтов, и каждый из них имеет собственные характеристики. Во всех них описано создание лабиринта вырезанием проходов, однако если не указано иное, каждый также можно реализовать добавлением стен:

  • При вырезании он ведёт себя максимально жадно, и всегда вырезает проход в несозданной части, если она существует рядом с текущей ячейкой. Recursive backtracker: он в чём-то похож на метод решения лабиринтов recursive backtracker, и требует стека, объём которого может доходить до размеров лабиринта. Если рядом с текущей позицией нет несозданных ячеек, то извлекаем из стека предыдущую позицию. Каждый раз, когда мы перемещаемся к новой ячейке, записываем предыдущую ячейку в стек. Это приводит к созданию лабиринтов с максимальным показателем текучести, тупиков меньше, но они длиннее, а решение обычно оказывается очень долгим и извилистым. Лабиринт завершён, когда в стеке больше ничего не остаётся. Recursive backtracking не может работать с добавлением стен, потому что обычно приводит к пути решения, следующему по внешнему краю, когда вся внутренняя часть лабиринта соединена с границей одним проходом. При правильной реализации он выполняется быстро, и быстрее работают только очень специализированные алгоритмы.

  • Это интересно, потому что он не «выращивает» лабиринт подобно дереву, а скорее вырезает сегменты проходов по всему лабиринту случайным образом, и тем не менее в результате создаёт в конце идеальный лабиринт. Алгоритм Краскала: это алгоритм, создающий минимальное связующее дерево. Помечаем каждую ячейку уникальным идентификатором, а затем обходим все рёбра в случайном порядке. Для его работы требуется объём памяти, пропорциональный размеру лабиринта, а также возможность перечисления каждого ребра или стены между ячейками лабиринта в случайном порядке (обычно для этого создаётся список всех рёбер и перемешивается случайным образом). Если ячейки на обеих сторонах стены уже имеют одинаковый идентификатор, то между ними уже существует какой-то путь, поэтому стену можно оставить, чтобы не создавать петель. Если ячейки с обеих сторон от каждого ребра имеют разные идентификаторы, то удаляем стену и задаём всем ячейкам с одной стороны тот же идентификатор, что и ячейкам с другой. Объединение двух множество по обеим сторонам стены будет медленной операцией, если у каждой ячейки есть только номер и они объединяются в цикле. Этот алгоритм создаёт лабиринты с низким показателем текучести, но не таким низким, как у алгоритма Прима. Объединение выполняется быстро благодаря сращиванию двух деревьев. Объединение, а также поиск можно выполнять почти за постоянное время благодаря использованию алгоритма объединения-поиска (union-find algorithm): помещаем каждую ячейку в древовидную структуру, корневым элементом является идентификатор. При правильной реализации этот алгоритм работает достаточно быстро, но медленнее большинства из-за создания списка рёбер и управления множествами.

  • Объём требуемой памяти пропорционален размеру лабиринта. Алгоритм Прима (истинный): этот алгоритм создаёт минимальное связующее дерево, обрабатывая уникально случайные веса рёбер. Выполняем выбор ребра прохода с наименьшим весом, соединяющим лабиринт к точке, которая ещё в нём не находится, а затем присоединяем её к лабиринту. Начинаем с любой вершины (готовый лабиринт будет одинаковым, с какой бы вершины мы ни начали). Для эффективного выбора следующего ребра необходима очередь с приоритетом (обычно реализуемая с помощью кучи), хранящая все рёбра границы. Создание лабиринта завершается, когда больше не осталось рассматриваемых рёбер. Поэтому лучше предпочесть алгоритм Краскала, который тоже создаёт минимальное связующее дерево, ведь он быстрее и создаёт лабиринты с идентичной структурой. Тем не менее, этот алгоритм достаточно медленный, потому что для выбора элементов из обработка кучи требует времени log(n). На самом деле при одинаковом случайном seed алгоритмами Прима и Краскала можно создавать одинаковые лабиринты.

  • Он упрощён таким образом, что все веса рёбер одинаковы. Алгоритм Прима (упрощённый): этот алгоритм Прима создаёт минимальное связующее дерево. Начинаем со случайной вершины. Для него требуется объём памяти, пропорциональный размеру лабиринта. Лабиринт оказывается завершённым, когда больше не остаётся рассматриваемых рёбер. Выбираем случайным образом ребро прохода, соединяющее лабиринт с точкой, которая ещё не в нём, а затем присоединяем её к лабиринту. Поэтому он намного быстрее истинного алгоритма Прима со случайными весами рёбер. Так как рёбра не имеют веса и не упорядочены, их можно хранить как простой список, то есть выбор элементов из списка будет очень быстрым и занимает постоянное время. Создаваемая текстура лабиринта будет иметь меньший показатель текучести и более простое решение, чем у истинного алгоритма Прима, потому что распространяется из начальной точки равномерно, как пролитый сироп, а не обходит фрагменты рёбер с более высоким весом, которые учитываются позже.

  • Однако он реализован таким образом, что вместо рёбер смотрит на ячейки. Алгоритм Прима (модифицированный): этот алгоритм Прима создаёт минимальное связующее дерево, изменённое так, что все веса рёбер одинаковы. В процессе создания каждая ячейка может иметь один из трёх типов: (1) "внутренняя": ячейка является частью лабиринта и уже вырезана в нём, (2) "граничная": ячейка не является частью лабиринта и ещё не вырезана в нём, но находится рядом с ячейкой, которая уже является «внутренней», и (3) "внешняя": ячейка ещё не является часть лабиринта, и ни один из её соседей тоже не является «внутренней» ячейкой. Объём памяти пропорционален размеру лабиринта. Выбираем случайным образом «граничную» ячейку и вырезаем в неё проход из одной из соседних «внутренних» ячеек. Начинаем с выбора ячейки, делаем её «внутренней», а для всех её соседей задаём тип «граничная». Лабиринт завершён, когда больше не остаётся «граничных» ячеек (то есть не осталось и «внешних» ячеек, а значит, все стали «внутренними»). Меняем состояние этой «граничной» ячейки на «внутреннюю» и изменяем тип всех её соседей с «внешней» на «граничную». Полученный лабиринт очень похож на результат упрощённого алгоритма Прима, за незначительным отличием: пустоты в связующем дереве заполняются, только если случайным образом выбирается граничная ячейка, в отличие от утроенной вероятности заполнения этой ячейки через одну из граничных ячеек, ведущих в неё. Этот алгоритм создаёт лабиринты с очень низким показателем текучести, имеет множество коротких тупиков и довольно прямолинейное решение. Кроме того, алгоритм очень быстр, быстрее упрощённого алгоритма Прима, потому что ему не нужно составлять и обрабатывать список рёбер.

  • Кроме того, ему не требуется дополнительной памяти или стека. Алгоритм Олдоса-Бродера: интересно в этом алгоритме то, что он однородный, то есть он с равной вероятностью создаёт все возможные лабиринты заданного размера. Если мы попали в невырезанную ячейку, то вырезаем в неё проход из предыдущей ячейки. Выбираем точку и случайным образом перемещаемся в соседнюю ячейку. Этот алгоритм создаёт лабиринты с низким показателем текучести, всего немного выше, чем у алгоритма Краскала. Продолжаем двигаться в соседние ячейки, пока не вырежем проходы во все ячейки. Однако из-за своей простоты он может быстро проходить по множеству ячеек, поэтому завершается быстрее, чем можно было бы подумать. (Это значит, что для заданного размена существует больше лабиринтов с низким показателем текучести, чем с высоким, потому что лабиринт со средней равной вероятностью имеет низкий показатель.) Плохо в этом алгоритме то, что он очень медленный, так как не выполняет интеллектуального поиска последних ячеек, то есть по сути не имеет гарантий завершения. Он может быть реализован как добавляющий стены, если стену границы считать единой вершиной, т.е., например, если ход перемещает нас к стене границы, мы телепортируемся к случайной точке вдоль границы, а уже потом продолжаем двигаться. В среднем его выполнение занимает в семь раз больше времени, чем у стандартных алгоритмов, хотя в плохих случаях оно может быть намного больше, если генератор случайных чисел постоянно избегает последних нескольких ячеек. В случае добавления стен он работает почти в два раза быстрее, потому что телепортация вдоль стены границы позволяет быстрее получать доступ к дальним частям лабиринта.

  • Он занимает память вплоть до размеров лабиринта. Алгоритм Уилсона: это усовершенствованная версия алгоритма Олдоса-Бродера, он создаёт лабиринты точно с такой же текстурой (алгоритмы однородны, то есть все возможные лабиринты генерируются с равной вероятностью), однако алгоритм Уилсона выполняется гораздо быстрее. Выбираем случайную ячейку, которая ещё не является частью лабиринта и выполняем случайный обход, пока не найдём ячейку, уже принадлежащую лабиринту. Начинаем со случайно выбранной начальной ячейки лабиринта. Конкретнее, при возврате по пути мы в каждой ячейке выполняем вырезание в том направлении, в котором проходил случайный обход при последнем выходе из ячейки. Как только мы наткнёмся на уже созданную часть лабиринта,, возвращаемся к выбранной случайной ячейке и вырезаем весь проделанный путь, добавляя эти ячейки к лабиринту. Лабиринт завершён, когда к нему присоединены все ячейки. Это позволяет избежать появления петель вдоль пути возврата, благодаря чему к лабиринту присоединяется один длинный проход. В среднем он выполняется в пять раз быстрее Олдоса-Бродера, и менее чем в два раза медленнее лучших алгоритмов. Алгоритм имеет те же проблемы со скоростью, что и Олдос-Бродер, потому что может уйти много времени на нахождение первого случайного пути к начальной ячейке, однако после размещения нескольких путей остальная часть лабиринта вырезается довольно быстро. Стоит учесть, что в случае добавления стен он работает в два раза быстрее, потому что вся стена границы изначально является частью лабиринта, поэтому первые стены присоединяются гораздо быстрее.

  • Так как в нём нет правил, которым нужно следовать постоянно, его также проще всего модифицировать и создавать с его помощью лабиринты с разной текстурой. Алгоритм Hunt and kill: этот алгоритм удобен, потому что не требует дополнительной памяти или стека, а потому подходит для создания огромных лабиринтов или лабиринтах на слабых компьютерах благодаря невозможности исчерпания памяти. Мы входим в режим «охоты» и систематично сканируем лабиринт, пока не найдём несозданную ячейку рядом с уже вырезанной ячейкой. Он почти схож с recursive backtracker, только рядом с текущей позицией нет несозданной ячейки. Лабиринт завершён, когда в режиме «охоты» просканированы все ячейки. На этом этапе мы снова начинаем вырезание в этой новой локации. Можно заставить его генерировать лабиринты с более низким показателем текучести, чаще входя в режим «охоты». Этот алгоритм склонен к созданию лабиринтов с высоким показателем текучести, но не таким высоким, как у recursive backtracker. Его можно реализовать по принципу добавления стен, если время от времени случайным образом телепортироваться, чтобы избежать проблем, свойственных recursive backtracker. Он выполняется медленнее из-за времени, потраченного на охоту за последними ячейками, но не намного медленее, чем алгоритм Краскала.

  • Требуемая память может достигать размера лабиринта. Алгоритм выращивания
    дерева (Growing tree algorithm)
    : это обобщённый алгоритм, способный создавать лабиринты с разной текстурой. Выбираем ячейку из списка и вырезаем проход в несозданную ячейку рядом с ней. При каждом вырезании ячейки мы добавляем её в список. Лабиринт завершён, когда в списке больше ничего нет. Если рядом с текущей нет несозданных ячеек, удаляем текущую ячейку из списка. Например, если всегда выбирать последнюю добавленную ячейку, то этот алгоритм превращается в recursive backtracker. Интересно в алгоритме то, что в зависимости от способа выбора ячейки из списка можно создавать множество разных текстур. Если всегда выбирать самые старые ячейки, добавленные в список, то мы создадим лабиринт с наименьшим возможным показателем текучести, даже ниже, чем у алгоритма Прима. Если всегда выбирать ячейки случайно, то он ведёт себя похоже, но не идентично алгоритму Прима. Если случайно выбирать одну из самых последних ячеек, то лабиринт будет иметь низкий показатель текучести, но долгое и извилистое решение. Если обычно выбирать самую последнюю ячейку, но время от времени выбирать случайную ячейку, то лабиринт будет иметь высокий показатель текучести, но короткое и прямое решение.

  • Он является расширением алгоритма выращивания дерева, по сути включающего в себя несколько экземпляров, расширяющихся одновременно. Алгоритм выращивания леса (Growing forest algorithm): это более обобщённый алгоритм, сочетающий в себе типы, основанные на деревьях и множествах. Сначлаа выбираем одну или несколько ячеек, перемещая их из списка «новых» в список «активных». Начинаем со всех ячеек, случайным образом отсортированных в список «новых»; кроме того, у каждой ячейки есть собственное множество, как в начале алгоритма Краскала. Если предпринята попытка выполнить вырезание в существующую часть лабиринта, то разрешить её, если ячейки находятся в разных множествах, и объединить ячейки, как это делается в алгоритме Краскала. Выбираем ячейку из «активного» списка и вырезаем проход в соседнюю несозданную ячейку из «нового» списка, добавляя новую ячейку в список «активных» и объединяя множества двух ячеек. Лабиринт завершён, когда становится пустым список «активных». Если рядом с текущей ячейкой нет несозданных «новых» ячеек, то перемещаем текущую ячейку в список «готовых». Периодически можно создавать новые деревья, перемещая одну или несколько ячеек из списка «новых» в список «активных», как это делалось в начале. В конце выполняем объединение всех оставшихся множеств, как в алгоритме Краскала. Управляя количество изначальных деревьев и долей новых создаваемых деревьев, можно сгенерировать множество уникальных текстур, сочетающихся с и так уже гибкими параметрами алгоритма выращивания дерева.

  • Для него даже не требуется, чтобы в памяти находился весь лабиринт, он использует объём, пропорциональный размеру строки. Алгоритм Эллера: это особый алгоритм, потому что он не только быстрее всех остальных, но и не имеет очевидной смещённости или недостатков; кроме того, при его создании память используется наиболее эффективно. Каждая ячейка в строке содержится во множестве; две ячейки принадлежат одному множеству, если между ними есть путь по уже созданному лабиринту. Он создаёт лабиринт построчно, после завершения генерации строки алгоритм больше её не учитывает. На самом деле это довольно похоже на алгоритм Краскала, только здесь формируется по одной строке за раз, в то время как Краскал просматривает весь лабиринт. Эта информация позволяет вырезать проходы в текущей строке без создания петель или изолированных областей. вырезаем горизонтальные проходы, затем случайным образом соединяем ячейки между текущей и следующей строками, т.е. Создание строки состоит из двух частей: случайным образом соединяем соседние в пределах строки ячейки, т.е. При вырезании горизонтальных проходов мы не соединяем ячейки, уже находящиеся в одном множестве (потому что иначе создастся петля), а при вырезании вертикальных проходов мы должны соединить ячейку, если она имеет единичный размер (потому что если её оставить, она создаст изолированную область). вырезаем вертикальные проходы. Создание начинается с того, что перед соединением ячеек в первой строке каждая ячейка имеет собственное множество. При вырезании горизонтальных проходов мы соединяем ячейки, если они находятся в одинаковом множестве (потому что теперь между ними есть путь), а при вырезании вертикальных проходов когда не соединяемся с ячейкой, помещаем её в отдельное множество (потому что теперь она отделена от остальной части лабиринта). Существует особое правило завершения: к моменту завершения каждая ячейка должна находиться в одинаковом множестве, чтобы избежать изолированных областей. Создание завершается после соединения ячеек в последней строке. Проблема этого алгоритма заключается в несбалансированности обработки разных краёв лабиринта; чтобы избежать пятен в текстурах нужно выполнять соединение и пропуск соединения ячеек в правильных пропорциях. (Последняя строка создаётся объединением каждой из пар соседних ячеек, ещё не находящихся в одном множестве.) Лучше всего реализовывать множество с помощью циклического двусвязного списка ячеек (который может быть просто массивом, привязывающим ячейки к парам ячеек с обеих сторон того же множества), позволяющего выполнять за постоянное время вставку, удаление и проверку нахождения соседних ячеек в одном множестве.

  • Рекурсивное деление (Recursive division):

    этот алгоритм чем-то похож на recursive backtracking, потому что в них обоих применяются стеки, только он работает не с проходами, а со стенами. Начинаем с создания случайной горизонтальной или вертикальной стены, пересекающей доступную область в случайной строке или столбце, и размещаем вдоль неё случайным образом пустые места. Затем рекурсивно повторяем процесс для двух подобластей, сгенерированных разделяющей стеной. Для наилучших результатов нужно добавить отклонение в выборе горизонтали или вертикали на основе пропорций области, например, область, ширина которой вдвое больше высоты, должна более часто делиться вертикальными стенами. Это самый быстрый алгоритм без отклонений в направлениях, и часто он может даже соперничать с лабиринтами на основе двоичных деревьев, потому что он создаёт одновременно несколько ячеек, хоть и имеет очевидный недостаток в виде длинных стен, пересекающих внутренности лабиринта. Этот алгоритм является разновидностью вложенных фрактальных лабиринтов, только вместо постоянного создания лабиринтов ячеек фиксированного размера с лабиринтами одного размера внутри каждой ячейки, он случайным образом делит заданную область на лабиринт случайного размера: 1x2 или 2x1. Рекурсивное деление нельзя использовать для вырезания проходов, потому что это приводит к созданию очевидного решения, которое или следует вдоль внешнего края, или иначе напрямую пересекает внутреннюю часть.

  • Для каждой ячейки мы вырезаем проход или вверх, или влево, но никогда не в обоих направлениях. Лабиринты на основе двоичных деревьев: по сути, это самые простые и быстрые из возможных алгоритмов, однако создаваемые лабиринты имеют текстуру с очень высокой смещённостью. Каждая ячейка независима от всех других ячеек, потому что нам не нужно при её создании проверять состояние каких-то других ячеек. В версии с добавлением стен для каждой вершины добавляется сегмент стены, ведущий вниз или вправо, но не в обоих направлениях. По сути, это двоичное дерево, если рассматривать верхний левый угол как корень, а каждый узел или ячейка имеет один уникальный родительский узел, являющийся ячейкой сверху или слева от неё. Следовательно, это настоящий алгоритм генерации лабиринтов без памяти, не ограниченный по размерам создаваемых лабиринтов. Например, в них никогда не будет перекрёстков, а все тупики имеют проходы, ведущие вверх или влево, и никогда не ведущие вниз или вправо. Лабиринты на основе двоичных деревьев отличаются от стандартных идеальных лабиринтов, потому что в них не может существовать больше половины типов ячеек. Всегда можно перемещаться вверх или влево, но никогда одновременно в оба направления, поэтому всегда можно детерминированно перемещаться по диагонали вверх и влево, не сталкиваясь с барьерами. Лабиринты склонны иметь проходы, ведущие по диагонали из верхнего левого в нижний правый угол, и по ним гораздо проще двигаться из нижнего правого в верхний левый угол. Учтите, что если перевернуть лабиринт двоичного дерева вниз головой и считать проходы стенами, и наоборот, то результатом по сути будет другое двоичное дерево. Иметь возможность выбора и попадать в тупики вы начнёте, перемещаясь вниз и вправо.

  • Лабиринты Sidewinder:

    этот простой алгоритм очень похож на алгоритм двоичного дерева, но немного более сложен. Лабиринт генерируется по одной строке за раз: для каждой ячейки случайным образом выбирается, нужно ли вырезать проход, ведущий вправо. Если проход не вырезан, то мы считаем, что только что завершили горизонтальный проход, образованный текущей ячейкой и всеми ячейками слева, вырезавшими проходы, ведущими в неё. Случайным образом выбираем одну ячейку вдоль этого прохода и вырезаем проход, ведущий из неё вверх (это должна быть текущая ячейка, если соседняя ячейка не вырезала проход). В то время как лабиринт двоичного дерева всегда поднимается вверх от самой левой ячейки горизонтального прохода, лабиринт sidewinder поднимается вверх от случайной ячейки. В двоичном дереве у лабиринта в верхнем и левом крае есть один длинный проход, а в лабиринте sidewinder есть только один длинный проход по верхнему краю. Как и лабиринт двоичного дерева, лабиринт sidewinder можно без ошибок и детерминированно решить снизу вверх, потому что в каждой строке всегда будет ровно один проход, ведущий вверх. Решение лабиринта sidewinder никогда не делает петель и не посещает одну строку больше одного раза, однако оно «извивается из стороны в сторону». Единственный тип ячеек, который не может существовать в лабиринте sidewinder — это тупик с ведущим вниз проходом, потому что это будет противоречить правилу, что каждый проход, ведущий вверх, возвращает нас к началу. Лабиринты sidewinder склонны к появлению элитного решения, при котором правильный путь оказывается очень прямым, но рядом с ним есть множество длинных ошибочных путей, ведущих сверху вниз.

  • Для сравнения добавлен алгоритм одномаршрутного лабиринта (теоретически одномаршрутные лабиринты являются идеальными). В этой таблице вкратце представлены характеристики описанных выше алгоритмов создания идеальных лабиринтов. Объяснение столбцов:

    Вот список конкретных алгоритмов: Существует множество способов решения лабиринтов, и каждый из них имеет собственные характеристики.

  • Приоритетом для него является проходящий лабиринт объект («вы»), он всегда очень быстр и не использует дополнительной памяти. Следование вдоль стен (Wall follower): это простой алгоритм решения лабиринтов. Чтобы применить такое решение лабиринта в реальном мире, нужно положить руку на правую (или левую) стену и постоянно держать её на стене в процессе прохождения лабиринта. Начинаем идти по проходам и при достижении развилки всегда поворачиваем направо (или всегда налево). В конце можно вернуться назад по решению, следуя только по ячейкам, посещённым один раз. При желании можно помечать уже посещённые ячейки и ячейки, посещённые дважды. Следование вдоль стены в 3D-лабиринте можно реализовать детерминированным способом, спроецировав 3D-проходы на 2D-плоскость, т.е. Этот метод необязательно найдёт кратчайшее решение, и он совершенно не работает, если цель находится в центре лабиринта и его окружает замкнутая цепь, потому что вы будете ходить вокруг центра и со временем придёте к началу. притворившись, что ведущие вверх проходы на самом деле ведут на северо-запад, а ведущие вниз ведут на юго-восток, а затем применить обычные правила следования вдоль стен.

  • Это гарантированный способ достижения выхода на внешнем крае любого 2D-лабиринта из любой точки внутри, однако он не способен выполнить обратную задачу, т.е. Алгоритм Пледжа: это модифицированная версия следования вдоль стены, способная перепрыгивать между «островами» для решения тех лабиринтов, которые не способно следование вдоль стен. Он отлично подходит для реализации с помощью сбегающего из лабиринта робота, потому что он сможет выбраться из любого лабиринта, не помечая и не запоминая ни каким образом путь. найти решение внутри лабиринта. Упёршись в стену, начинаем следовать вдоль неё, пока не сможем снова пойти в выбранном направлении. Начинаем с выбора направления и при возможности всегда движемся в этом направлении. Если в этом месте проход делает поворот, то это может привести к развороту посередине прохода и возврату тем же путём, которым мы пришли. Стоит заметить, что следование вдоль стены нужно начинать с дальней стены, в которую мы упёрлись. Прекращаем следование вдоль стен и начинаем двигаться в выбранном направлении только тогда, когда общая сумма сделанных поворотов равна, т.е. При следовании вдоль стены считаем количество сделанных поворотов, например, поворот налево — это -1, а поворот направо — это 1. Подсчёт гарантирует, что рано или поздно мы достигнем дальней части «острова», в котором находимся в данный момент, и перепрыгнем на следующий остров в выбранном направлении, после чего продолжим прыгать между островами, пока не упрёмся в стену границы, после чего следование вдоль стен приведёт нас к выходу. если вы повернулись на 360 градусов и более, то продолжаем следовать вдоль стены пока не «распутаемся». Без разметки пути единственный способ узнать, что лабиринт нерешаем — постоянное увеличение суммы поворотов, хотя в решаемых лабиринтах со спиральным прохождением сумма поворотов тоже может достигать больших значений. Стоит учесть, что алгоритм Пледжа может заставить нас посетить проход или начальную точку несколько раз, однако в последующие разы вы всегда будете иметь другую сумму поворотов.

  • Мы должны указать нужные места начала и конца, и алгоритм всегда найдёт путь от начала до конца, если он существует. Алгоритм цепей: алгоритм цепей (Chain algorithm) решает лабиринт, воспринимая его как множество лабиринтов меньшего размера (подобно звеньям цепи) и решая их по порядку. Это означает, что таким способом нельзя решать лабиринты, в которых неизвестно точное расположение конца. При этом решение склонно быть разумно коротким, если даже не кратчайшим. Начинаем с рисования прямой линии (или хотя бы линии без самопересечений) от начала до конца, позволяя ей при необходимости пересекать стены. Он наиболее похож на алгоритм Пледжа, потому что по сути это алгоритм следования вдоль стен со способом перепрыгивания между островами. Если мы натыкаемся на стену, то не можем пройти через неё, а значит должны обходить. Затем просто следуем по линии от начала до конца. Если робот снова пересечётся с указующей линией в той точке, где она ближе к выходу, тогда останавливаемся и следуем по этой стене, пока не доберёмся до неё сами. Отправляем двух следующих вдоль стен «роботов» по каждому из направлений вдоль стены, на которую наткнулись. Если оба робота вернутся к их исходным локациям и направлениям, то дальнейшие точки вдоль прямой недостижимы и лабиринт нерешаем. Продолжаем следовать по линии и повторять процесс, пока не достигнем конца.

  • Recursive backtracker:

    этот алгоритм находит решение, но оно необязательно будет кратчайшим. Приритетом для него является проходящий лабиринт объект, он быстр для всех типов лабиринтов и использует стек размером вплоть до размера лабиринта. Он очень прост: если мы находимся возле стены (или в помеченной линией области), то возвращаем «неудача», иначе, если мы находимся в конце, возвращаем «успех», иначе, рекурсивно пробуем двигаться во всех четырёх направлениях. Рисуем линию, когда пытаемся пройти в новом направлении и удаляем её, если возвращено значение «неудача»; после достижения состояния «успех» у нас будет нанесено линиями единственное решение. При возврате назад (backtracking) лучше помечать пространство особым значением посещённых мест, чтобы мы не посещали их снова, приходя с другого направления. По сути, в программировании это называется поиском в глубину. Этот метод всегда находит решение, если оно существует, но оно необязательно будет самым коротким.

  • Алгоритм Тремо (Trémaux's algorithm):

    этот метод решения лабиринтов разработан для использования человеком внутри лабиринта. Он похож на recursive backtracker и находит решение для всех лабиринтов: при движении по проходу мы рисуем линию за собой, помечающую наш путь. При попадании в тупик поворачиваемся назад и возвращаемся тем же путём, которым пришли. Дойдя до развилки, на которой ещё не были, случайным образом выбираем новый проход. Если мы проходим по новому проходу и доходим до развилки, которую посещали ранее, то считаем её тупиком и возвращаемся тем же путём, которым пришли. (Этот последний этап является самым важным, он не позволяет двигаться кругами и пропускать проходы в плетёном лабиринте.) Если двигаясь по проходу, который мы посещали раньше (т.е. раньше пометили), мы наткнулись на развилку, то выбираем любой новый проход, если это возможно, в противном случае выбираем старый проход (т.е. тот, который мы раньше пометили). Все проходы будут или пустыми, то есть мы их ещё не посещали, помеченными один раз,, то есть мы там были ровно один раз, или помеченными дважды, то есть мы двигались по ним и вынуждены были возвращаться в обратном направлении. Когда мы наконец достигнем решения, то помеченные один раз пути будут составлять прямой путь до самого начала. Если у лабиринта нет решения, то мы окажемся в начале, а все проходы будут помечены дважды.

  • Приоритетом для него является лабиринт, он всегда очень быстр и не использует дополнительной памяти. Заполнитель тупиков (Dead end filler): это простой алгоритм решения лабиринтов. В том числе это относится и к заливке проходов, которые стали частями тупиков после удаления других тупиков. Мы просто сканируем лабиринт и заполняем каждый тупик, заливая проход в обратном порядке от тупика, пока не достигнем развилки. Алгоритм всегда находит для идеальных лабиринтов одно уникальное решение, но не особо преуспевает в лабиринтах с сильным плетением, и на самом деле почти бесполезен во всех лабиринтах без тупиков. В конце у нас останется одно решение, или несколько решений, если у лабиринта их больше одного.

  • Как и в dead end filler, приоритетом здесь является лабиринт, алгоритм всегда быстр и не использует дополнительной памяти. Cul-de-sac filler: этот метод находит и заполняет тупиковые развязки или петли, то есть конструкции в лабиринте, состоящие из тупикового пути с единственной петлёй в конце. Затем мы запускаем dead end filler. Сканируем лабиринт и для каждой петлевой развилки (петлевая развилка — это такая развилка, в которой два ведущих из неё прохода соединяются друг с другом, по пути не образуя новых развилок) добавляем стену, чтобы превратить всю петлю в длинный тупик. Этот алгоритм не очень полезен в сложных, сильно плетёных лабиринтах, но будет отсекать больше путей, чем простой dead end filler. В лабиринтах могут быть петли, выдающиеся из других конструкций, которые становятся петлями после удаления первых петель, поэтому весь процесс нужно повторять, пока при сканировании ничего не станет происходить.

  • Он делает это, заполняя все тупиковые развязки. Blind alley filler: этот метод находит все возможные решения, вне зависимости от того, насколько они длинные или короткие. Все тупики являются тупиковыми развязками, как и все петли, описанные в алгоритме cul-de-sac filler, а также секции проходов любого размера. Тупиковая развязка — это такая конструкция, в которой двигаясь в одном направлении, для достижения цели придётся возвращаться назад по тому же пути в другом направлении. Приоритет он отдаёт лабиринту, не использует дополнительной памяти, но, к сожалению, довольно медленный. соединённые с остальной частью лабиринта единственным проходом. Если это происходит, то такой проход и всё после него не может быть никаким путём решения, поэтому мы перекрываем этот проход и заливаем всё за ним. В каждой развилке мы отправляем следующего вдоль стен робота по каждому проходу, ведущему из неё, и смотрим, вернулся ли отправленный по пути робот тем же маршрутом (то есть не пришёл с другого направления и не вышел из лабиринта). Этот алгоритм заполняет всё то же, что и cul-de-sac filler и кое-что ещё, однако описанный ниже алгоритм collision solver заполнит всё то же, что и этот алгоритм и кое-что ещё.

  • Однако он заполняет только проходы в каждую тупиковую развязку и не касается набора проходов в их конце. Blind alley sealer: этот алгоритм похож на blind alley filler тем, что он тоже находит все возможные решения, удаляя из лабиринта тупиковые развязки. Этот алгоритм отдаёт приоритет лабиринту, работает гораздо быстрее, чем blind alley filler, хоть и требует дополнительной памяти. В результате он создаст во всех тупиковых развязках и петлях сложнее простых тупиков недостижимые проходы. Чтобы сделать это, для каждой секции стен, ещё не находящихся в множестве, мы выполняем заливку поверх стен в этой точке, и определяем все достижимые стены в новое множество. Мы определяем каждую соединённую секцию стен в уникальное множество. Если стены по обеим её сторонам находятся в одном множестве, то мы перекрываем этот проход. После того, как все стены окажутся в множествах, мы проверяем каждую секцию проходов. Стоит заметить, что подобную технику можно использовать для помощи в решении гиперлабиринтов благодаря перекрытию пространства между ветвями, соединёнными друг с другом. Такой проход должен быть тупиковой развязкой, потому что стены по обеим сторонам соединены друг с другом, образуя огороженную площадку.

  • Поиск кратчайшего пути (Shortest path finder):

    как можно понять из названия, этот алгоритм находит кратчайшее решение, при наличии нескольких решений выбирая одно из них. Он множество раз отдаёт приоритет находящемуся в лабиринте, быстр для всех типов лабиринтов и требует довольно много дополнительной памяти, пропорциональной размеру лабиринта. Как и collision solver, он, по сути, заливает лабиринт «водой» так, что всё на одном расстоянии от начала заливается одновременно (в программировании это называется поиском в ширину), однако каждая «капля» или пиксель, запоминает, каким пикселем они были заполнены. Как только в решение попадает «капля», мы возвращаемся обратно от неё к началу, и это будет кратчайшим путём. Этот алгоритм хорошо работает для любых входных данных, потому что в отличие от большинства остальных не требует наличия в лабиринте каких-то проходов в пиксель шириной, по которым можно пройти. Стоит заметить, что это, по сути, алгоритм поиска пути A* без эвристики, то есть всему движению присваивается одинаковый вес.

  • Как и поиск кратчайшего пути, он множество раз отдаёт приоритет находящемуся в лабиринте, быстр для всех типов лабиринтов, требует дополнительной памяти, пропорциональной размеру лабиринта, и хорошо работает с любыми входными данными, потому что не требует, чтобы в лабиринте были какие-то проходы шириной в один пиксель, по которым можно пройти. Поиск кратчайших путей (Shortest paths finder): он очень похож на поиск кратчайшего пути, только находит все кратчайшие решения. После достижения конца выполняется ещё один поиск в ширину, начинающийся с конца, однако в него включаются только те пиксели, чьё расстояние на одну единицу меньше, чем у текущего пикселя. Кроме того, как и поиск кратчайшего пути, он выполняет поиск в ширину, заполняя лабиринт «водой» так, что всё на одинаковом расстоянии от начала заполняется одновременно, только здесь каждый пиксель запоминает, как далеко он находится от начала. Включённые в путь пиксели точно помечают все кратчайшие пути, так как в тупиковых развязках и в не самых коротких путях расстояния в пикселях будут скакать или увеличиваться.

  • Collision solver: также называется "amoeba" solver. Этот метод находит все кратчайшие решения. Он множество раз отдаёт приоритет находящемуся в лабиринте, быстр для всех типов лабиринтов и требует наличия в памяти хотя бы одной копии лабиринта в дополнение к объёму памяти вплоть до размеров лабиринта. Он заливает лабиринт «водой» так, что всё на одном расстоянии от начала заливается одновременно (поиск в ширину). Когда два «столбца воды» приближаются к проходу с обоих краёв (сигнализируя о наличии петли), мы добавляем в исходный лабиринт стену там, где они сталкиваются. Когда все части лабиринта окажутся «затопленными», мы заполняем все новые тупики, которые не могут находиться на кратчайшем пути, и повторяем процесс, пока больше не останется столкновений. (Представьте амёбу, плывущую на гребне «волны», когда она втекает в проходы. Когда волны сталкиваются, амёбы сталкиваются и выходят из строя, создавая на этом месте новую стену потерявших сознание амёб, отсюда и название алгоритма.) По сути, он аналогичен shortest paths finder, однако эффективнее использует память (так как ему нужно отслеживать координаты только переднего края каждого столбца воды) и немного медленнее (так как потенциально должен выполняться несколько раз для устранения всего).
  • Random mouse: для контраста приведу неэффективный метод решения лабиринта, который по сути заключается в случайном перемещении, т.е. движении в одном направлении и следовании по этому проходу со всеми поворотами, пока мы не достигнем следующей развилки. Мы не делаем никаких поворотов на 180 градусов, если без них можно обойтись. Это симулирует поведение человека, случайно блуждающего по лабиринту и не помнящему, где он уже был. Алгоритм медленный и не гарантирует завершения или решения лабиринта, а после достижения конца будет столь же сложно вернуться к началу, зато он прост и не требует дополнительной памяти для реализации.
  • По этим критериям можно классифицировать и оценивать алгоритмы решения лабиринтов. В этой таблице вкратце перечислены характеристики описанных выше алгоритмов решения лабиринтов. Объяснения столбцов:

    Кроме создания и решения лабиринтов, с ними можно выполнять другие операции:

    Показать больше

    Похожие публикации

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *

    Кнопка «Наверх»