Procedural Generation of a Cityscape – Proposal

Outline

My project will attempt to use PCG (Procedural Content Generation) to create a city-like environment. I will begin to explore different algorithms and methods and analyse the generation time as well as the representation of a feasible city landscape.

The city should be generated at runtime and each execution should generate a different city for the user to explore. The end result will be a full formed 3D environment that is able to be explored by the player in a first-person perspective.

Rationale

Procedural Content Generation has been an aspect of games that has interested me for a long time. It has been a part of games for a long time ranging from level generation to difficulty scaling to item stats.

Having PCG incorporated within a game gives it more of a mystery and extends the level or replay ability for the users.

Areas for Investigation

There will be numerous areas for me to research over the time of this project.

  1. What algorithm/method will be the fastest to generate a city landscape?
  2. Alongside the speed of generation, I have to also consider which algorithm will give me the most realistic layout of buildings that it actually seems like a modelling city rather than a generated one.
  3. I must investigate whether generating the whole city upon game start will be more beneficial to the player or if it will carry on to generate as their location becomes closer to the edge.

Knowing the best approach based upon these three questions will be beneficial to my project making the generation ideal and the game more enjoyable to the player.

Background Research

So far in my project I have done background research on Procedural Content Generation in general and the algorithms that are used most commonly. My starting point will be to explore the use of L-Systems to generate the city. I will also see how a grid based system could be of use in this circumstance.

I have also had a look into existing games that already use PCG such as Path of Exile, Diablo, Doom 2 where the levels are generated. Games like Minecraft and Terraria where the initial level is generated upon start and extended as the player explores. The Left 4 Dead series uses PCG to place items, Borderlands goes a step further with this and also uses PCG to generate the stats placed on the items found by the player. The Elder Scrolls III: Morrowind uses Procedural Content Generation in a less prominent way to create the water effects on the fly.

Literature Review

Journals or Surveys that investigate the wide variety of uses of Procedural Content Generation in games [5] will help me to better understand why they are such a key part in today’s industry.

For the generation to feel like an authentic and realistic city, trying to understand different layouts for real cities [6] would be a huge benefit and could be used in the generation rules.

Any other journals or websites that can give me any knowledge about Procedural Content Generation in games [3][7] will be a huge help or how Procedural Content Generation can be used to render whole cities. [1][2][4] This will give me a starting foot and to see what different approaches have already been taken.

Methodology

To start the project I will begin to develop the Procedural Generation method so that it generates a 2D city layout without actual buildings. Once this has been successful and I have explored different approaches and algorithms, I will build upon what I have with the chosen method and transform it into a 3D cityscape.

The development method I have chosen is ‘Agile’ with 2 week iterations. I have chosen this method as I have experience with it in industry and have a good understanding in how to use it so it will benefit me with my product. Using Agile development will allow me to keep track of key areas that need to be done and gives me an idea of how fast I am working through features.

My product will be created in Unity using C#.

Research Ethics

There are no ethical aspects of my project that I will need to address and there should be no clearance needed in this area.

Project Plan

My product will have a few different stages of development for me to focus on. The first is the 2D rendering with the chosen method, the second is the 3D rendering build on top of the 2D aspect. Finally there is the user input and UI elements.

So I have enough time to complete the project I will aim to have the 2D city layout and a solid method for generation completed and the conversion to 3D started by late December with full 3D rendering completed by February.

Two days a week will be spent on the project, with every other day of the week being focused on a different module that I am also studying. Sundays will be left clear of work as it is American Football game day which will require my attendance.

Project Deliverables

My project will be a 3D procedurally generated cityscape that can be explored in first person. The city will be generated and rendered upon application start and each successive restart will generate a brand new layout for the city.

References

[1] LECHNER, T. & WATSON, B. & WILENSKY, U. & FELSON, M. (2004) Procedural Modelling of Land Use in Cities [Online] Available from: https://ccl.northwestern.edu/papers/ProceduralCityMod.pdf

[2] PARISH, Y I H. & MÜLLER (2001) Procedural Modeling of Cities [Online] Available from: http://www.cs.berkeley.edu/~sequin/PAPERS/Parish_Mueller_Cities.pdf

[3] PCG BOOK (2014) Procedural Content Generation in Games [Online] Available from: http://pcgbook.com/ [Accessed: 23rd October 2014]

[4] GREUTER, S. & PARKER, J. & STEWART, N. & LEACH, G. (2003) Real-time procedural generation of ‘pseudo infinite’ cities [Online] Available from: http://www.google.co.uk/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&uact=8&ved=0CDAQFjAB&url=http%3A%2F%2Fprocedural.googlecode.com%2Fsvn-history%2Fr118%2Ftrunk%2Farticles_cities%2Fgreuter-03-real-time.pdf&ei=I4BJVI6rAsqS7AbP04DIDQ&usg=AFQjCNHY4zGOqb93SESqBV98V1poVwOdwQ&sig2=bmDP0kIkAj_wEOZQxllMWQ&bvm=bv.77880786,d.ZGU

