Я реализовал алгоритм поиска пути A * следующим образом: https://www.redblobgames.com/pathfinding/a-star/introduction.html
Моя сетка имеет много препятствий (более десяти тысяч) и очень большая. Я понимаю, что для получения одного из кратчайших путей мне нужно реализовать допустимую эвристику, чтобы не переоценивать расстояние между текущей точкой и целью. Теоретически евклидово расстояние всегда должно быть меньше или равно. Однако, используя его, я вообще не получаю кратчайшего пути, потому что, используя диагональное (чебышевское или октильное) расстояние, я получаю более короткий путь. Это почему? Я что-то упускаю? Вот код:
graph.cost всегда возвращает 1
graph.neighbors возвращает 8 смежных позиций (меньше, если есть препятствия)
def a_star_search(graph, start, goal):
frontier = PriorityQueue()
frontier.put(start, 0)
came_from = {}
cost_so_far = {}
came_from[start] = None
cost_so_far[start] = 0
while not frontier.empty():
current = frontier.get()
if current == goal:
break
for next in graph.neighbors(current):
new_cost = cost_so_far[current] + graph.cost(current, next)
if next not in cost_so_far or new_cost < cost_so_far[next]:
cost_so_far[next] = new_cost
priority = new_cost + heuristic(goal, next)
frontier.put(next, priority)
came_from[next] = current
return get_path(came_from, start, goal)
def heuristic(a, b):
dx = abs(b[0] - a[0])
dy = abs(b[1] - a[1])
D = 1
#with D2 = 1 it's even slower but more accurate
D2 = math.sqrt(2)
#Diagonal distance - this is more accurate
#return D*(dx + dy) + (D2 - 2*D)*min(dx, dy)
#Euclidean distance - this is faster and less accurate
return math.sqrt(dx*dx + dy*dy)
