Sunday, July 24, 2011

City Lots

Last week's post showed a practical way to create countries and provinces. The next logical step was to split the resulting regions even more and produce cities and even lots for individual buildings.

My approach as usual was to find a sweet-spot between effort and realism. I made geography the main influence to city location and layout, with some hints from cultural properties.

First I subdivided the regions I had found before. I added a new set of points and computed the resulting Voronoi for it:


Yes, it is quite messy, but it will clean up very nicely later. Each patch in the previous image is a few hundred meters diameter. They are roughly the size of a real-life city block.

Two things about this Voronoi phase: Seed points were placed where the slope was maximum. This is so the boundaries would end up in places where the slope was not too high.

Also the distance function is warped in the Y coordinate, which is up/down in the world. The warp makes a difference in the vertical axis weight more than a difference in the horizontal axis. This has an interesting effect on the resulting Voronoi cells. They are not convex anymore in Euclidian space, and they tend to be constrained to areas of similar altitude. Later you will see why this helps.

It is time for clean up. First I removed patches in the frontier with another province. I wanted some undeveloped space between cities.

Then I removed patches that were in steep terrain. This is controlled by a cultural parameter, since some cultures are better building on the slopes.

Here you can see the results:


It is harder to see in just a screenshot, but the resulting cities end up in mostly flat locations. They still make use of interesting places like some mountain tops or the border of a cliff. This is thanks to the peculiar characteristics of the earlier Voronoi phase.

Next I extended the roads so the city blocks would be connected to the main road system:


At this point I had the city mapped out. The next step was to break down each block and determine the location of individual buildings.

There was one hairy problem. All this generation so far was done in two dimensional arrays, where each cell of the array was roughly 5 meters wide. My architecture system, on the other hand, is based on vector shapes. Somehow I needed to convert the 2D maps into shapes before I could feed building locations and sizes to the architecture layer.

The first step was to clean the 2D map. I filtered it to make sure there were no weird pixel configurations ending in non-manifold shapes. I also made it all just two values: 0 for empty and 1 for taken. The following image shows the resulting bitmap for one area:


So it was about converting a map of bits into polygonal shapes. I wonder where did I hear that before?

At the beginning of this project I considered representing voxels just as bits and then produce smooth polygonal surfaces by using mesh relaxation. I did not use that method for the virtual world at the end, but all the work I did back then became really helpful for this task. It was pretty much the same problem, only in 2D.

The first step was to create a Lattice of points, but only for those cells in the boundaries; that is, when the 1 became a 0 or the other way around:



Next I applied my old smoothing algorithm to the lattice grid. For each point a new position is computed based on the two other points that are connected to it. After enough iterations it not only becomes smooth, it actually flattens out and sharp features appear.

Even if sharp and flat, there were a lot of vertices in the resulting polygons. I used some form of greedy simplification to take them out:


Not bad. While it is all polygons now, this is still far from what the architecture system can take.

In this system, buildings start from what it's called a "scope", which is pretty much a 3D box with some orientation. Even round buildings start from a scope. Some buildings may span from one scope to another, like a castle for instance, which may be composed of many scopes bound together by hallways, flying bridges, etc.

I devised several methods of cutting these polygons into boxes. Each method produces a different feel, and each one can be controlled by some parameters. All this is determined by the culture settings of the city.

These methods work in two phases. First they subdivide polygons until they are roughly square:

And then they output actual boxes for building scopes:


In this last image the boxes appear in black. This is where the buildings will be.

As you can see, the buildings closely follow the roads and make good use of the space available. Not every block has to be filled with buildings. Depending on cultural or even random factors, there could be parks or entirely undeveloped lots. Some further blocks could be marked as agriculture, if the climate and culture allows for it.

At this point you may be curious about how these lots would look over the terrain. It is quite cool actually, I will post soon about it. As usual I look forward to you comments and ideas.

