Научно-исследовательская работа по математике "виды лабиринтов и выходы из них". Алгоритмы генерации лабиринтов

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

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

Также существуют уже готовые решения для генерации лабиринтов: , который используется в 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» - вы можете поэкспериментировать с интерактивной демкой, устанавливая различные значения для генерации: количество итераций обновления, граничные значения для жизни/смерти клетки и т.п. - и увидеть результат. Там же рассказывается о подводных камнях реализации.

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

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

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

В русскоязычном интернете очень мало информации по алгоритмам генерации лабиринтов, что и стало причиной для написания этой статьи.
Примеры кода на языке Си, а также полный исходный код проекта на 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.

Ребята, мы вкладываем душу в сайт. Cпасибо за то,
что открываете эту красоту. Спасибо за вдохновение и мурашки.
Присоединяйтесь к нам в Facebook и ВКонтакте

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

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

1.

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

2.

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

3.

Благополучно миновав огненные преграды предыдущего зала, вы попадаете в небольшую комнату с похожими каменными плитами на полу. Вам необходимо пересечь комнату из левого верхнего угла в правый нижний. При этом обязательно нужно пройти через все клетки, не вставая на одну и ту же дважды. Передвигаться можно по горизонтали, вертикали и диагонали. Ваши шаги должны соответствовать последовательности: 1-2-3-4-5-6-1-2-3- и т. д. В данном случае плиты - это кнопки с кодом к следующей двери. Наступая на плиту, вы нажимаете на соответствующую цифру. Если ошибетесь, сверху мгновенно упадет тяжелая решетка и вы окажетесь в тюрьме без возможности выбраться. Берегитесь и тщательно обдумайте каждый шаг.

4.

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

5.

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

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

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

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

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

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

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

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

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

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

Мунгунова Намсалма

Научно-исследовательская работа по математике "Виды лабиринтов и выходы из них"

Скачать:

Предварительный просмотр:

Курумканское районное управление образования МО «Курумканский район»

МУНИЦИПАЛЬНОЕ БЮДЖЕТНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

«УЛЮНХАНСКАЯ СРЕДНЯЯ ОБЩЕОБРАЗОВАТЕЛЬНАЯ ШКОЛА»

671642, Республика Бурятия, с. Улюнхан, ул. Новая, 1., тел.: 91-5-74, 91-5-24

Научно-практическая конференция

«Шаг в будущее»

Тема работы:

«Виды лабиринтов и выходы из них»

Секция «Математика»

Выполнила: Мунгунова Намсалма,

ученица 8 класса

Руководитель: Аюшеева О.Ю.,

Учитель математики

2016 год

Введение.

§1 История лабиринта.

§2 Виды лабиринтов.

§3 Способы выхода из лабиринтов.

3.1Теорема Тремо.

3.2 Правило правой и левой руки

§4 Задачи про лабиринты.

Заключение.

Список используемой литературы.

Приложение.

Введение

В лабиринте человек не теряет себя,

В лабиринте человек находит себя,

В лабиринте человек встречается не с Минотавром,

В лабиринте человек встречается сам с собой.

Герман Керн «Лабиринты Мира»

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

И я решил узнать о лабиринтах больше и посвятил этому свою работу.

Актуальность:

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

ЦЕЛЬ: Изучить историю возникновения лабиринтов и методы решения задач о лабиринтах.

Задачи:

1. Провести отбор материала, связанного с лабиринтами.

2. Выявление различных методов нахождения выходов из лабиринтов и применение их к решению задач.

3. Нахождение связи лабиринтов с нашей жизнью.

4. Создать буклет с задачами о лабиринтах.

Методы и приемы : анализ тематических источников информации, наблюдения, пробы, эксперименты.

Предмет исследования : алгоритмы решения задачи о лабиринтах.

Объекты исследования : лабиринты разных типов.

Гипотеза: чем чаще распутываем лабиринт, тем быстрее подойдем к решению трудных задач.

§1. История лабиринта.

Многие из нас встречали в жизни интересное понятие - лабиринт. Но не все знают - что такое «лабиринты» и откуда они появились. Хотя с лабиринтами встречаемся довольно часто: в рисунках ребенка, чертежах конструкторов, схемах работы городского транспорта можно заметить тот или иной вариант лабиринта. Так что же это такое «лабиринт»?
Слово «лабиринт» произошло от греческого и означает «ходы в подземельях». Действительно, существует очень много природных подземных пещер с таким огромным количеством перекрещивающихся коридоров, закоулков и тупиков, что нетрудно в них заблудиться и потеряться. Воспроизведение спиралей и лабиринтов относится к самым древним творениям человеческих рук, это первые картины, рисующие не события – сцены охоты или битвы, – а идеи. Они появились одновременно в различных частях света, на больших расстояниях друг от друга, так что их возникновение нельзя объяснить взаимовлиянием культур. Изображения лабиринтов, относящиеся к одному времени, были обнаружены в Северной Америке, Индии и на Суматре, а также на территории Европы.
Нет на земле более загадочных построек, чем лабиринты. Они манят, запутывают, пугают и даже могут довести до отчаяния тех, кто в них оказывается. С лабиринтами связано немало мистических поверий. Взять хотя бы такое: войдя в лабиринт, человек попадает в “мир иной”. Существует много историй о лабиринтах, из которых невозможно выбраться. И даже если выход был близок, какая-то неведомая сила возвращала жертву к исходной точке..

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

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

