Across an endless grid

The grid has no edges: x and y can be any whole numbers, including negative ones. Some squares are walls. Each move goes one square up, down, left or right, into a square that is not a wall. Return the fewest moves from start to goal. A route always exists, and the start is never a wall.

moves_needed((0, 0), (4, 0), [(2, -1), (2, 0), (2, 1)])  # 8
moves_needed((-2, 7), (3, 1), [])                        # 11

Limits

• Up to 3,000 moves apart, and a few hundred walls.
• A breadth-first search looks at every square closer than the goal: millions of squares. Use A* with a good guess, and think about which entry should come first when two have the same f. The big tests have 3 seconds each.