Лабиринт. Генерация и поиск кратчайшего пути
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
Чувашский государственный университет имени И. Н. Ульянова.
Кафедра вычислительной техники.
Тема: Лабиринт. Генерация и поиск кратчайшего пути
Работу выполнил:
студент группы
ИВТ-42-05
Тарасов Е.Э.
Руководитель:
Васильев Ю.Г.
Чебоксары 2006 г.
1. Задание
Лабиринт.
Написать программу нахождения кратчайшего пути в лабиринте. Предусмотреть генерацию лабиринта и возможность выбора пользователем точки входа в лабиринт и точки выхода из него. В программе предусмотреть использование мыши и разбиение на модули.
2. Функциональное назначение
Программа Labirint выполняет ряд следующих операций:
генерация лабиринта;
определение пользователем точки входа в лабиринт и точки выхода из него;
нахождение кратчайшего пути от заданной пользователем точки входа в лабиринт до точки выхода и вывод пути на экран либо вывод на экран сообщения о том, что не существует пути между двумя выбранными пользователем локациями.
3. Описание логической структуры
.1 Выбор способа решения задачи
Задача может быть решена несколькими способами:
1)организовать лабиринт с использованием записи:
В каждой локации лабиринта нас интересует информация о стенах/проходах. В локации может существовать от одной до четырех стен (сверху, снизу, слева и справа). Если значение поля равно true, значит, соответствующая стена существует, иначе - нет.
Прежде всего, создадим заготовку - лабиринт со всеми возможными стенами. Далее последуем алгоритму:
:= количество локаций в лабиринте
ПОКА locations > 1
выбираем случайную стену в лабиринте
ЕСЛИ не существует пути между локациями, разделенными этой стеной, разбиваем стену := locations - 1
КОНЕЦ ЦИКЛА
Находить путь между точкой входа и выхода можно по алгоритму метода волновой трассировки: Стартовую локацию пометим единицей (вылили кисель). Теперь выполняем действия.
Найти в лабиринте локации, помеченные единицами для каждой из четырех соседних с ней локаций проверить два условия:
- помечена ли она нулем
- есть ли стена между двумя локациями (выбранной и соседней) если оба условия выполнены, помечаем соседнее локацию двойкой.
Вторая итерация алгоритма выглядит так:
найти в лабиринте локации, помеченные двойками;
для каждой из четырех соседних с ней локаций проверить те же условия;
если оба условия выполнены, помечаем соседнею локацию тройкой и так далее.
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]:= . Полученный массив выводится на экран.
Для решения данной задачи я выбрал второй способ, так как организация данных с помощью массива относительно проста и нет необходимости использовать более сложную структуру. Для выполнения задачи, а именно визуального представления сгенерированного лабиринта и пути от точки входа до точки выхода памяти хватает. Окно программы позволяет выводить лабиринты в приемлемом для пользователя виде с максимальным размером 2580 элементов. Памяти же хватает для того, чтобы задать массив размерностью 146146 символов, то есть, нет необходимости прибегать к более сложным структурам.
3.3 Структура данных
НаименованиетипНазначение переменнойДопустимые значенияChсимвольныйХранит код нажатой клавиши пользователем0..255whatцелыйРегистрирует действия пользователя/обрабатывает события0,1,2X YцелыйГрафические координаты точки по щелчку мыши0..640 0..480exцелыйОпределяет координаты входа или выхода0..1KeyцелыйОпределяет, перезапускать ли программу0,1existцелыйОпределяет наличие лабиринта0..1a[n][n]МассивХранит лабиринтN=1..15x_en, y_en /x_ex, y_exЦелыеКоординаты входа/выхода1..15
3.4 Описание процед