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

imperfect_maze.py

grid[row][randrange(2, x_max - 1)] = False for row in range(4, y_max - 1, 4):

grid[row][x_max - 2] = False grid[row][randrange(1, x_max - 2)] = False

return grid

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

"""

Small rooms 2D imperfect maze generation algorithm :param y_max: height

:param x_max: width

:return: 2D imperfect 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)] for y in range(1, y_max - 1):

if y % 2:

for x in range(1, x_max - 3, 4): grid[y][x] = False

grid[y][x + 1] = False grid[y][x + 2] = False

if x < x_max - 4 and not randrange(3): grid[y][x + 3] = False

else:

for x in range(2, x_max - 1, 4): grid[y][x] = False

y_mid = y_max // 2

for x in range(1, x_max - 1): grid[y_mid][x] = False

return grid

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

"""

Spiral 2D imperfect maze generation algorithm :param y_max: height

:param x_max: width

:return: 2D imperfect 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), (0, 2), (2, 0), (0, -2)]

if randrange(2): directions.reverse()

current = (1, 1) grid[1][1] = False next_dir = 0

while True:

y, x = current

new_y, new_x = (y + directions[next_dir][0], x + directions[next_dir][1]) 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 if grid[y][x]] if (new_y, new_x) in neighbors:

grid[(y + new_y) // 2][(x + new_x) // 2] = False grid[new_y][new_x] = False

current = (new_y, new_x) elif not neighbors:

break else:

next_dir = (next_dir + 1) % 4 for i in range(max(y_max, x_max)):

grid[randrange(1, y_max - 1)][randrange(1, x_max - 1)] = False return grid

def main():

from timeit import timeit

def print_maze(maze):

56

imperfect_maze.py

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

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)

functions = [serpentine, small_rooms, spiral]

n_functions = ['Serpentine algorithm', 'Small rooms algorithm', 'Spiral algorithm'] time_functions = [0 for _ in n_functions]

print('== Imperfect maze ===')

