Optimizing a custom pathfinding algorithm in a dynamic grid environment

Question

I'm working on a pathfinding algorithm for a dynamic grid environment where obstacles can appear and disappear during the runtime. My goal is to find the shortest path from a start point to an end point in real-time, considering the changing nature of the grid.

Environment Details:

• The grid is 2D, with a size of 1000x1000.
• Each cell in the grid can be either passable or an obstacle.
• Obstacles can appear or disappear based on external events.
• The algorithm needs to run in a Python environment, preferably using Python 3.8 or later.

Current Approach:

I've tried implementing an A* algorithm with a heuristic based on the Manhattan distance. Here's a simplified version of my code:

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)

Problem:

While this works for static grids, it struggles with performance in dynamic environments, especially when obstacles change frequently. The algorithm often recalculates paths that become invalid due to new obstacles, leading to noticeable delays.

I've considered implementing D* Lite or other incremental pathfinding algorithms, but I'm unsure how to efficiently integrate them into my current setup.

Questions:

• How can I modify my current algorithm to better handle dynamic changes in the grid?
• Are there more suitable algorithms for this kind of real-time, dynamic pathfinding?
• Any suggestions for optimizing the performance in a large grid environment?

Any help or pointers would be greatly appreciated!

I have studied this answer, but it doesn't help me address my specific problem.