Разработка программы генерации лабиринтов и бот-программы для обхода лабиринтов
Автор: Ugin • Май 21, 2020 • Курсовая работа • 3,168 Слов (13 Страниц) • 415 Просмотры
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ
«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»
Факультет информатики, математики и компьютерных наук
Программа подготовки бакалавров по направлению
09.03.04- "Программная инженерия"
Жихарев Евгений Сергеевич
КУРСОВАЯ РАБОТА
Разработка программы генерации лабиринтов и бот-программы для обхода лабиринтов
Научный руководитель
Доцент
С.П. Скулкин
Нижний Новгород, 2017
Оглавление
Введение…………………………………………………………………………...3
Теоретическая часть……………………………………...……………………….4
Практическая часть……………………………………………………………….6
Заключение………………………………………………………………………...7
Литература……..………………………………………………………………….8
Приложение 1…………………………………………………………………….9
Введение
Лабири́нт - структура, которая состоит из большого количества запутанных путей, которые могут привести к выходу или в тупик. Лабиринты могут быть различного вида:
- Двухмерные
- Трёхмерные
- Прямоугольные
- Круглые
- Без пересечений путей
- С пересечениями путей
Так как в лабиринте много различных путей и они могут привести в тупик, то в лабиринте сложно найти выход-это и делает интересной задачу нахождения выхода в лабиринте.
Цель работы: Разработка программы генерации лабиринта и прохода этого лабиринта.
Задачи:
- Изучение алгоритмов генерации лабиринта.
- Выбор оптимального алгоритма для генерации лабиринта.
- Сгенерировать лабиринт.
- Найти выход в данном лабиринте.
Актуальность: Данная программа поможет в построении лабиринта, который в дальнейшем может использоваться в играх, которые в наше время набирают популярность. Но всё-таки актуальность этой программы не так велика, т.к. есть большое количество программ для генерации различных лабиринтов.
Теоретическая часть
Для генерации лабиринта я выбрал алгоритм Эллера, так как он быстро работает и использует память эффективно. Данный алгоритм генерирует лабиринт построчно и основан на деление всей строки на множества.
Алгоритм Эллера:
- Присваиваем ячейкам в первой строке своё множество (номер ячейки).
- Ячейкам, которые не принадлежат ни одному множеству, присваиваем номер ячейки.
- Создаём границы справа случайно:
- Не добавили границу, тогда объединяем множества в которых находится данная ячейка и ячейка справа.
- А если данная ячейка и ячейка справа относятся к одному множеству, то обязательно создаём границу между ними.
- Создаём границы снизу, если есть две или более ячеек из одного множества (случайно определяем создаём границу или нет и где создаём, при этом хотя бы одна ячейка из множества обязательно должна остаться без границы снизу).
- Решаем, завершаем лабиринт или продолжаем создавать дальше:
- Если продолжаем, то копируем предыдущую строку, при этом удаляем боковые границы, убираем из множеств ячейки с нижней границей и удаляем нижние границы и возвращаемся ко 2-му шагу.
- Если нужно завершить лабиринт, то копируем предыдущую строку и если данная ячейка и ячейка справа относятся к разным множествам, то удаляем боковую границу и объединяем множества.
Для нахождения выхода из лабиринта будем запоминать координаты перекрёстков и количество путей от него, идём по случайному пути и если это тупик и не выход, то возвращаемся к перекрёстку и так пока не найдём выход.
Инструмент разработки:
Microsoft Visual Studio 2013- продукт компании Microsoft, который позволяет разрабатывать приложения на множестве различных поддерживаемых языков программирования.
Практическая часть
Используемые заголовочные файлы:
- Stdio.h- отвечает за ввод/вывод информации.
- Conio.h- отвечает за консольный ввод/вывод информации.
- Locale.h- отвечает за региональные настройки интерфейса (страна, язык, часовой пояс и т.п.) (в данной программе нужен для использования функции getch() ).
- Stdlib.h- отвечает за выделение памяти, преобразования типов, контролирует процесс выполнения программы (в данной программе нужен для использования функции rand() ).
- String.h- отвечает за работу со строками.
- Time.h- отвечает за работу с датой и временем.
Используемые переменные:
- char l[50][50]- Двумерный массив символов, в котором хранится сам лабиринт.
- int h- высота лабиринта.
- int w- ширина лабиринта.
Инструкция для запуска:
...