i don't see how another algorithm can be better then A*
A* gives all you need. Ow, you can basicly strip A* a bit down to get the same effect. Some call it 'First Depth Search", which is true , but you have to do some optimization afterwards to get good results as well. Download the RealBot source code for information about its path finder.. it could help you a bit.
Nevertheless, you should really read the articles proposed