Military tactics generally place huge importance on identifying and securing key terrain, which tends to favor those with local knowledge or the most accurate maps; so I'm curious how they accomplished such vast conquests if they didn't have this knowledge in advance.
Generally, maps as we think of them today as precise navigational documents arose roughly around the 15th century with the Enlightenment and western colonialism (see Denis Wood's 'Rethinking the Power of Maps') although there are exceptions. There's an example of a Chinese map, the Yu Ji Tu, which is interesting as it maps China fairly accurately with the exception of having deliberately moved and even invented some features to conform with the Yu Gong, an ancient text. Maps of the ancient world were often interwoven with myths and are often more a reflection of the culture of the people who produced them, rather than a "reflection" (contentious word in cartographic literature!) of the world as it geographically was.
Anyway, detailed ancient mapping of terrain was very rare (even nonexistent) and not precise, often simply mapping the time to travel between places rather than the geography itself. An example of this is the Tabula Peutingeriana which is a 4th century Roman map based upon a map made for Augustus which depicts the Roman empire. Geographically the map is very distorted, but it does show the major cities of the Empire and the time taken to travel between them.
In terms of military command, in his book 'In the name of Rome' Adrian Goldsworthy explains how Roman commanders would base their military planning based on scouts of local terrain whilst in the field. Often commanders would personally conduct these scouts so as to have a first hand account of the area. Indeed the Roman commander Marcus Claudius Marcellus was famously ambushed whilst on a reconnaissance mission during the Second Punic War.
Thus, I would imagine that Alexander's situation was much the same in that he would have have no precise maps of his empire nor that which he was planning to conquer. His military planning was in all likelihood based upon scouting of the terrain whilst he was in the field.
EDIT: Expanded answer
You can read the Anabasis by Xenophon to get a feel for this. Xenophon was a Greek mercenary in the 5th-4th century BC, traveling through unfamiliar Persian (and other) territory. Their navigation is part relying on locals to tell the truth, part following rumors and legends, and part guesswork. When the army finally arrives at a town they recognize as part of the Greek world, they fall on their faces and offer sacrifices because it's the first time they really believe they'll get home.