I'm writing a pathfinding algorithm, more precisely creating a map that indicates the direction to move in order to reach the goal. It seems to work, but there is one problem: the algorithm does not always find the optimal path. For example, → → → → → ↘ # → → ↘ ↓ ↙ # ↘ ↘ # ↘ ↓ ↘ ↘ ↘ ↓ ↘ # ↗ # ↗ ↗ ↗ → ↗ ↗ ↗ → ↘ # # # ↓ ↘ ↘ ↘ # ↘ ↘ ↓ # ↓ ↘ # ↗ # ↗ ↗ ↗ ↗ ↗ # → ↘ # → ↘ # ↘ ↘ ↘ ↘ ↘ ↘ # ↓ → ↗ → ↗ ↗ # ↗ ↗ → ↗ ↗ → ↘ ↘ → ↘ # ↘ ↘ ↘ ↓ ↘ ↓ ↙ ↗ ↗ ↗ ↗ ↘ # # ↗ ↗ # # ↗ → ↘ ↓ # ↘ # ↘ ↘ ↘ # ↘ # ↗ ↗ ↗ ↗ # → ↗ ↗ → → ↗ ↗ ↗ → ↘ # ↘ ↘ ↘ ↘ ↘ ↓ ↘ ↓ ↗ ↗ ↗ → ↗ # ↗ ↗ ↗ # ↗ ↗ ↗ ↗ → ↘ → ↘ ↘ ↘ ↘ ↘ # ↙ ↗ # ↗ ↗ → ↗ ↗ ↗ → ↗ ↗ ↗ ↗ ↗ ↗ → ↘ → ↘ ↘ ↘ ↘ ↘ # → ↗ ↗ ↗ ↗ ↗ ↗ ↗ ↗ ↗ ↗ ↗ # ↗ ↗ ↗ → ↘ → ↘ ↘ ↘ ↘ ↓ ↗ ↗ ↗ ↗ # ↗ ↗ ↗ # ↗ ↗ → ↗ ↗ ↗ ↗ ↗ → ↘ → ↘ ↘ ↘ ↓ ↗ ↗ ↗ → ↗ ↗ ↗ ↘ # ↗ ↗ ↗ ↗ ↗ ↗ # ↗ # → ↘ → ↘ ↓ ↙ ↗ ↗ ↗ ↗ ↗ ↗ ↗ → ↗ ↗ ↗ ↗ ↗ ↗ → ↗ # ↗ ↗ → ↘ # ↓ # ↗ ↗ ↗ # ↗ ↗ ↗ ↗ # ↗ ↗ ↗ ↗ ↗ ↗ → ↗ ↗ ↗ ↗ → → ↘ # ↗ ↗ → ↗ ↗ ↗ ↗ # ↗ # ↗ ↗ # ↗ ↗ ↗ ↗ # ↗ # # ↗ → · As you can see, from the top right corner, the algorithm found a very good path to the finish (bottom right corner), but from the bottom left corner, it produces a really bad path. Please help if you know how to fix this 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 <= nx < width and 0 <= ny < height: neighbor = map[ny][nx] print(f'Neighbor x:{nx} y:{ny}') if neighbor.wall or visited[ny][nx]: print('Neighbor is wall or visited') continue cost = 14 if abs(dx) + abs(dy) == 2 else 10 new_distance = current.distance + cost if new_distance < neighbor.distance: print('and we do analyze') neighbor.distance = new_distance neighbor.parent = current directions_map[ny][nx] = (-dx, -dy) visited[ny][nx] = True queue.append(neighbor) return directions_map map = [[Cell(x, y) for x in range(24)] for y in range(14)] for rock in ROCKS: rx, ry = rock map[ry][rx].wall = True path_map = build_direction_map(map[13][23], map) direction_symbols = { (0, -1): '↑', (1, -1): '↗', (1, 0): '→', (1, 1): '↘', (0, 1): '↓', (-1, 1): '↙', (-1, 0): '←', (-1, -1): '↖', (0, 0): '·' } for y, row in enumerate(path_map): line = '' for x, direction in enumerate(row): if map[y][x].wall: line += ' # ' else: line += f' {direction_symbols.get(direction)} ' print(line) Continue reading...
