Continuing the discussion from @erdman has unseated @djma:
I have used A* to produce paths for some cells in Java (should have similar runtime to C#) and had reasonable performance. I basically worked from the example code on Wikipedia without any real optimizations.
Personally I found that calculating an entire path wasn't worth it because the map was so dynamic. By the time my cell had made a few moves towards its target, the path was no longer very valuable. Calculating a new path on each turn didn't prove to be much more effective than naïvely moving in the general direction of my target with some heuristics regarding my immediate surroundings.