Procedural world generation oriented on gameplay features

Question

In large procedural landscape games, the land seems dull, but that's probably because the real world is largely dull, with only limited places where the scenery is dramatic or tactical.

Looking at world generation from this point of view, a landscape generator for a game (that is, not for the sake of scenery, but for the sake of gameplay) needs to not follow the rules of landscaping, but instead some rules married to the expectations of the gamer. For example, there could be a choke point / route generator that creates hills ravines, rivers and mountains between cities, rather than the natural way cities arise, scattered on the land based on resources or conditions generated by the mountains and rainfall patterns.

Is there any existing work being done like this? Start with cities or population centres and then add in terrain afterwards?

The reason I'm asking is that I'd previously pondered taking existing maps from fantasy fiction (my own and others), putting the information into the system as a base point, and then generating a good world to play in from it. This seems covered by existing technology, that is, where the designer puts in all the necessary information such as the city populations, resources, biomes, road networks and rivers, then allows the PCG fill in the gaps.

But now I'm wondering if it may be possible to have a content generator generate also the overall design. Generate the cities and population centres, balancing them so that there is a natural seeming need of commerce, then generate the positions and connectivity, then from the type of city produce the list of necessary resources that must be nearby, and only then, maybe given some rules on how to make the journey between cities both believable and interesting, generate the final content including the roads, the choke points, the bridges and tunnels, ferries and the terrain including the biomes and coastline necessary.

If this has been done before, I'd like to know, and would like to know what went wrong, and what went right.

Answer 1

Here's a great example of procedural terrain generation, using parameters like moisture, height etc... http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/

Answer 2

I believe I've been staring back at this question for the last three days, while asking myself how the procedural generation of worlds or even galaxies can, at the same time, be deterministic(such as always generating the same content from the same seed), look natural, and still have unique, interesting, unusual or even beautiful features in its landscape.

I keep going back to the same generic answer that this is going highly dependent on the genre of the game and its own internal consistent history within the story. For example, post-apocalyptic genre, why would anyone build a metropolis with massive walls in the middle of a wasteland, and make everyone inside of it live miserably? Why colonize such planets? In high fantasy, why make a city on top of a floating island? Why do dwarves make cities inside of mountains? And your generic evil enemy comes from fiery land with active volcanoes? Rule of Cool?

So it all goes back to your own answer where you input information into the PCG and it fills the gap, and also to the other answer about generating worlds which match plot lines and the overall story.

So plot generates gameplay elements which generates suitable landscape.

That said, I wonder if a story that generates a tree of consistent plot lines, will generate the overall gameplay design you're looking for.

(PS: These same three days thinking also made me come with another answer to a problem that may rise: there should be an automated test tool to check if the generated game design is sound, eg, you should have a medieval army having a hard time to defeat a generated fortress)

Answer 3

Only paper dealing with similar issues I could find off-hand is Stachniak and Stuerzlinger's "An Algorithm for Automated Fractal Terrain Deformation". It assumes you create the terrain first and deform it (or rather, let the algorithm pick the parameters to deform it with automatically) to fit your constraints later, so it doesn't answer the question directly. Still, the methods presented therein might prove useful for others with similar problems.

Answer 4

Wouldn't such an algorithm automatically generate more 'tactical' terrain when roads are generated between cities?

Assuming that roads can only have a certain elevetion change per distance, terrain height would be adapted to the heigth of the road, which would lead to generation of chokepoints whenever a road passes through a hill/ravine/whatever. Of course, the amount of change in terrain height would need to be limited too, or you'd have roads running straight through the highest peaks.

Answer 5

When I was at Cryptic Studios we were working on something like this for mission/quest generation. The designers specified mission objectives somewhat abstractly and it laid those out with some randomness in "player travel order" and cut paths between them.

An early version shipped with Star Trek Online as Genesis Missions^(archive). At the time we were very excited about it but I have no idea how much it continued after I left, or if it's available in the end-user Foundry tools. (Which was the eventual goal.)

Answer 6

A typical approach for procedural terrain generation is to draw specific features by hand and use the generator to fill in the rest. VTerrain is bound to have something interesting on this topic.

Answer 7

Lighthouse 3D has a good survey of some simple algorithms for terrain generation. If you're starting with a map that contains cities or other interesting areas, you could use some of these techniques to generate whatever terrain you would like. For example, intelligent use of the fault algorithm could be used to create cliffs or valleys around your city that would act as choke points. Also, using the circle algorithm would be a great way to generate terrian for turret placement. These are just some examples, but using these simple algorithms would be a fairly easy way to generate interesting terrain around your cities.

Answer 8

