I answered this question sort of broadly on maps in the Roman world. You may find it useful. Since you mention armies on the march, however, I must assume that you're talking about physical paper maps. The existence of such charts can be reasonably conjectured, but we have no surviving examples of any such materials. Nor, I think, should we necessarily think of them as being a requirement for accurate navigation over land or sea. A map consists of a visual representation of a catalog of distances between various points. As such ancient geographers like Ptolemy and Eratosthenes compiled lists of distances between known points, from which medieval cartographers were able to draw up the "Ptolemaic" maps that survive throughout the Middle Ages. Similar catalogs, called itineraries, were compiled for the purpose of travel rather than spacial representation (Janni's controversial hypothesis , which has met with great skepticism, supposes that the Romans thought of the space between settlements as being entirely linear and conceptually could not have made maps). Such itineraries are extremely well-attested, both as manuscripts and in inscriptions. Essentially they consist of lists of two points and the distance between them. These itineraries could be quite complex--the Tabula Peutingeriana is a visual representation of one--and were arguably faster to use to figure out the distance and speed of a journey. As for military matters, Vegetius mentions that a commander should memorize his itineraries so that not only does he know the distances of the major routes but also the shortcuts and natural obstacles and so forth. Vegetius also mentions that a good commander should have his itinerary information both written and in visual form, although to what extent these visual itineraries really preserved spacial relationships, rather than being essentially like subway maps, is unclear.