City generation

By Jelmar Riedeman

Table of contents

  1. Introduction
  2. City generation algorithms
    1. Delaunay triangulation
    2. Cellular automata
    3. Grid system
    4. L system
    5. Fungi based algorithm
  3. The used algorithms
    1. Cellular automata
    2. The grid system
  4. Generating the details
  5. Testing the city
    1. The first test
    2. The second test
  6. Final product
  7. Future plans
  8. Sources
  9. Used assets

1. Introduction

My goal for the R&D project is to be able to generate city’s where the player can walk while feel like traversing a city. Because there are many different types and shapes of city’s I have chosen to use figure 1 and figure 2 as references for the generation of the city.

Figure 1: https://unsplash.com/photos/h0l8MLFOUgo

Figure 2: https://www.google.nl/maps

2. City generation algorithms

Here are some algorithms that can be used to generate city’s.

2.1. Delaunay triangulation

Delaunay triangulation can be used to generate the outline and the main roads of a city.

If you look at a city at night and mark the light spots you will see that most of the light spots are in the middle. By then making a triangle between the points and using the surface of the triangle as city you will get a natural looking city (Jiang & Miao, 2014).

Figure 3: https://arxiv.org/ftp/arxiv/papers/1401/1401.6756.pdf

2.2. Cellular automata

Cellular automata works by having a simple set of instructions whereby can be determined what will happen at every small level. By having enough small things (buildings) together a city will form.

One of the ways to make the city more realistic with cellular automata is by putting the basic needs of neighborhoods as small rules. This way the city will not only have houses, but also shops and roads (Mavroudi, 2007).

Figure 4: https://discovery.ucl.ac.uk/id/eprint/7894/1/7894.pdf

2.3. Grid system

One way to simulate real city’s is with a grid system. To simulate the inner and the outer part of the city you can use a grid whereby every layer you go further from the center the grid size doubles. The size of the city can be determined by choosing a maximum grid distance, and by also giving a minimum grid size the center of the city also remains at normal proportions (Jiang & Miao, 2014).

Figure 5: https://arxiv.org/ftp/arxiv/papers/1401/1401.6756.pdf

2.4. L system

L system is an algorithm that is usually used to generate fractals. It can however also be used to generate towns. The way it generates towns is by spawning new roads halfway the existing roads until there is no more room to expand or it is stopped by the user. After that it places houses next to the roads to make it look like a town as can be seen bellow (Sunny Valley Studio, 2020).

Figure 6: https://www.youtube.com/watch?v=umedtEzrpvU&t=3s

2.5. Fungi based algorithm

The fungi based algorithm is a sort of algorithm to create natural looking connections (roads).

It does this by following simple directions to get around obstacles.

This algorithm can be used to place some “natural obstacles” in the city and generate a natural road work around these obstacles (Asenova et al., 2016).

Figure 7: https://eudl.eu/pdf/10.4108/eai.3-12-2015.2262591

3. The used algorithms

In the ideal scenario I would like to use all algorithms. Delaunay triangulation to generate the shape of the city, a grid system to decide the density of the districts, Cellular automata to fill in the urban part of the city, the L system to generate the outskirts of the city and the fungi based algorithm so I can place natural obstacles and make the city more realistic.

Because my goal is to make a city where the player can navigate, while having it actually feeling like a city, I choose to implement Cellular Automata and the grid system. By starting with the implementation of cellular automata (which looks at its neighbors to form decisions) the base is really adaptable and the other algorithms can be easier implemented if there is enough time to do so.

3.1. Cellular automata

Not every meter of the city consists of housing, there also need to be parks and commercial buildings.

A neighborhood should consist of 10% recreation and park space. It should also have some wide and open areas (Dover, 2020).

To make it so that there is 10% parks consisting of a variation of smaller parks and bigger parks, I made it so that every cell has a 10% change to become a park and merge multiple adjacent parks together to one big park.

A city should also be economically vaible. This means that there should be stores and jobs in the city (Jeffries, 2020).

Because of this reason I also chose to also add commercial buildings to the city. This will be a place where the citizens will be able to work and buy things to make the city economically viable.

To make sure every person has a job I made it so that there is always a commercial building close to the houses. To simulate the shopping centers that then form I also made the commercial buildings taller when there are more together.

Parks are also not divided in multiple neighborhoods, so if there are parks on two or more sides of the road, then that road transforms into a park as well. In figure 8 you can see how the city looks with cellular automata, using only the grid system to create the square neighborhoods.

Here you can see an example of the part of the code that removes the roads in the parks and prepares it for the next checks. Every part of the city is coded like this, where it looks at its neighboring cells (the cells are buildings and equivalent size objects) to base its own state on. An cells state says multiple things about itself. The height of the cell, if it is connected to another cell. Currently only the roads use the connection, but it is also possible to merge buildings, parks and other things together. One example could be to merge the parks together and create a fence around them, or as a second example it could merge two buildings in a single bigger building. This is however not implemented because all of that would require assets, and extra research when things are actually merged in a normal city.

Figure: 8

3.2. The grid system

The grid system itself is fairly simple. It basically says that every neighborhood outside of the main neighborhood should be twice as big (Jiang & Miao, 2014). Because most of the changes implemented by the grid system should be made by cellular automata this chapter will not be as big.

What I have done is made it so that after the cellular automata has finished generating splitting the cells in rectangular shapes of variable sizes. Then I made it so that first a city part is generated with a four by four ratio (neighborhood) as can be seen in figure 8. Then I made another eight city parts with twice the neighborhood size around the first city part. It would be better if this is all done at once instead of making nine separate parts so the transition between the city parts would be seamless. The result, after all the different parts of the city are added can be seen on figure 9.

