My area of research, actually. Wow. Never thought this would come up in a reddit question. No, there is no evidence for these kinds of maps being used in the medieval period. By some accounts Napoleon was the first general to use anything like this. (See Andrew Hersey’s “Not Just Lines on a Map: A History of Military Mapping.”) For instance, in his book Recollections of the Private Life of Napoleon, Napoleon’s valet Louis Constant Wairy says: “During the three or four hours preceding an engagement, the Emperor spent most of the time with large maps spread out before him, the places on which he marked with pins with heads of different colored wax” (427).

You are right that accurate maps were closely guarded secrets for much of history. But, in the early 19th century, European general staffs dedicated huge amounts of time to surveying and cartography. The Prussians were the masters of this kind of stuff, having vowed never to suffer the kinds of defeats they did in the early days of the War of the Fourth Coalition.

It was around this time that Baron Georg Leopold von Reiswitz created a tabletop battle simulation (or, in German, Kriegsspiel). This was a huge novelty at the time, and soon everyone in the Prussian court was nerding out on it. The early Kriegsspiel was refined by Reiswitz's son, and then came to be played on actual terrain maps. (The earlier Kriegsspiel was played on terrain pieces that could move around each game, kinda like Settlers of Catan). The Kriegsspiel system then started to get used a planning and strategy map for actual wars, kinda like in the famous scene from Downfall.

For more info, check out this book. It's kinda overloaded with philosophical jargon, but still very interesting.

Follow up question:

This trope extends right through to the modern day, (perhaps just up to the end of WWII) with films still depicting battle ships or similar on a map. If the trope outlined by OP is true, but perhaps it started later, when did it start?

edit: Sorry OP, I feel I've derailed the post away from your original question. Hopefully you get the answer you were looking for.

Contrary to what most of the others have said, I believe that at the very least, Byzantine generals and their officers partook in planning such as what you have described. I will support my claim with just a few excerpts from just one of the many Byzantine military manuals from the 10th Century - The Taktika of Leo VI the Wise

The Taktika of Leo VI, Constitution XIII: The Day Before Battle, Paragraph 3

You will make every effort, employing scouts and spies, to record accurate intelligence about the enemy's movements and the number and disposition of their troops. This will allow you to make the proper adjustments [to your strategy] and not be caught off guard by them.

Constitution XVII: Surprise Attacks, Paragraph 68

You must always investigate in detail, O General, the quality of the force of our adversaries. You are to take the appropriate steps and organize measures to counter it. The arrangement of the cavalry and infantry formations and the lay of the land cause great differences in the strength of an army. An inexperienced person may casually look at them and be very poor in his estimates. To show the truth of my remarks, the following examples will be given here to readily bear witness to the theory...

Constitution XIX: Naval Warfare, Paragraph 41

Before the day of battle you, together with the officers under your command, must make plans about what must be done. Whatever this common counsel judges advantageous should be presented in detail and announced to the officers of the dromons so that they may be prepared to put those plans into action. In the event of an enemy attack, of course, a backup plan may have to be put into effect. Everyone will then be prepared to look to your dromon in order to receive a signal for what they must do. When this has been given, they will promptly carry out your plans. (This is also a useful example in refuting the commonly-held belief that maritime signal flags were a product of the Renaissance)

Constitution XX: Concise Sayings, Paragraphs 121, 122, and 126

Undertake military operations with intelligence and extensive investigation. If some mistake is made in on other matters , in a little while, perhaps, the mistake can be rectified, but errors made in war can cause lasting harm, for the dead are gone for good.

Study and carefully make note of the location of [your] camp, O General. Is it healthy and safe, or is it inhospitable and poorly-suited for your troops? Are the necessary supplies: water, wood, forage, nearby? If these are distant, it will be difficult and dangerous to procure them, especially in the presence of the enemy. Try and locate a high spot in the vicinity, and, if you find one, ascend it before the enemy and occupy it.

The cautious general should not only be good at making arrangements for what is likely to happen in time of danger, but he should also consider the unexpected and make plans for it ahead of time.

All of these sections emphasize the importance of military planning well before the onset of battle. Considering that both the Taktika of Leo VI, as well as its predecessor, Maurice's Strategikon, both include extensive and detailed diagrams of how to array the troops in battle formation, I am convinced that they must have had meetings to discuss the organization and movements of units for the course of battle. There would have been no way to effectively lay an ambush or designate a fleet formation without some kind of prior visualization.

The authors seem to hint towards these kinds of meetings in the Taktika of Leo VI and Nikephoros Ouranos, the Pracepta Militaria, and the Strategikon, but they never explicitly say "the general and his officers should convene around a table to discuss tactics using troop representations". More extensive scouring of further treatises may yield a more explicit example, but even lacking that perfect line, I am virtually certain that this must have happened.

I don't think so. I've certainly never seen any evidence for this. I'd suggest that such representations would not have been particularly useful, for several reasons.

1. Medieval generals didn't need maps and plans when they could easily view the battlefield in person. Battlefields were not particularly large. If an average medieval army was something like 10,000 men strong, and those men are arrayed in battle formation, the army isn't actually going to take up a lot of space. Unless you are talking about a really massive battle, it would be unlikely that the general would be unable to view the whole thing himself. These maps of Courtrai, Crecy, and Agincourt illustrate this. Even going into the early modern period, most battles took place in a rather limited area--the battlefield of Naseby was quite large, but it would but still have been possible to oversee it as a whole, as the artist of this depiction may have done, because there were only about 20,000 men on the field. Well into modern times we can see crucial battles which were tiny and easily surveyed, especially in the context of colonial wars. While it had always been useful at a strategic level to know where the major settlements and lines of communication were in relation to one another, was really only in the 19th century that military cartography really began to become crucial in tactics due to the increased size and dispersion of armies.

