На этом шаге мы рассмотрим достижение цели и перемещение внутри лабиринта.
Позже нам пригодится функция, которая проверяет, достигли ли мы цели в процессе поиска. Другими словами, мы хотим проверить, является ли определенная MazeLocation, которой достиг поиск, нашей целью. Можем добавить в Maze следующий метод.
def goal_test(self, ml: MazeLocation) -> bool: return ml == self.goal
Как передвигаться в лабиринте? Допустим, из заданной ячейки лабиринта мы можем двигаться по горизонтали и вертикали по одной ячейке за ход. Используя эти критерии, функция successors() способна находить возможные следующие местоположения из заданной ячейки Maze. Однако функция successors() будет отличаться для каждой Maze, поскольку любой лабиринт имеет собственный размер и набор стен. Поэтому мы определим ее как метод Maze:
def successors(self, ml: MazeLocation) -> List[MazeLocation]:
locations: List[MazeLocation] = []
if ml.row + 1 < self._rows and self._grid[ml.row + 1][ml.column] != Cell.BLOCKED:
locations.append(MazeLocation(ml.row + 1, ml.column))
if ml.row - 1 >= 0 and self._grid[ml.row - 1][ml.column] != Cell.BLOCKED:
locations.append(MazeLocation(ml.row - 1, ml.column))
if ml.column + 1 < self._columns and self._grid[ml.row][ml.column + 1] != Cell.BLOCKED:
locations.append(MazeLocation(ml.row, ml.column + 1))
if ml.column - 1 >= 0 and self._grid[ml.row][ml.column - 1] != Cell.BLOCKED:
locations.append(MazeLocation(ml.row, ml.column - 1))
return locations
Метод successors() просто проверяет верхнюю, нижнюю, правую и левую смежные ячейки по отношению к MazeLocation в Maze, чтобы увидеть, есть ли там пустые места, в которые можно попасть из этой ячейки. Также это позволяет избежать проверки ячеек за пределами лабиринта. Все возможные обнаруженные MazeLocation помещаются в список, который в итоге возвращается вызывающей функции.
На следующем шаге мы рассмотрим поиск в глубину.
