procedural generation
Unity
C#

A generator of cities following the style of Minna O.

This was the Honours Project for my degree in Games Development at Edinburgh Napier University. I studied and classified the different procedural content generation (PCG) techniques and used them to create cities similar to the ones drawn by Minna O.:

The following are screenshots of the generated artefacts (in the app they would be 3D and interactive). I was extremely lucky to have Minna helping me throughout the project — she made all the assets I needed!

And a 2D one (with an orthographic projection):

Needless to say, the final result is way more limited than initially imagined, but I'm extremely happy with what I've learnt. Procedural art is really fascinating!

Try it

If you'd like to learn more about how I did it, keep reading!

Classification

PCG techniques can be divided in two categories:

  • additive techniques, where the artefacts are created: goblins and treasures are placed in a map, the loot of a chest is created, etc.;
  • substractive techniques, where the artefacts are filtered: the generator (or sometimes a human) needs to evaluate what has been produced and pick the correct or best ones.

For this project I ended up using only additive techniques. Here's a short summary of the most used additive PCG algorithms:

  • Tiles: As the name suggests, when you have a bunch of equally sized tiles you can place them by following certain rules.
  • Grammars: These techniques usually consist on a set of rewriting rules. For example, if I have a rule such as A → AB (A will transform into AB), I can iteratively expand a string A in AAB, ABABB, ABBABBB, etc. This is called an L-system, and it was initially developed to describe how plants look. Fractals are also a type of grammar.
  • Distribution: Let's say you need to populate a map with trees, and you want them to be at a certain distance from each other, or you need to cluster them more tightly in certain areas. You can use distribution techniques, which give you more control over randomness.
  • Parametric: Not really an algorithm by itself, it usually refers to generators that can be controlled through parameters.
  • Interpretative: noise (usually Perlin noise) can be interpreted as a height map, which can then be used to create a terrain mesh.
  • Simulations: Involve usually advanced algorithms like neural networks and evolutionary ones, which are out of the scope of this project.

Techniques used

For each category I identified its strengths and weaknesses, and then picked the ones that better suited what I wanted to achieve.

A city is made of stacked 2D layers. Each layer is essentially a list where the items are building, tree, brigde, empty space, etc., and this list is populated using a Markov chain, which is a distribution technique. The idea of a Markov chain is simple: the probability to pick a certain item depends on the preceding item.

Of that list, the building is a special element. It's a stack of blocks generated by an L-system.

Finally, you can change the overall generation rules of a city, e.g. the amount of vegetation, by a set of parameter that amend the values of the Markov chain or of the L-system.

Academic poster