Генерирование лабиринта и нахождение выхода из него

Размещено на http://www.allbest.ru/

Введение

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

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

В курсовой работе разработана программа, которая может сгенерировать лабиринт заданного размера, после этого может найти оптимальный путь разными алгоритмами прохождения. Программа выполнена с помощью языка программирования Borland Delphi 7. В качестве инструмента для поиска оптимального пути лабиринта использовались алгоритм волновой трассировки и рекурсивный обход. Для генерирования лабиринта так же можно использовать алгоритм Краскала и алгоритм Прима. Так же можно сохранить лабиринт и загрузить ранее сохраненный лабиринт.



1. Цели и задачи курсового проекта

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

Целью программы является:

Создание лабиринта

Нахождение оптимального пути в лабиринте

Возможность сохранить и загрузить лабиринт

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

Разработанная программа доступна всем и может использоваться в любой отрасли.

2. Постановка задачи

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

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

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

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

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

Вид интерфейса представлен на Рис. 2.1.

Рисунок 2.1 - Интерфейс генератора лабиринта

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

Что бы пройти лабиринт другим методом не обязательно создавать новый лабиринт, но от того каким методом его проходить результат всё равно не изменится так как в основном лишь один путь является самым коротким, а в большинстве случаев вообще существует лишь один путь. Единственная разница по которой вы определите каким методом был пройден лабиринт это цвет пути. Алгоритм рекурсивного обхода отображается красным(Рис. 2.2), а алгоритм волновой трассировки - синим(Рис. 2.3).



Рисунок 2.2 - отображение пути рекурсивным обходом

Рисунок 2.3 - отображение пути волновой трасировкой

3. Описание математической модели решения задачи

Рекурсивный обход

Главное достоинство этого метода это то что он простой и очень популярный.

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

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

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

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

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

Например, финишная локация полностью окружена сплошной стеной. Вот и весь алгоритм.

Используя этот алгоритм мы найдём выход из лабиринта но большая его часть не будет исследована.

Пример предоставлен на Рис. 3.1.

Рисунок 3.1 - Пример рекурсивного обхода

Алгоритм волновой трассировки

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

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

помечена ли она нулем

есть ли стена между двумя локациями (выбранной и соседней) если оба условия выполнены, помечаем соседнюю локацию двойкой

На примере алгоритма на Рис. 3.2 будет рассмотрено действие алгоритма.

Рисунок 3.2 - Лабиринт для прохождения методом волновой трассировки

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

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

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

Пример найденного пути этим методом в лабиринте предоставлен на Рис.3.3.

Рисунок 3.3 - Лабиринт пройденный алгоритмом волновой трассировки

Генерация лабиринтов

Алгоритм Прима

Создадим "заготовку" -- лабиринт, в котором все локации полностью окружены стенами (разумеется, далеко от стартовой точки в таком лабиринте не уйдешь). Сопоставим каждой локации переменную-атрибут (соответственно, у нас получится двумерный массив атрибутов), которая может принимать значения Inside (внутри), Outside (снаружи) и Border (на границе). Изначально атрибут каждой локации должен быть равен Outside. Выберем случайную локацию в лабиринте и присвоим ее атрибуту значение Inside. Присвоим также атрибутам соседних с ней локаций значение Border. Теперь надо действовать по алгоритму:

ПОКА атрибут хотя бы одной локации равен Border

выберем случайную локацию, атрибут которой равен Border, и присвоим ей атрибут Inside

изменим на Border атрибут всех соседних с текущей локаций, атрибут которых равен Outside

из всех соседей текущей локации, атрибут которых равен Inside, выберем случайную и разрушим стену между ней и текущей локацией

В последнем действии предполагается, что такие соседи (имеющие атрибут, равный Inside) у текущей локации имеются. Почему? А потому, что атрибут текущей локации изначально был равен Border -- это гарантирует выполнение условия. По той же причине между такими локациями (текущей, атрибут которой был равен Border и соседней -- с атрибутом Inside) всегда есть стена. Я понимаю, эти утверждения не так очевидны; на самом деле они вытекают из принципа работы алгоритма -- попробуйте сделать несколько шагов вручную, на бумаге, и вы убедитесь в их справедливости. Если какая-то клетка имеет атрибут Inside, это означает, что она принадлежит к "внутренней", уже построенной области лабиринта. Любые две Inside-локации косвенно связаны между собой (то есть существует маршрут между ними). Outside-локации никак не связаны с Inside-локациями -- их еще только предстоит обработать. Border-локации тоже находятся извне лабиринта, но каждая из них граничит хотя бы с одной Inside-локацией.

Пример создания лабиринта по алгоритму Прима на Рис. 3.4.

Рисунок 3.4 - Созданный лабиринт по алгоритму Прима



Алгоритм Краскала

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

locations := количество локаций в лабиринте

ПОКА locations > 1

выбираем случайную стену в лабиринте

ЕСЛИ не существует пути между локациями, разделенными этой стеной,

разбиваем стену

locations := locations - 1

Конец цикла

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

function IsConnected(x1, y1, x2, y2) : Boolean

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

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

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

1. Запоминать все ранее выбранные генератором случайных чисел значения. Если на очередной итерации выпало какое-то "старое" значение, просто запустить генератор еще раз (а если понадобится, то еще и еще раз).

