Cantor City

The Cantor set (or how you obtain it) is probably one of the simplest fractals out there. It was one of the first examples I encountered and it helped me greatly understanding whatever came after. Here is how I like to explain it:

1. We start with a horizontal segment.
2. We divide the segment into three equally sized segments.
3. We remove the segment in the middle
4. Repeat from step (2) for the two remaining segments

This produces a set of segments that puzzled mathematicians for a while. I am more interested in the fractal properties of the whole construct. It shows how a simple rule operating at multiple scales can generate complex structures. This set is too primitive to be used for realistic content, but it is the seed of many techniques you will require to achieve that.

This is how you would code the Cantor set using our grammars:

This is the real world so we need to make sure it stops. An easy way would be to add another definition of "cantordust" for when the size is small enough. This definition would do nothing, thus stopping any further subdivision:

Here you can see the output:

Let's make it more interesting. First let's add depth to it. Instead of segments we will use 3D boxes:

This already looks like we were growing little towers. We can make the towers taller if there is enough room:

Let's add a random element. We will not split into three equal spaces anymore, instead we will pick a random value for each iteration:

For a microsecond this image can fool you into thinking you have seen a city. I think that is pretty cool if you consider it is only a few lines of grammar code.

Of course this is not a replacement for a city or buildings. The cantor grammars are probably the simplest you can have. You will need a lot of more code to produce somethings that can pass as a city. But odds are it will be mostly variations of the Cantor dust.

Screenshots of Building Scopes

As promised here are a few screenshots of building scopes over the terrain.

This is only a bunch of boxes now, eventually buildings will appear there. Also the density may be too high for the type of game I have in mind. So be aware this is work in progress.

The first image includes a previous rendering of the same area so you can get a feeling of the scale of these towns.

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.

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.