width = (get_input('Enter the width of the maze (odd number)', 5, 100000) // 2) * 2 + 1 height = (get_input('Enter the height of the maze (odd number)', 5, 100000) // 2) * 2 + 1 for n, func in zip(n_functions, functions):

print(n) print_maze(func(height, width)) input('next >>')

print('\n', '=== Time test ===', 'Tests: 15', 'Sizes: 11-41', sep='\n') for i in range(15):

y, x = (randrange(10, 40) // 2) * 2 + 1, (randrange(10, 40) // 2) * 2 + 1 for j, func in enumerate(functions):

name = func.__name__

time_functions[j] += timeit(f"{name}({y}, {x})", f"from __main__ import {name}", number=15) for time, n in sorted(zip(time_functions, n_functions)):

print(n + ': ' + str(time)) input()

if __name__ == '__main__': main()

Таблица 28. Файл с алгоритмами поиска кратчайших путей в лабиринтах

solve_maze.py

#!/usr/bin/env python3

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

"""

Implementation of algorithms for finding the shortest paths in 2D mazes. Algorithms:

-A* algorithm

-BFS (breadth-first search) (iterative version)

-Dijkstra algorithm

"""

import heapq

from collections import deque from math import inf

from typing import Callable, List, Tuple

class Heuristic:

"""

A class with basic heuristics for the A * algorithm

"""

@staticmethod

def octile(y0, x0, y1, x1):

(ty, tx) = (abs(y0 - y1), abs(x0 - x1))

return max(ty, tx) + (2 ** 0.5 - 1) * min(ty, tx)

@staticmethod

def manhattan(y0, x0, y1, x1):

return abs(y0 - y1) + abs(x0 - x1)

@staticmethod

def chebyshev(y0, x0, y1, x1):

return max(abs(y0 - y1), abs(x0 - x1))

57

solve_maze.py

@staticmethod

def euclidean(y0, x0, y1, x1):

return ((y0 - y1) ** 2 + (x0 - x1) ** 2) ** 0.5

def a_star(maze: List[List[bool]], beginNode: Tuple[int, int], endNode: Tuple[int, int], heuristic: Callable = Heuristic.manhattan) -> List[Tuple[int, int]]:

"""

A* algorithm

This implementation uses heapq - a priority queue. :param maze: 2D maze grid

:param beginNode: initial position :param endNode: target position :param heuristic: heuristic function

:return: path from initial to target position

"""

current = (-1, -1)

(y_max, x_max) = (len(maze), len(maze[0])) q = []

cost = 0

heapq.heappush(q, (cost, endNode))

directions = ((-1, 0), (0, -1), (1, 0), (0, 1)) parentNode = {endNode: endNode}

costMap = {endNode: cost} while q:

current = heapq.heappop(q)[1] if current == beginNode:

break

cost = costMap[current] + 1 for y_dir, x_dir in directions:

(dy, dx) = (current[0] + y_dir, current[1] + x_dir)

if dy >= y_max or dy < 0 or dx >= x_max or dx < 0 or maze[dy][dx]: continue

neighbor = (dy, dx)

if cost < costMap.get(neighbor, inf): costMap[neighbor] = cost parentNode[neighbor] = current

heapq.heappush(q, (cost + heuristic(current[0], current[1], beginNode[0], beginNode[1]),

neighbor))

path = list()

if current == beginNode: path.append(current) while current != endNode:

current = parentNode[current] path.append(current)

return path

def bfs(maze: List[List[bool]], beginNode: Tuple[int, int], endNode: Tuple[int, int]) -> List[Tuple[int, int]]:

"""

Breadth-first search algorithm (iterative version)

(!) This implementation uses a deque instead of a queue. This choice is only related to the speed. :param maze: 2D maze grid

:param beginNode: initial position :param endNode: target position

:return: path from initial to target position

"""

current = (-1, -1)

(y_max, x_max) = (len(maze), len(maze[0])) q = deque()

q.append(endNode)

directions = ((-1, 0), (0, -1), (1, 0), (0, 1)) parentNode = {endNode: endNode}

while q:

current = q.popleft() if current == beginNode:

break

for y_dir, x_dir in directions:

58

solve_maze.py

(dy, dx) = (current[0] + y_dir, current[1] + x_dir)

if dy >= y_max or dy < 0 or dx >= x_max or dx < 0 or maze[dy][dx]: continue

neighbor = (dy, dx)

if neighbor not in parentNode: q.append(neighbor) parentNode[neighbor] = current

path = list()

if current == beginNode: path.append(current) while current != endNode:

current = parentNode[current] path.append(current)

return path

def dijkstra(maze: List[List[bool]], beginNode: Tuple[int, int], endNode: Tuple[int, int]) -> List[Tuple[int, int]]:

"""

Dijkstra algorithm

This implementation uses heapq - a priority queue. :param maze: 2D maze grid

:param beginNode: initial position :param endNode: target position

:return: path from initial to target position

"""

current = (-1, -1)

(y_max, x_max) = (len(maze), len(maze[0])) q = []

heapq.heappush(q, (0, endNode))

directions = ((-1, 0), (0, -1), (1, 0), (0, 1)) parentNode = {endNode: endNode}

costMap = {endNode: 0} while q:

current = heapq.heappop(q)[1] if current == beginNode:

break

cost = costMap[current] + 1 for y_dir, x_dir in directions:

(dy, dx) = (current[0] + y_dir, current[1] + x_dir)

if dy >= y_max or dy < 0 or dx >= x_max or dx < 0 or maze[dy][dx]: continue

neighbor = (dy, dx)

if cost < costMap.get(neighbor, inf): costMap[neighbor] = cost parentNode[neighbor] = current heapq.heappush(q, (cost, neighbor))

path = list()

if current == beginNode: path.append(current) while current != endNode:

current = parentNode[current] path.append(current)

return path

Таблица 29. Файл с выводом результата работы файла-программы test_maze.py

Вывод программы

=== Perfect algorithms ===

Enter the number of tests (1-100000):100

Enter the minimum length of the maze (odd number) (5-100000):200 Enter the maximum length of the maze (odd number) (5-100000):200 Time of execution of maze generation algorithms

Sidewinder algorithm: 2.046875 Binary tree algorithm: 2.625 Division algorithm: 5.515625 Backtracking algorithm: 11.046875 Eller's algorithm: 15.609375

59