Do you have time to preprocess the map? Do you have some spare memory? If so, check out Compressed path databases. They're a type of oracle that does exactly w

Do you have time to preprocess the map? Do you have some spare memory? If so, check out Compressed path databases. They're a type of oracle that does exactly what you want: given a start and target position, the oracle returns the next step on the optimal path to the target. You can extract one step, a few steps or the entire path. Extracting a single step is very fast since it requires little more than a memory lookup. Needless to say this approach has significant advantages if you need to constantly replan your path.