Этот метод прекрасно работает, если вам надо, к примеру, выбрать десять неповторяющихся чисел из диапазона [1…10 000]. Вероятность того, что одно и то же число выпадет два раза, очень невелика, и нет беды, если пару раз генератор сработает два-три раза вхолостую. А вот в случае вроде русского лото его применять не стоит: когда почти все значения из диапазона исчерпаны, как раз-таки вероятность получить новое, не выбранное ранее число мала. Наш случай, к сожалению, куда ближе к варианту русского лото, поэтому перейдем ко второму методу.

2. Предположим, что в массиве A[1..N] находятся все значения, которые надо выбрать в случайном порядке. Создадим массив B[1..N] и заполним его произвольными случайными числами. Практически любой универсальный алгоритм сортировки массива основан на операции обмена элементов. Я имею в виду, что основой алгоритма всегда является операция поменять местами B[i] и B[j]

3. Теперь надо отсортировать массив B по возрастанию, меняя местами каждый раз элементы массива A при обмене элементов из B. Иными словами, вместо кода поменять местами B[i] и B[j] везде будет использоваться поменять местами B[i] и B[j] iiiaiyou ianoaie A[i] e A[j]

4. После работы алгоритма сортировки массив A окажется полностью перемешанным в случайном порядке. В качестве первого случайного элемента можно взять первый элемент массива A, в качестве второго -- второй и т. д. Вот и все. Давайте теперь немного уточним алгоритм Краскала с учетом сказанного: l

ocations := количество локаций в лабиринте { Width * Height } записываем все стены лабиринта в массив Walls перемешиваем массив Walls в случайном порядке

ЕСЛИ не существует пути между локациями, разделенными этой стеной

разбиваем стену

locations := locations - 1

Любую стену можно задать четырьмя числами: (x, y, dx, dy), то есть с помощью координат локации и смещений (я особо не останавливаюсь на этом, потому что мы не раз уже пользовались таким способом, например в функции CanGo() и процедуре BreakWall()). Таким образом, "массив стен" -- это массив таких четверок.

Пример создания лабиринта по алгоритму Краскала на Рис.2.5.

Рисунок 3.5 - Созданный лабиринт по алгоритму Краскала

4. Выбор операционной системы

Разработанная программа предназначена для работы с операционными системами семейства Windows. Этот выбор опирался на то что операционные системы данного семейства самые распространенные в мире. У этих операционных систем много возможностей и приятный интерфейс, так же выходят регулярные обновления который оптимизируют её и исправляют ошибки.

5. Системные требования

Процессор: 1ГГц;

Операционная система: Windows 95/98/ME/NT4/2000/XP/Vista/7/8/10;

Оперативная память 64 мб;

Язык программы: Русский;

Видео: VGA

700 кб свободного места на жестком диске.

6. Блок-схемы алгоритма

На Рис. 6.1 представлена блок-схема процедуры TForm1.BitBtn1Click.

Рисунок 6.1 - блок схема процедуры TForm1.BitBtn1Click



На Рис. 6.2 изображена блок схема для процедуры TForm1.BitBtn7Click.

Рисунок 6.2 - блок схема процедуры TForm1.BitBtn7Click

На Рис. 6.3 изображена блок схема для процедуры TForm1.BitBtn8Click.

Рисунок 6.3 - блок схема процедуры TForm1.BitBtn8Click

На Рис. 6.4 изображена блок схема для процедуры TForm1.BitBtn5Click.



Рисунок 6.4 - блок схема процедуры TForm1.BitBtn5Click

На Рис. 6.5 изображена блок схема для процедуры TForm1.Button1Click.

Рисунок 6.5 - блок схема процедуры TForm1.Button1Click

На Рис. 6.6 изображена блок схема для процедуры TForm1.BitBtn6Click.

Рисунок 6.6 - блок схема процедуры TForm1.BitBtn6Click

На Рис. 6.7 изображена блок схема для процедуры TForm1.BitBtn3Click

Рисунок 6.7 - блок схема процедуры TForm1.BitBtn3Click

На Рис. 6.8 изображена блок схема для процедуры TForm1.BitBtn2Click

Рисунок 6.8 - блок схема процедуры TForm1.BitBtn2Click

7. Контрольный пример

На Рис. 7.1 представлен сгенерированный лабиринт по алгоритму Прима.

Рисунок 7.1 - Сгенерированный лабиринт

На Рис. 7.2 представлен найденный путь по алгоритму волновой трассировки.

Рисунок 7.2 - Найденный путь в лабиринте

8. Анализ результатов

Результаты полученные путем выполнения программы в Borland Delphi 7 идентичны данным полученным вручную, разница лишь в скорости вычислений.

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

компьютерный алгоритм краскал лабиринт



Заключение

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

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



Список литературы

1. Тейксера С. и Пачеко К. "Delphi 5. Руководство разработчика, том 1. Основные методы и технологии программирования" Пер. с англ.- М.: "Вильямс".-2001.- 832 с.

2. Озеров В. Электронный учебник: "Советы по Delphi". Версия 1.0.8 от 2.5.2000.

3. Озеров В. Электронный учебник: "Советы по Delphi". Версия 1.1.7 от 1.12.1999.

4. Озеров В. Электронный учебник: "Советы по Delphi". Версия 1.4.6 от 1.4.2001.

5. Драхвелидзе П.Г., Марков Е.П.: "Программирование в Delphi 7". - СПб.: "БХВ-Петербург", 2003.-784 с.

6. Фленов М. "Библия для программиста в среде Delphi 7" //http//www.cydsoft.com/vr-online

Размещено на Allbest.ru

...