More context would be useful to know exactly what kind of algorithm you need. In our game we use a bounding ellipse to limit the A* traversal with the actors c

More context would be useful to know exactly what kind of algorithm you need. In our game we use a bounding ellipse to limit the A* traversal with the actors current position and the target position as the focal points. If a pathfind fails, we still move towards the closest square that we found to the goal. When the two points are far away from each other the ellipse is long and thin which causes the paths to be very direct. As the current position and target position get closer the ellipse turns in to more of a circle meaning that the pathfinder will discover more indirect routes should they be needed to get to the final goal. So this means that entities will tend to move in direct paths when they are far away (even if they don't actually know if they will be able to complete the path yet) and then discover an actual route around blocking obsticals as they get closer. Because long and thin ellipses tend to really constrain the number of nodes that will be considered, it works pretty well to speed up the A* searches.