Kristo's School of Quality Mapmaking
Step Three: Mountains and Trees
This is the biggest, longest, and most boring step in the entire map design process. Now you must place all the mountains and trees that break up the map and make it look real. ALL wide open spaces need to be eliminated at this point. There are few things worse than having a large section of a map with nothing in it. When choosing your objects, you literally want to pick them at random. Under no circumstances should you repeat the same object over and over again. I cannot stress this enough. Monotone forests and mountain ranges look really ugly.
You should also be thinking ahead to the placement on mines and such on the map.
For example, the Lumber Mill has trees in it so groves of trees around it look nice. I've found that Sulfur Dunes are the toughest to make look natural; they stick out like the proverbial sore thumb. I usually go with the Abandoned Mine and set it to Sulfur only (bonus: it's inherently guarded).
When your foliage etc. starts to look real, and there aren't any wide open spaces left, you're done. With the addition of the random object tool in the Shadow of Death map editor, this becomes a lot easier. I like to use it to rough in natural features and then tweak it later.
Step Four: Mines and Defenses
At this point it makes sense to add in all the mines to the map. No doubt thereare logical pockets for these to fit in the trees and mountains, but if by chance there aren't, make some. One thing I need to mention: Every town needs unrestricted access to wood and ore. That doesn't mean little piles of it here and there, it means unguarded mines. Your map can be played on impossible, and you cannot survive without these mines. Rare resource and gold mines can be guarded, and I recommend a stepladder approach to defending them. Think about how important each mine will be to the overall success of the player its placed nearest to, and then defend it accordingly. For instance, an Alchemist Lab near a Castle shouldn't be too heavily defended because a Castle doesn't require tons of mercury.
Gold mines, on the other hand, should be adaquately defended at all times, as they are the most important. Another thing to look at when placing the mines is how long it would take a player to reach them. Lumber Mills and Ore Pits need not be more than one turn's movement away from a home town. Rare resource producers can be anywhere though. Part of the challenge of the game is being short on certain resources and having to find and control those mines.
I've put together a collection of map files as an example of how all this works. An explanatory text file is included. Download it here.