Procedural City generation using an L-system

By Vincent Vlaanderen Oldenzeel

Introduction

During bootcamp we had a lecture on different PCG techniques, some of which I was familiar with like Perlin noise and BSP. I didn’t know anything about generative grammars though. In the presentation there was an example of a village which was generated by an L-system, which is a type of generative grammar. A student from last semester had also used this system to generate cities.

Most PCG techniques produce results which are characteristic for the algorithm, whereas L-systems can create very different patterns and shapes depending on the parameters that are used. At the start of the project i considered a few different PCG techniques, but the potential for variety that L-systems can generate is why I chose to use this algorithm.

As I was working on the project I found that the versatility of this algorithm is also its weak point, and i had to adjust my scope a bit. In the end i learned a lot about using this technique, and despite its flaws I’m quite happy with the final product.

Index

  • Personal goal
  • Scope
  • How basic L-systems work
  • Setting up the L-system
  • Tweaking the L-system
  • Adjusting scope
  • Connecting dead ends
  • Building generation
  • Building height with perlin noise
  • Building height influenced by branch depth
  • Different length and width ratios for buildings
  • Conclusion, possible improvements and additions
  • Sources

Personal goal

Learn about L-systems and how they can be used to generate city layouts.

Scope

Generate a road network using L-systems and populate it with simple buildings in such a way that it appears to have some structure and does not look completely random. Buildings should not overlap with each other or with roads.

How basic L-systems work

A Lindenmayer system or L-system is a type of generative grammar. In a nutshell it is a system that rewrites a string of symbols using a set of rules. After it is done it uses the string as instructions to draw complex shapes. The system was first created to simulate growth of simple organisms like bacteria, but it can also be used for other things.

An L-system is made up of the following,