Артур Эванс, английский археолог с 1900 года вел раскопки в Крите почти 30 лет и раскопал не город, а дворец, равный по площади целому городу. Это был знаменитый Кносский лабиринт, который представлял собой сооружение общей площадью 22 тыс. квадратных метров, имевшее как минимум 5-6 надземных уровней-этажей, соединенных проходами и лестницами, и целый ряд подземных склепов. Критский лабиринт оказался не выдумкой древних, а настоящим чудом архитектуры, в котором было что-то непонятное разуму.
Так, попав в критские парки и дворцы, человек даже не подозревал, что вошел в лабиринт, гранитный исполин в это время начинает вытягивать жизненные силы из жертвы. Древние знали, что проводить длительное время в лабиринте нельзя, иначе можно тяжело заболеть.

В городе Помпеи, погибшем в результате извержения Везувия в 79 году н. э., тоже находилось два лабиринта. Один из них, “Дом с лабиринтом”, известен удивительным мозаичным полом, на котором изображена борьба Тесея с Минотавром.

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

Были свои лабиринты в Индии – в храме Хапебт в Майсуре, а в Китае лабиринты строились при входе в каждый город и даже дом. Жители Поднебесной верили, что лабиринты спасают от алых духов. Демоны могут летать только по прямой, и если построить вход з дом в виде лабиринтов, можно уберечь свое жилище от злых духов.

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

В России тоже есть свои лабиринты. Так, на Соловецких островах насчитывается около 30 лабиринтов и более 1000 насыпей-курганов и разнообразных символических узоров из камня. До сих пор эти сооружения остаются одними из самых загадочных мест на Земле. На них нет никакой растительности, кроме мхов и ягодников. Высаженные растения и деревья погибают, а животные избегают этих мест.

Европе особенное распространение получили лабиринты из дерна: дерновый холмик в центре и ведущие к нему дорожки в виде неглубоких канавок. Обычно эти лабиринты делались в форме круга диаметром от 9 до 18 метров. Но были и квадратные, и многоугольные дерновые лабиринты, а также те, что имели поистине огромные размеры.

С конца ХV века лабиринты начали появляться в храмах, на плитках церковного пола. Такие напольные изображения лабиринтов стали неотъемлемой частью наказания, когда раскаивающийся грешник должен был пройти на коленях по всем изгибам и поворотам лабиринта. Такая епитимья налагалась на тех, кто не мог совершить паломничество к святым местам, и называлась “дорога в Иерусалим”.

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

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

§2. Виды лабиринтов.

Существует несколько видов лабиринтов, вот некоторые из них.

Церковные лабиринты Европы.

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

Головоломный лабиринт.

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

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

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

Л абиринт как геометрическая сеть.

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

§3. Способы выхода из лабиринта.

3.1 Теорема Тремо.

Универсальный алгоритм прохождения любых лабиринтов был описан только через столетие в книге французского математика Э. Люка "Recreations matematiques", изданной в 1882 году. Интересно, что Люка при описании алгоритма указал на первенство другого французского математика М. Тремо. Таким образом, алгоритм стал известен как алгоритм Люка-Тремо.

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

1. Если подошли к перекрестку, на котором ни разу небыли, то дальше идем по любому коридору (рис. 1), если же попали в тупик – идем обратно (рис. 2).

2. Если подошли к перекрестку, где уже побывали, и подошли к нему по такой дороге, по которой мы идем в первый раз, то немедленно отправляемся обратно (рис. 3).

3. Если подошли к перекрестку таким путем, по которому уже дважды шли, то далее, если есть коридоры, по которым ещё ни разу не ходили, идем по любому из них (рис. 4).

Если же таких коридоров нет, то идем по любому пройденному один раз (рис. 5).

3.2. Правила правой и левой руки.

Одним из самых простых правил для прохождения лабиринта является правило "одной руки": двигаясь по лабиринту, надо все время касаться правой или левой рукой его стены. Этот алгоритм, вероятно, был известен еще древним грекам. Придется пройти долгий путь, заходя во все тупики, но в итоге цель будет достигнута. Хотя у этого правила и есть один недостаток, но о нем мы поговорим позже.

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

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

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

§4. Задачи про лабиринты.

Задача №1. Тропинки в садах.

В саду Александра Ивановича тропинки проложены, как это показано на рис. 4, а у Бориса Борисовича - как показано на рис. 5. Кто из них может обойти все тропинки, проходя по каждой всего один раз?

Ответ: Александр Иванович.

Задача № 2. Среди георгин .

Садовник имел квадратную клумбу 4*4 метра, на которой он вырастил 16 кустов георгин. Расстояние между кустами было 1 метр. Пока кусты еще не расцвели, цветовод обходил все кусты, идя по кратчайшему пути, но когда чудесные цветы распустились, садовник обходил их по самому длинному пути. К каждому цветку он подходил всего один раз. Как выглядел самый короткий путь от куста к кусту, а как самый длинный?

Решение: 1. Самый кратчайший путь: 1;2;3;4;8;7;6;5;9;10;11;12;16;15;14;13 (рис.6)

Самый длинный путь: 5;9;13;10;7;4;3;2;1;6;11;16;12;8;15;14 (рис.7)

Задача № 3. Задача садовника.

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

Решение: Садовник посадил 4 акации и 6 лип (рис.8).

Задача № 4. Клад.

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

Решение: Путь к кладу и обратно показан на рисунке 10.

Заключение

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

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

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