[5] HENDRIKX, M. & MEIHER, S. & VAN DER VELDEN, J. & IOSUP, A. (2013) Procedural content generation for games: A survey [Online] Available from: http://www.pds.ewi.tudelft.nl/~iosup/pcg-g-survey11tomccap_rev_sub.pdf

[6] MOTHERBOARD (2014) There Are Only Four Types of City in the World, Says Math [Online] Available from: http://motherboard.vice.com/read/there-are-only-four-types-of-city-in-the-world-says-math [Accessed: 23rd October 2014]

[7] GAMES BY ANGELINA (2013) The Saturday Paper – A World Just For You [Online] Available from: http://www.gamesbyangelina.org/2013/07/the-saturday-paper-a-world-just-for-you/ [Accessed: 23rd October 2014]

Procedural Generation of a Cityscape – Placing Buildings into the City, Part 2

Some more progress has been made with the building placement on the grid layout. It now uses a modified version of a ‘Box Fit’ algorithm. It randomly selects a building from the generated list of prefabs, it then proceeds to find the first place that this building can fit where it is not overlaying onto a road. This is different from an actual box fit algorithm as it leaves spaces behind where no buildings can fit. This is more like a realistic city as there are places in actual cities where buildings are not present.

Next I decided to make the place look a little more appealing by adding a basic texture to the road to look like concrete, and adding in planes with a default grass texture on them. When looking at a few of these grid pieces in a row it is possible to see repetition but at the moment this isn’t an issue. The road texture will eventually be swapped out so that the roads have markings on them and possibly a textured pavement.

I also added a texture onto the buildings that is procedurally generated. It is a simple grid (this is meant to resemble windows on city buildings) that are shaded either 1 of 3 shades of grey (lights off) or a dark-ish yellow colour (light on). This doesn’t look too bad when looking at the buildings from a distance but up close it bares no resemblance to a city building so this still needs some work.

BuildingsTextured 29012015

Procedural Generation of a Cityscape – Placing Buildings into the City, Part 1

The randomly generated buildings are now being placed into the city. Some toying about with sizes between the three different types of buildings has been done to see how that effects the look of the city.

Improvements need to be made with the placements to make it both faster and more space manageable, too many gaps are being left unused at the moment. I would also like to start experimenting with ‘districts’ or ‘areas’ so that the taller buildings are more frequent in the middle of the city and the smaller buildings are more frequent around the outskirts as if it was more rural.

WithBuildings-Take1

Procedural Generation of a Cityscape – Building Generation

Last Friday I started on the generation of the buildings. Multiple building prefabs are randomly generated upon start up of the application with a mixture of small, medium and large buildings varying in height, width and depth. These prefabs are saved into a ‘Buildings’ folder ready to be used once the city has been created.

Procedural Generation of a Cityscape – Using L-Systems, Part 2

Before Christmas I managed to extend on the L-System layout to use actual models for the roads. The rotation is correct and the length of the roads now connect successfully. Each road starts off being a 1×1 plane and gets stretched to the right length based on the parameters generated.

This layout still needs some work with adding in some kind of rule set so that the roads aren’t too convoluted and intersecting too regularly.

 LSystem Layout 21012015

Procedural Generation of a Cityscape – Using L-Systems

I have got a second city layout started using basics L-systems. At the moment it only draws debug lines on the screen and they only go towards one direction.

My aim by Friday is to get the distribution of the lines sorted so that they aren’t all going in a similar direction and they aren’t too close together so there is enough room for buildings.

A problem I encountered today was that the rotation always sent the next line pointing to the right at some angle. I soon realised after I had finished working on it for the day that I was always rotating between 60 and -60 but in world space only. This can easily be fixed by taking into account the direction of the parent line.

Procedural Generation of a Cityscape – The Beginning.

So the research has been done and my proposal submitted for my Final year Project. I have found a fair amount of papers around using Procedural Content Generation to create a Cityscape.

I have begun to program the generation to use a grid approach and it is going quite well. The only drawback I have of this is that the layout is restricted to being a grid system, much like New York is.

Going to carry on with this method to see how advanced I can get it before adding in buildings.

Grid Layout first attempt

Procedural Generation of a Cityscape – What it is

My project will attempt to use PCG (Procedural Content Generation) to create a city-like environment. I will begin to explore different algorithms and methods and analyse the generation time as well as the representation of a feasible city landscape.

The city should be generated at runtime and each execution should generate a different city for the user to explore. The end result will be a full formed 3D environment that is able to be explored by the player in a first-person perspective.

This project will be developed in Unity 4 using C#.