Алгоритм приставления пути не всегда находит оптимальный путь - почему? ⇐ Python

[Anonymous]

Я пишу алгоритм нанесения пути, более точно создавая карту, которая указывает направление для движения, чтобы достичь цели. Кажется, это работает, но есть одна проблема: алгоритм не всегда находит оптимальный путь.
Например,
Изображение
Как вы можете видеть, с правого верхнего правого углу, алгоритм нашел очень хороший путь к финишу (в нижнем правом углу), но из нижнего левого углу, он создает очень плохую путь. /> Помогите, пожалуйста, если вы знаете, как это исправить < /p>
from settings import *
from collections import deque

ROCKS = [(1, 1), (1, 2), (9, 13), (12, 2), (4, 5),
(16, 11), (22, 1), (6, 4), (5, 6), (12, 0),
(19, 13), (15, 2), (18, 1), (15, 0), (1, 7),
(23, 4), (16, 3), (23, 7), (10, 4), (12, 1),
(15, 4), (9, 4), (3, 2), (17, 4), (3, 12), (4, 9),
(8, 10), (22, 6), (7, 13), (6, 0), (15, 10), (8, 12),
(15, 5), (12, 8), (22, 2), (23, 12), (5, 4),
(21, 4), (8, 10), (13, 1), (8, 9), (21, 11),
(17, 13), (20, 13), (23, 0), (11, 1), (23, 11),
(17, 10), (5, 3), (12, 13), (9, 6), (9, 2)]

class Cell:
def __init__(self, x, y):
self.x = x
self.y = y
self.wall = False
self.distance = 9999
self.distance_to_target = 9999
self.mass = 9999
self.parent = None

def __repr__(self):
return f"Cell({self.x},{self.y})"

def manhattan_distance(x1, y1, x2, y2):
return abs(x1 - x2) + abs(y1 - y2)

from collections import deque

def build_direction_map(goal, map):
height = len(map)
width = len(map[0])

directions_map = [[None for _ in range(width)] for _ in range(height)]
visited = [[False for _ in range(width)] for _ in range(height)]

directions_map[goal.y][goal.x] = (0, 0)
goal.distance = 0
visited[goal.y][goal.x] = True

queue = deque()
queue.append(goal)

directions = [
(1, 1), (1, 0), (1, -1),
(0, -1), (-1, -1), (-1, 0),
(-1, 1), (0, 1)
]

while queue:
current = queue.popleft()
print(f"========Start analyze cell x:{current.x} y:{current.y}========")
if current.wall:
continue

for dx, dy in directions:
nx = current.x + dx
ny = current.y + dy

if 0

Подробнее здесь: https://stackoverflow.com/questions/797 ... l-path-why