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

[Anonymous]

Я пишу алгоритм нанесения пути, более точно создавая карту, которая указывает направление для движения, чтобы достичь цели. Кажется, это работает, но есть одна проблема: алгоритм не всегда находит оптимальный путь. < /P>
Например, < /p>
→ → → → → ↘ # → → ↘ ↓ ↙ # ↘ ↘ # ↘ ↓ ↘ ↘ ↘ ↓ ↘ #
↗ # ↗ ↗ ↗ → ↗ ↗ ↗ → ↘ # # # ↓ ↘ ↘ ↘ # ↘ ↘ ↓ # ↓
↘ # ↗ # ↗ ↗ ↗ ↗ ↗ # → ↘ # → ↘ # ↘ ↘ ↘ ↘ ↘ ↘ # ↓
→ ↗ → ↗ ↗ # ↗ ↗ → ↗ ↗ → ↘ ↘ → ↘ # ↘ ↘ ↘ ↓ ↘ ↓ ↙
↗ ↗ ↗ ↗ ↘ # # ↗ ↗ # # ↗ → ↘ ↓ # ↘ # ↘ ↘ ↘ # ↘ #
↗ ↗ ↗ ↗ # → ↗ ↗ → → ↗ ↗ ↗ → ↘ # ↘ ↘ ↘ ↘ ↘ ↓ ↘ ↓
↗ ↗ ↗ → ↗ # ↗ ↗ ↗ # ↗ ↗ ↗ ↗ → ↘ → ↘ ↘ ↘ ↘ ↘ # ↙
↗ # ↗ ↗ → ↗ ↗ ↗ → ↗ ↗ ↗ ↗ ↗ ↗ → ↘ → ↘ ↘ ↘ ↘ ↘ #
→ ↗ ↗ ↗ ↗ ↗ ↗ ↗ ↗ ↗ ↗ ↗ # ↗ ↗ ↗ → ↘ → ↘ ↘ ↘ ↘ ↓
↗ ↗ ↗ ↗ # ↗ ↗ ↗ # ↗ ↗ → ↗ ↗ ↗ ↗ ↗ → ↘ → ↘ ↘ ↘ ↓
↗ ↗ ↗ → ↗ ↗ ↗ ↘ # ↗ ↗ ↗ ↗ ↗ ↗ # ↗ # → ↘ → ↘ ↓ ↙
↗ ↗ ↗ ↗ ↗ ↗ ↗ → ↗ ↗ ↗ ↗ ↗ ↗ → ↗ # ↗ ↗ → ↘ # ↓ #
↗ ↗ ↗ # ↗ ↗ ↗ ↗ # ↗ ↗ ↗ ↗ ↗ ↗ → ↗ ↗ ↗ ↗ → → ↘ #
↗ ↗ → ↗ ↗ ↗ ↗ # ↗ # ↗ ↗ # ↗ ↗ ↗ ↗ # ↗ # # ↗ → ·
< /code>
Как вы можете видеть, из правого верхнего угла алгоритм нашел очень хороший путь к финишу (правый нижний угол), но из левого нижнего угла он создает действительно плохой путь. < /p>
Пожалуйста, помогите, если вы знаете, как это исправить < /p>
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)

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