Wednesday, July 13, 2011

Political Landscape

I was on my way to create the first city. How would I do it? Should I start from a street layout, key landmark locations and fill up the gaps? Soon I faced a simpler if not bigger question: Where should I build this city?

Cities do not happen just anywhere. Geography is key, but it is more than that. Even social and political factors have a lot to do. For instance, it is unlikely that two large cities will end up being too close. Somehow people in the middle will gravitate to either one and leave a gap in the middle.

This post is not about cities but rather about everything that is around them. As usual my goal was to have an algorithm that required little or no human input but still produce believable results. I saw that modeling some form of historic development was the simplest way. This is how it works:

The first step is to identify suitable locations for a new settlement. Obviously the slope of the terrain had a lot to do. Both valleys and mesas make for nice locations, so I just placed points where the derivative of the terrain height was close to zero. I also made sure these points would not end up being too close from one another. The following screenshot shows the results:


The slope intensity is shown in red, the settlement points appear as green dots.

The people (or smart things) in each settlement would naturally expand. That is the second step. They expand as much as possible considering the geography and most important, the expansion of neighboring settlements.

This results in something close to a Voronoi graph:


Each colored patch shows the area of a different settlement.

The next step is conquest. Settlements conquer their neighbors. For any two neighboring settlements the odds of a conquest is computed. This depends on how much of a border they share, how steep the terrain is at the border. And there is also a cultural element. Each settlement has a culture value, which mainly comes from bio-geological factors. For instance a settlement that covers mostly fertile land will have trouble conquering a settlement that is mostly on desertic terrain.

When two settlements merge, a country appears. Countries are allowed to grow in this phase, but only up to certain point. As a country grows it becomes less aggressive, nearby settlements may be snatched first by a more motivated smaller country.

The following image shows a newly formed set of countries:


As you can see the original settlement lines still persist, but they became sub-divisions inside a country: provinces, states, counties, any way you may call it.

Each country needs a capital. That is the next step. A capital usually should be as far from neighboring countries as possible, but as close to all other provinces as possible too. It is a delicate balance, and it can be tweaked towards either extreme. I picked a balance that made sense to me:


Here the province containing the capital appears highlighted and its location circled in red.

The last step is to create the main road system. Neighboring cities should be connected, but not every time. The cost of building roads in steep terrain had to be factored. Also, existing roads should be leveraged instead of building new ones. And last, roads should avoid crossing country lines unless absolutely necessary.

I used A* path-finding to bring all these factors together, here you can see the results:


Note that not every province is connected to its neighbor. This usually happens when mountains make a new road too expensive and it is better to just go around the mountains.

So far I am happy with the results. The political divisions match the landscape and terrain types. The roads make sense, but also leave place for exploration.

The next phase is to break down each province and build a large city starting from each green dot. I'm already working on this and it is quite interesting. As soon as I have some results I'll post about it.

