Материал: АиСД. Проектная работа

test_maze.py

print(solve_maze_n_functions[k], solve_results[k]) raise AttributeError

if is_perfect_mazes and k and solve_results[k - 1] != solve_results[k] \

or not is_perfect_mazes and len(solve_results[k - 1]) != len(solve_results[k]): print('Miscellaneous answers')

print(*[''.join('█' if col else ' ' for col in row) for row in maze], sep='\n') print((yFrom, xFrom), (yTo, xTo))

print(solve_maze_n_functions[k - 1], solve_results[k - 1]) print(solve_maze_n_functions[k], solve_results[k])

raise AttributeError

print('Time of execution of maze generation algorithms')

for time, n in sorted(zip(maze_time_functions, maze_n_functions)): print(n + ': ' + str(time))

print('\n' + 'Time of execution of algorithms to find the shortest paths in the mazes (briefly)') for time, sn in sorted(zip(solve_maze_time_functions, solve_maze_n_functions), key=lambda x:

sum(x[0])):

print(sn + ': ' + str(sum(time)))

print('\n' + 'Time of execution of algorithms to find the shortest paths in the mazes (in detail)') for time, sn in sorted(zip(solve_maze_time_functions, solve_maze_n_functions), key=lambda x:

sum(x[0])):

print('#' * 30 + '\n' + 'Function:', sn)

for n, t in sorted(zip(maze_n_functions, time), key=lambda x: x[1]): print(n + ': ' + str(t))

def main():

def get_input(string, begin, end): string += f" ({begin}-{end}):" input_result = input(string)

while not (input_result.isdecimal() and begin <= int(input_result) <= end): input_result = input(string)

return int(input_result)

print('=== Perfect algorithms ===')

n_tests = get_input('Enter the number of tests', 1, 100000)

min_length = get_input('Enter the minimum length of the maze (odd number)', 5, 100000) max_length = get_input('Enter the maximum length of the maze (odd number)', 5, 100000)

maze_functions = [aldous_broder, wilson, backtracking, binary_tree, division, eller, growing_tree, kruskal,

prim, modified_prim, sidewinder]

maze_n_functions = ['Aldous-Broder algorithm', 'Wilson\'s algorithm', 'Backtracking algorithm', 'Binary tree algorithm', 'Division algorithm', 'Eller\'s algorithm', 'Growing tree

algorithm',

'Kruskal\'s algorithm', 'Prim\'s algorithm', 'Prim\'s algorithm (modified)', 'Sidewinder algorithm']

solve_maze_functions = [bfs, dijkstra,

lambda mz, begin, end: a_star(mz, begin, end, Heuristic.octile), lambda mz, begin, end: a_star(mz, begin, end, Heuristic.manhattan), lambda mz, begin, end: a_star(mz, begin, end, Heuristic.chebyshev), lambda mz, begin, end: a_star(mz, begin, end, Heuristic.euclidean)]

solve_maze_n_functions = ['BFS algorithm', 'Dijkstra algorithm', 'A* algorithm (Octile heuristic)', 'A* algorithm (Manhattan heuristic)', 'A* algorithm (Chebyshev heuristic)', 'A* algorithm (Euclidean heuristic)']

test_algorithms(n_tests, min_length, max_length, maze_functions, maze_n_functions, solve_maze_functions,

solve_maze_n_functions, is_perfect_mazes=True)

print('\n', '=== Imperfect algorithms ===', sep='\n') n_tests = get_input('Enter the number of tests', 1, 100000)

min_length = get_input('Enter the minimum length of the maze (odd number)', 5, 100000) max_length = get_input('Enter the maximum length of the maze (odd number)', 5, 100000) maze_functions = [serpentine, small_rooms, spiral]

maze_n_functions = ['Serpentine algorithm', 'Small rooms algorithm', 'Spiral algorithm'] test_algorithms(n_tests, min_length, max_length, maze_functions, maze_n_functions,

solve_maze_functions,

solve_maze_n_functions, is_perfect_mazes=False)

input()

48

test_maze.py

if __name__ == '__main__': main()

Таблица 26. Файл с алгоритмами генерации идеальных лабиринтов

perfect_maze.py

#!/usr/bin/env python3

# -*- coding: utf-8 -*-

"""

Implementation of 2D perfect maze generation algorithms. Algorithms:

-Aldous-Broder algorithm (unbiased maze)

-Wilson's algorithm (unbiased maze)

-Backtracking (depth-first search, iterative version)

-Binary tree algorithm

-Division algorithm

-Eller's algorithm

-Growing tree algorithm

-Kruskal's algorithm

-Prim's algorithm

-Prim's algorithm (modified)

-Sidewinder algorithm

"""

from random import choice, random, randrange, sample, shuffle from typing import List

