Лабиринт. Генерация и поиск кратчайшего пути

Лабиринт. Генерация и поиск кратчайшего пути

Чувашский государственный университет имени И. Н. Ульянова.

Кафедра вычислительной техники.

Тема: «Лабиринт. Генерация и поиск кратчайшего пути»

Работу выполнил:

студент группы

ИВТ-42-05

Тарасов Е.Э.

Руководитель:

Васильев Ю.Г.

Чебоксары 2006 г.

1. Задание

Лабиринт.

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

2. Функциональное назначение

Программа Labirint выполняет ряд следующих операций:

генерация лабиринта;

определение пользователем точки входа в лабиринт и точки выхода из него;

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

3. Описание логической структуры

.1 Выбор способа решения задачи

Задача может быть решена несколькими способами:

1)      организовать лабиринт с использованием записи:

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

Прежде всего, создадим заготовку - лабиринт со всеми возможными стенами. Далее последуем алгоритму:

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

ПОКА locations > 1

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

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

КОНЕЦ ЦИКЛА

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

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

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

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

Вторая итерация алгоритма выглядит так:

найти в лабиринте локации, помеченные двойками;

для каждой из четырех соседних с ней локаций проверить те же условия;

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

2)      задать лабиринт массивом:

Если на пересечении i-ой строки и j-ого столбца стена, то элемент массива с индексами i и j имеет значение 0, в противном случае 1.

Для генерации лабиринта был создан начальный массив a, состоящий из целых чисел:

0

0

… 0

0

0

… 0

Далее генератором случайных чисел выбирается определенное число нечетных локаций в каждом четном ряду (кроме последнего) и им присваивается значение 1, в каждом нечетном ряду (кроме первого и последнего) определенному числу четных локаций присваивается значение 0. Далее пользователем вводятся координаты точки входа в лабиринт и точки выхода из него. Элементу массива, принятому за точку входа присваивается значение 3. Если соседние с ним локации пусты (то есть имеют значение 1), то им присваивается значение 3+1=4. Далее в Лабиринте ищутся все элементы, имеющие значение 4 и с ними производится та же процедура.

Выглядеть это будет примерно так:

0000000

Переменной d присвоим значение элемента массива, принятого за точку выхода, после нескольких циклов вышеуказанных операций, а затем присвоим ему значение 2. Далее проверяются все соседние с ним элементы. Если их значение равно d-1, то таким элементам присваивается значение 2, а значение переменной d уменьшаем на 1. Проделываем эту операцию со всеми элементами массива, равными 2, если это возможно.

Затем, для вывода результата на экран вводится массив символов b, такой же размерности как массив a. Если элемента a[i,j]=0, то соответствующему элементу массива b присваивается символ ‘0’, если a[i,j]=2, то b[i,j]:=’*’ если a[i,j] не равно 0 или 2, то b[i,j]:=’ ‘. Полученный массив выводится на экран.

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

3.3 Структура данных

3.4 Описание процедур и функций (Все процедуры используют локальные переменные (описаны в п.3.3.))

Процедура GenLab

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

Процедура OutLab

Процедура выводит лабиринт на экран.

Процедура Result

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

Процедура GetEvent

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

Процедура Event

Обрабатывает любое событие.

Процедура far Handler

Обработчик событий мышки.

Процедура CheckMouse

Определяет, есть мышка или нет.

Процедура Init

Инициализация экрана.

4. Вызов и загрузка

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

5. Выходные данные

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

По мере работы с программой в этих окнах отображается соответствующая информация.

6. Выводы по работе

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

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

7. Приложение к пояснительной записке

.1 Назначение программы

Программа Labirint выполняет ряд следующих операций:

генерация лабиринта

определение пользователем точки входа в лабиринт и точки выхода из него

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

7.2 Требования к запуску

Для запуска программы запустите файл Labirint.exe

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

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

программа labirint пользователь локальный

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