Разработка программы генерации лабиринтов и бот-программы для обхода лабиринтов

ФЕДЕРАЛЬНОЕ  ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Факультет информатики, математики и компьютерных наук

Программа подготовки бакалавров по направлению

09.03.04- "Программная инженерия"

Жихарев Евгений Сергеевич

КУРСОВАЯ РАБОТА

Разработка программы генерации лабиринтов и бот-программы для обхода лабиринтов

Научный руководитель

Доцент

С.П. Скулкин

Нижний Новгород, 2017

Оглавление

Введение…………………………………………………………………………...3

Теоретическая часть……………………………………...……………………….4

Практическая часть……………………………………………………………….6

Заключение………………………………………………………………………...7

Литература……..………………………………………………………………….8

Приложение 1…………………………………………………………………….9

Введение

Лабири́нт - структура, которая состоит из большого количества запутанных путей, которые могут привести к выходу или в тупик. Лабиринты могут быть различного вида:

• Двухмерные
• Трёхмерные
• Прямоугольные
• Круглые
• Без пересечений путей
• С пересечениями путей

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

Цель работы: Разработка программы генерации лабиринта и прохода этого лабиринта.

Задачи:

1. Изучение алгоритмов генерации лабиринта.
2. Выбор оптимального алгоритма для генерации лабиринта.
3. Сгенерировать лабиринт.
4. Найти выход в данном лабиринте.

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

Теоретическая часть

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

Алгоритм Эллера:

1. Присваиваем ячейкам в первой строке своё множество (номер ячейки).
2. Ячейкам, которые не принадлежат ни одному множеству, присваиваем номер ячейки.
3. Создаём границы справа случайно:

1. Не добавили границу, тогда объединяем множества в которых находится данная ячейка и ячейка справа.
2. А если данная ячейка и ячейка справа относятся к одному множеству, то обязательно создаём границу между ними.

1. Создаём границы снизу, если есть две или более ячеек из одного множества (случайно определяем создаём границу или нет и где создаём, при этом хотя бы одна ячейка из множества обязательно должна остаться без границы снизу).
2. Решаем, завершаем лабиринт или продолжаем создавать дальше:

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

Инструкция для запуска: