在动态网格环境中优化自定义寻路算法

问：

我正在研究一种用于动态网格环境的寻路算法，在该环境中，障碍物可以在运行时出现和消失。我的目标是实时找到从起点到终点的最短路径，同时考虑到网格的变化性质。

环境详细信息：

• 网格是 2D 的，尺寸为 1000x1000。
• 网格中的每个单元格可以是可通行的，也可以是障碍物。
• 障碍物可以根据外部事件出现或消失。
• 该算法需要在 Python 环境中运行，最好使用 Python 3.8 或更高版本。

目前的方法：

我尝试过使用基于曼哈顿距离的启发式算法实现 A* 算法。这是我的代码的简化版本：

import heapq

def a_star(grid, start, end):
    def heuristic(a, b):
        return abs(a[0] - b[0]) + abs(a[1] - b[1])

    neighbors = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 4-directional movement
    closed_set = set()
    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic(start, end)}

    open_heap = []
    heapq.heappush(open_heap, (f_score[start], start))

    while open_heap:
        current = heapq.heappop(open_heap)[1]

        if current == end:
            # Reconstruct path
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            return path[::-1]

        closed_set.add(current)
        for i, j in neighbors:
            neighbor = current[0] + i, current[1] + j
            tentative_g_score = g_score[current] + 1
            if 0 <= neighbor[0] < len(grid) and 0 <= neighbor[1] < len(grid[0]) and grid[neighbor[0]][neighbor[1]] != 1:
                if neighbor in closed_set and tentative_g_score >= g_score.get(neighbor, 0):
                    continue

                if tentative_g_score < g_score.get(neighbor, float('inf')) or neighbor not in [i[1] for i in open_heap]:
                    came_from[neighbor] = current
                    g_score[neighbor] = tentative_g_score
                    f_score[neighbor] = tentative_g_score + heuristic(neighbor, end)
                    heapq.heappush(open_heap, (f_score[neighbor], neighbor))
    return []

# Example usage
grid = [[0 for _ in range(1000)] for _ in range(1000)]  # 0 for passable, 1 for obstacle
path = a_star(grid, (0, 0), (999, 999))
print(path)

问题：

虽然这适用于静态网格，但它在动态环境中的性能不佳，尤其是当障碍物频繁变化时。该算法通常会重新计算由于新障碍物而变得无效的路径，从而导致明显的延迟。

我考虑过实现 D* Lite 或其他增量寻路算法，但我不确定如何有效地将它们集成到我当前的设置中。

问题：

• 如何修改当前算法以更好地处理网格中的动态变化？
• 对于这种实时、动态的寻路，有没有更合适的算法？
• 在大型网格环境中优化性能的任何建议？

任何帮助或指示将不胜感激！

我已经研究了这个答案，但它并不能帮助我解决我的具体问题。