It's an extension of Dijkstra's algorithm that adds a few heuristics.
@omginternets:
> dates back ... extension of ... adds a few heuristics.
Blabla, BS.
Fact is Empire Earth was one of the very first computer games to use A* algo. Age of Empires 1 used a worse faster different algo.
Fact is in the age before Wikipedia and Google, decade old papers of obscure algos were more or less lost and forgotten. They were written on paper with no digital copy readly available. So game devs often reinvented things without not knowing of previous work, it took several years until the early 2000s that this old stuff got scanned and made public viewable.
Citation? The only mention I can find about the pathfinding algorithm used by Age of Empires is this: http://artho.com/age/pathfinding.html
A* is supposed to be an optimization of Dijkstra's. I don't know why you call it CPU intensive.