PDA

View Full Version : 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:

http://www.gamecareerguide.com/db_area/images/item_images/gcg/features/20070207/roadgen2.jpg

http://odforce.net/uploads/847/gallery/3/city_06.jpg

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/salingar/connecting.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.

http://www.infinitespace-online.net/images/rcity.png

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! (http://www.centralpictures.com/ce/index.html)

madwoody
16-10-2007, 11:19 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.

http://www.infinitespace-online.net/images/rcity.png

you could also vary the length of each line so it does not cross the entire polygon.This is maybe a great idea todo. It's simple and you can change the size of it (big city, small city etc) and maybe you als can connect them to get more realistic roadmap.

WILL
17-10-2007, 02:28 AM
technomage's concept of using randomized polygonal intersections might work fairly well for making some of the more complex city layouts as pointed out in the article I posted. (I REALLY recommend that you guys at least go over it once or twice (http://www.centralpictures.com/ce/index.html) for ideas! It's damn juicy...) Though if you were to attempt to do a more New York/Toronto(where I live and it's like that too) style layout where everything is more at a right angle, with the odd exception, you could add/simplify the method where you'd be using rectangle/square polygon segments instead for the majority and keeping the streets parallel with the edges.

If you stuck a river or a lake/large pond in there for flavour then you would probably need some exceptions to handle those gaps, but it would still sort of match up with the different style of cities.

Just an alternate spin-off to add variety to your collection of cities.

NecroDOME
17-10-2007, 06:11 AM
I think that would be our first attempt to generate it random. Currently I first want to fix the network (should be done by last Sunday, but I encountered some errors/bugs).