Садовый лабиринт — запутанные ходы ландшафтного дизайна. Мастерим необычные игры из подручных материалов

По традиции, еще со времен Древних Египта и Греции, под лабиринтом понимают участок местности с дорожками, тропинками, которые создают замысловатый рисунок и при этом ведут к центральной части. Изгородь из растений, высаженных в подобной форме, стала появляться в средневековых садах к середине XV в. Наверняка все любители Джерома К. Джерома помнят, как его герои блуждали по лабиринту (кстати, немаленькому – длина аллей ок. 500 м), находящемуся в Хемпптон-корте. Интересно, что хоть он был создан аж в 1690 году, но пройти по следам веселых персонажей из «Трое в лодке, не считая собаки» можно и сегодня.

Не чужда изгородь в подобной форме и русским садам, в усадьбах Архангельское, Кусково, Петергофе аллеи из аккуратно подстриженных кустов формировали четкий рисунок. Со временем композиции из живой изгороди усложнялись, создавая запутанные конструкции. Переменчивая мода на какое-то время забыла о лабиринтах, но в наши дни они снова стали объектом интереса ландшафтных дизайнеров.

Лабиринт у себя на участке

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

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

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

Растения, формирующие изгородь, определяют размеры композиции, можно создать детский мини-вариант диаметром до 2 метров, а можно и с поперечников в 10-20 м, из которых далеко не сразу найдешь выход.

Растения для сада-лабиринта

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

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

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

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

Лабиринтные формы

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

Выбор места для композиции

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

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

Садовый лабиринт из живой изгороди

В ландшафтном дизайне различают несколько типов лабиринта по основному «строительному материалу». Живая изгородь до 3 метров высотой – идеальный материал. Но помните, что внешняя красота такого лабиринта сопряжена с необходимостью уделять изрядно сил и времени поддержанию деревьев в надлежащем виде, в том числе стрижке, обрезанию веток. Конечно, под устройство этого варианта требуется довольно большая площадь, но если уж вы можете себе такое позволить, то получите чудесное место для прогулок, а ваши дети – для игр.

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

Цветочный лабиринт

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

Хорошие варианты для оформления – львиный зев, роза бордюрная, кустовая петуния.

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

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

Каменный лабиринт

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

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

Фантазийная композиция

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

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

Каменный лабиринт в саду (видео)

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

Прогулка по лабиринту будет особенно приятна, если за поворотом путника будет ждать красивая скамья, изящная клумба или оригинальная скульптура.

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

Идя по жизни, мы понятия не имеем, где окажемся завтра.
Мы стремимся к цели, но не знаем, как ее достичь.
Плутаем, рискуя оказаться в тупике.
Ломаем голову: какую дорогу выбрать?
Символ нашей жизни — лабиринт.

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

Kлассический трехкружный лабиринт

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

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

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

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

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

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

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

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

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

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

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

Классический трехкружный лабиринт (левосторонний)

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

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

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

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

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

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

Шаги 5-7. Четвертая, пятая и шестая дуги.

Шаги 8-9. Седьмая и восьмая дуги.

И вот, что получается в результате:

Классический семикружный лабиринт (левосторонний)

Если, начиная с первой дуги, вести дуги не направо, а налево, то лабиринт получится правосторонним.

Классический семикружный лабиринт (правосторонний)

А вот вариант сквозного семикружного лабиринта:

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

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

Второй: Прототип построения одинаков, в данном варианте просто сделаны два «загиба» для обеспечения сквозного прохода. Не уверен точно, где-то встречал упоминание о том, что лабиринт такой формы называется «лабиринтом святой Варвары».
Лабиринт другой формы (и тоже сквозной) можно построить, наложив друг на друга со смещением два критских лабиринта (из 2 трехкружных выходит 1 семикружный).

Первый : Прототип построения может быть и «одинаков», только есть одна, пусть на первый взгляд маленькая, но всё-таки разница – в классическом лабиринте так строится стенка, а в обсуждаемом лабиринте – дорожка. Не уверен, что это не в коей мере не меняет сути…
А вот то, что некоторые из лабиринтов состоят из двух (и более) вложенных друг в друга более простых лабиринтов – действительно очень интересный факт. Похоже древние строители лабиринтов об этом свойстве лабиринтов не только хорошо знали и, более того, активно пользовались (вот в каких целях – это вопрос!). Примеров тому можно привести много, но, чтобы далеко не ходить, достаточно, для начала, обратиться к картинке «Классический правосторонний одиннадцатикружный лабиринт на острове Готланд, Швеция.» в статье «Как построить одиннадцатикружный лабиринт» этого журнала. Там в условном центре лабиринта есть камушек, вынь который и лабиринт превратится в безтупиковый или «распадётся» на 2-а один-в-другом (это как посмотреть). А вставь камушек на место и снова получим лабиринт классического/критского типа.

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

Одиннадцатикружный лабиринт.

Для построения одиннадцатикружного классического лабиринта к прототипу семикружного лабиринта добавляется еще четыре «уголка».

«Зерно» одиннадцатикружного лабиринта

Способ рисования лабиринта – тот же самый. Начните с вершины креста, и на этот раз ведите линию вверх и налево (против часовой стрелки) к вершине ближайшего «уголка» (в верхней левосторонней четверти креста). Затем оторвите карандаш и перейдите к вершине внутреннего, расположенного ближе к кресту «уголка» в верхней правой четверти креста. Ведите дугу над первой дугой к вершине второго «уголка» в верхней левой четверти. И так далее…

Классический правосторонний одиннадцатикружный лабиринт на острове Готланд, Швеция.

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

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

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

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

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

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

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

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

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

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

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

Необходимое время: примерно 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, готовый лабиринт вероятнее всего будет иметь изолированную область.
Это условие включено в алгоритм в порядке исключения, на практике при нормальной работе алгоритма и правильных исходных данных, оно не выполняется никогда.

Реализация

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

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

 0.    < - Начальная матрица.

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.