An Alphabet, which is a collection of the different symbols that can be used. These can be letters or other symbols like X, F, A, B, +, -, and [.

A Word or String, which is the string of symbols that is rewritten and used to draw shapes.

Productions or Rules, which are the rules that dictate how symbols in the Word are replaced by multiple other symbols. For example, when the system finds an F in the word it replaces it with FA.

An Axiom, the Word the system starts out with.

The system first rewrites the Word multiple times using the production rules. Then it goes through the Word one symbol at a time and performs an instruction depending on the meaning of the symbol, like drawing a line or branching out.

When setting up an L-system, you are free to choose the number of productions and symbols, and what they do. You can also choose an axiom. This flexibility is part of the reason why L-system can create so many different shapes.

There are a few L-systems that create interesting patterns. The L-systems below are a dragon curve and a Sierpinski triangle(image is gone?). Other L-systems create more tree- or plant like shapes. Because it can create branching lines and intersections i found it useful to create street layouts. Not all layouts are equally useful for city generation though. There should be enough space in between the roads to place buildings and roads should not overlap too much, which would look messy.

Setting up the L-system

I used the system made by the previous semester’s student as a reference. The system is made up of 2 parts, the part which mutates the string(left) and the part that uses the string to build road sections(right).

It is quite a simple system to set up. The MutateWord method takes the Word (currentWord) and steps through each character. If it finds a character that matches one of the Symbols in the productions dictionary, it will append the replacement to a temporary string. If it isn’t in the dictionary it will just append that single character to the string. After has stepped through all characters the Word gets the value of the temporary string and the temporary string is emptied. It repeats this for however many iterations the user wants.

The RoadBuilder method is used for the second part. It steps through each character in the Word and performs different actions depending on the character. A roadbuilder gameobject is used to determine the positioning and rotation of the next road section. In this case, an F builds a road section, + and – turns the builder clockwise and counter-clockwise respectively. A [ marks the last piece of road as a branching point and stores it in a stack. The ] symbol ends the road and pops the stack, which puts the builder back at the previous branching point. X doesn’t do anything here but is used to mutate the string in the previous step. The image below shows the result.

The result is quite messy but at least some patterns are visible. The roadbuilder does not yet take into account how far apart the different pieces should be so that they connect seamlessly, regardless of rotation. When i showed it at the first guild meeting, one of the teachers noted that the main and side roads were not distinguishable. When I thought about it, I got an idea for a system that would make the road section longer depending on the branch depth.

At this point i started thinking about how i wanted to handle buildings later on. Instead of actual models i wanted to try placing cubes and modifying them with perlin noise to get groups of buildings that fit together. I knew that it was too early to work on that yet, but i kept it in mind for when the system was further along.

The next week i worked on getting the roads to connect seamlessly. Now each road section has a start and endpoint which the builder uses as a reference to move between.

The next piece of the puzzle was adjusting the length of the individual road sections depending on the amount of branches. This helps spacing the roads out bit more and create the idea of a main road with side roads. This is done by saving a value in the road section, which is how often the builder has branched out when it reached this branch point. Some branches still overlap with each other because the splitting direction per branch is not made symmetrical, but each branch is split alternately to the left and right. The result can be seen in the image below.

The roads are stretched out a lot more, but there is still a bit too much overlap. The result of what you see above is with very shallow angles between 10 and 20 degrees per turn which creates a plant-like structure. I used this most of the time for testing. It could do other shapes as well but the roads would oftentimes still get ‘tangled’. Depending on the settings, it could create some results that looked more organized though.

In the next guild meeting i got a tip to use different kinds of angles to try and untangle the roads a bit more, and to add some variety in the road layout.

Tweaking the L-system

The next week i started working on some tweaks to improve the road layout. I changed the branching in such a way that branches would diverge in a more reliable way, with both branches always curving away. I borrowed this from the binary tree L-system. Before, there was a chance that both branches would curve in the same direction which caused more overlap. I also fixed a bug which would carry over some of the rotation from the previous branch after the builder object would reset to start on the other branch. These helped to make the results more consistent but didn’t make as much as a difference as i hoped they would. On the right is a test to see if the branching was symmetrical. the left image is the output of the same algorithm as the image above.

One addition that made a big difference was to have an option for branches to have different angles from regular corners. I had made this to be able to easily test variations and to see if it made the roads less dense. Below is an example where the curves and branches both work with angles of 20 degrees.

If you take the same settings but have all branches do 90 degree angles and the regular curves are still 20 degrees it looks like this:

The second layout is much better suited for my goal because the roads don’t overlap as much unnecessarily and there is enough space between the roads to place buildings. It should be noted however that both with different and same angles for branches the system can yield good or bad results. This addition didn’t solve the roads from tangling but it was easier to find results that were desirable.

Something important i realized while building and testing this, is to pay attention to if the builder instructions and the word symbols are not clashing with each other. If there is a rotation symbol after a branch symbol, the builder will rotate several times. If it is 1x to the left and 1x to the right and the number of degrees that is rotated is the same, the branch will go straight ahead, which can be confusing during debugging. This explains why in the image above there are no 90 degree turns, the production rules seem to always place an angle after a branching point.

Adjusting scope

After the standup at the beginning of the last week, it became clear i had to consider my priorities about what features would and would not be included in the project. When I listed the things I wanted I saw that they could be divided into 2 categories: Things that could improve the L-system so that it would produce more useful results, and things that add to the other parts of city generation such as different heights for buildings.

I went with the second option because there wasn’t anything besides the road network and because at that point I realized that L-systems are very difficult to keep in check. At the start of the project I thought that with enough tweaking it could produce consistently usable results with whatever parameter settings you wanted. However, you cannot always see in advance how a change of one parameter will affect the rest of the system. Sometimes a slightly different input gives a completely different end result. Connecting the dead ends and placing buildings was my goal for the last week.

Connecting dead ends

The L-system that I use works with branches, which means that many roads do not connect to the rest of the roads but come to a dead end. Not all roads are dead ends in a city, so I created a system that connects most dead ends. The system tries to find another road section within a set radius to which it can be connected. From the possible options, it chooses the closest and spawns a new section of road in between. Below you can see that a dead end part of the road connects with an existing part that falls within the radius of the blue sphere. In case a dead end happens to overlap with another piece of road it won’t spawn a new section.

Building generation

For my city builder I wanted to experiment with buildings that have adjustable heights. I wanted to do this so i could get variation in a different way as opposed to decoration and nice models. That’s why I chose to use cubes that you can scale without it looking weird like it would with regular models. To determine where a building will be placed, I do a collision check in a grid shape for each road section. A check is done to determine whether the area required for a building already overlaps with a stretch of road or another building. Below is a test with some road sections in a straight line and thin blocks for buildings. In the version of this screenshot, the alignment is not symmetrical to the road, this has been fixed later. The density of the buildings in X and Z direction and the maximum distance from the road where buildings can spawn can be set arbitrarily.

Below is a screenshot of the builder in action with buildings of variable height. For this I made a simple random function that gives the buildings 1 of 3 preset heights. The length and width ratios of the buildings are all the same.

Building height with perlin noise

To get more variation in the height of the buildings I wanted to try other ways than total randomness. I first tried perlin noise, in a number of examples they chose perlin noise to determine what kind of buildings should be placed where. I hoped that the gradual height differences would also create more neighborhood / district-like structures.

The results were okay but not that great. I had expected that a bit because of the different street layout. The buildings all have an arbitrary height but no real “neighborhoods” can be recognized. Most buildings fall within a certain range of heights, which makes the city as a whole look a bit boring. You can also recognize patterns in the building height in some of the longer line segments that are not really realistic as in the picture above. Typically, different neighborhoods are separated by roads and do not look like the “organic” shapes that perlin noise produces. I wanted to see if I could create neighborhoods in another way that is more realistic.

Building height influenced by branch depth

The second approach I have tried is to alter the height of buildings by the branch depth of the road section they are spawned on. This means that more buildings of the same height will be placed in close proximity to each other. The lower the branch depth, the higher the building. For each building, a random value (no perlin) is also added to the height for variation. Buildings that are already higher due to a lower branch depth have a larger range of random values ​​than low buildings. I chose this because residential areas often have many of the same types of houses that differ little from each other, while neighborhoods with many high-rise buildings such as the Zuidas in Amsterdam have a lot of difference in height per building. Result in the image below.

Certainly not perfect yet, but a lot better than perlin noise. Areas can be seen with houses of the same height standing together. There is some variation in the higher houses. There is still room for improvement. The average building is still a bit on the high side and in my opinion there are too few “single-family homes” like the one in the center of the image.Also, a group of the tallest buildings on the right and center-back of the image are close to the “residential area” in the center, which is not very realistic. This is due to the layout that the L-system makes. I accept this shortcoming because designing a system for this will probably take a lot of time and will work to a greater or lesser extent depending on the output of the L-system.

I then made 2 adjustments to the system. The height of all houses can be adjusted with a variable to preference. The second is for all houses that are smaller than a certain height, the scale is changed to a preset of a detached single-family house. This way, the ratio between high and low buildings becomes somewhat more even. This can all be adjusted by a user so you can still create a “concrete jungle” of apartment buildings if so desired. Example below.

As a final tweak for the height of the buildings, I wanted to give the tallest buildings a chance to become skyscrapers. This gives you even more variety in the cities that are generated and gives a city a ‘skyline’. Since these buildings are already in parts where other tall buildings spawn, they don’t appear out of place. There won’t be a skyscraper on the same road section with small buildings (apart from the l-system that can put those road sections close together).

These additions produce good results. There is enough difference in height between the buildings, and the variation gives an illusion of different neighborhoods within the city.

Different length and width ratios for buildings

Now all buildings are the same length and width. This looks strange, especially with tall buildings. Therefore the length and width are also adjusted depending on the branch depth. The smallest buildings remain the same size, but the taller buildings take up much more space. The building clearance function has been modified to deal with variable size. See image.

This change provides some extra variation and larger buildings are no longer thin sticks. It is quite noticeable that all buildings are square, so I shorten all buildings – except those of the smallest type – on one side with a random value between 0.5 and 1.

With these adjustments there is enough variation in the shapes the buildings can have. They are all rectangular, but for more complex shapes you would need to write more advanced algorithms.

Finally, I made an adjustment to the roads so that they always have a sidewalk and are therefore more visible from afar.

Final result

Conclusion, possible improvements and additions

I learned a lot from this project about how this PCG technique works and how to apply it. At times it was a bit frustrating to get things to work the way i wanted to, but the unexpected results it produced were worth it. Thanks to some tips and guidance i got at the standups i was able to get good feedback and move in the right direction.

Most important takeaways

L systems do not deliver consistently workable results like some other PCG techniques can, which i assumed when i started this project. They are better suited for offline generation where you pick the best results.

Working with an L-system comes down to writing the algorithm, then limiting its unwanted results and solving edge cases. Annoyingly, these corrections can be redundant or wrong if the underlying algorithm is modified.

I think if you wanted to use an L-system for on-line generation to get consistent playable results you’d have to either make it simple enough, or put so many restrictions and checks on it that the results it generates are very similar. The last solution would defeat the merit of using an L-system though.

Possible future additions

The system definitely has some flaws still. Below is a list of things that could be improved upon.

  • Untangle the roads when they get too dense
  • Improve L-system production rules
  • Context aware L-system
  • Ability to save and load L-system presets
  • Buildings with more complex shapes
  • Optimize code and algorithms so it takes less generation time and runs more efficient
  • Move code to different classes so it is more tidy and maintainable
  • Get nicer looking corners for roads
  • More variables directly controllable in the editor, more clear variable layout
  • More intelligent endpoint connection

Sources

Kelly, G., & McCabe, H. (z.d.). A Survey of Procedural Techniques for City Generation. citygen.net. Geraadpleegd 26 oktober 2020, van http://www.citygen.net/files/Procedural_City_Generation_Survey.pdf

Nicola, A., & Goel, N. (z.d.). Perlin City – Procedural 3D City Generation Project. technion.ac.il. Geraadpleegd 26 oktober 2020, van http://www.cs.technion.ac.il/cggc/files/projects/bin/Procedural+City+Generation+-+Perlin+City.pdf

Spronsen, M. (2020, 9 maart). City Generation. game-lab.nl. https://summit2020a.game-lab.nl/wp-content/uploads/2020/04/RD-Marc.pdf

Wikipedia contributors. (2020, 8 oktober). L-system. Wikipedia. https://en.wikipedia.org/wiki/L-system

Related Posts