2. Even on the relatively small medieval battlefield, generals rarely tried to orchestrate the entire battle in person. Looking at Crecy again, Edward III divided his force up into two divisions (or battles) which he placed under his son Edward the Prince of Wales and the Earl of Northampton, while he supervised the reserves personally. In this case the commander didn't actually have to intervene in the battle personally, because his subordinates managed their respective divisions on their own. Splitting an army up into two or three parts like this was standard practice. Since so much of the burden of directing the actual fighting would be taken up by his subordinates, it was of limited usefulness for the commander to orchestrate everything from a central point. Complicated tactical manoeuvres were rare, given the undisciplined nature of armies at the time, and usually it was only in the power of battlefield leaders to bring their troops into contact with the enemy and provide an inspiring presence for them to win the fight. In most cases the commander's influence would extend only as far as appointing subordinates and perhaps leading the reserves in a decisive attack on the weak point of the enemy formation, or to shore up his own army's formation, if the opportunity presented itself. There was limited advantage to be gained by plotting the battle out when decisive maneouvres were next to impossible to pull off and the actual influence of the commanders on events was rather limited.

3. Intelligence was limited and the 'fog of war' in medieval battles was extreme. It was very difficult to find out exactly what was happening, because to do so required a scout to be sent out, observe, and return, by which point the information might be out of date. Even if the general knew where the enemy were, he'd have little chance of being able to correctly assess the exact size and makeup of the enemy force, their formation, or their intentions, which might change rapidly. In such a situation, instead of trying to plot every development on a tabletop, a process fraught with the risk of misinformation, and devise a plan of action according to that, it was safer to simply observe events in person as much as possible.

4. Much of the time, there simply would not have been time to set up a table and get your little wooden soldiers out. Many medieval battles were encounter battles, in which two armies, with limited knowledge as to each other's whereabouts, fought as and where they met. More often than not, given the personal motivations for war at the time which usually involved disputes over titles and successions, the purpose of campaigns was to bring the enemy to battle so a victor might be decided and the defeated party brought to terms. Campaigns based around the capture or defence of strategically important locations were few--the capture of castles as part of dynastic disputes aside. So preparation before a medieval battle was rare. Sand tables and the like became useful later in history as battles became vast, predictable, prepared events and generals gained better technology and command structures, as well as greater intelligence as to the composition of enemy forces, so it became possible and worthwhile to closely plan how an operation would proceed. In medieval times, with battles unpredictable and intelligence extremely limited, none of this applied.

Of course, much of my reasoning rests on generalisations, I've got a limited amount of evidence to back it up, and it doesn't apply to sieges, which were extremely common and lent themselves far more to precise planning, possibly including tabletop diagrams and little figures. But hopefully, in the absence of any other answers, I've suggested some pertinent factors.

If you want a really good representation of commanders surveying a battlefield prior to engagement the movie Gettysburg is an excellent representation of this.

It excellently illustrates the use of cavalry scouts reporting to local command (who were often traveling with the main body of troops) the locations of the enemy and the relative locations of terrain features for them to make decisions. Not to mention the urgency that commanders use to try to get a good vantage point.

As a modern reference, this trope is slightly more applicable. Due to higher mobility, greater distances of effective engagements, and smaller units operating more independently officers will commonly brief troops using sand tables (quick models in the dirt) rather than maps. Sand tables offer the next best thing to actually having eyes on an area of operation.

I know I am a bit late to the party on this question, but I recall reading a crusade article on the matter and it took me a while to track it down.

Medieval narrative in the 12th century was full of leaders using maps. One example, in an Old French narrative, describes Godfrey of Bouillon's tent in the first crusade stating that it contained "a world map to show the kingdoms."

[P. Mayer, "La chanson de Doon de Nanteuil. Fragments inédits." Romania, 13 (1884)]

There are others, such as in the Roman de Thèbes from the 1150s, the Romans d'Alixandre, and the 1181 work of Walter Châtillion entitled 'Alexandreis.' In all of these they authors talk about strategic maps being displayed, though they were often more often mappemonde rather than zoomed in battle maps. But, the idea remains - they are brought out during battles implying that the leader used them for fighting in some regard.

Now, there is an entire school of thought who thinks these French narratives have no idea what they are talking about, as many are fiction or much after the fact, and they were only using the map imagery for effect. This is a very valid criticism. Yet, I still bring it to your attention because at least since the 12th century, and probably before, the theme that leaders should be sitting in tents with maps has been a idea in western culture.

One crusade example of narrative includes Richard the Lionheart asking for a map of Jerusalem to be drawn by Ibn al-Athīr (d. 1233). Again, in 1270, William of Nangis describes that when St Louis IX was in route to Tunis, they were hit by a storm. King Louis asked the shipmasters for their opinion of their location in the sea, the shipmasters then produced maps and pinpointed their location for the monarch.

There are others, but you get the idea.

See: Benjamin Z. Kedar, Reflections on maps, Crusading, and logistics. In Logistics of Warfare in the Age of the Crusades. Ashgate: Hampshire, 2006.