so i think pre-calculated routes will not work
They are not required. I don't know how intsense your game is on pathfinding, but I doubt with optimization that you'll overpower a*, especially with path limitations (which is extremely easy to impliment). If your game is multiplayer, you'll probobly smack your bandwidth before a* movement processing.
If you don't need 'good' pathfinding, then go ahead with checking out others, otherwise you have nothing to lose with a-star, just limit range and path calculation counts and you'll be more then fine.