Essays.club - Получите бесплатные рефераты, курсовые работы и научные статьи
Поиск

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

Автор:   •  Май 21, 2020  •  Курсовая работа  •  3,168 Слов (13 Страниц)  •  411 Просмотры

Страница 1 из 13

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

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

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

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

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

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

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- ширина лабиринта.

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

...

Скачать:   txt (14.2 Kb)   pdf (136 Kb)   docx (14.2 Kb)  
Продолжить читать еще 12 страниц(ы) »
Доступно только на Essays.club