Генерация и решение лабиринта с помощью метода поиска в глубину по графу. Алгоритмы генерации лабиринтов

Нарисовать этот лабиринт очень просто. Возьмите лист бумаги. Нарисуйте крест и поставьте точки в центре каждой из четырех четвертей креста. Это – прототип лабиринта.

Шаг 1. Прототип трехкружного лабиринта

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

Шаг 2. Первая дуга

Затем от точки в верхней левой четверти креста проведите дугу к правому концу горизонтальной линии.

Шаг 3. Вторая дуга

А от левого конца этой горизонтальной линии – к точке в нижней правой четверти креста.

Шаг 4. Третья дуга

И наконец, от точки в нижней левой четверти креста – к нижнему концу вертикальной линии.

Шаг 5. Четвертая дуга

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

Пожалуйста, возьмите чистый лист бумаги и карандаш и нарисуйте три классических трехкружных лабиринта.
Очень важно сделать лабиринт своими руками, а не только умозрительно. В том, чтобы самостоятельно сделать лабиринт, есть нечто особенное. Это происходит после пятого или шестого раза. Действительно, когда известен способ, несложно понять рассудком, как чертится лабиринт, но после полудюжины рисунков руки перестают знать и начинают ведать, как это делается. Не пренебрегайте этими упражнениями, ибо они помогут понять этот магический инструмент таким способом, который никогда не откроется, если только читать или размышлять о лабиринтах. Классические лабиринты предполагают другой способ постижения.

Пожалуй, все владельцы дачных участков пытаются сделать во дворе что-то необычное и оригинальное, что-то такое, что выделяло бы его из остальных. Это может быть небольшой , спрятанная между развесистыми деревьями, другие варианты. Это все классика, но есть и другие, более таинственные садовые элементы – вспомните, к примеру, лабиринты во времена Средневековья, который обрамляли роскошные дворцы! И нечто подобное (в более скромных масштабах, разумеется) может сделать любой владелец загородного участка, если у него есть возможности и желание. И о том, как сделать садовый лабиринт своими руками , мы и расскажем в сегодняшней статье.

Интересно! Знаете ли вы, что существует несколько способов корчевания пней? Если желаете узнать об этом поподробнее, то для вас!

Но чем хорош лабиринт в саду? Вы удивитесь, но у данной затеи есть многочисленные преимущества:

• сад будет обустроен нетрадиционно, оригинально;
• детишкам это будет полезно в плане развития;
• домашние и гости смогут отлично развлечься.

Определяемся, что собой представляет садовый лабиринт

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

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

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

Теперь – непосредственно к процессу создания лабиринта!

Этап первый. Месторасположение, композиция

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

Самым примитивным вариантом лабиринта является закрученная спираль, дорожки которой соединяются по центру. А вот с композициями, в которых есть несколько выходов или тупик, все намного сложнее. И отличным тому примером может являться любой парковый лабиринт Европы, а если его упростить, то можно получить и собственную оригинальную схему.

При создании лабиринта следует уделять внимание как переплетению дорожек, так и «сердцу» композиции, то есть центральной части. Там рекомендуется обустроить зону отдыха, для чего можно, например, поставить столик с креслами, соорудить перголу и так далее. «Сердцем» может стать даже красивая скульптура, клумба, водоем или даже солнечные часы.

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

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

При создании среднего лабиринта используются растения высотой не более 0,5 метра (это может быть низкорослая спирея, альпийская смородина, самшит). Все указанные культуры произрастают в средней полосе. А если вы затеваете действительно что-то масштабное – композицию, в котором и взрослые некоторое время будут блудить, то оптимальным вариантом будут деревья высотой до 3-х метров. По мнению опытных специалистов, для этого больше всего подходит тис, шиповник, татарский клен, граб, другие.

Обратите внимание! Сочетание видов культур должно быть подобрано так, чтобы те имели разные периоды цветения, то есть цвели не в одно время. Только в таком случае садовый лабиринт будет выглядеть великолепно большую часть года!

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

• входа;
• нескольких поворотов;
• выхода.

Что же касается форм, то самыми простыми из них являются спиралевидные композиции, где все дорожки соединяются по центру. Существует также сквозная схема, в которой отсутствует ярко выраженное «сердце». А теперь разберемся, какие виды лабиринтов самые популярные в ландшафтном дизайне.

Этап третий. Беремся за дело – несколько возможных вариантов действий

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

Вариант №1. Композиция из живой изгороди

Самым привлекательным, а оттого и заманчивым вариантом является садовый лабиринт, выполненный из живой изгороди. Вполне очевидно, что этот вариант является еще и самым трудоемким и сложным в выполнении. Культуры (это могут быть как деревья, так и кусты), образующие ходы в такого рода композиции, нуждаются в постоянном уходе и частой стрижке. Более того, площадь такой вот прелести будет немалой – никакие 6 соток в данном случае уже не спасут.

Хотя если площадь участка достаточно большая, а вы сами преисполнены желанием поддерживать живую изгородь «в форме», то такая конструкция превратится в ваше любимое место для прогулок! Скорее всего, не только дети, но и внуки смогут играть в запутанных ходах, так как при должном уходе композиция будет все так же привлекательной десятки лет.

Если планируете использовать в качестве «стройматериала» живую изгородь, то советуем прибегнуть к:

• кизильнику блестящему;
• лавру;
• бирючине;
• вечнозеленому самшиту.

А ежели желания ждать того, когда вырастут многолетние кусты, у вас нет, можете сделать все по-быстрому, используя быстрорастущие однолетние культуры (это может быть, к примеру, веничная кохия, которая вырастает не выше 1-го метра). Она в рекордно короткие сроки образует плотную зеленую массу, к тому же, ее достаточно легко стричь. Хотя есть и существенный минус – такой лабиринт из однолетних культур придется восстанавливать каждый год, по этой причине он – скорее временный вариант.

Вариант №2. Лабиринт из камня

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

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

Вариант №3. Композиция из цветов

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

Обратите внимание! Если эти самосеющиеся культуры все же использовать, то композиция потеряет четкость и станет расплывчатым пятном. Поэтому лучше брать для этого компактные растения – розу бордюрную, например, или же кустовую петунию.

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

Вариант №4. Фантазийная композиция

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

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

Все растительные культуры, в том числе живая изгородь, будут здесь свободно произрастать, разрастаться так, как «захочется», дабы скрыть от человека все, что находится в нескольких шагах. И после каждого поворота посетителя будет ждать что-то необычное и в то же время приятное: прекрасная клумба, удобная скамья для отдыха, гипсовая скульптура и т. д.

Подводя итоги

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

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

Поэтому, если вы переживаете, что ваши питомцы будут скучать и при этом не хотите раскошеливаться, предлагаем вам идею – сделать лабиринт для хомяка своими руками!

В начале статьи вы видели картину конечного результата. Конечно, он выглядит не очень приглядно, но этот туннельный лабиринт состоит из пластиковых бутылок, а значит, обойдется вам бесплатно! А в наше время хочется хоть на чем-то сэкономить.

Обратите внимание, такой же лабиринт-туннель можно сделать своими руками и для крыс, хорьков, морских свинок и других грызунов.

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

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

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

Внимание! При работе вы будете использовать острые инструменты, поэтому соблюдайте крайнюю осторожность во время изготовления лабиринта для хомяка.

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

Необходимое время: примерно 30 минут.

1. Тщательно промойте все бутылки – вы же не хотите, чтобы туннели для ваших домашних питомцев были вонючими и липкими!
2. Удалите этикетки и крышки с бутылок – они просто не нужны и к тому же мешают!
3. Свой первый проект можете начать с 4-х бутылок, но количество можно легко увеличить на любом этапе – это только вопрос хранения готового лабиринта – чем больше, тем сложнее его куда-либо пристроить. Здесь есть также место для творчества, ведь пластиковые бутылки бывают разных цветов и форм. Это поможет вам создать лабиринт не похожий на другие.
4. Осторожно с помощью канцелярского ножа удалите верхнюю и нижнюю часть каждой бутылки. Желательно сделать это на достаточно твердой поверхности, иначе вы рискуете продырявить ножом что-либо ценное. Также имейте в виду, что обрезанные края, скорее всего, будут зубчатые и острые. Это мы устраним на следующем шагу.

   
   

   
   
