One method is to preprocess the map, which then can greatly increase the accuracy of the A* heuristic.

https://www.redblobgames.com/pathfinding/l1-clarkson/