Why don't you use the good old grid + A* pathfinding?
It is a pretty simple approach, limit the amount of paths calculated and you should have an OK FPS rate.
If you need better approachs you will have to look for a better graph representation for A* than a grid.
I suggest reading:
http://theory.stanford.edu/~amitp/GameProgramming/ (A LOT of information on A*)
http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html (Map representation only)