I will now explain how the extra city parts are placed around the center part. First the neighborhood size is doubled, then the size of the old district is calculated to determine the position and size of the new city part.

There are eight parts connected around each center part, so the code repeats the last three lines six more times after the shown code snippet. If the city would need to become even bigger than these generated nine parts would form the center part and the code would repeat itself.

Figure: 9

4. Generating the details

I did not generate the prefabs in the city from scratch, but instead I used premade assets from the asset store. All the assets come from two asset packages, one for the roads (Poly City – Free Cartoon Pack, 2017). The other assets are for the buildings and parks (Ukraine free road roadsign cars, 2021).

When the roads are placed, they also know to which other road segment they are connected. When they are connected along one axis, they use the straight road piece and rotate it in the right connection. When they are connected along two axis they will become a crossroad (sadly there is no usable prefab for a crossroad in the packages I used).

I have chosen the buildings designs, because these are modular. This means that if the building is taller module can simply be put on the top. Below are two images, figure 10 for the bottom part of the house and figure 9 for the center part of the house. These work the same for the commercial buildings.

When the city is generated, it is stored in a two dimensional list where everything in the city knows how it should be placed as can be seen in this code snippet.

Figure 10

Figure 11

5. Testing the city

I did two tests of the project. The first test I did with only one city part; The second test with multiple city parts.

5.1. The first test

After I implemented the cellular automata and generated the city I tested the city with other people.

For the test I first let them play the game without telling them anything. In figure 12 you can see the top down view of the city the player walked trough when they tested.

Figure 12

Then I asked the testers what place they feel like they are.

The testers answered it felt like a city, mainly because of the structure and the close proximity of the buildings.

Then I showed the testers figure 1 and figure 2 and asked them if they were at one or both of the images.

On this the testers answered that the city felt like Figure 1, because of how close the buildings are together and organized in squares.

Then I asked the testers what could be improved.

For this question I got more varied feedback. The testers wanted that the roads would not suddenly be interrupted for the parks, a more organic shape to the city and more variety in the prefabs used to generate the city.

I also asked them if it actually felt like a city.

The testers said it felt like a city, but there could be more single green spots that are not parks.

Because the deadline was approaching, I could only change a small thing on the project and so I added more prefabs for the trees. Mainly because I had to make to assemble the segments of the buildings (from all kinds of smaller assets that where in the asset pack) myself so that was not possible in the given deadline.

5.2. The second test

The second test followed shortly after the first test.

For the second test I returned to the testers of the first test and let them play on the map on figure 11.

Figure 13

After they were finished testing I asked them if they noticed something has changed.

All except for one tester had noticed that there was more green, and the neighborhoods where bigger (mostly by longer intervals between houses and also by doors in all streets).

Then I asked them how they thought about the new districts.

They said that there was more variation in the city.

That is was good that there are doors on all streets now.

All the extra green with still some houses around them gives off a backyard feel.

6. Final product

The final product is certainly not finished, but it feels like a city. This is mostly because it is more the base of a city than a fully refined and finished city. To give more of a first-person-feeling from this project you can see a streetcorner on figure 14, a small park on figure 15, a big park at figure 16 and the top down view of the city on figure 17.

Figure 14

Figure 15

Figure 16

Figure 17

7. Future plans

There are plenty of features and improvements that can be made to the project.

The most immediate improvements would be that there should be more height difference between the buildings. There should also be more buildings than the two currently in the game to make the city feel less repetitive.

After that is all done and tested (with different testers than the first tests) an nice improvement could be to add Delaunay triangulation to the algorithm. Because the grid system already differentiates between the center and the outer parts of the city, the next step is the shape and the big roads throughout the city. This could look something like the prototype I made in figure 16.

Figure 16

Then there is one final thing I would like to implement in the generation algorithm, which is the fungi based algorithm. With this algorithm I could place some natural obstacles around the city such as rivers or lakes and have the city be even less square and more organic around these obstacles.

8. Sources:

Sunny Valley Studio. (2020, 17 april). Unity Procedural Town / City generation Tutorial Ep1 Intro [Video]. YouTube. https://www.youtube.com/watch?v=umedtEzrpvU

Asenova, E., Fu, E., Nicolau, D. V., & Lin, H. (2016). Space Searching Algorithms Used by Fungi. BICT’15 Proceedings of the 9th EAI International Conference on Bio-inspired Information and Communications Technologies (formerly BIONETICS). https://doi.org/10.4108/eai.3-12-2015.2262591

Jiang, B., & Miao, Y. (2014, maart). The Evolution of Natural Cities from the Perspective of Location-Based Social Media. https://arxiv.org/ftp/arxiv/papers/1401/1401.6756.pdf

Mavroudi, A. (2007, september). Simulating city growth by using the Cellular Automata Algorithm. https://discovery.ucl.ac.uk/id/eprint/7894/1/7894.pdf

Dover, V. (2020, 16 mei). Every Neighborhood Should Have These Five Things — Dover, Kohl & Partners. Dover, Kohl & Partners. https://www.doverkohl.com/blog/2020/5/10/every-neighborhood-should-have-these-five-things

Jeffries, S. (2020, 23 september). How to build a city from scratch: the handy step-by-step DIY guide. the Guardian. https://www.theguardian.com/cities/2015/jun/30/how-build-city-step-by-step-diy-guide

9. Used assets:

Poly City – Free Cartoon Pack (1.0). (2017). [Software]. WAND AND CIRCLES. https://assetstore.unity.com/packages/3d/poly-city-free-cartoon-pack-95242#description

Ukraine free road roadsign cars (2.0). (2021). [Software]. KOS-store. https://assetstore.unity.com/packages/3d/environments/roadways/ukraine-free-road-roadsign-cars-191827