A*算法路径规划问题：兼顾禁切角与必要对角线移动

问题描述 #

• 需求矛盾：需同时实现禁止切角移动和仅在唯一路径/必要场景允许对角线移动
• 现有代码缺陷：非对角线场景运行正常，但在必须依赖对角线的场景（如红方块到目标G）无法找到路径，要么全程优先走对角线，要么禁切角后完全无法使用必要的对角线，期望路径为截图中的蓝色路径（#代表不可行走格子，.代表可行走格子）

核心问题分析 #

当前代码的对角线移动判断逻辑完全倒置：if not (grid[y][nx] == 0 and grid[ny][x] == 0) 这个条件会在两个相邻直走格子不同时被堵时允许对角线，导致非必要场景也会触发对角线移动；而真正需要对角线的场景（两个相邻直走格子都被堵）反而被禁止，这直接导致必要路径无法被识别。

修复方案 #

修改get_neighbors中的对角线移动判断逻辑，同时调整启发式函数和移动成本，适配需求：

1. 禁止切角：若对角线移动的两个相邻直走格子任意一个可行走，则不允许对角线移动（避免直接切角走捷径）
2. 允许必要对角线：仅当两个相邻直走格子全部被堵死，且对角线格子本身可行走时，才允许对角线移动（此时为唯一路径选择）
3. 优化启发式与成本：将对角线成本设为符合几何距离的√2（约1.414），同时将启发式改为切比雪夫距离，保证A*算法的最优性和路径选择合理性

修改后的完整代码 #

import heapq

def heuristic(a, b):
    """ 切比雪夫距离，适配允许对角线移动的场景，准确估计剩余路径成本 """
    dx = abs(a[0] - b[0])
    dy = abs(a[1] - b[1])
    return max(dx, dy)

def get_neighbors(grid, node):
    x, y = node
    neighbors = []
    rows = len(grid)
    cols = len(grid[0]) if rows > 0 else 0

    # 直走移动（上下左右）- 成本1，优先选择
    for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
        nx, ny = x + dx, y + dy
        if 0 <= nx < cols and 0 <= ny < rows and grid[ny][nx] == 1:
            neighbors.append(((nx, ny), 1))

    # 对角线移动 - 成本√2≈1.414，仅必要时允许
    diagonal_cost = 1.414
    for dx, dy in [(-1,-1), (-1,1), (1,-1), (1,1)]:
        nx, ny = x + dx, y + dy
        if 0 <= nx < cols and 0 <= ny < rows and grid[ny][nx] == 1:
            # 检查相邻直走格子是否都被堵死
            left_blocked = grid[y][nx] == 0 if 0 <= nx < cols else True
            top_blocked = grid[ny][x] == 0 if 0 <= ny < rows else True
            # 仅当两个直走方向都被堵时，允许对角线移动
            if left_blocked and top_blocked:
                neighbors.append(((nx, ny), diagonal_cost))

    return neighbors

def astar(grid, start, goal):
    """ A*寻路算法实现 """
    open_set = []
    heapq.heappush(open_set, (0, start))
    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic(start, goal)}

    while open_set:
        _, current = heapq.heappop(open_set)

        if current == goal:
            return reconstruct_path(came_from, current)

        for neighbor, move_cost in get_neighbors(grid, current):
            tentative_g_score = g_score[current] + move_cost
            if neighbor not in g_score or tentative_g_score < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g_score
                f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal)
                heapq.heappush(open_set, (f_score[neighbor], neighbor))
    
    return None

def reconstruct_path(came_from, current):
    """ 从终点回溯重建路径 """
    path = [current]
    while current in came_from:
        current = came_from[current]
        path.append(current)
    path.reverse()
    return path

关键修改说明 #

1. 启发式函数：替换曼哈顿距离为切比雪夫距离，适配对角线移动场景，确保启发式不会低估剩余成本，保证A*算法的最优性
2. 对角线判断逻辑：反转原条件，仅在两个相邻直走格子都被堵死时允许对角线，既禁止了切角，又保留了必要场景下的路径
3. 移动成本：将对角线成本从2.1调整为1.414（√2），符合实际几何距离，让算法在必要时愿意选择对角线，同时保证直走仍是优先选项

内容的提问来源于stack exchange，提问作者Howcio