5. Возьмите изоленту. Изоляционная лента идеально подходит для этого проекта, так как она хорошо облегает пластик, а также хорошо обклеивает края бутылок. Скрыть неровные края очень важно – вы же не хотите, чтобы ваши питомцы порезали свои маленькие лапки! Сделайте короткие полоски липкой ленты и приклейте их половину на обратную сторону ободка бутылки. Затем сделайте разрезы в ленте примерно на расстоянии 1 см друг от друга, и заверните на другую сторону. Это позволит вам получить более скругленные углы во время наклейки изоленты. Хоть этот процесс и занимает довольно много времени, тем не менее, он очень важен. После того как вы обклеите края всех бутылок, переходите к следующему шагу.

   
   

   
   
6. При подготовке «Т» соединений двух бутылок вам необходимо в одной из них вырезать круглое отверстие. С помощью канцелярского ножа сделайте надрез в виде «+» в месте будущего отверстия. Отогните края пластика, стараясь не дергать слишком сильно, так как пластик может порваться дальше по надрезу и тогда бутылку придется заменить! Затем вставьте в получившееся маленькое отверстие ножницы и вырежьте с их помощью круг диаметром второй бутылки. Используя 1 см полоски изоленты, обклейте края получившегося отверстия.

   

7. Возьмите бутылку, которая будет присоединяться к первой и сожмите её край, сделав его плоским. Вырежьте по диагональной линии верхний и нижний угол, как показано на рисунке. Это сделает край изогнутым, что позволит одной бутылке удобно «сидеть» на другой. Не волнуйтесь, если вы слишком много отрезали. Обклеивая края изолентой, вы можете просто прикрепить излишне отрезанный кусочек на свое место.
   
8. Удерживая обе трубки в месте соединения, убедитесь, что трубка, сделанная на 7 шаге, плотно прилегает к трубке, сделанной на 6 шаге. Удерживая их в нужном положении, используйте один длинный кусок ленты, чтобы прикрепить бутылки между собой. Для этого приклейте изоленту на одну сторону прикрепляемой бутылки и, обведя вокруг другой бутылки, приклейте конец ленты с другой стороны. Затем оставшиеся щели в месте соединения заклейте кусками изоленты. Более подробно данный процесс можете посмотреть на фото.
   
9. Теперь ваши две трубки должны выглядеть как на следующем рисунке. Повторите все шаги, начиная с 6го, для оставшихся двух труб. После завершения вы будете иметь два набора двух труб.
10. Последнее, что нужно сделать, это соединить вместе с помощью изоленты ваши два набора двух труб.

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

В этой статье речь пойдет о самом простом в реализации алгоритме генерации «идеального» лабиринта и его применении для поиска пути.

Мы рассмотрим алгоритм, основанный на бэктрекинге, позволяющий создавать лабиринты без циклов, имеющие единственный путь между двумя точками. Алгоритм не самый быстрый, довольно требователен к ресурсам, по сравнению с алгоритмом Эйлера или Крускала, но очень прост в реализации и позволяет создавать ветвистые лабиринты с очень длинными тупиковыми ответвлениями.

Заинтересовавшихся - прошу под кат.

В русскоязычном интернете очень мало информации по алгоритмам генерации лабиринтов, что и стало причиной для написания этой статьи.
Примеры кода на языке Си, а также полный исходный код проекта на GitHub доступны под лицензией GNU GPLv3.
Ссылки на англоязычные ресурсы и проект вы найдете в конце статьи.

Описание алгоритма

2. Пока есть непосещенные клетки



    3. Уберите стенку между текущей клеткой и выбранной
    4. Сделайте выбранную клетку текущей и отметьте ее как посещенную.
  2. Иначе если стек не пуст

    2. Сделайте ее текущей
  3. Иначе
    1. Выберите случайную непосещенную клетку, сделайте ее текущей и отметьте как посещенную.

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

Реализация

Иллюстрация работы алгоритма

1.    < - Выбираем начальную точку стартовой.

2.1.   < - Перемещаемся к случайному непосещенному соседу, пока таковые есть.

2.2.   < - Непосещенных соседей нет. Возвращаемся назад по стеку, пока нет непосещенных соседей.

2.1.   < - Непосещенные соседи есть. Перемещаемся к случайному непосещенному соседу.

