2d - How can I identify feature regions in a procedurally generated world?

I'm building an Island. I use the classical heightmap solution : with a hill-building function, avoiding the corners of the map, I make altitude. Then, perlin noise give me some climatic variables to handle the biomes. Now, I'm facing two challenges who are, in some way, connected :

• 
  
  

  In Dwarf Fortress, one of the neat aspects of world generation is how the game seems to "know" areas, and give them names, though they are not rectangular shapes. I would like to be able to "recognize" my forests, my rivers, my hills... any idea what kind of algorithm I could use to scan my map and interpret its areas ? And how would you store that ? I'm using a basic C++ graph made out of a vector of vector of "tiles object".

  
  


• 
  

  This Island should be divided in political areas, not only purely natural regions. I could use mountains and rivers to make "natural borders", but my procedurally generated map doesn't garantee I will have nice "enclaves" that would form a kingdom ; I could find myself having a gigantic "ribbon-formed" political areas surounded by micro-kingdoms. Another possibility would be to look for appropriate areas for a city or a castle. Then, "grow" a political area around it. But there again, I'd like to have some well-known algorithms before trying to devise my own.

  
  

This question could be interpreted as a bit too vague, so one way of rephrasing it would be : how to partition (without modifying !) a procedurally generated world into areas suitable for gameplay ? Thanks in advance for your help.

Answer

Amitp suggests using watersheds to define various regions, as explained in his post on polygonal map generation. The watersheds are best seen by generating a map using his demo. The advantage of using watersheds to help subdivide continents is that it provides boundaries perpendicular to the shoreline, while mountains usually provide parallel boundaries.

If I were subdividing geographic regions, I would use a combination of mountains, watersheds, and edge detection on the various biomes on my map.

I'll also point out that political regions generally span many geographic regions. I would generate geographic regions first, then assign each region a desirability rating (is it a coast? is there gold? good farm land?) and travel cost (steep terrain? heavy woods?.) Then using your favorite pathing algorithm, generate a heatmap of travel between desirable regions. These will end up being your roads, and you can build your political boundaries from there. These boundaries will generally have many roads within them, and less roads between them.