Update

I’m about to commence a day of work now that all my other coursework commitments are out of the way but I thought I’d start by updating my neglected blog with an update of where I’m at. I haven’t done much but I have a pretty solid foundation for laying the roads and some nice joining algorithms. Anyway, probably best explained through the power of pictures:

Generation with buildings off and grid pattern disabled

Generation with Buildings on and grid pattern enabled

As you can see in the photos I have already achieved one massive technological leap that no other procedural generator can lay claim too: I’ve fashioned the ugliest GUI known to man.

Joking aside it is very early days, the buildings may look nice but if you really look close you’ll see they’re far from perfect. They bump into each far too much and are often stupid shapes.

Today though is not about the buildings, today I’m going to get the roads joining up in a nice manner.

Project Proposal final

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

Quick Tree Vid

Here’s a video of the tree generation, I was experimenting with making it animate the growth since that’s what I hope to do with the roads in my city (much like the Subversion video). Anyway, the vid:

My next small mini project will probably be making a wandering path algorithm so that a line joins two points but meanders in an organic looking way.  I’ll also try making my project proposal a damn sight better.

(really) Rough Proposal

Introduction

The aim of the project is to investigate and evaluate different procedural techniques used to create an urban environment through the generation of it’s transportation network. The viability of the techniques in a game will be evaluated based on how long the technique takes to achieve it’s result, how realistic the result and how much it suits a game.

Motivation

As games get bigger so does the amount of content that needs to go into them to fill them out. Using procedural techniques it is possible to generate a huge range of content using algorithms instead of artists. In games especially the urban environment is an exciting setting and has proven commercially successful (Left 4 Dead, Call of Duty Modern Warfare, Grand Theft Auto). Using procedural techniques to create the environment would lead to near infinite variation in level design, this would maximize replay value of titles since if the player gets sick of one world he can just generate another.

Procedural content is not a new subject by any means but it is only now that the techniques being used are advanced enough to rival manually produced content. Games such as Spore, Left 4 Dead and Darwinia all successfully utilise procedural content to make the game play experience richer.

Research question

Can procedural techniques be used to create a realistic cityscape by procedural generation of  its transportation network?

Addressing the Question

To address the question I will create a simulation program that will create an urban environment using 1 or more procedural techniques. The user will be able to specify input parameters and change the terrain heights and then the application will create and render a road map of the city and fill it with some rudimentary procedurally generated buildings.  All of this will be done in full 3D using the OpenGL API on a windows machine.

Resource Requirements

A PC with a high amount of RAM and a reasonable GPU and CPU will be required to process and render the cityscape.

References and Bibliography

I’ll do this in a bit

Procedural Trees and how awesome they are

Hello there blog viewer!

So I’ve just had a super productive afternoon fiddling around with L-Systems trying to get some procedural trees on the go. I thought I should look into L-Systems since they are what I’m most likely going to use for my city and I found that they are pretty awesome, at least for trees anyway! Anyway, I got some groovy pictures of my lovely trees:

It was amazing how simple all that was using a bit of recursion. I’m not sure how to write it out in the correct grammar so I’ll try my best to explain what I did. I start with 1 branch, the bottom one, that branch spawns three more:

1. Spawns mid branch at angle of theta, at j times the scale of the parent branch(0<x<1)

2. Spawns mid branch at an angle of -theta, at j times the scale of the parent branch(0<x<1)

3. Spawns at the top of the branch, at k times the scale of the parent branch(0<k<1)

Every consequtive branch does the same thing until the 10th level is reached. Varying theta, j and k gave me loads of outcomes and vastly different tree shapes and sizes.

Anyway, this was my first foray into L-Systems and it was a pretty darn good one, I really must learn how to write it out using the correct style (i.e. (A → B−A−B), (B → A+B+A)).  It was ace fun to program and has got me extremely excited to start something more complex like…ooh….I dunno, a city?

Unlike my buildings test before I don’t think I’ll be using trees in my city, the trees in the gallery above slowed down my computer significantly (and my PC is no slouch!) and that’s just one (granted the drawing process was extremely inefficient). Those trees were only going down 10 iterations, I think the total number of unique branches at that point is 88573, a ridiculous amount!

Anyway, project proposal should be up soonish!

Rudimentary Building Test

So I made a quick program to output some procedural skyscrapers and it was….pretty easy. Before I go on a bit here’s a screenshot:

First Procedural building test

As you can see it’s not terribly amazing looking but I’d be quite happy if this type of thing was in my project to represent the buildings as it is really simple and still looks all right. With a larger texture library and proper mipmapped textures it could look all right too! The real big problem with these buildings is that they are square, I think I could tweak the algorithm to take in random corner values which should be pretty easy.

This is just a side thing though I did when I was bored and buildings aren’t going to be the focus of my project, that privilege belongs to the streets! It was quite good doing a casual PC programming exercise, I found myself using a few too many lines of PSP code though which is a bit worrying (the PSP library I use is very similar to OpenGl).

Anyway, expect my draft project proposal up Tuesday at the latest!

Similar Projects (Part 1)

Thought I’d post links to some of the other projects doing similar things to what I intend to do.

Subversion – Introversion

Hugely impressive stuff from the introversion guys and if I get close to this with my project I’ll be happy. From what I’ve read from their forum this city generator expands upon the Parish-Mueller technique of using L-Systems to generate the transportation network. The program follows a simple and obvious structure of:

1. Terrain generation
2. city concentration point placement
3. Connecting highways
4. Connecting Streets
5. Zoning
6. Lot division
7. building generation

One aspect I’m not entirely keen on is the multiple points of concentration, this isn’t really realistic and I can’t think of any real life cities I’ve seen that mimic this.

CityEngine – Procedural Inc.

Pretty much the daddy of Urban procedural generation packages, retailing for about $4000 it’s not cheap! These guys are the elite and the people who work their have authored many papers on the subject that have been invaluable in my research so far.

CityGen – George Kelly, Hugh McCabe

No video for that one. It doesn’t look that impressive just looking at screen shots of it but the techniques used by it are pretty exciting! I hope I can nab some because no matter what generation I end up with there are a few tricks in CityGen that’ll help regardless.

There are a few more noteworthy projects that I’ll discuss later when I’ve had a chance to look in more depth.

Quick update on the progress of my honours: I’m trying to get my project proposal sorted out, trying to keep it vague so not to lock down one technique before properly researching them all(L-Systems are still looking like the best option however). I’m also experimenting with rudimentary building generation to see how hard/easy it would be to get buildings into the project, obviously this is outwith the scope of the project so I’m not going to spend much time on it but it’s an interesting area.