2.    < - Нет непосещенных клеток. Лабиринт сгенерирован.

Программный код

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

Int maze; //создаем матрицу - двумерный массив for(i = 0; i < height; i++){ for(j = 0; j < width; j++){ if((i % 2 != 0 && j % 2 != 0) && //если ячейка нечетная по x и y, (i < height-1 && j < width-1)) //и при этом находится в пределах стен лабиринта maze[i][j] = CELL; //то это КЛЕТКА else maze[i][j] = WALL; //в остальных случаях это СТЕНА. } }
Теперь, когда все приготовления сделаны, можно приступать к генерации.

Typedef struct cell{ //структура, хранящая координаты клетки в матрице unsigned int x; unsigned int y; } cell; typedef struct cellString{ cell* cells; unsigned int size; } cellString;
Структуры значительно упростят жизнь при обмене информацией между функциями.

Отрывок кода, отвечающий за генерацию:

Cell startCell = {1, 1} cell currentCell = startCell; cell neighbourCell; do{ cellString Neighbours = getNeighbours(width, height, maze, startPoint, 2); if(Neighbours.size != 0){ //если у клетки есть непосещенные соседи randNum = randomRange(0, Neighbours.size-1); neighbourCell = cellStringNeighbours.cells; //выбираем случайного соседа push(d.startPoint); //заносим текущую точку в стек maze = removeWall(currentCell, neighbourCell, maze); //убираем стену между текущей и сосендней точками currentCell = neighbourCell; //делаем соседнюю точку текущей и отмечаем ее посещенной maze = setMode(d.startPoint, d.maze, VISITED); free(cellStringNeighbours.cells); } else if(stackSize > 0){ //если нет соседей, возвращаемся на предыдущую точку startPoint = pop(); } else{ //если нет соседей и точек в стеке, но не все точки посещены, выбираем случайную из непосещенных cellString cellStringUnvisited = getUnvisitedCells(width, height, maze); randNum = randomRange(0, cellStringUnvisited.size-1); currentCell = cellStringUnvisited.cells; free(cellStringUnvisited.cells); } while(unvisitedCount() > 0);
Как видно, реализация алгоритма проста и абстрактна от теории, как говорится, «справится даже ребенок».
Чтобы не перегружать статью, код функций, используемых в вышеприведенном отрывке, под спойлером.

Код функций

Функция getNeighbours возвращает массив непосещенных соседей клетки

CellString getNeighbours(unsigned int width, unsigned int height, int** maze, cell c){ unsigned int i; unsigned int x = c.x; unsigned int y = c.y; cell up = {x, y - distance}; cell rt = {x + distance, y}; cell dw = {x, y + distance}; cell lt = {x - distance, y}; cell d = {dw, rt, up, lt}; unsigned int size = 0; cellString cells; cells.cells = malloc(4 * sizeof(cell)); for(i = 0; i < 4; i++){ //для каждого направдения if(d[i].x > 0 && d[i].x < width && d[i].y > 0 && d[i].y < height){ //если не выходит за границы лабиринта unsigned int mazeCellCurrent = maze.y].x]; cell cellCurrent = d[i]; if(mazeCellCurrent != WALL && mazeCellCurrent != VISITED){ //и не посещена\является стеной cells.cells = cellCurrent; //записать в массив; size++; } } } cells.size = size; return cells;
Функция removeWall убирает стенку между двумя клетками:

MazeMatrix removeWall(cell first, cell second, int** maze){ short int xDiff = second.x - first.x; short int yDiff = second.y - first.y; short int addX, addY; cell target; addX = (xDiff != 0) ? (xDiff / abs(xDiff)) : 0; addY = (yDiff != 0) ? (yDiff / abs(yDiff)) : 0; target.x = first.x + addX; //координаты стенки target.y = first.y + addY; maze = VISITED; return maze; }
Сначала вычисляется значение разности координат второй и первой точек. Очевидно, значение может быть либо отрицательное, либо положительное, либо 0.

Надо найти такие координаты xy, чтобы при сложении их с координатами первой точки получались координаты стенки.

Так как мы точно знаем, что вектор разности между координатами стенки и первой точке равен либо (|1|, 0) либо (0, |1|), мы можем этим воспользоваться.

Таким образом, аддитив для x координаты при xDiff != 0 будет равен xDiff / |xDiff|, при xDiff = 0, нулю. Для y соответственно.
Получив аддитивы для x и y, мы легко вычисляем координаты стенки между первой и второй клетками и назначаем клетку по этим координатам посещенной.

В итоге, мы можем получить что-то такое:

Лабиринты. Осторожно, трафик!

100x100


  500x500

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

И все еще сильнее упрощается, так как нам больше не надо убирать стенки.

Алгоритм поиска пути бэктрекингом:
1. Сделайте начальную клетку текущей и отметьте ее как посещенную.
2. Пока не найден выход
  1. Если текущая клетка имеет непосещенных «соседей»
    1. Протолкните текущую клетку в стек
    2. Выберите случайную клетку из соседних
    3. Сделайте выбранную клетку текущей и отметьте ее как посещенную.
  2. Иначе если стек не пуст
    1. Выдерните клетку из стека
    2. Сделайте ее текущей
  3. Иначе выхода нет

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

Критерий нахождения «выхода» очень прост: достаточно сравнить координаты текущей точки и координаты «выхода»: если они равны, путь между стартовой и выходной точками найден.

Посмотрим что вышло:

Вот и все, что нужно для самой простой реализации генератора случайных лабиринтов.

Для тех, кто заинтересовался, полный исходный код проекта на GitHub.

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

Лабиринты мы будем строить на прямоугольном клеточном поле (+ одна из статей о генерации в трехмерном пространстве), поэтому все их можно разделить на две группы: лабиринты с «тонкими» стенками и с «толстыми». Первые - это те, у которых стены расположены на границах клеток, вторые - это те, в которых некоторые клетки сами являются непроходимыми, т.е. стенами. Их отличает, например, способ хранения данных о карте.

Также существуют уже готовые решения для генерации лабиринтов: , который используется в DOOM, DOOM II и Heretic, и др.

Алгоритм Эллера

На тему генерации лабиринтов, где стенки расположены на границах клеток, на Хабре есть хороший перевод статьи «Eller’s Algorithm» (именно Эллера, а не Эйлера - «Eller’s», а не «Euler’s») о том, как создать идеальный (perfect) лабиринт - такой, что между любыми двумя его клетками существует путь, и притом единственный.

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

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

Как хранить лабиринты с «толстыми» стенками?

Ответ на вопрос о хранении карт таких лабиринтов очевиден: в виде двумерного boolean массива, где, например, 1 - это непроходимая клетка (стена), 0 - свободная.

Подробнее о картах на клеточных полях написано в статье «Tilebased games» . Теперь перейдем к самим лабиринтам генерации.

Наивный алгоритм

Лабиринт на таблице

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

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

Подробно этот алгоритм генерации описан в статье «Grid Based Dungeon Generator» .

BSP деревья

BSP - это аббревиатура от Binary Space Partitioning - двоичное разделение пространства. Этот алгоритм также позволяет избежать пересечения комнат еще в процессе помещения их на карту, т.к. также предварительно делит игровое поле на части - «листья», внутри которых затем генерирует комнаты. Это деление площади идейно сложнее, т.к. разделяет все, чем предыдущий алгоритм, но и позволяет создать более интересные конфигурации расположения помещений.

Генерация лабиринтов с использованием клеточного автомата

Каждый программист хотя бы раз писал «Жизнь» - клеточный автомат, придуманный математиком Конвэем. Так почему бы не использовать схожую идею для генерации лабиринтов? Суть предложенного алгоритма состоит в реализации всего двух шагов: сначала все поле заполняется случайным образом стенами - т.е. для каждой клетки случайным образом определяется, будет ли она свободной или непроходимой - а затем несколько раз происходит обновление состояния карты в соответствии с условиями, похожими на условия рождения/смерти в «Жизни».

В источнике - на странице статьи «Generate Random Cave Levels Using Cellular Automata» - вы можете поэкспериментировать с интерактивной демкой, устанавливая различные значения для генерации: количество итераций обновления, граничные значения для жизни/смерти клетки и т.п. - и увидеть результат. Там же рассказывается о подводных камнях реализации.