Нарисовать этот лабиринт очень просто. Возьмите лист бумаги. Нарисуйте крест и поставьте точки в центре каждой из четырех четвертей креста. Это – прототип лабиринта.
Шаг 1. Прототип трехкружного лабиринта
Теперь нарисуйте, начиная с вершины креста, дугу – либо вверх и налево к точке в верхней левой четверти, либо вверх и направо к точке в верхней правой четверти. В данном примере – вверх и направо.
Шаг 2. Первая дуга
Затем от точки в верхней левой четверти креста проведите дугу к правому концу горизонтальной линии.
Шаг 3. Вторая дуга
А от левого конца этой горизонтальной линии – к точке в нижней правой четверти креста.
Шаг 4. Третья дуга
И наконец, от точки в нижней левой четверти креста – к нижнему концу вертикальной линии.
Шаг 5. Четвертая дуга
Этот лабиринт называется левосторонним, так как первый поворот при входе в него – налево. Если первую дугу провести вверх и налево, получится правосторонний лабиринт.
Пожалуйста, возьмите чистый лист бумаги и карандаш и нарисуйте три классических трехкружных лабиринта.
Очень важно сделать лабиринт своими руками, а не только умозрительно. В том, чтобы самостоятельно сделать лабиринт, есть нечто особенное. Это происходит после пятого или шестого раза. Действительно, когда известен способ, несложно понять рассудком, как чертится лабиринт, но после полудюжины рисунков руки перестают знать и начинают ведать, как это делается. Не пренебрегайте этими упражнениями, ибо они помогут понять этот магический инструмент таким способом, который никогда не откроется, если только читать или размышлять о лабиринтах. Классические лабиринты предполагают другой способ постижения.
Вам понадобится
- Фанера, инструменты для работы с деревом, материал для обшивки, звуковая составляющая, провода, лампы для подсветки, игрушки и аксессуары.
Инструкция
Для начала необходимо определиться с тем, каким именно будет ваш . В городской довольно-таки трудно его сделать, если только у вас не двухъярусная квартира. Лучше всего для создания лабиринт а подойдет загородный дом или дача. Подумайте о том, где вы хотите разместить будущий лабиринт . Это может быть подвальное помещение вашего дома. Это придаст вашему лабиринт у больше таинственности и загадочности. Также можно сделать небольшой лабиринт , в котором будут играть ваши дети. Разместив его под второго этажа, вы сможете сверху наблюдать за тем, как ваш ребенок пытается найти единственно правильный путь.
Допустим, что вы выбрали местом для будущего лабиринт а подвальное помещение. теперь самое время подумать о чертеже. Это одна из самых главных частей постройки лабиринт а. Лабиринты бывают разного типа и разной сложности. Лучше всего в доме лабиринт прямоугольной или квадратной формы. Такой лабиринт прост в постройке. Разработайте подробный лабиринт а на бумаге. Можно взять уже готовую схему из какого-либо источника, а можно использовать собственную фантазию. Помните, что у лабиринт а должен быть только один правильный выход. Также старайтесь не делать слишком сложных путей. Все-таки это небольшое развлечение для ваших гостей, а не пытка. После изготовления эскиза сделайте точный чертеж с размерами. Ширина должна быть достаточной, чтобы в нем спокойно перемещался взрослый человек, но и не очень широкой, чтобы создавал впечатление замкнутого пространства.
Теперь, когда готов подробный чертеж, можно приступать непосредственно к подготовке помещения. Необходимо полностью очистить его от лишних предметов. Также исследуйте пол, стены и на наличие неровностей. Их необходимо удалить. Теперь нужно закупить материал, из которого вы будете делать коридоры будущего лабиринт а. Лучше всего использовать нетолстые листы и фанеры. Они легки в обработке и не занимают много места. Материал нужно взять с запасом на тот случай, если вы испортите часть заготовок.
Из купленного материала сделайте заготовки лабиринт а. Их будет очень много, поэтому следует по мере изготовления собирать их, начиная от дальней стены. Крепить между собой детали рекомендуется шурупами. Следите за тем, чтобы снизу детали плотно прилегали к полу и не оставалось маленьких щелей, через которые может проникать свет. Когда все заготовки будут установлены, нужно продумать освещение. Здесь все зависит только от вашей фантазии. Лучше всего установить небольшие лампы в разных частях лабиринт а, но делать это нужно равномерно, чтобы не выделить правильного пути выхода.
После установки освещения нужно позаботиться о внешнем украшении. Можно покрасить стенки лабиринт а в какой-то цвет или имитировать поверхность дубовых досок. Но лучше всего обшить стены лабиринт а тканью, например, материалом, похожим на бархат. Также задумайтесь об аксессуарах. Установите стилизованные игрушки с таинственной тускловатой подсветкой. Красиво будут смотреться летучие мыши со светящимися глазами. Также можно повесить портреты магов или колдунов, слегка подсветив их. Будет очень реалистично, если вы добавите ко всем еще и звуковое сопровождение. Для этого установите несколько
Если у вас в доме живут хомяки, то вы, скорее всего, уже купили или только думаете купить для них игрушки. Ведь они, как малые дети, любят резвиться и играться. В пустой клетке ваши хомячки будут скучать, а значит и вы не получите всего удовольствия от наблюдения за ними. Однако сумма денег, потраченных на , может вас неприятно удивить.
Поэтому, если вы переживаете, что ваши питомцы будут скучать и при этом не хотите раскошеливаться, предлагаем вам идею – сделать лабиринт для хомяка своими руками!
В начале статьи вы видели картину конечного результата. Конечно, он выглядит не очень приглядно, но этот туннельный лабиринт состоит из пластиковых бутылок, а значит, обойдется вам бесплатно! А в наше время хочется хоть на чем-то сэкономить.
Обратите внимание, такой же лабиринт-туннель можно сделать своими руками и для крыс, хорьков, морских свинок и других грызунов.
Однако эту игрушку нельзя оставлять в клетке хомяков надолго. Бутылки сделаны из пластика, а ваши питомцы любят все грызть. В результате могут появиться острые края в местах, где поработали хомячки – это может поранить их, а также съеденный пластик может вызвать у них расстройство.
Лабиринт для хомяка, сделанный своими руками из пластиковых бутылок, можно использовать во время игр с вашими питомцами в течение небольших промежутков времени.
Представленное руководство поможет вам шаг за шагом сделать свой собственный туннельный лабиринт у себя дома. Причем форма лабиринта и его сложность зависит только от вашего желания и фантазии.
Внимание! При работе вы будете использовать острые инструменты, поэтому соблюдайте крайнюю осторожность во время изготовления лабиринта для хомяка.
Что понадобится для того, чтобы сделать лабиринт для хомяка своими руками:
Необходимое время: примерно 30 минут.
- Тщательно промойте все бутылки – вы же не хотите, чтобы туннели для ваших домашних питомцев были вонючими и липкими!
- Удалите этикетки и крышки с бутылок – они просто не нужны и к тому же мешают!
- Свой первый проект можете начать с 4-х бутылок, но количество можно легко увеличить на любом этапе – это только вопрос хранения готового лабиринта – чем больше, тем сложнее его куда-либо пристроить. Здесь есть также место для творчества, ведь пластиковые бутылки бывают разных цветов и форм. Это поможет вам создать лабиринт не похожий на другие.
- Осторожно
с помощью канцелярского ножа удалите верхнюю и нижнюю часть каждой бутылки. Желательно сделать это на достаточно твердой поверхности, иначе вы рискуете продырявить ножом что-либо ценное. Также имейте в виду, что обрезанные края, скорее всего, будут зубчатые и острые. Это мы устраним на следующем шагу.
- Возьмите изоленту. Изоляционная лента идеально подходит для этого проекта, так как она хорошо облегает пластик, а также хорошо обклеивает края бутылок. Скрыть неровные края очень важно – вы же не хотите, чтобы ваши питомцы порезали свои маленькие лапки! Сделайте короткие полоски липкой ленты и приклейте их половину на обратную сторону ободка бутылки. Затем сделайте разрезы в ленте примерно на расстоянии 1 см друг от друга, и заверните на другую сторону. Это позволит вам получить более скругленные углы во время наклейки изоленты. Хоть этот процесс и занимает довольно много времени, тем не менее, он очень важен. После того как вы обклеите края всех бутылок, переходите к следующему шагу.
- При подготовке «Т» соединений двух бутылок вам необходимо в одной из них вырезать круглое отверстие. С помощью канцелярского ножа сделайте надрез в виде «+» в месте будущего отверстия. Отогните края пластика, стараясь не дергать слишком сильно, так как пластик может порваться дальше по надрезу и тогда бутылку придется заменить! Затем вставьте в получившееся маленькое отверстие ножницы и вырежьте с их помощью круг диаметром второй бутылки. Используя 1 см полоски изоленты, обклейте края получившегося отверстия.
- Возьмите бутылку, которая будет присоединяться к первой и сожмите её край, сделав его плоским. Вырежьте по диагональной линии верхний и нижний угол, как показано на рисунке. Это сделает край изогнутым, что позволит одной бутылке удобно «сидеть» на другой. Не волнуйтесь, если вы слишком много отрезали. Обклеивая края изолентой, вы можете просто прикрепить излишне отрезанный кусочек на свое место.
- Удерживая обе трубки в месте соединения, убедитесь, что трубка, сделанная на 7 шаге, плотно прилегает к трубке, сделанной на 6 шаге. Удерживая их в нужном положении, используйте один длинный кусок ленты, чтобы прикрепить бутылки между собой. Для этого приклейте изоленту на одну сторону прикрепляемой бутылки и, обведя вокруг другой бутылки, приклейте конец ленты с другой стороны. Затем оставшиеся щели в месте соединения заклейте кусками изоленты. Более подробно данный процесс можете посмотреть на фото.
- Теперь ваши две трубки должны выглядеть как на следующем рисунке. Повторите все шаги, начиная с 6го, для оставшихся двух труб. После завершения вы будете иметь два набора двух труб.
- Последнее, что нужно сделать, это соединить вместе с помощью изоленты ваши два набора двух труб.
Итак, как видите, сделать лабиринт для хомяка своими руками не сложно. Немного вашего времени, несколько подручных средств и вуаля – изделие готово к работе! Ваши хомячки будут счастливы исследовать новые туннельные лабиринты, а вы получите массу позитивных эмоций наблюдая за ними. Напоследок, посмотрите видео с забавным хомяком в главной роли, который пытается найти выход из лего-лабиринта.
Тайна лабиринтов. Для чего они были созданы и как брать из них Силу Жикаренцев Владимир Васильевич
Классический лабиринт, как его строить и как с ним работать
Классический лабиринт (он же Критский) выглядит как на рис. 14. Заметьте, что в нём две группы окружностей: внешняя и внутренняя - в каждой по четыре штуки. Сначала человек движется по внешним окружностям, потом переходит на внутренние и, в конце концов, приходит в центр. Внешние и внутренние окружности это внешнее и внутреннее в формуле Христа.
Рис. 14 - Классический критский лабиринт
Как строить лабиринт . Порядок построения любого лабиринта показан на рис. 15. Лабиринты отличаются друг от друга по количеству углов (ниже вы поймёте о чём идёт речь) и формой: в основе одних лежит вила, в основе других - крест. Существуют также лабиринты, в основе которых лежит форма человека с его пятью членами (см. ). Отдельно стоят лабиринты, в которых 30 углов, а крест в них присутствует в неявном виде, о них мы подробно поговорим позже.
Рис. 15 - Принцип построения лабиринтов
Заготовки для построения лабиринтов и сами лабиринты показаны на рис. 16–21. Сложность лабиринтов зависит от того, сколько углов вы к нему добавляете. Пусть вас не смущает то, что вход у критского лабиринта, который построил я, зеркальный по отношению к классическому, просто до него я построил несколько лабиринтов, у которых вход был слева, поэтому здесь я решил сделать вход справа. С другой стороны, в мире существует немало лабиринтов именно с таким расположением входа.
Рис. 16а - основа для построения троичного лабиринта-вилы
Рис. 16б - лабиринт-тройка, построенный мной
Рис. 16в - он же зимой
Рис. 17а - основа для построения шестиричного либиринта-вилы
Рис. 17б - шестеричный лабиринт-вила, который построил я
Рис. 17в - шестеричный лабиринт, вид сверху
Рис. 17 г - он же зимой
Рис. 18а - основа для построения четверичного лабиринта-креста
Рис. 18б - четверичный лабиринт-крест, который построил я
Рис. 18в - он же зимой
Рис. 19а - основа для построения восьмеричного лабиринта-креста - классический критский лабиринт
Рис. 19б - Критский лабиринт, построенный мной
Рис. 19в - Критский лабиринт, построенный мной
Рис. 19 г - он же зимой
Рис. 20 - основа для построения двенадцатеричного лабиринта-креста
Рис. 21 - основа для построения десятеричного лабиринта-человек
Смысл лабиринтов. У каждого из них свой, мы разберём только два лабиринта, над смыслом остальных подумайте сами.
Лабиринт-вила. Если вы посмотрите на лабиринт на рис. 16а-в, то увидите перед собой вилу, концы которой загнуты. Тупик, куда заходит идущий по лабиринту человек, это и есть место, где живёт Минотавр - наше я. Вила состоит из двух концов, один из которых загнут, указывая на замкнутое на себя я, а другой конец - другая противоположность - окружает со всех сторон это я. Например, мужчину окружают со всех сторон женщины - женское начало, а женщину - мужчины. Заходя в лабиринт, это можно увидеть и прочувствовать, как вас всегда окружает то, что вы отрицаете.
В общем, смысл данного лабиринта заключается в следующем. Наше замкнутое на себя я со всех сторон окружает отрицаемая нами противоположность (чем больше отрицаний, тем больше таких окружностей), а саму вилу противопложностей окружает со всех сторон целостный мир, а за этим миром мир с его противоположностями лежит ещё нечто, пустота - вот что можно почувствовать и пережить в данном лабиринте.
Лабиринт-крест. Посмотрите на рис. 18а-в. Перпендикулярные линии креста указывают на два начала - мужское и женское, состоящие внутри себя из противоположностей. Загнутый конец, где живёт Минотавр, это позиция ума или мысль, взгляд на вещи, в которых замкнулся человек. Например, кто-то замкнулся на демократии, кто-то на деньгах, на женщинах, на религии, на интернете, а противоположная позиция отрицается, конечно же. Но она, как можно увидеть из рисунка, никуда не девается, она окружает я со всех сторон - это другой конец линии, который огибает весь лабиринт. Например, моралиста со всех сторон окружает разврат, материалиста - верующие, и т. п. Причём не только окружают, а достают, раздражают. О том, как вас достаёт то, что вы отрицаете, можно подумать, придя в центр лабиринта к Минотавру.
Далее. Посмотрите, как противоположности горизонтальной линии, которая представляет другое начало, меняются местами: левый конец горизонтальной линии уходит направо, а правый - налево, окружая замкнутое на себя я. Что это означает? То, что в голове видение перевернулось - это действует Гордеев узел (см. ). Он переворачивает всё, что вы видите вокруг и представляя белое чёрным, черное - белым, добрые намерения - как злые, злые - как добрые, и т. д. Так в голове поселются путанка и ложь, иллюзия. Эту иллюзию, этот обман тоже можно поискать, когда вы придёте к Минотавру.
Всё, что вы видите вокруг, это не так, всё наоборот. Отсюда известная поговорка: Выслушай женщину и поступи наоборот.
Как работать с лабиринтом. Если вы мысленно пойдёте по лабиринту, то заметите, что попеременно переходите с одной стороны лабиринта на другую - это идёт соединение левого и правого - мужского и женского начал - по сути, здесь соединяются левая и правая половины тела, при этом полушария мозга начинают работать синхронно.
Внешние и внутренние окружности это внешнее и внутреннее в знаменитом выражении Христа: Когда вы соедините внешнее и внутреннее, левое и правое, верх и низ, вы соединитесь с Богом. А где в лабиринте верх и низ? Это мы обсудим ниже.
Как ходить по лабиринту? Это ясно сказано в истории о падении Иерихона. Иисус Навин семь раз обошёл город Иерихон с Ковчегом Завета, трубя в трубы юбилейные, и стены города пали. Иначе говоря, если вы, думая с любовью о волнующей вас проблеме, пройдёте по лабиринту по семи окружностям в центр, она решится, и вы окажетесь в раю в данном месте своего существа.
Переход с одной стороны лабиринта на другую это и есть те самые трубы ювилейные - вилы, в которые «трубит» идущий по лабиринту человек. Посмотрите на рис. 22, видите, в профиль труба в точности изображает вилу?
Лабиринт соединяет разорванный ум в целое… С помощью чего единый ум разрывается? Его рвут сети ума. Поговорим о них (более подробно о сетях ума смотрите учебник «Строение и Законы Ума» ).
Из книги Тайны древних цивилизаций. Энциклопедия самых интригующих загадок прошлого автора Джеймс Питер Из книги Сам себе волшебник автора Гурангов ВадимЛАБИРИНТ После 17 августа на нашу семью обрушились напасти. Дочь Светлана работала в банке, тот рухнул, и она осталась без работы. Предприятие, на котором работаю я, несло большие убытки. У мужа тоже дела шли неважно. Как назло, Константин вдребезги разбил свою новую машину,
Из книги Духовный кризис [Когда преобразование личности становится кризисом] автора Гроф СтаниславЛи Санелла КУНДАЛИНИ: КЛАССИЧЕСКИЙ И КЛИНИЧЕСКИЙ ПОДХОДЫ [Кундалини] создает вселенную из Своего собственного бытия, и именно Она Сама становится этой вселенной. Она становится всеми элементами мироздания и входит во все разнообразные формы, которые мы видим вокруг. Она
Из книги Тайны древних цивилизаций автора Джеймс ПитерКлассический период истории майя Достигнув определенной стабильности, цивилизация майя устремилась к новым высотам изощренности и экстравагантности. Археологи, изучавшие жизнь древних майя, находились под глубоким впечатлением от их достижений и восхищались ими.
Из книги Пророчества майя: 2012 автора Попов АлександрКлассический период За очень короткий по историческим меркам срок, примерно на протяжении шести веков, с IV по X век н. э., народы майя, в особенности те, что жили в центральной области, достигли невиданных интеллектуальных и художественных высот. Причем в это время подобных
Из книги Магия бессмертия. Главный барьер автора Сервест Бурислав Из книги Нумерология успеха. Запусти Колесо Фортуны автора Коровина Елена АнатольевнаСтроить или разрушать Если вам необходимо приумножение, построение, восстановление чего-то, представьте это нечто и повторяйте: «сорок сороков». Помните, как величалось в старой Москве невиданное множество церквей – именно так, магически: сорок сороков.Между прочим,
Из книги Заговоры сибирской целительницы. Выпуск 06 автора Степанова Наталья ИвановнаМожно ли строить дом на месте сгоревшего Из письма:
Из книги Мудры: как влиять на других и самому защититься от чужого влияния автора Таль МаксМудры, дающие власть и помогающие строить карьеру развивать свое дело Мудра, помогающая стать харизматичным лидером (особенно хорошо работает во время публичных выступлений) Кому понадобится мудра Качества лидера могут быть необходимы в самых разных ситуациях. Эта
Из книги Ванга. Как управлять другими людьми автора Пономарева Наталья ВладимировнаКак строить отношения с мужчинами
Из книги Тайна лабиринтов. Для чего они были созданы и как брать из них Силу автора Жикаренцев Владимир ВасильевичКак строить отношения с женщинами
Из книги Сокровенный смысл жизни. Том 2 автора Ливрага Хорхе АнхельКак на самом деле действует классический лабиринт - Спас в силах Это открытие пришло неожиданно, после того, как одна женщина, пройдя критский лабиринт (см. рис. 14 и 19а, б, в), спросила: «А где же тут квадрат, тут должен быть квадрат?» Логика была простая: раз квадрат проводит
Из книги Тайные учения. Алхимия, гипноз и магия автора Гордеев Сергей Васильевич Из книги Маленькие Будды…а так же их родители! Буддийские секреты воспитания детей автора Клэридж Сиэл15.17. КЛАССИЧЕСКИЙ ГИПНОЗ Душевный дискомфорт не всегда считается болезнью. Однако именно он вызывает множество функциональных расстройств, страдая от которых человек вынужден обращаться к врачам. После обследования обычно выясняется, что проблема со здоровьем
Из книги автораРаздел 5 Сочувствие как искусство строить отношения Как мать, которая защищала бы свое дитя даже ценой жизни, Питай в сердце бесконечную любовь ко всем живущим. Пусть твои добрые мысли пронизывают весь мир. Наполни ум сочувствием. Будда Шакьямуни Три главы этого
Из книги автораКак строить прочные отношения Вся методика воспитания детей с раскрытием природы Будды посвящена установлению глубоких и теплых взаимоотношений, в которых могли бы развиваться и родители, и дети. Идеи и взгляды буддизма составляют канву этих методов, а практические
В этой статье речь пойдет о самом простом в реализации алгоритме генерации «идеального» лабиринта и его применении для поиска пути.
Мы рассмотрим алгоритм, основанный на бэктрекинге, позволяющий создавать лабиринты без циклов, имеющие единственный путь между двумя точками. Алгоритм не самый быстрый, довольно требователен к ресурсам, по сравнению с алгоритмом Эйлера или Крускала, но очень прост в реализации и позволяет создавать ветвистые лабиринты с очень длинными тупиковыми ответвлениями.
Заинтересовавшихся - прошу под кат.
В русскоязычном интернете очень мало информации по алгоритмам генерации лабиринтов, что и стало причиной для написания этой статьи.
Примеры кода на языке Си, а также полный исходный код проекта на 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.
