КУРСАЧ / ТП КР Пояснительная записка

2

ВВЕДЕНИЕ

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

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

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

Хорошим примером такого рода генерации без участия человека подземелий в приключенческих играх является игра The Legend of Zelda в

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

Так же данный подход может быть использован в любой сфере, где необходимо случайными образом по заданным правилам создавать уникальные сочетания заданных объектов. Поэтому процедурная генерация так же может применятся при создании текстур и 3D-моделей растений, которые в природе имеют определенную одинаковую структуру в приделах вида, но нет двух одинаковых особей.

В данном курсовом проекте разработаем оконное приложение, в котором реализуем один из алгоритмов процедурной генерации и на сгенерированной

3

карте будем искать кратчайший путь между двумя точками.

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

4

1 Постановка задачи

1.1 Описание предметной области

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

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

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

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

возвращает кратчайший маршрут и выводит его на экран поверх карты местности.

1.2 Выбор методов решения задачи

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

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

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

полученном массиве определяется точка, в которой возможно установить наименьшее количество паттернов ее называют точкой с наименьшей энтропией

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

5

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

Затем, когда карта сгенерирована выведена на экран и пользователь выбрал точку на карте необходимо найти кратчайший путь с помощью алгоритма поиска А*. Данный алгоритм нам подходит лучше всего, потому что мы знаем начальную и конечную точки нашего маршрута и нам не нужно находить оптимальный путь от одной из вершин графа до всех остальных.

A* пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный. Как и все информированные алгоритмы поиска, он просматривает сначала те маршруты, которые «кажутся» ведущими к цели. От жадного алгоритма, который тоже является алгоритмом поиска по первому лучшему совпадению, его отличает то, что при выборе вершины он учитывает, помимо прочего, весь пройденный до неё путь.

Поиск происходит в следующей последовательности в начале работы просматриваются узлы, смежные с начальным; выбирается тот из них, который имеет минимальное значение, после чего этот узел раскрывается. На каждом этапе алгоритм оперирует с множеством путей из начальной точки до всех ещё не раскрытых вершин графа — множеством частных решений, — которое размещается в очереди с приоритетом. Приоритет пути определяется по значению суммы стоимости пути и значению эвристической функции в заданной точке. В качестве эвристической функции в нашем случае берем Манхэттенское расстояние оно подходит в данном случае, потому что наш путь не может идти наискосок. Алгоритм продолжает свою работу до тех пор, пока значение целевой вершины не окажется меньшим, чем любое значение в очереди, либо пока всё дерево не будет просмотрено. Из множества решений выбирается решение с

6

наименьшей стоимостью.

1.3 Язык программирования Python

Для реализации данного программного кода применим высокоуровневый язык программирования Python общего назначения с динамической строгой типизацией и автоматическим управлением памятью, ориентированный на повышение производительности разработчика, читаемости кода и его качества,

а также на обеспечение переносимости написанных на нём программ. Язык является полностью объектно-ориентированным, всё является объектами.

Реализацию интерфейса будем производить с помощью библиотек для

Python предназначенных для этого.

Для разработки начального меню, в котором можно будет задать размер генерируемой карты, применим библиотеку графического фреймворка Qt для языка программирования Python – PyQt. В Qt Designer – кроссплатформенной свободной среде для разработки графических интерфейсов программ,

использующих библиотеку Qt, разработаем внешний вид окна и при помощи пакета pyqt5-tools транслируем код сгенерированный Qt Designer в код Python.

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

1.4 Требования к разрабатываемому приложению (структуре,

функциональности)

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

Необходимо написать функцию-обработчик события нажатия на кнопку.

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

Для этого нужно реализовать функцию с циклом в котором будет

7

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

Также необходимо реализовать функцию коллапса волновой функции,

которая по переданному в нее примеру создаст карту местности заданного ей размер.

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

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

8

2 Описание разработанной программы

2.1 Описание используемых библиотек

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

Также воспользовались модулем heapq при реализации алгоритма очереди приоритетов во время поиска кратчайшего пути алгоритмом А*.

2.2 Описание созданных функций

Интерфейс стартового меню состоит из нескольких пояснительных надписей к окнам ввода и кнопки начала генерации карты. Обработка нажатия на кнопку в функции start_functions, она вызывает основную функцию отрисовки второго окна с картой местности draw_best_way. Код интерфейса стартового меню представлен в листинге A.1 приложения A.

Основная функция draw_best_way отвечает за отрисовку карты и оптимального маршрута код функции представлен в листинге A.2 приложения А. Начинается с задания необходимых переменных для отображения окна карты: WIDTH (ширина окна), HEIGHT (высот экрана), colors (словарь цветов для каждого типа тайла); для генерации карты местности: grid_exampl (пример карты местности на основе которого будет сгенерирована карта); для поиска оптимального пути start (статическая начальная точка маршрута) , goal (точка назначения выбираемая пользователем), visited (словарь шагов оптимального пути). Затем инициализируется окно и таймер для отсчета времени обновления кадров. Затем начинается бесконечный цикл, который заканчивается по условию, когда пользователь нажмет на кнопку закрытия окна. Цикле начинается с проверки сгенерирована ли карта местности, если нет, то на экран выводится надпись, сообщающая о загрузки, и вызывается функция коллапса волновой функции wfc с необходимыми для генерации карты параметрами.

Когда функция возвращает результат он сохраняется в grid и отправляется в функцию build_graph для создания на его основе графа местности. Затем идет проверка на возникновение события закрытия окна и обновление окна. Цикл повторяется в этот раз карта создана и происходит отрисовка карты местности и

9

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

Функция build_graph формирует граф по карте местности и возвращает его.

Код функции в соответствии с листингом 1.

Листинг 1 – Код функции «Отрисовка карты местности»

def build_graph(grid): graph = {}

for y, row in enumerate(grid): for x, col in enumerate(row):

graph[(x, y)] = graph.get((x, y), []) + get_neighbours(x, y, grid)

return graph

Функция get_neighbours получает на вход координаты, текущей клетка карты и карту местности. Проверяет не выходит ли точка за пределы массива карты. Если нет, то вычисляет координаты и получает цену перехода в клетку и объединяет эти значения в кортеж. Из кортежей формируется массив и возвращается из функции. Код функции в соответствии с листингом 2.

Листинг 2 – Код функции «get_neighbours»

def get_neighbours(x, y, grid):

check_neighbour = lambda x, y: True if 0 <= x < len(grid[0])

10