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

Question

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 1

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.

Answer 2

To add to Dan Rasmussen's answer:

One of the main reasons I switched from Perlin Noise (this project) to using polygons (this project) is that polygons provide some nice structure for assigning larger areas (political regions, forests, deserts, named areas, boundaries, etc.). Starting with the structure and then generating the map is similar to polygon rendering — something that is relatively easy. Starting with the map and then inferring the structure is similar to computer vision — something that is relatively hard, but possible. I want both the structure and the map so I decided to go the relatively easy route of building a map on top of the structure (nodes and edges).

Even then, I found that I wanted larger structures than what I had generated. Watersheds were one attempt to build those larger structures but I need to try more approaches of grouping polygons together. I haven't found something I'm happy with.

I'm not sure how Dwarf Fortress does it. Given how brilliant those guys are I wouldn't be surprised if they have a sophisticated “computer vision” type of algorithm.

Answer 3

For your first question, my best guess would be to use an edge detection algorithm to find the limits of your natural regions (forest, hills, ...). Lots of algorithms exist for this kind of problem.

For the second question, you could use your own idea to spawn a castle (usually on top of a hill for good defense, and near fresh water), then use a voronoi algorithm to have regions around each castle. You can use noise or your biomes limits to make the boundaries more realistic.