You'll get a better idea about how this works over the next week, we just sent out our first two video devlogs to a couple of sites to hope they got posted and we're going to be setting them up publicly over the next few days - they cover Scenario Selection Generation (the randomization for a given scenario) and then Scenario Layout along with Map Functionality.
I'll try and break it down - each of the scenarios is handmade, meaning the background is a static sprite(s) (the map itself) overlaid with some details. The nations, leaders, and champions are all crafted in advance as well. Heroes are randomly generated at game start based on a selection of variables, as are ruins (with some exceptions) and a few other elements.
Inside of that structure Scenarios contain map variations, not just in the how the map looks (an island missing, mountains where their were plains) but also variants on the available nations, their individual settings, cultural values, and overall statistics (Such as frequency of lore, which champions exist and their agendas, what type of ruins are common, etc). These are set by the Scenario Generation process, where you go through a series of King of Dragon Pass esque questions "Who served you most loyally, how were you sealed away, what kept you alive during your slumber, how did you interfere with teh world" type questions. The world that results is a variant of the Scenario, but still maintains the general idea and character.
The other point is that Scenarios are VERY easy to make, though of course it takes time to make a nicely balanced one. We accomplished this by having the POI system. All someone needs to do is have a "map" image, then click on any point and say 'City, Village, Ruin, etc'. At start the game spawns all the necessary details around that point, the shields depicting value, banners for the army, dynamic naming, etc. Create a POI, assign it to a nation, which has a leader and a culture, and that's enough for it run at a high level - you can also get down into the details of each POI and customize them further.
Using this approach, each Scenario has a unique look, feel, and overall strategy.
We went with this approach not just because procedural generation presents its own set of challenges, but because our gaming history is greatly informed by modern Board Games (EU follows a similar path of inspiration). Seeing the re playability that can be accomplished in a strategically designed world (see the War of the Rings board game, Twilight Struggle, Here I Stand) is inspiring, and we think we've reached a respectable level of the same with That Which Sleeps..