КУРСАЧ / ТП КР Пояснительная записка
.pdf
Функция initialize_wave_function возвращает массив размером size каждый элемент которого заполнен списком всех возможных паттернов. Код функции в соответствии с листингом 16.
Листинг 16 – Код функции «initialize_wave_function»
def initialize_wave_function(size, patterns): coefficients = []
for col in range(size[0]): row = []
for r in range(size[1]): row.append(patterns) coefficients.append(row)
return coefficients
Функция is_fully_collapsed проверяет всели элементы массива coefficients
имеют только одно значение. Код функции в соответствии с листингом 17.
Листинг 17 – Код функции «is_fully_collapsed»
def is_fully_collapsed(coefficients):
for col in coefficients:
for entry in col:
if(len(entry)>1):
return False
return True
21
Функция observe определяет координаты клетки карты с наименьшей энтропией. Зазывает в coefficients по указынным координатам один случайный паттерн из доступных для нее. Затем возвращает координаты данной клетки. Код функции в соответствии с листингом 18.
Листинг 18 – Код функции «observe»
def observe(probability, coefficients):
min_entropy_pos = get_min_entropy_pos(coefficients, probability)
if min_entropy_pos == None: print("All tiles have 0 entropy") return
semi_random_pattern = random.choice(get_possible_patterns_at_position(min_entropy_pos, coefficients))
coefficients[min_entropy_pos[0]][min_entropy_pos[1]] = semi_random_pattern
return min_entropy_po
22
Функция get_min_entropy_pos проходит по массиву coefficients вычисляет для каждого значения энтропию функцией get_shannon_entropy, определяет у кого она наименьшая и возвращает его координаты. Код функции в соответствии с листингом 19.
Листинг 19 – Код функции «get_min_entropy_pos»
def get_min_entropy_pos(coefficients, probability): minEntropy = None
minEntropyPos = None
for x, col in enumerate(coefficients): for y, row in enumerate(col):
entropy = get_shannon_entropy((x, y), coefficients,
probability)
if entropy == 0: continue
if minEntropy is None or entropy < minEntropy: minEntropy = entropy
minEntropyPos = (x, y) return minEntropyPos
Функция get_min_entropy_pos высчитывает и возвращает энтропию Шеннона и добавляет к ней шума для более случайного результат генерации. Код функции в соответствии с листингом 20.
Листинг 20 – Код функции «get_min_entropy_pos»
def get_shannon_entropy(position, coefficients, probability): x, y = position
entropy = 0
if len(coefficients[x][y]) == 1: return 0
for pattern in coefficients[x][y]:
entropy += probability[pattern] * math.log(probability[pattern], 2)
entropy *= -1
entropy -= random.uniform(0, 0.1) return entropy
23
Функция propagate проходит циклом по всем соседям сколлапсированной клетки и обновляет списки возможных паттернов для них. На каждой итерации цикла получает текущие возможные паттерны для каждого соседа с помощью функции get_possible_patterns_at_position, а затем проверяет с помощью функции check_possibility класса Index каждый из паттернов на валидность при условии сколлапсировавшей ячейки по соседству. Код функции в соответствии с листингом А.5 приложения А.
Функция get_possible_patterns_at_position возвращает все значения паттернов из coefficients по указанному адресу. Код функции в соответствии с листингом 21.
Листинг 1 – Фрагмент функции «get_possible_patterns_at_position»
def get_possible_patterns_at_position(position, coefficients):
x, y = position
possible_patterns = coefficients[x][y] return possible_patterns
Функция final_pixels_map создает карту местности final_pixels из элементов паттернов по индексу [0][0], оставшихся в списке coefficients после его коллапсирования и возвращает его. Код функции в соответствии с листингом 22.
Листинг 22 – Код функции «final_pixels_map»
def final_pixels_map(coefficients): final_pixels = []
for i in coefficients: row = []
for j in i:
if isinstance(j, list):
first_pixel = j[0].pixels[0][0] else:
first_pixel = j.pixels[0][0] row.append(first_pixel)
final_pixels.append(row) return final_pixels
24
Для реализации использовался Python версии 3.10.0.
25
3 Примеры работы приложения
Реализовали оконное приложение, в котором можно выбрать размер генерируемой карты местности и сгенерировать ее, а потом на ней находить оптимальные пути до нужных точек.
На рисунке 1 изображен интерфейс стартового меню, в котором можно выбрать размер карты для генерации генерация начинается после нажатия кнопки в нижней части окна, созданный с помощью PyQt.
Рисунок 1 – Интерфейс стартового меню На рисунке 2 изображен интерфейс окна с картой местности и поиском
оптимального пути, созданный с помощью Pygame. Карта местности отображается после генерации и затем на ней мышкой можно выбрать точку, до которой мы хотим построить маршрут. Информация о построенном маршруте отображается в нижней части экрана.
Рисунок 2 – Интерфейс экрана карты
26
В программе учтены все возможные крайние случаи, которые могут вызвать ошибку или привести к некорректному выводу данных. Пользователь может генерировать несколько карт местности за один сеанс работы программы.
Для этого необходимо закрыть окно карты местности и нажать кнопку начала генерации в стартовом меню, не закрыв окно карты не удастся сгенерировать новую карту так как во время работы окна карты кнопка генерации в окне меню не активна.
27
ЗАКЛЮЧЕНИЕ
В ходе выполнения данной курсовой работы были изучены алгоритмы процедурной генерации и поиска кратчайшего пути в графе, выбраны наиболее подходящие для решения поставленной задачи и применены в реализации оконного приложения с генерацией карты местности алгоритмом коллапса волновой функции и поиском кратчайшего пути с помощью алгоритма А*.
Программа написана на языке программирования Python и может быть запущена на любом компьютере, имеющем интерпретатор для установленной на нем операционной системы.
Удобный интерфейс позволяет легко ориентироваться в программе.
Таким образом, основная цель работы была достигнута и все задачи успешно выполнены.
При необходимости есть возможность расширить возможности разработанного приложения, а именно добавить в него возможность загружать в него свои примеры карт местности для тестирования на различных наборах паттернов.
Данное программное обеспечение наглядно демонстрирует возможности прикладных алгоритмов писка кратчайшего пути и процедурной генерации, в
данной курсовой работе затронута лишь малая часть этих обширных тем.
В целом можно сделать вывод о том, что программное средство эффективно, выполняет все требования, которые выдвигались к нему и все удалось реализовать.
28
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1 Habr: Доступное объяснение алгоритма коллапса волновой функции,
URL: https://habr.com/ru/post/461323/ (дата обращения 21.10.2021)
2 Habr: Введение в алгоритм A*, URL: https://habr.com/ru/post/331192/ (дата обращения 21.11.2021)
3 python.org: Официальный сайт python, URL: https://www.python.org/ (дата обращения 28.11.2021)
4 doc.qt.io: Документация по PyQt, URL: https://doc.qt.io/qtforpython/
(дата обращения 05.12.2021)
5 pygame.org: Документация по Pygame, URL: https://www.pygame.org/docs/
(дата обращения 10.12.2021)
29
ПРИЛОЖЕНИЕ А
Код программы
Листинг А.1 – Код «Стартового меню»
from typing import ForwardRef, MappingView from PyQt5 import QtCore, QtGui, QtWidgets from draw import draw_best_way
from threading import *
class Ui_MainWindow(object):
def setupUi(self, MainWindow):
MainWindow.setObjectName("Сгенерируй и найди")
MainWindow.resize(600, 350)
sizePolicy = QtWidgets.QSizePolicy(QtWidgets.QSizePolicy.Fixed, QtWidgets.QSizePolicy.Fixed)
sizePolicy.setHorizontalStretch(0)
sizePolicy.setVerticalStretch(0)
sizePolicy.setHeightForWidth(MainWindow.sizePolicy().hasHeightFor Width())
MainWindow.setSizePolicy(sizePolicy)
MainWindow.setAutoFillBackground(False)
MainWindow.setDocumentMode(False)
MainWindow.setDockNestingEnabled(False) self.centralwidget = QtWidgets.QWidget(MainWindow) self.centralwidget.setObjectName("centralwidget") self.verticalLayout_2 =
QtWidgets.QVBoxLayout(self.centralwidget) self.verticalLayout_2.setObjectName("verticalLayout_2") self.verticalLayout = QtWidgets.QVBoxLayout() self.verticalLayout.setObjectName("verticalLayout") self.label_3 = QtWidgets.QLabel(self.centralwidget) font = QtGui.QFont()
30