35 comments:

  1. If you want to keep the borders as defined by the Voronoi raster, I suggest perturbing them a bit with some kind of distance function.

    I've done such a thing myself, see here for an example:
    http://dl.dropbox.com/u/17511787/latest.png

    ReplyDelete
  2. This is amazing! And the scope is evidently there to enhance the history(legend)-generation conquest part to something similar to Dwarf Fortress!

    I could see your technology producing a procedurally-generated version of Morrowind, which would be amazing.

    ReplyDelete
  3. @Wouter: Thanks for the hint. It improves the look. I will add it.

    ReplyDelete
  4. Cities usually start out as villages and villages usually start out because there's some resource to be exploited nearby or a trade route to support (like all the cities built on rivers, or villages where the goods are shifted from desert caravans to donkeys). A really thorough city generation map would probably have to include this, probably with some ideas from Guns, Germs and Steel.

    ALl this stuff looks great, though.

    ReplyDelete
  5. This: a system for specific resource placement.

    ReplyDelete
  6. A fantastic system you've built there and I definitely think it's believable. I'm curious though; the system takes into account the slope of the land, but does it take into account resources. I believe most villages start out close to a water source. Then other resources could be taken into account such as food supply and metals/lumber etc.

    ReplyDelete
  7. @Megazver: Yes, water is a big factor. I do place some points in the coast, but failed to mention that. I do not have rivers or lakes now, I don't have a nice way to render them so better to stay out.

    I plan to add small secondary towns based on the roads generated by the initial settlements, if you see the green points are the main cities, state capitals. There will be other points of interest like smaller towns, ruins, mines.

    About other resources than water and geographic properties as seeds for cities, I'm not so sure. You never see a quarry in the middle of a city. So I rather build the city first and then add a quarry nearby. Even if it may seem counter intuitive, I will add resources after the cities.

    ReplyDelete
    Replies
    1. You do if the city is Aberdeen, Scotland. :-) I think it is a case that the city was a lot smaller when the quarry was started; but was still in use when the major expansion of the city took place.

      Delete
  8. Well, I was thinking about modeling the resource placement abstractly first. Just split the map into zones, just like you did, and give each zone a list of resources it ought to have based on its geographic position and other stuff. And add the actual 3d stuff on the map afterwards, yeah.

    And by resources I also mean agriculture and livestock.

    Also: http://blogofholding.com/?p=507

    ReplyDelete
  9. Miguel,

    I’d like to ask you about some of your work. I cannot find an email address for you. Could you ping me at mine?

    ifischer@robotentertainment.com

    ReplyDelete
  10. @Megazver: Thanks for the very interesting link.

    @ArchDragon: Yes, for procedural things sometimes you don't need to be accurate in the modeling if the results are believable. Once the world is created you won't be able to tell if the mine is there because the city was there, or the other way around.

    As I see it, it depends on how hard is to find a believable location. For instance it would be hard to design terrain after cities so clearly terrain goes first. The same rationale applied to resources and cities made me chose for placing cities based on geography, and then resources based on cities and geography.

    Time will tell if this is really a good idea.

    ReplyDelete
  11. Bearing in mind that I have not researched this in great detail, the shape of the countries you come with bug me. They're all so long and serpentine. Intuitively, it seems like that would be less than ideal for infrastructure--it will be harder to move resources to the ends of the long thin sections without intruding on another nations soil, which will make it a devil of a time to defend those end points.

    I realize this happens sometime in real life, but there's almost no point in the entire map where a country is more than two provinces wide. Consequently, I only see a single capital where the province containing the capital doesn't border on a rival nation. Heuristically, it seems like provinces which share borders with multiple provinces of a rival nation should get a slight increase to the probability that they are conquered, to round out the final country shapes a bit more.

    ReplyDelete
  12. @Abnaxis: You may be right, I will double check for bugs.

    Long serpentine countries could be happening because of the extreme geography of this island. It cannot be fully appreciated in the screenshots, but there are very large mountains, which form some kind of long and serpentine system. Conquest is easier along the valleys which are serpentine too.

    Mountains are game-changers I think. Look at the Tirol in Austria (http://www.lib.utexas.edu/maps/europe/austria_rel99.jpg). It looks close to the country things my system does.

    As you say capital provinces in most cases share a border with a different country. The criteria I use considers more the location of the green dot. You will see that even if there is a border the location of the city is far from the border.

    I could make it so there are no borders if possible, but to me the capital should be as close to any other province as possible. It may be harder to keep a country together than invaders out.

    ReplyDelete
  13. Cool! I've been interested in a project along the same lines.

    You might want to generate cities and boundaries in several phases of history, so that you can have different rules to match the changes in transportation and settlement size. That'll give you variety and history.

    In early times, mountains and rivers are barriers to travel, so they're good places for boundaries. The Rhine for example was a boundary of the Roman Empire. Early towns would likely form where there's good (mostly flat) farmland and building material (wood, straw, mud).

    In the middle times, rivers and seas became important for travel. Some rivers remain boundaries between countries but others become central to a country. In the U.S., the Rio Grande, Ohio, Mississippi, Missouri, Colorado, Columbia, and Red Rivers are part of state boundaries along part of their course and interior to states in other parts. Places where rivers meet each other, or where rivers meet the sea, are good places for cities: San Francisco, Paris, Hong Kong, Cairo, London, Vienna, Shanghai, Budapest, Istanbul, Sao Paolo, Belgrade, Portland Oregon, Timbuktu, New Orleans, St. Louis, Chongqing are all of this sort. Iron, stone, and other materials become important so you might want to place these materials in the middle phase.

    In later times, roads/rails took over for travel and rivers became less influential in forming borders. Warfare can join or split countries to make things look less uniform.

    ReplyDelete
  14. Thanks Amit, that is useful information. You have helped me already, your page on world generation (http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/) gave me the idea of starting from voronoi cells.

    ReplyDelete
  15. looks impressive, but I would say that the roads might have to focus more around the captial, as this tends to be the end point for the majority of major roads (all roads lead to rome!)
    And towns should form on crossroads (and of course river crossings, but without those it's kind of tricky

    ReplyDelete
  16. @Anonymous: Thanks for the hint. At some point I thought about forcing road connections to the capital, but was not sure about it. It made sense as you say, but I also wanted to encourage exploration and taking risks. If the road system is too good there is no point in taking dangerous shortcuts.

    ReplyDelete
  17. I'd just like to say that I'm fascinated by your procedural world, I'm always excited to see a new post. Some of this stuff goes over my head, but I'm really interested to see where the project goes :)

    ReplyDelete
  18. I've discovered this blog recently and read only of it. This particular post however awed me in how far you are taking this procedural thing in everything!

    Great, great work!

    And a question, if you see it:
    It seems at the beginning of your blog you are posting about stuff you've already done, at some point though you started posting about stuff the same time as you are developing them. When was that exactly? There are probably some interjections too like your recent tree post (I assume you had done that back when you were posting a lot about trees)

    ReplyDelete
  19. @Stankor: Yes, the posts come in any order. Each topic is long on its own, if I had to cover it sequentially the blog would be about only that topic for too long. I still need to cover many things that I have done.

    ReplyDelete
  20. Thanks for the reply!
    It would be nice if you mentioned which posts are about recent developments and which cover past topics, just so we could know about where you are right now. For your future posts, I mean.

    ReplyDelete
  21. I'm looking to use (or build) something like this in a science fiction based game I'm working on, which leads me to offer a few minor suggestions:

    1. Non-human lifeforms could have different needs, including sociability and resource requirements. Rather than a fixed value for these species attributes, it might be interesting to use sliders to enable interesting alternatives to human patterns. Could an avian or burrowing species prefer high mountain peaks for settlement? How might a greater level of sociability affect population spreading? (And so on.)

    2. Another important factor in determining the processes of settlement and conquest is technology level. The earliest human civilizations formed at the fertile mouths of river deltas (Nile, Indus), but with advancing technology came less dependence on easy agriculture; eventually arcologies might be built anywhere. Similarly, sufficiently advanced civilizations should have a greater ability to absorb or replace less advanced population sites.

    3. A fantastic reference for this kind of stuff is _The Evolution of Civilizations_ by Carroll Quigley. It's better IMO both as an explanatory system and as a cookbook for procedural world design than _GG&S_.

    4. I'm really looking forward to seeing the population-spreading and political-border generation system come together with architecture generation. The bibliography that Will Wright used when designing The Sims might be very useful here -- in particular Alexander's book _A Pattern Language_ might offer some valuable practical ideas for procedural architecture generation.

    ReplyDelete
  22. Geography is definitely important. Depending on the species involved, access to a reliable source of fresh water is a must. Look at just about any map and you will see that most of the cities of the world follow the paths of major rivers (and their tributaries) or which are otherwise situated near water access. Tapping into an aquifer is also viable of course.

    I am interested in how you will approach city & settlement generation. Will these locales be placed as complete structures, or rather as ones that grow over time. Afterall the longer a settlement exists in an area, the more opportunity it has to grow and to alter the surrounding terrain to suit its needs.

    There is a very nice diagram (from the 1st edition of WHFRP) that shows how smaller settlements are clustered around larger ones. Cities are often dependent on the existence of these smaller communities for resources.
    Example 1: http://imageshack.us/photo/my-images/4/cities01.gif/
    Example 2: http://imageshack.us/photo/my-images/16/cities02.gif/

    ReplyDelete
  23. @Alluvian: Right, if I could do rivers and lakes no question they would determine city location. Bad news is I probably won't have time to have realistic rivers so they will be out, at least in the first iteration of this project. We could assume rivers in this island flow underground and still somehow influenced where cities appeared.

    I think a strict cause-effect model would not be very good. A city may spawn for so many different reasons that sticking to rules will eventually limit the output. My point is you need pure randomness too. Let me provide an example:

    My hometown was founded in the 17th century. Population hovers around 250,000. It is a Province capital. It is not near any river, resources or anything like that. It is perfectly away from any coastline, which is hard because this town is in an island. So how it ended up there? Pirates. My ancestors were so fed up with the pirate raids that they moved to the geometric center of the island.

    You can say in this case the Pirate Density rule determined the location of the city, and add this to the system so eventually a city like my hometown can be produced, but then what about many other towns which had similar wacky origins?

    You can see it the other way around too. When you see my hometown's location on a map you don't scratch your head in disbelief. The town is actually there so you assume there is a reason: pirates, dragons, rivers, saints, it is always something, and in most cases it is not there anymore.

    My point is when approaching procedural generation, not every time the best simulation produces better results than a basic simulation with some chaos on top of it. You cannot explain chaos, but most humans won't care about explanations if the thing is already there to be experienced.

    ReplyDelete
  24. @Bart: Thanks for the input. No question the comments here are already more valuable than the actual post.

    Even if some of my cities are inhabited by fish-like creatures, I'm going for the human model and scale. Political divisions, city layouts, architecture, will be reminiscent of what we humans have.

    Non-human settlements are an interesting possibility, but it creates too many questions. These beings could even inhabit other dimensions, producing cities like Lovecraft's R'lyeh. Other cities could be Hives, or could be made of water or energy channels. An entire civilization could be just a parasite of a planet sized creature... remember that city on the back of the turtle thing?

    Anyway you need to draw a line and say some things are just not possible in your world. For this project I'm sticking with the human model, which allows for a lot of drama anyway.

    ReplyDelete
  25. Now this is an interesting blog. Been thinking about developing pretty similar system to aid content creation, although from the perspective of probability distributions. Cities have log-normal size distributions etc.
    Great work!

    ReplyDelete
  26. MCeperoG, thanks for the response.

    If non-human modeling doesn't advance the goals you have for the technology you're developing, I understand not spending time on those features. But I admit I'm hoping that you may choose at some point to license (not give away! ;) this tech as an engine; in that case it would be nice if key control values could be exposed as parameters.

    ReplyDelete
  27. @Bart: Yes, so far no hard-coded or magic values in what I do. If I ever release any content edition tool, these parameters would be available to the user. Still, the results you may get are largely controlled by the nature of the algorithms. Parameters alone won't get you too far.

    I'm enjoying your blog, btw.

    ReplyDelete
  28. A thought for when your generating cities, would be eventually implementing a little bit of cultural blending. Cities that are near, with easy access, to each other would gain some architectural features of the other country, probably superficial elements or ones that were already similar beforehand.

    Also will you also, eventually, give each culture their own 'city plan'? Because different cultures have different priorities when designing cities, not mention cities that are unique for some reason-Rome, D.C., the Forbidden City.

    ReplyDelete
  29. I have plans laid out for cultural blending. This is something I mentioned a while ago when introducing my architecture system. Not only a city can have a blend of buildings inspired by the style of neighboring countries, the blend can happen within a building itself, for instance a mostly European building featuring north African style windows.

    About culture depending city plans, I'm not considering it. It would be a good addition, thanks for the hint.

    ReplyDelete
  30. Also an interesting idea might be that colonies of a state might be more culturally tied to the state out of want for societal cohesion. Similarily, border towns may either be weak culturally, or identify VERY strongly with their percieved nation-hood so as to keep a sense of 'them' and 'us'.

    Other interesting factors might include the similarities in climate, topography, and soil grades. You mentioned it already, but some cultures may be more inclined to inhabit areas they 'grew up' in. Dessert-people may thrive in a lush environment if they learn to adapt to using the resources around them, or may collapse if they either do not, or do, then over-harvest the area they are in during a boom-decade.

    ReplyDelete
  31. Similarily, a society used to lush environments with a long growing year, good harvests of their desired plants, and resilient soils and forrests would find themselves at odds in cooler or hotter climbs. Those areas would provide them with challenges of prefered crop failures, new diseases, resource-mismanagement in the form of over-harvesting of trees and crops, etc. If there was some way to calculate 'failed states' that overharvested frail resource areas, that were then re-claimed by a nation with either better technology, smaller populations, or better trade networks (to provide that area with food when poor years of harvest makes food scarce)then you have an instant 'ruin generator'.

    Just thoughts. All likely painful to create and manage. :>

    ReplyDelete
  32. @Anonymous, it turns out you don't even have to leave your house for those things to happen.

    Variations in temperature and rainfall over the past 10,000 years have more than once altered the kinds of plant and animal species that thrive in Europe. These changes actually caused mass migrations, altering settlement patterns.

    It would be *very* interesting to see a political map generator that took these kinds of long-term effects into account. ;)

    ReplyDelete
  33. Love it! This post was actually the one that drew me to read the others (not ALL the others, I admit, but give me time :D ). Procedural population and infrastructure generation is utterly fascinating to me, as well as a necessary step to a fully generated game world, which I very much hope this kind of technology turns into. I defer to your amazing skill in such areas, as I am primarily a physicist and know only how to model simple systems computationally, and hopefully my following two observations are not too ill-informed.

    I would like to reiterate previous comments on resources. Once you get rivers and lakes, of course you can take those into account, but even before that would it not be fairly easy to seed such things as woods (you already generate trees, just get a density function), fertile land, hunting grounds, and minerals? From there you can form population centers around these things, as well as have the "conquering" process take these into account, as nations want their neighbors' resources.

    If you do the above, since you are running this as a forward-in-time simulation from procedurally seeded cities to political areas, why not take the first step back a bit further? Start with a very low, sparse, and nearly homogeneous population over land, and run a diffusion algorithm throughout the time. Start by having them gravitate to easily towards resources and towards population centers, but with a diffusion coefficient and a friction coefficient across less-transversable terrain; meanwhile have population grow as a function of food availability and current population. Have the resources operate on a hierarchy such as food (hunting early on, farming later) > building and tool materials (wood and stone early, metal later) > transportation availability > [possibly] energy resources. Have that go until it defines population centers, then assume those population centers become political entities and run the simulation like you have.

    I know I'm basically saying to build a socioeconomic and history simulator, but I think that would be pretty cool, as well as having several peripheral advantages. It would allow you to define people groups (those areas that have had little population flux from outside areas for a long time) which would allow different regional flavor. It would let you seed any game that this turns into with a developed history. It should scale fairly well, operating with new resources or elements with just an added variable.

    That being said... I have no idea how much resources this simulation should take up, depending on your scale and resolution it could be quite a bit.

    ReplyDelete
  34. Some things might be able to be made completely random, but so much hinges on the development of the culture at hand.

    Does it value and harvest alot of iron? If so, it's going to need either coal, or charcoal to get the job done.

    Does it value pastoral activities, and agriculture? Then it will need to have hardy soils to withstand mineral depletion and over-grazing.

    There's alot of little things that could be made random, but I'm lead to believe that this might require a good bit of research to figure out what sort of environment can adequately support what kinds of cultures.

    ReplyDelete