На этом шаге мы приведем функцию, рассчитывающую это расстояние.
Евклидово расстояние - это прекрасно, но для нашей конкретной задачи (лабиринт, в котором можно передвигаться только в одном из четырех направлений) можно добиться еще большего. Манхэттенское расстояние определяется навигацией по улицам Манхэттена - самого известного района Нью-Йорка, улицы которого образуют регулярную сетку. Чтобы добраться из любой его точки в любую другую точку, нужно пройти определенное количество кварталов по горизонтали и вертикали. (На Манхэттене почти нет диагональных улиц.) Расстояние в Манхэттене определяется путем простого вычисления разности в строках между двумя точками лабиринта и суммирования ее с разностью в столбцах:
def manhattan_distance(goal: MazeLocation) -> Callable[[MazeLocation], float]: def distance(ml: MazeLocation) -> float: xdist: int = abs(ml.column - goal.column) ydist: int = abs(ml.row - goal.row) return (xdist + ydist) return distance
Вычисление манхэттенского расстояния показано на рисунке 1.
Рис.1. У манхэттенского расстояния нет диагоналей. Путь должен проходить по параллельным или перпендикулярным линиям
На следующем шаге мы рассмотрим алгоритм А*.
