Advanced procedural level generation

**madwoody** · 10-10-2007, 01:39 PM

For our new game we want to develop a system that generates our world. For example we want to easily create big cities and multiple cities in 1 one world.

Here is a good example of what we want to create:

I was thinking of the use of multiple levels of procedural generation. So in a world different areas should be generated like an area for woods and cities. After that the layout of the city and streets would be generated and spots where buildings can stand. And after that the buildings would be generated for that spots. Same for woods and other areas. To set the parameters for this I was thinking about sliders just like the Far Cry editor does.

We want to know what is the best way to do this and if there are some algorithms to do this. If you guys have some other ideas I'm glad to hear them.

**NecroDOME** · 10-10-2007, 01:46 PM

We already had a discussion with WILL, and we thought it would be nice to move the problem to the forum

!
So any suggestions of what algo's we can/should use? The speed of the generation process is not relevant, it's more relevant we can generate a city, woods etc from a random seed and some slider input. The city should be generated and then we are ready to design missions and add key objects.

**Robert Kosek** · 10-10-2007, 01:47 PM

The best algorithms I've seen, not tried, are those that emulate fractals. Usually the fractals are layered and patterned after the type of structures/layouts generated. For instance squarish fractal patterns for cities, and more organic ones for woods.

You certainly aren't tackling the easiest side of things there.

**Robert Kosek** · 10-10-2007, 01:55 PM

Okay, a good theoretical article, with little to no math in it, that explains a good bit of why/how/in-what-amount in fractal city generation. It's pretty interesting to read, so I certainly suggest that.

http://www.math.utsa.edu/sphere/sali...onnecting.html

It is hard to find good material on this subject without paying though.

**NecroDOME** · 10-10-2007, 02:00 PM

We never said it would be easy

Thats why we started this topic. I took a quick look at the article, looks nice. I read it when I get home from work.

**madwoody** · 10-10-2007, 02:32 PM

This article really helps. Thx. But we are still open for other suggestions and ideas

**AthenaOfDelphi** · 10-10-2007, 06:44 PM

A good place to start might be some reading material...

We're planning a project that has similar requirements... we want to store a massive game universe with minimal data, so I'm planning on seeding. One numerical seed gets pumped into various algorithms to generate each world.

I found a series of books, which have so far proved very interesting, although I can't comment on implementation because I haven't got that far yet.

The books are:-

Infinite Game Universe: Mathematical Techniques - This covers the maths behind generating predictable random numbers, fractals and a bunch of other stuff relating to seeding and that kind of technique (or at least thats my interpretation of the content so far)

and

Infinite Game Universe: Level Design, Terrain, and Sound - I've not gotten too far into this one yet, but what I have skimmed of it seems like it could be useful reading based on your opening posts.

Both are by Guy W. Lecky-Thompson, published by Charles River Media.

**NecroDOME** · 10-10-2007, 07:42 PM

Actually we don't really care on how much data input is required. We want to save the world as a map so we can later on add or delete some building or trees for example. It's just that this would save a lot of time on modeling a city/forest/other stuff.

But I think we can start by reading something about fractals.

**technomage** · 10-10-2007, 09:50 PM

if you want to get a city style layout, you could try a fault formation algorithm. With this method you draw a bunch of random lines across a square (or any polygon) from one side to the other, the start and end points are randomly generated from a seed value. These lines become your "streets" , after that you then need to process the street map to fill in which areas are buildings (and what type) or grass etc. again using the same pseudo random generator.

Here is an example.

you could also vary the length of each line so it does not cross the entire polygon.

**WILL** · 11-10-2007, 07:29 AM

Hey guys, thought I'd post this publicly as well. This is a great little find that was actually shown off at SIGGRAPH 2001.

This site seems to server mostly as a showcase for the main resource; a technical paper on the 'CityEngine' techniques that this group that has supposedly been used to generate large scale city scapes. Goes into some details as to how they go about it to produce some of the cleaner details.

'Procedural Modeling of Cities' by Yoav I H Parish & Pascal M?ºller. Both Switzerland natives.

Here is the site link!