Introduction
The city is one of the most complex manmade creations on the planet. Taking shape over decades, if not hundreds of years, no two are the same and each is home to thousands, sometimes millions of people. In today’s game marketplace there are an abundance of video games that use the city as a setting. Many of these games, such as the hugely successful Grand Theft Auto franchise (Rockstar North, 2008) let the player loose to wander about the city as they choose. The cities involved in these games have been hand crafted by a huge team of artists and level designers at a very high financial cost and take many man hours to complete. This project will look at techniques to generate a city setting algorithmically, easing the burden on content producers and allowing for near infinite level variation.
Motivation and Purpose
The game industry is presented with a major challenge in trying to create content that uses the full potential of the hardware on offer, a common approach to this problem being simply to increase the number of artists working on the game to produce more of the content required (Kelly and McCabe, 2007). This project presents procedural techniques as a way of combating this problem in an urban based game. Procedural generation techniques are algorithms that create content algorithmically through preset instructions. Procedural techniques can be utilised to create near infinite variety in content, in this project they will be used to create an urban environment with the purpose of that environment being its use in a 3D open world game such as the aforementioned Grand Theft Auto franchise.
The project will focus on how viable such procedural techniques are within an actual game application. To clarify: the goal is not to create a tool for content producers but to make an automated system that can be placed inside a game for the creation of unique levels. The underlying algorithms will be the same for both a tool and an automated system however since the application is being designed for use within a game the amount of user input needs to be minimal after generation has taken place so good results need to be obtained without the need to edit the output afterwards. If successful these techniques could be used to make a game where each player has a unique version of the game world leading to massively increased replay value in open world city games.
Related Research
There has been some research and development in the area of procedural cities. Most of this focuses on a broad target market and not specifically on games. Procedural Inc, creators of CityEngine, state that their product can be used for: Film & TV, game development, architecture, archaeology and simulation (Procedural Inc, 2010). CityEngine uses extended L-Systems and geo-statistical image maps to produce its cities (Parish and Müller, 2001). L-Systems are commonly used to generate the geometry for organic objects like plant life. Parish and Müller (2001) define an L-System as “a parallel string rewriting mechanism based on a set of production rules”. L-Systems use strings to represent the production rules with each string consisting of a number of different modules; each module includes a set of commands and parameters that are used within those commands. In CityEngine L-Systems have been extended to follow global and local constraints. Global constraints include street patterns and population density while local constraints are things like local streets, land/water boundaries and elevation (Parish and Müller, 2001).
A template based approach is suggested by Sun et al (2002) whereby a predefined pattern is imposed on road creation. Using these templates various categories of cities can be produced that have recognisable real world characteristics. For example using a grid like template would give a city layout resembling Manhattan.
Another example of a procedural urban generation tool is CityGen though this isn’t commercially available. CityGen uses a combination of a template based approach and the L-Systems presented by Parish and Müller (2001). CityGen endeavours to be an ‘interactive’ city generator in that the user can change generated node positions to get the desired outcome.
Addressing the Question
Can procedural techniques be used to create a realistic cityscape to be used in a game application by procedural generation of its transportation network?
To address this question a demo application will be made. The application will not be designed to be a tool used by content creators but instead show off procedural techniques with a high level of autonomy that can be run from within a game application by the end user. Having this autonomy would lead to the game being able to generate unique cities for its players without the need for any extra input. This autonomy is a key design goal of the project.
The slowest changing aspects of a city are its networks, such as transportation and utility networks, its land use and housing (Wegener, 1998). For this project the primary focus will be on the generation of the road network. The road network is the most important for a player navigating the city at street level since it is the space that the player will inhabit. The road network also helps dictate the overall character of a city (Kelly and McCabe, 2007).
For generation of the road network two different types of road will be required, primary roads and secondary roads (Kelly and McCabe, 2007). Primary road networks are the main roads within a city; these roads have a strong influence on the character of a city and define its constituent elements such as neighbourhoods and districts (Whelan, Kelly and McCabe, 2008). The secondary road network is used to connect the main roads to the individual lots. Using different techniques to generate primary and secondary road networks leads to increased variation in the cities’ structure.
The L-System method represented by Parish et al will be used to generate both the primary and secondary road systems. A global shape template will also be imposed on the primary network (Sun et al, 2002). Using this template based approach an overall pattern can be imposed on the main roads of the city while still allowing variation. A raster pattern for example would generate a grid like city similar to that of Manhattan whilst an organic pattern would generate a city similar to Paris.
Many of the methods used in similar city generation application use input data in the form of 2D images to control the behaviour of the generation system (Parish and Müller, 2001). This data can include the elevation map, population map, street patterns or height maps. For this project the only input necessary will be the height map of the terrain that the city is to be rendered on. The inclusion of a height map instead of the city being on a flat plane opens up new development opportunities where the road network can adapt to the height of the landscape.
This combination of the template and L-System based approach is similar to that present in the CityGen application (Kelly and McCabe, 2007), in that application however they give the user the tools to edit the resultant road map manually. For this project the application will be fully automatic once the user has specified a few parameters before generation (such as the template being used). This is to ensure that the results rely entirely on the algorithms being used so that the procedural technique could be used in a game application without any need for the player to be involved with the creation of the city.
After the transportation network has been created lot division will take place. Lot division involves dividing the space between the roads into lots that buildings will fit into. Lot division can be achieved easily by simply dividing the space along each road into blocks and then scanning for overlapping lots that need either joining or repositioning. After lot division has taken place rudimentary buildings will be placed into them. The buildings will simply be rectangles fitting into the allotted space. The inclusion of rendered buildings in the visualisation will increase the realism of the city and, by making it more believable, will make it easier to judge the outcome.
To be a viable generation technique to be used within a game application and not just as a tool the generation techniques utilised must be fairly quick to produce decent results. Multithreading will be utilised to speed up city generation, L-Systems in particular lend themselves well to parallel processing. The vertex count will be kept deliberately low at the rendering stage by having simplistic buildings so that the entire generated environment can be viewed in real time.
The criteria on which the demo application will be evaluated will be the detail, complexity, heterogeneity and realism of the output (Kelly and McCabe, 2007) as well as the time it takes to generate good results. A planned schedule for the project can be seen in the appendix.
Summary
In summary the main objectives of this application will be:
- Using procedural techniques to create a coherent and believable cityscape.
- Primary and secondary road systems (main roads and utility roads).
- High level of variation in outputs
- Rudimentary buildings set out into lots.
- 3D real time rendering of generated city with user controlled camera.
- Minimal data input
- Some customisability via user interface
- Small generation time
Resource Requirements
The demo application produced should not need an abnormally good PC to run on. A standard desktop should suffice with the only requirement being able to run multithreading technology to aid in quick generation. As multi-core CPUs are standard on modern PCs this shouldn’t be an issue.
References
Procedural Inc. 2010. [online]. Available from: http://www.procedural.com/industries.html [Accessed 07 January 2010].
M. Wegener. Operational Urban Models: State of the Art 1998.
J. Sun et al. Template-Based Generation of Road Networks for Virtual City Modeling, 2002
G. Kelly and H. McCabe. Citygen: An interactive system for procedural city generation. 2007.
Rockstar North. 2008. Grand Theft Auto IV. [Disk]. Xbox 360. Rockstar Games.
G. Whelan, G. Kelly and H. McCabe, Roll Your Own City, 2008