Maybe I'm oversimplifying, but why ignore the fact that cities are built on advantageous terrain, or for that matter, any size of a civilized area for whatever reason? Maybe the terrain offers a tactical advantage for a military installment or perhaps there is a lumber mill at the intersection of a large forest and a river that has a larger village downstream. Even "holy" places are based on terrain even if for the simple fact that that particular section of land was at some point deemed holy, etc. No matter what the consequences are, the final resting place of the overwhelming majority of civilization exists in a physical spot for very terrain-based reasons. Even in the case of a city sprouting up simply because there's enough trade happening between two larger cities to warrant a middle-man, if you will, that city location would be chosen based on the path of least resistance. It would be placed somewhere that offered good flat farmland for the local food supply coupled with land that lends itself well to the construction of roads. I'm sure you've thought about this...

So, if you're going to build the cities first, sure, why not? Why not build the city, village, settlement or whatever, along with a decent chunk of surrounding terrain, built by hand, that supports that type of establishment?

Take procedural biomes as an example. They're usually applied to pseudo-random temperature, humidity and height maps. If you've already designed the city (or lumber-mill, etc.) then you likely have a firm concept of what the land needs to look like, which if I'm not misunderstanding, is exactly your point. Take a fantasy building like Orthanc, replete with floor-plans and surrounding terrain, which you've dutifully replicated. Well, we know, depending on timeline, Orthanc was surrounded by a huge forest populated with Ents (tree creatures), etc. If you're trying to replicate that, then applying a random terrain makes no sense to me. That being said, once you've created this setting for the tower itself and the surrounding forest what's between Orthanc and whatever your next city is?

Simple approach might be writing your procedural terrain generation, place your setting inside of a randomly generated terrain system and lerp your heights out around your fixed setting and viola you can place Orthanc in many different randomly generated worlds (should that be what your after).

I think however, you'd be best off with a combination of setting, terrain and defined biome and making sure Orthanc gets placed inside of a procedurally generated large forest biome. Depending on how you code it, you could set min/max biome, terrain, humidity, etc. for each pre-defined setting or building or city that you've sculpted. Would this be a small task in a full fledged photorealistic 3d world? Obviously not.

I think if I were to attempt this, I would research coastline procedural algorithms first. Taking the approach that almost all civilizations throughout history have followed any coastline, be it an ocean, sea or large lake. It's the path of least resistance for growth since there's likely abundant fishing, trees nearby for wood, and certainly faster travel even with rudimentary watercraft (at least one-way).

I would think you would have to build completely backwards. Think, pseudo-random dots on a map representing points of civilization possibly with a noise algorithm determining the populations of those civilizations before anything else is determined. OK, so 1 point comes out to a population of 1,000, another 2,000,000 (or whatever ratio depending on your world population of course). Why? Why are those numbers of populations there? A population of 1,000 might be the little lumber-mill community. Maybe it's a mining community if it's on the north side of the map should you be creating a 3d spherical world. It gets a little fuzzy here because I don't know if you're going infinite in all directions making NESW pointless in determining biomes or if you want a very real "Earth" world where extreme north and south are always frozen, etc.

However, if you plop down your civilizations, based on pseudo-random noise populations I think we can safely assume a few rules (but maybe not absolutes) like... The larger the civilization, most likely, the larger number of useful resources on hand and the terrain to support them. Precious minerals, woods, etc. ad nauseam have to be present or there must be a huge trade system in place to support such a vast enterprise. Based on that you can start generating highways from city to city and roads to the outlying settlements like a deep mining operation, etc. Pick points of civilization that would formulate good coastlines and drop the population points completely off the map where you need to fill your oceans (or maybe you have Atlantis's in your world, or offshore oil drills). Do the same for ellipsoid patterns inside those coastlines to represent your larger lakes, or forests, etc.

Filling in the terrain in-between again depends on your biome approach completely. If you have a infinite in every direction world then put Orthanc down wherever it fits population-wise, force it into a forest biome and build around it outward until you get to halfway to your next preset destination which your algorithm is doing the same procedural generation around. Lerp/Blend the two terrains together as they meet and yes this is an obvious oversimplification.

Without a real working knowledge of what you're actually trying to accomplish mechanically I can only throw out ideas and possibly bad ones. I think your approach has merit, even if it is completely fantastical in reality, because you're targeting what's always the most important factor in any game: Is the player having fun? Or, am I creating a random world that isn't boring and thus, not fun?

What would also get interesting, and this could be a part of the generation of civilizations in any game, terrain first or not, are what happens if you plop down 2 large cities next to each other? What does it mean? Are they at war? Are they massive trading operations between two flourishing nations? What kind of enemies lurk in the woods of that lumber-mill?

I do think one thing is certain if you're trying to build terrain based on "cities" and that is the terrain would be directly affected by the population of said city, both in landscape and natural resources (and perhaps even in beauty).

I'm not sure if I actually answered anything or if this was appropriate but it's a very interesting concept and I'd love to hear where you head with it.

Answer 9

I would do generate the game-play features concurrently as part of the same process. There are a number of ways to build terrain based on rules. This YouTube talk by the Path to Exile devs is a pretty good example: https://www.youtube.com/watch?v=GcM9Ynfzll0. Also, for a less pre-built aproach, this looks interesting: https://www.youtube.com/watch?v=RAtdFKiqs34. You could use perlin noise to generate heights for each voronoi vertex and go from there