На этом шаге мы рассмотрим один из способов представления любиринта.
Поиск пути через лабиринт аналогичен многим распространенным задачам поиска в информатике. Почему бы буквально не найти путь через лабиринт, чтобы проиллюстрировать алгоритмы поиска в ширину, поиска в глубину и алгоритмы А*?
Наш лабиринт представляет собой двумерную сеть ячеек - объектов Cell. Cell - это перечисление значений str, где " " означает пустое пространство, а "X" - занятое. В иллюстративных целях при выводе лабиринта на печать существуют и другие варианты заполнения ячеек.
from typing import List, NamedTuple, Callable, Optional import random from math import sqrt from generic_search import dfs, bfs, node_to_path, astar, Node class Cell(str, Enum): EMPTY = " " BLOCKED = "X" START = "S" GOAL = "G" PATH = "*"
Мы снова чересчур много импортируем. Обратите внимание на то, что последний импорт (из generic_search) состоит из символов, которые мы еще не определили. Он включен сюда для удобства, но вы можете закомментировать его, пока он не потребуется.
Нам понадобится способ сослаться на конкретную точку в лабиринте. Это будет просто NamedTuple со свойствами, представляющими строку и столбец данной ячейки в сетке:
class MazeLocation(NamedTuple): row: int column: int
На следующем шаге мы рассмотрим создание случайного лабиринта.
