This is theoretical, not something I especially want help with. I was messing recently with the "diamond-square algorithm" and related things, and used the "Voronoi algorithm" plus that to make random colored regions on a random map, like this. (Terrain too.) The results (done in Python; ask if you want the code) sometimes look plausible, but it makes me wonder how it'd be possible to build boundaries around terrain features like mountains and rivers, not just land vs. water. I could see doing something that plays a mini-game of Civilization, with little tribes moving around and claiming territory. That doesn't sound suitable for quick generation though; you can make a 513x513 heightmap in about five seconds, then determine terrain and place random resources in another few seconds -- those things are simple algorithms -- but that kind of country generation would be much more complex. I know that Unreal World (not related to Unreal) does build villages on top of random terrain, but it doesn't make up things like history and government. By the way, I was shown this paper about procedural terrain generation, and found it useful.

I'd go with a more real-life approach - why do country borders exist as they do?

The simplest approach would be to triangulate the map. Doesn't really matter how, just split it into irregular triangles. This triangulation can assume terrain features. for example, make highest peaks vertices.

Then assign each triangle a set of weights. There's several criteria which determine value of that chunk of land: food, building materials, environmental friendliness, cost of construction, ... It would probably be necessary to balance these out among themselves, possibly in relation to geography.

Next, define nations. Each nation has a set of weights as well indicating their priorities and needs.

Plant these nations into several squares, and start iterating. The expansion criteria would be a nation's average population density. A nation with low tolerance for density would have expansionist tendencies, a nation with high desire for resources would too, but a nation with priority on buildings wouldn't.

All of this is highly suitable for vector processing, since it's all just a set of values vs. weights. Once the iteration runs long enough, simulating proper population growth, the borders would settle (genocide is not an option, so no nation can be removed).

This should give you a fairly balanced distribution of the world, and borders would be more or less realistic. And since the original topology would be designed with geographic features in mind, borders would resemble those (border running on top of a mountain range).

But as always, this type of content generation is more luck and tweaking than science.

Quote:Original post by Kris Schnee... it makes me wonder how it'd be possible to build boundaries around terrain features like mountains and rivers, not just land vs. water.

I'd use a simple flood-fill algorithm, expanding from each country's starting point in parallel. If you slow down the expansion at rivers and high slopes, you would pretty much get the results you're asking for.

Quote:Original post by Kris Schnee
By the way, I was shown this paper about procedural terrain generation, and found it useful.

Do you know where they found that? I'd love to know if there was a place that had a wealth of papers such as this.

Awesome, thanks!

The strategy game "Dominions 3: Awakening" features a random map system like you're talking about. I believe it starts by creating a heightmap, then divides land and sea into regions that look very much like a voronoi diagram. Some region borders have high mountains along the border to block movement, and the coastal borders follow the water line. It takes a while (up to a few minutes) to generate the map this way. Here's the URL for the game; the same website also has a forum where you *might* be able to ask the devs about how it works:

http://www.shrapnelgames.com/Illwinter/Dom3/1.htm

Personally, I'd create the voronoi diagram first... Make random points, calculate polygonal regions around them, then set some to be "land" and some to be "sea" etc... Place mountains and rivers along the borders. Jiggle the lines a bit so it's not all straight polygons. This should be faster than starting with a heightmap but might not look as natural. I've only used voronoi regions in a space-based game before, that didn't have such terrain features.