Do you happen to remember what the lessons learned from that experience were -- what the most important things that should have been optimized were for example?
As a side note, one very simple optimization I will probably do is only calculating costs of squares that I know are possible to move to, instead of parsing all map squares. The worst case cost would remain the same if a unit could theoretically move everywhere, of course.
The two main ones were C++ related. I wasn't really used to namespaces and the new (to me) data structures. As such I kind of panicked with doing a find in a set (IIRC) and implemented my own find routine as the iterator concept was so new to me. Turns out it is really easy and not using it looked amateurish as well as failed to use any inbuilt optimisations.
For the other major one, referring to the wiki page (I basically implemented the pseudocode on there):
http://en.wikipedia.org/wiki/A*_search_algorithm
For this:
current := the node in openset having the lowest f_score[] value
I originally had everything going into (IIRC) a set ordered by f score, which would make finding the lowest very quick. However, I ran into problems (obviously) when different nodes had the same f score, so I panicked (again) and just ordered them by an ID number. The correct thing would have been to use (IIRC) multiset which allows entries with the same value. So instead of iterating through the entire set to find the lowest f score I could have taken it from the ordered multiset.
To be honest, if you follow the pseudocode it only does the nodes you need to do, rather than the whole map, which I understand is your major issue.
I also found this page really useful:
http://www.policyalmanac.org/games/aStarTutorial.htm