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

Функция fill_screen отрисовывает на экране карту местности. Код функции

в соответствии с листингом 3.

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

def fill_screen(surface, col, row, tile_width, tile_height, grid, color):

for r in range(row): for c in range(col):

pg.draw.rect(surface, pg.Color(color[grid[r][c]]), (c * tile_width, r * tile_height, tile_width, tile_height))

Функция draw_circle рисует кружок для шага маршрута оптимального пути. Код функции в соответствии с листингом 4.

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

def draw_circle(surface ,x, y, color, TILE_HEIGHT, TILE_WIDTH): pg.draw.circle(surface, pg.Color(color), (x * TILE_WIDTH +

TILE_WIDTH // 2, y * TILE_HEIGHT + TILE_HEIGHT // 2), (TILE_WIDTH if TILE_WIDTH < TILE_HEIGHT else TILE_HEIGHT) // 4)

Функция get_click_mouse_pos определяет позицию мышки на экране и,

если произошел клик в районе карты местности возвращает координаты по х и у для тайла находящегося под курсором. Код функции в соответствии с листингом 5.

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

def get_click_mouse_pos(TILE_WIDTH, TILE_HEIGHT, HEIGHT, surface): x, y = pg.mouse.get_pos()

if y >= HEIGHT - 50: return False

grid_x, grid_y = x // TILE_WIDTH, y // TILE_HEIGHT draw_circle(surface, grid_x, grid_y, 'red', TILE_HEIGHT,

TILE_WIDTH)

click = pg.mouse.get_pressed()

return (grid_x, grid_y) if click[0] else False

11

Функция text_on_screen выводит заданный текст в необходимой точке на экране. Используется для вывода сообщения о загрузке карты местности и информационного сообщения об оптимальном маршруте. Код функции в соответствии с листингом 6.

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

def text_on_screen(screen, font, font_size, text, color, width, height):

myfont = pg.font.SysFont(font, font_size) textsurface = myfont.render(str(text), False, color) screen.blit(textsurface,(width, height)) pg.display.flip()

Функция dijkstra реализует алгоритм поиска кратчайшего пути в графе код представлен листинге 8. Алгоритм получает на вход начальную, конечную точки маршрута и граф карты местности. Начинается с создания переменных для очереди queue и добавления в нее начальной точки маршрута, для записи стоимости посещения точек на пути словарь cost_visited, для списка точек оптимального пути словарь visited. Затем начинается цикл, в котором сначала мы берем одно значение из кучи queue проверяем не является ли она точной назначения, если является цикл прерывается. Дальше получаем из графа все возможные варианты перехода из текущей точки в соседние и проходимся по ним в цикле. В этом цикле мы получаем для каждого возможного перехода вычисляем общее время пути при переходе в данное состояние. Если данные переход оказывается выгоднее остальных мы записываем эту точку в путь и обновляем цену, которая вычисляется суммой текущей цены пути и значения эвристической функции heuristic_manhattan, так продолжаем пока не пройдем все соседние клетки. Затем выходим на внешний цикл и процесс повторяется пока мы не дойдем до точки назначения. Как только мы достигли точки назначения мы возвращаем словарь точек маршрута visited.

12

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

def dijkstra(start, goal, graph): queue = []

hp.heappush(queue, (0, start)) cost_visited = {start: 0} visited = {start: None}

while queue:

cur_node = hp.heappop(queue)[1] if cur_node == goal:

break

neighbours = graph[cur_node] for neighbour in neighbours:

neigh_cost, neigh_node = neighbour

new_cost = cost_visited[cur_node] + neigh_cost

if neigh_node not in cost_visited or new_cost < cost_visited[neigh_node]:

priority = new_cost + heuristic_manhattan(neigh_node, goal)

hp.heappush(queue, (priority, neigh_node)) cost_visited[neigh_node] = new_cost visited[neigh_node] = cur_node

return visited

Функция heuristic_manhattan высчитывает манхэттенское расстояние между точкой назначения и текущей точкой маршрута переданные ей из функции dijkstra. Код функции в соответствии с листингом 9.

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

def heuristic_manhattan(a, b):

return abs(a[0] - b[0]) + abs(a[1] - b[1])

Функция wfc основная коллапса волновой функции код в соответствии с листингом А.4 приложения А из нее происходит управление всей генерацией карты местности на вход ей приходит пример карты местности и размеры карты,

которую необходимо сгенерировать. Начинается с создания необходимых

13

переменных input_size (кортеж высоты и ширины примера), output_size (кортеж высоты и ширины выходной карты), N = 2 (размер выделяемых паттернов), patterns список паттернов, weights (словарь наблюдений паттерна в примере

{паттерн: кол-во в примере}). Когда все переменные созданы вызывается функция parse_patterns в ней из примера выделяются все паттерны подсчитывается их количество в weights и уникальные значения записываются patterns. Затем подсчитывается количество всех паттернов из weights. Паттерны записываются в специальные объекты класса Pattern который содержит все точки паттерна. Определяется вероятность появления каждого из паттернов в примере и записывается в probability. Создаем список directions всех возможных направлений, в которых паттерны могут стыковаться. Затем записываем все объекты Pattern в объекты Index со всеми значениями directions для каждого

Pattern. Дальше мы записываем для каждого объекта Index все возможные паттерны, которые стыкуются с текущем в каждом из направлений directions с

помощью функции rule_generator. Затем инициализируем карту местности coefficients записывая в каждую клетку все паттерны, потому что до начала генерации каждая клетка имеет максимальную непременность и может принять любое значение из возможных. Теперь можно приступить непосредственно к коллапсированию карты местности coefficients (определению единственного значения для каждой ецейки). Запускаем цикл, который будет повторятся пока каждая клетка карты местности не примет единственное значение, условие проверяется функцией is_fully_collapsed или если 5 раз не получится сгенерировать карту. Первое с чего начинается цикл это определение позиции с наименьшей энтропией (точки с наименьшим количеством возможных паттернов), ее координаты определяет и возвращает в переменную min_entropy_pos функция observe. Затем в функции propagate случайным образом выбирается значение для min_entropy_pos и с учетом этого значения переопределяются возможные петтерны для соседних клеток в coefficients. Затем идет проверка если функция propagate возвращает None, что означает что в какой-то клетке условия соседства с уже определенными клетками не позволяет

14

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

Далее цикл повторяется. Когда карта местности получена она приводится в виду списка как в примере с помощью функции final_pixels_map и возвращается из функции wfc.

Класс Pattern содержит пиксели паттерна. Код класса в соответствии с листингом 10.

Листинг 10 – Код класса «Pattern»

class Pattern:

def __init__(self, pixels):

self.pixels = pixels

def __len__(self):

return 1

15

Класс Index хранит объекты Pattern и по каждому направлению, в котором может стыковаться паттерн с другими список паттернов, которые можно присоединить к нему с данной стороны. Также в классе есть функция add_rule

добавляющая паттерн в список возможных на присоединение в определенном направлении, и функция check_possibility которая проверяет есть ли переданный паттерн в списке возможных на присоединение. Код класса в соответствии с листингом 11.

Листинг 11 – Код класса «Index»

class Index:

def __init__(self, patterns: List[Pattern], directions): self.data = {}

for pattern in patterns: self.data[pattern] = {} for d in directions:

self.data[pattern][d] = []

def add_rule(self, pattern: Pattern, relative_position: tuple, next_pattern: Pattern):

self.data[pattern][relative_position].append(next_pattern)

def check_possibility(self, pattern: Pattern, check_pattern: Pattern, relative_pos: tuple):

if not pattern: return None if isinstance(pattern, list):

pattern = pattern[0]

return check_pattern in self.data[pattern][relative_pos]

16

Функция parse_patterns проходит циклом по всему примеру карты местности и выделяет уникальные паттерны со всеми возможными их поворотами (для поворота паттерна применяется функция get_all_rotations)

сохраняет их patterns, а также подсчитывает и сохраняет количество паттернов в weights. Код функции в соответствии с листингом 12.

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

def parse_patterns(input_size, pixels, weights, patterns, N): for y in range(input_size[0]-(N-1)): # row

for x in range(input_size[1]-(N-1)): # column pattern = []

for k in pixels[y:y+N]:

pattern.append([int(i) for i in k[x:x+N]]) for rotation in get_all_rotations(pattern):

if rotation not in weights: weights[rotation] = 1 patterns.append(rotation)

else:

weights[rotation] += 1

17

Функция get_all_rotations поворачивает матрицу паттерна на 90, 180, 270

градусов соответственно и возвращает эти значения кортежем. Код функции в соответствии с листингом 13.

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

def get_all_rotations(pixelMatrix):

pixelMatrix_rotated_90 = [[pixelMatrix[j][i] for j in range(len(pixelMatrix))] for i in range(len(pixelMatrix[0])-1,-1,- 1)]

pixelMatrix_rotated_180 = [[pixelMatrix_rotated_90[j][i] for j in range(len(pixelMatrix_rotated_90))] for i in range(len(pixelMatrix_rotated_90[0])-1,-1,-1)]

pixelMatrix_rotated_270 = [[pixelMatrix_rotated_180[j][i] for j in range(len(pixelMatrix_rotated_180))] for i in range(len(pixelMatrix_rotated_180[0])-1,-1,-1)]

return tuple(tuple(row) for row in pixelMatrix), \ tuple(tuple(row) for row in pixelMatrix_rotated_90), \ tuple(tuple(row) for row in pixelMatrix_rotated_180),

\

tuple(tuple(row) for row in pixelMatrix_rotated_270)

18

Функция rule_generator проходится массивам для каждого паттерна по каждому направлению и проверяет с какими паттернами он может состыковаться и записывает эти значения в объект Index каждого паттерна. Для этого в массиве нижнего уровня с помощью функции get_offset_tiles возвращаются стыкуемые стороны проверяемых паттернов, если они равны паттерн записывается в возможные. Код функции в соответствии с листингом 14.

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

def rule_generator(patterns, directions, index): for pattern in patterns:

for d in directions:

for pattern_next in patterns:

# here's checking all offsets

overlap = get_offset_tiles(pattern_next, d) og_dir = tuple([d[0]*-1, d[1]*-1]) part_of_og_pattern = get_offset_tiles(pattern,

og_dir)

if (overlap) == (part_of_og_pattern): index.add_rule(pattern, d, pattern_next)

19

Функция get_offset_tiles возвращает элементы стороны паттерна указанной в offset для проверки функции rule_generator. Код функции в соответствии с листингом 15.

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

def get_offset_tiles(pattern: Pattern, offset: tuple):

if offset == (0, 0):

return pattern.pixels

if offset == (-1, -1):

return tuple([pattern.pixels[1][1]])

if offset == (0, -1):

return tuple(pattern.pixels[1][:])

if offset == (1, -1):

return tuple([pattern.pixels[1][0]])

if offset == (-1, 0):
return	tuple([pattern.pixels[0][1],
pattern.pixels[1][1]])
if offset == (1, 0):
return	tuple([pattern.pixels[0][0],

pattern.pixels[1][0]])

if offset == (-1, 1):

return tuple([pattern.pixels[0][1]]) if offset == (0, 1):

return tuple(pattern.pixels[0][:]) if offset == (1, 1):

return tuple([pattern.pixels[0][0]])

20