25 comments:

  1. very cool stuff! how do you plan to handle inner city road?

    ReplyDelete
  2. Dude, you are a god to me. Really.

    ReplyDelete
  3. Truly amazing, but I'm wondering how you'll tackle the types and locations of buildings. Do you plan on using something similar to a simplified Burgess model with a "central business district", or will there just be scattered buildings for now?

    Sounds pretty complicated, but I really like where you're going.

    ReplyDelete
  4. Really interesting, I can't wait to see how this entire project turns out.

    Did you say you aren't going to have rivers and lakes?

    ReplyDelete
  5. Truly amazing stuff. One only consideration would be about buildings facades. If you take a look at ancient european cities, building perimeters are often not exactly rectangular but their facade follows the street line.

    Keebus

    ReplyDelete
  6. I have two suggestions. For one, think "wild west". Towns might form along central streets and sprawl from there. Since you're doing this after the road system, maybe it would be wise to make a regular distribution of buildings around major junctions.

    Also, how "modern" is the world you're generating? If it's 1850+ then some cities will be organized along city blocks, a relatively easy thing to generate.

    ReplyDelete
  7. A paper on generating city layout, if you're interested, focused on deciding what different areas are used for...
    http://www.groenewegen.de/delft/thesis-final/ProceduralCityLayoutGeneration-Preprint.pdf

    I'm writing my own (real-time) world generator, so this blog has been very interesting so far. I'm certainly having to investigate using some OpenCL.

    ReplyDelete
  8. @Anonymous 0..N:

    > how do you plan to handle inner city road?

    You can see inner city roads already. They form when two blocks touch each other. They will get geometry and texturing depending on the type of civilization and population density.

    > how you'll tackle the types and locations of buildings?

    Each civilization type will have a list of buildings type that are likely to appear in a city. This goes from crappy houses to castles, theaters and courthouses. Based on their probability, lot location and specific building rules, I should be able to figure out what type of building is the most likely for a given lot.

    > Did you say you aren't going to have rivers and lakes?

    No plans for rivers and lakes for a first release.

    > Also, how "modern" is the world you're generating?

    Alternate fantastic universe, but with a realistic feel.

    ReplyDelete
  9. @Keebus: Yes, I have a different block partition algorithm that makes facades stick closer to street lines. Some cities will use it more.

    ReplyDelete
  10. @John Keyworth: Thanks for the link. There is also the work done by the CityEngine guys at procedural.com. It is pretty comprehensive, but I think (hope) I can get away with less.

    I'm going for a world where you can walk around and still be entertained. That constraints the scale of cities. Large cities may become boring soon. For the city sizes I'm going for I suspect too elaborate city planning algorithms are an overkill as they will go unnoticed.

    ReplyDelete
  11. Starting to remind me of this now:
    http://www.introversion.co.uk/subversion/

    Keep up the great work

    ReplyDelete
  12. Something I found interesting: I happened to be about 40,000 feet over Chicago a couple of weekends ago. Some things I noticed: 1) Something like 90% of the city was short (1- or 2-story) buildings -- apparently low-density residential and light commercial -- with tall buildings clustered in about 10% of the non-agricultural area. 2) The tallest buildings weren't in or near the "center" of the city, but were clustered next to Lake Michigan. I wonder how typical this kind of pattern is, and what cultural factors might affect these patterns?

    http://www.millionface.com/l/amazing-scenes-of-world-cities-from-the-sky/ has some good images of cities from fairly high up, including one of Chicago. Also, Google Earth has an interesting "3D Buildings" feature that gives you a sense of the taller buildings in many metropolitan areas.

    ReplyDelete
  13. I am concerned.

    I realize you are taking a sort of Bayesian approach to resource placement (i.e. "there is a city here so odds are there is fertile land nearby and resources and water nearby"), but the order you're going about doing things strikes me as very difficult to modify in the future, especially with regards to bodies of water.

    As I see it, you're going Political Landscape > Layout > Resources. The problem is, some resources (especially water sources) modify the landscape, which will modify the layout, which will modify the resources...

    Resources which have an effect on landscape may not be part of the current build, but if you ever want to add them it seems the proper order should be Political Landscape > Resources > Layout, to avoid the dependency loops.

    Maybe I am wrong, but it seems like you could take the same approach you are using for creating city layouts to make resource "zones," then build city layouts from there. It probably won't make any difference in the results you get now, but it should (hopefully) make the system more modular.

    ReplyDelete
  14. @Abnaxis: Actually, the order I follow is:

    Geography > Politics > Layout > Some Resources

    Water is part of the geography, so it comes first. I might add some resources like farms in the outskirts of cities. Same as other features like ruins.

    Also the term resource is somewhat misleading. In some cases terrain elevation is a resource, or vicinity to a different culture is also a resource.

    ReplyDelete
  15. Ah. I thought the eventual plan was to bulldoze rivers to cities similar to the way you make roads during the resource generation step.

    I know resource is an abstraction, but it still strikes me as a potential chicken/egg problem with industries like farming/mining/foresting/infrastructure, probably because it can be that way so often in real life. Just something to think about.

    ReplyDelete
  16. Is there a point where you're going to start exploring the game interactions, as opposed to geography/history/politics/layout etc?

    I'm conscious of the fact that you're likely to end up in a position similar to where Spore ended up (and arguably Love) with a whole lot of beautiful systems interacting in a way that isn't fun to actually play...

    ReplyDelete
  17. @Andrew: How to make an entertaining game. This is the one million dollar question. It keeps me up at night. It has little to do with procedural generation or any other technology. For now I'm just aware of this pitfall, let's see if I manage to avoid it.

    ReplyDelete
    Replies
    1. If you DO end up painting yourself into a corner (the way Introversion did with Subversion). I hope you'll consider open-sourcing what you have (or just plain releasing it anyway, as a sandbox game). Introversion let a lot of people down when they just shut down Subversion without delivering anything (even an incomplete product).

      Delete
    2. I used to have a tennis partner. We would play at least once a week for years. My elbow was giving me trouble at some point. My partner then said to me: "Miguel, if you cannot play tennis ever again, would you give me your racket?"

      I rather concentrate on positive scenarios for now.

      As for Introversion, I do not judge. I am sure they had their reasons. As long as they didn't scam anybody it is all good. Even if they did not deliver a final product, it was entertaining to see them try. I am thankful for that.

      Delete
  18. only walking in this world would make me so happy...

    About the buildings, it would be so cool to add like a "religious" factor... some old temples on top of the mountain for exemple, or hidden in very old caves...

    Anyway, your work is really amazing ! Keep going !

    ReplyDelete
  19. @benj: Thanks for the kind comments. Odds are you will need to run instead of walking. The indigenous population will use you for target practice.

    ReplyDelete
  20. A very interesting post as always. Coincides with my own (inferior) experiments with procedural city generation chronicled on my own blog:

    http://jwhigham.wordpress.com/2011/08/05/a-tale-of-two-thousand-cities/

    I think I'm going to have to revisit this now :-)

    ReplyDelete
  21. The first screenshot looks like an aerial photo of Southern England.

    ReplyDelete
  22. Hi, i was hoping to find out, while reading the paper, which algorithms were used to construct the blocky building lay out. However, i couldn't find it :)
    Would you be so kind as to share your algorithm with us? I'm really curious! i would like to use it as well for my own project where i need to create small towns.

    ReplyDelete
    Replies
    1. The algorithm is quite simple. You start with a polygon you want to subdivide. For the largest segment your find a line perpendicular to the segment and that also crosses another vertex in the polygon. If you find more than one of such lines, you keep the longest. Then you break the polygon in two using that line. You have two polygons now.

      You will repeat this until all polygons have three or four vertices only. Once you are there, a 3 or 4 vertex poly is guaranteed to be convex, so you can easily inscribe a box inside. Due to the nature of the partition you get segments that are aligned for the most part, so the boxes will end up aligned as well.

      Delete