Because the earth is a sphere, it actually doesn't matter where it is in the world, because it is an regional map. Plate Carreé projections (also called "equirectangular") were also invented around 100 BC, so having one exist in the middle ages actually is completely valid. In fact, the Mercator map, one which is usually imagined when you think about old maps, was invented in the mid 16th century. Latitude and Longitude were also invented by the ancient greeks, as evidence by this map made in the second century.
Although this map is inaccurate, Latitude and Longitude were, in fact, used.
There is, however, one important thing to take away from this discussion: if you make a world map, you will be forced to decide on a projection, or else have your world be literally flat. Wikipedia is a great place to compare what different projections look like- mercator vs equirectangular, robinson vs mollweide....