def aldous_broder(y_max: int, x_max: int) -> List[List[bool]]:

"""

Aldous-Broder 2D perfect maze generation algorithm (unbiased maze) :param y_max: height

:param x_max: width

:return: 2D perfect maze grid

"""

assert y_max % 2 and x_max % 2 and y_max >= 3 and x_max >= 3 grid = [[True for _ in range(x_max)] for _ in range(y_max)] directions = ((2, 0), (-2, 0), (0, 2), (0, -2))

(current_row, current_col) = (randrange(1, y_max, 2), randrange(1, x_max, 2)) grid[current_row][current_col] = False

num_visited = 1

max_visited = ((y_max - 1) // 2 * (x_max - 1) // 2) while num_visited < max_visited:

neighbors = [(current_row + dy, current_col + dx) for dy, dx in directions]

valid_neighbors = [(y, x) for y, x in neighbors if 0 < y < y_max and 0 < x < x_max and grid[y][x]] if not valid_neighbors:

free_neighbors = [(y, x) for y, x in neighbors if 0 < y < y_max and 0 < x < x_max and not

grid[y][x]]

(current_row, current_col) = choice(free_neighbors) continue

shuffle(valid_neighbors)

for new_row, new_col in valid_neighbors: if grid[new_row][new_col]:

grid[new_row][new_col] = grid[(new_row + current_row) // 2][(new_col + current_col) // 2]

= False

(current_row, current_col) = (new_row, new_col) num_visited += 1

break

return grid

def wilson(y_max: int, x_max: int) -> List[List[bool]]:

"""

Wilson's 2D perfect maze generation algorithm (unbiased maze) :param y_max: height

:param x_max: width

:return: 2D perfect maze grid

"""

assert y_max % 2 and x_max % 2 and y_max >= 3 and x_max >= 3

49

perfect_maze.py

grid = [[True for _ in range(x_max)] for _ in range(y_max)] directions = ((2, 0), (-2, 0), (0, 2), (0, -2))

free = {(y, x) for y in range(1, y_max, 2) for x in range(1, x_max, 2)} (y, x) = (2 * randrange(y_max // 2) + 1, 2 * randrange(x_max // 2) + 1) grid[y][x] = False

free.remove((y, x)) while free:

y, x = key = sample(free, 1)[0] free.remove(key)

path = [key] grid[y][x] = False

neighbors = ((y + dy, x + dx) for dy, dx in directions)

neighbors = [(y, x) for y, x in neighbors if 0 < y < y_max and 0 < x < x_max] y, x = key = choice(neighbors)

while grid[y][x]:

grid[y][x] = grid[(y + path[-1][0]) // 2][(x + path[-1][1]) // 2] = False neighbors = ((y + dy, x + dx) for dy, dx in directions)

neighbors = [(y, x) for y, x in neighbors if 0 < y < y_max and 0 < x < x_max] neighbors.remove(path[-1])

free.remove(key) path.append(key)

y, x = key = choice(neighbors) if key in path:

last_key = path.pop() free.add(last_key) grid[last_key[0]][last_key[1]] = True for key in reversed(path):

free.add(key)

grid[key[0]][key[1]] = grid[(last_key[0] + key[0]) // 2][(last_key[1] + key[1]) // 2] =

True

last_key = key

else:

grid[(y + path[-1][0]) // 2][(x + path[-1][1]) // 2] = False return grid

def backtracking(y_max: int, x_max: int) -> List[List[bool]]:

"""

Iterative version of depth-first search 2D perfect maze generation algorithm :param y_max: height

:param x_max: width

:return: 2D perfect maze grid

"""

grid = [[True for _ in range(x_max)] for _ in range(y_max)] directions = [(0, -2), (0, 2), (-2, 0), (2, 0)]

stack = [(2 * randrange(y_max // 2) + 1, 2 * randrange(x_max // 2) + 1)] while stack:

y, x = stack.pop() grid[y][x] = False

neighbors = ((y + dy, x + dx) for dy, dx in directions)

neighbors = [(y, x) for y, x in neighbors if 0 < y < y_max and 0 < x < x_max and grid[y][x]] if len(neighbors) > 1:

stack.append((y, x)) if neighbors:

ny, nx = choice(neighbors)

grid[(y + ny) // 2][(x + nx) // 2] = False stack.append((ny, nx))

return grid

def binary_tree(y_max: int, x_max: int) -> List[List[bool]]:

"""

Binary tree 2D perfect maze generation algorithm :param y_max: height

:param x_max: width

:return: 2D perfect maze grid

"""

assert y_max % 2 and x_max % 2 and y_max >= 3 and x_max >= 3 grid = [[True for _ in range(x_max)] for _ in range(y_max)] grid[1][1] = False

50