Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
    
Thank you for the correction, and sorry for the bad quality of my english :) –  Raveline Aug 10 '11 at 15:02
    
Your English is great, it's just that the "title" is preferably phrased as a question on the StackExchange sites. –  dlras2 Aug 10 '11 at 15:13
add comment

3 Answers

up vote 11 down vote accepted

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.

share|improve this answer
1  
Thank you for your help. I already knew Amit's solution, and though I found it quite elegant, I do not know enough about the maths behind (I'd have to study them, which I'll do sooner or later, but not now !). Thinking in terms of watershed could certainly help me and tweaking the river-generation algorithm should not be too difficult. I love your solution for building roads and political boundaries, I have to consider how exactly I'm going to implement it, but the idea is great ! –  Raveline Aug 10 '11 at 16:57
    
@Raveline - If you use the political boundaries generation, comment here and let me know! I'd love to see how it turns out. –  dlras2 Aug 10 '11 at 17:34
add comment

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.

share|improve this answer
    
I understand the reasoning, though I'm not sure your path is that easy... Since my project is quite humble, I'll try to patch something not too sophisticated, but without polygons, since it would mean studying much more the algorithms implied. (P.S. : your website is an amazing source of inspiration and I love it !) –  Raveline Aug 10 '11 at 17:00
2  
the polygonal map generation article was superb. –  Raine Aug 10 '11 at 17:01
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.