Looking for procedural game design

This isn't a well-known solved problem. People have done it (kkrieger) by taking the basic procedural components such as fractals and noise, and combining them in interesting ways. It's very much an art that involves a lot of tweaking and experimentation. There are no "stock solutions" (yet).

That said, I'll keep an eye on this thread as well to see what resources people have.

I've done a few recent journal posts specifically about Minecraft-style world generation, as well as a number of other posts about procedural world generation in general.

Great posts on creating Minecraft style maps. Thanks for creating those.

Some pretty good articles here: http://pcg.wikidot.com/

I initiated a project years ago to generate procedural worlds with an underlying hierarchical structure. You can see how far we got here.

If this looks like the kind of thing you would like to do, I can give you some guidelines as to how to build something like that.

Hey guys, thanks for all your answers.

I initiated a project years ago to generate procedural worlds with an underlying hierarchical structure. You can see how far we got here.

If this looks like the kind of thing you would like to do, I can give you some guidelines as to how to build something like that.

Yes I'd love to see that hierarchial structure. The world Im about to create for my game contains streets, rivers and houses. It is a topview 2D game.

I'll try to explain the basic ideas behind Descensor to see if they might help you. I have to warn you that it's not the easiest thing to understand, so you may have to read this post several times and think hard about it before it makes sense.

The scene is a tree. Each node has a bounding volume (a polygon on the ground and some range of heights, but for your 2D situation just think of it as a polygon), and it either is a leaf or it has a method that gives you a list of descendants. The leaves contain actual geometry to draw. In the case of the city that Descensor draws, the hierarchy goes something like this:


A Region has descendants of type City. A City has descendants of types Neighborhood, MajorAvenue and MajorSquare. A Neighborhood has descendants of types Block, Street and Square. A Block has descendants of type Building and Park. A Building has descendants of type Floor, Stairwell and Roof. This continues in this fashion until you get to leaves of types Window, Wall, StreetLight, Tree...

Notice that at each step the problem to solve is not very complicated. You have to come up with some way of dividing a city into neighborhoods, major avenues and major squares. Well, you can drop a few random points inside the polygon that defines the city. If the random point you pick is either too close to the border or too close to a previously generated random point, ignore it. Now do a triangulation of the original polygon that uses the new points as vertices. Join some triangles together to form the shapes of the neighborhoods. Place major avenues at the sides of the neighborhoods and major squares at the vertices. Play around with the code until you are satisfied with the results. You similarly solve the decomposition of every other node type into its descendants.

The other trick that Descensor used to allow for gigantic worlds is that only the parts of the scene that the camera can see get generated. You originally try to render the scene (the root node). First you check if its bounding volume intersects the view frustum at all. Since it does and it's not a leaf, you have to decompose it. So you call the code to decompose it into its descendants and recursively render them. The ones whose bounding volume doesn't intersect the view frustum don't get processed further. This way, if your camera is looking to a small piece of the city from above, you only go down a very narrow subtree of the whole thing and you can render it pretty quickly.

The obvious problem with this approach is that you need to make sure that if you move the camera around and then come back to where you where, the world gets regenerated in a consistent fashion, because you used a bunch of "random" numbers in the generation. In order to ensure this consistency, you assign each node in the tree a 64-bit number to be used as a seed for the pseudo-random numbers that will be used in its expansion into descendants. The descendants get their own 64-bit seeds, and every time you repeat the process, you'll get the same answers, no matter what parts of the tree you decide to ignore.

One can also modify a node in the scene, to allow a designer to specify certain parts of the scene and let the rest be generated procedurally. Basically you have a table of exceptions, which says things like "the building with seed 11950597896610578432 shouldn't be generated using the usual rules: Use this other design instead". This way one can describe a huge world very compactly by the initial seed plus a small table of exceptions. For instance, you could use this method to distribute scenes in a MMORPG.

Those are the main ideas. We had an architect in the team that made some pretty believable buildings using this philosophy. You may want to read some of the works of Christopher Alexander: "A city is not a tree", "The timeless way of building", "A pattern language"... Even though "A city is not a tree" basically says that what I described above won't work, it can be made to work by using the context of what's around each node when generating its descendants (this building has this seed, this polygonal shape, and the neighboring areas to each side of the polygon are: a major avenue, another building, a patio, a street). Also, the standards of believability that we need for a game might not be as high as what Alexander requires in that article. The other two are books that actually describe a lot of recipes to solve the specific problems that you need to solve to refine a node into its descendants.

There are lots of huge holes to fill to make this master plan work. The Descensor project was basically stopped when the architect that had done most of the work died in an accident. At some point I might go back to working on it. Done right, I believe this scheme can be used to design pretty much anything: gardens, rooms, houses, airports, cities, planets, galaxies, music, literature... OK, OK: I would have to think hard about how to write automated literature using these ideas, but I don't think it's impossible.

I hope some of this helps you, or at least it inspires you in some way. Also, feel free to ask for further explanations if anything above isn't clear.

I'll try to explain the basic ideas behind Descensor to see if they might help you. I have to warn you that it's not the easiest thing to understand, so you may have to read this post several times and think hard about it before it makes sense.

The scene is a tree. Each node has a bounding volume (a polygon on the ground and some range of heights, but for your 2D situation just think of it as a polygon), and it either is a leaf or it has a method that gives you a list of descendants. The leaves contain actual geometry to draw. In the case of the city that Descensor draws, the hierarchy goes something like this:


A Region has descendants of type City. A City has descendants of types Neighborhood, MajorAvenue and MajorSquare. A Neighborhood has descendants of types Block, Street and Square. A Block has descendants of type Building and Park. A Building has descendants of type Floor, Stairwell and Roof. This continues in this fashion until you get to leaves of types Window, Wall, StreetLight, Tree...

Notice that at each step the problem to solve is not very complicated. You have to come up with some way of dividing a city into neighborhoods, major avenues and major squares. Well, you can drop a few random points inside the polygon that defines the city. If the random point you pick is either too close to the border or too close to a previously generated random point, ignore it. Now do a triangulation of the original polygon that uses the new points as vertices. Join some triangles together to form the shapes of the neighborhoods. Place major avenues at the sides of the neighborhoods and major squares at the vertices. Play around with the code until you are satisfied with the results. You similarly solve the decomposition of every other node type into its descendants.

The other trick that Descensor used to allow for gigantic worlds is that only the parts of the scene that the camera can see get generated. You originally try to render the scene (the root node). First you check if its bounding volume intersects the view frustum at all. Since it does and it's not a leaf, you have to decompose it. So you call the code to decompose it into its descendants and recursively render them. The ones whose bounding volume doesn't intersect the view frustum don't get processed further. This way, if your camera is looking to a small piece of the city from above, you only go down a very narrow subtree of the whole thing and you can render it pretty quickly.

The obvious problem with this approach is that you need to make sure that if you move the camera around and then come back to where you where, the world gets regenerated in a consistent fashion, because you used a bunch of "random" numbers in the generation. In order to ensure this consistency, you assign each node in the tree a 64-bit number to be used as a seed for the pseudo-random numbers that will be used in its expansion into descendants. The descendants get their own 64-bit seeds, and every time you repeat the process, you'll get the same answers, no matter what parts of the tree you decide to ignore.

One can also modify a node in the scene, to allow a designer to specify certain parts of the scene and let the rest be generated procedurally. Basically you have a table of exceptions, which says things like "the building with seed 11950597896610578432 shouldn't be generated using the usual rules: Use this other design instead". This way one can describe a huge world very compactly by the initial seed plus a small table of exceptions. For instance, you could use this method to distribute scenes in a MMORPG.

Those are the main ideas. We had an architect in the team that made some pretty believable buildings using this philosophy. You may want to read some of the works of Christopher Alexander: "A city is not a tree", "The timeless way of building", "A pattern language"... Even though "A city is not a tree" basically says that what I described above won't work, it can be made to work by using the context of what's around each node when generating its descendants (this building has this seed, this polygonal shape, and the neighboring areas to each side of the polygon are: a major avenue, another building, a patio, a street). Also, the standards of believability that we need for a game might not be as high as what Alexander requires in that article. The other two are books that actually describe a lot of recipes to solve the specific problems that you need to solve to refine a node into its descendants.

There are lots of huge holes to fill to make this master plan work. The Descensor project was basically stopped when the architect that had done most of the work died in an accident. At some point I might go back to working on it. Done right, I believe this scheme can be used to design pretty much anything: gardens, rooms, houses, airports, cities, planets, galaxies, music, literature... OK, OK: I would have to think hard about how to write automated literature using these ideas, but I don't think it's impossible.

I hope some of this helps you, or at least it inspires you in some way. Also, feel free to ask for further explanations if anything above isn't clear.

Thanks for a very informative and good read. I've already started to do the tree/leaf approach where I use arrays that I fill with different cells that either is a leaf or a branch - so I am glad to see that you had an similar approach and that its been tested by someone else but me.

An other problem Im curious about is spawning stuff like rivers, etc. If a river intersects a city do I have to pass that river as an argument to the city generation or is it easier to first make the city and then the river? Right now I have this neighbourhood where I spawn the roads first, then I spawn houses next to the roads. When I spawn the houses I pass the road as argument so that the house knows which direction it should face (which side the main door should be on that is). But I think that, although this is a very simple problem, it is to much overhead and I cant see how one would do this with much more complex problems without passing hundreads of arguments.

An other problem Im curious about is spawning stuff like rivers, etc. If a river intersects a city do I have to pass that river as an argument to the city generation or is it easier to first make the city and then the river? Right now I have this neighbourhood where I spawn the roads first, then I spawn houses next to the roads. When I spawn the houses I pass the road as argument so that the house knows which direction it should face (which side the main door should be on that is). But I think that, although this is a very simple problem, it is to much overhead and I cant see how one would do this with much more complex problems without passing hundreads of arguments.

Rivers and mountains are tricky. We did implement mountains by first having a Terrain object which can respond to queries like "what's the height at (x,y)?". Then this object is passed to every node so it can be used in the procedures that generate the descendants. For rivers I would do something similar, where the nodes can query the Terrain to know if there is a river in their polygon and where it is.

The obvious problem with this approach is that you need to make sure that if you move the camera around and then come back to where you where, the world gets regenerated in a consistent fashion, because you used a bunch of "random" numbers in the generation. In order to ensure this consistency, you assign each node in the tree a 64-bit number to be used as a seed for the pseudo-random numbers that will be used in its expansion into descendants. The descendants get their own 64-bit seeds, and every time you repeat the process, you'll get the same answers, no matter what parts of the tree you decide to ignore.[/quote]

This is a very important piece of advice. It's probably obvious to most people who've done procedural generation for a while, but it's something I only realized relatively late into the process of learning and experimenting... A lot of tutorials and resources out there tend to present "basic" Perlin noise as the only thing you'll need to generate a landscape... And it's definitely true that it's good at generating tiling textures made up of blobs -- lends itself well to defining regions and getting smooth elevation changes, etc -- but that's ultimately just a byproduct of superimposing and interpolating noise fields of varying amplitudes.

What's "truly revolutionary" (maybe I'm pushing it a little) is the idea that your noise is random, but predictable -- for a given seed or seeds, the generated data is always the same. So heightmap and texture generation is only one side of the coin. It's actually a terrible, terrible way to generate natural-looking landscapes if you use it by itself... Cross your fingers and hope it kind of looks like a natural land formation...

What I would have liked to see in more resources overall is the idea that the data you use doesn't have to be a field of colored blobs. In a lot of instances, it makes a lot more sense to generate random 2d/3d points, weighted graphs, even curves. In other words, each specific feature should come with its own specific generation behavior.

An other problem Im curious about is spawning stuff like rivers, etc. If a river intersects a city do I have to pass that river as an argument to the city generation or is it easier to first make the city and then the river?[/quote]

I would recommend rivers first for historical reasons -- the most developed areas in the world are the ones closest to water; and the largest commercial hubs are often at "deltas" (ocean-river, or river-river), especially port cities surrounded by water on all sides. If you want your cities to look like they were constructed "logically," they should definitely take the natural land formations and bodies of water into account. i.e. most developed near river-ocean or river-river junctions, least developed in areas that are less accessible (mountains, rainforests, extreme climate, lack of water, lack of natural resources).

Good thread. Another approach I was thinking about was a tile based map system, which is simpler and more restrictive compared to the techniques described here. Basically you have regular grid arrangement, where each cell represents a patch land, and consists of independently generated content. One can assign each grid a procedural content type, with a random seed, that could represent things like block of buildings, parks land, forest, garbage dump, ..., etc. Then devise an automatic blending method that can stitch the patch boundaries together with their neighbours. Or perhaps setup boundaries so that they overlap and have geometric features mix with its neighbour; for example, shrubs encroaching farm land at a forest edge.

Im looking for some kind of Noise function that takes two float values x and y and returns a value in between -1 and 1. I've been googling around for Perlin Noise, but I all I find is where people use it for images and creating the same bitmaps with width and height as parameters.

Does anyone know a good site or even more simple, have anyone written such a function?

The input(s) for Perlin noise could represent anything, it does not have to be actual points or coordinates in space.

I don't know if using floats as input would be a good idea -- it would probably unbalance the random distribution (if your PRNG makes use of integers/modulus), and could have very unpredictable results as far as repeatability goes...

If you're iterating over an array of 2d float vectors, you could probably use the array index as the integer you pass to the PRNG?

Im looking for some kind of Noise function that takes two float values x and y and returns a value in between -1 and 1. I've been googling around for Perlin Noise, but I all I find is where people use it for images and creating the same bitmaps with width and height as parameters.

Does anyone know a good site or even more simple, have anyone written such a function?

I wrote this a while back, and was my second attempt. Sorry for the messiness. My style was not so good back then. You'd have to normalize it for -1 to 1

[spoiler]

class World
{
private:
const int N;
const int Sz_2powN;
const int Sz_2powN_plus1;
const int Half_Sz_2powN;
const int Last_Seed;

const int Num_Planes;
const int Num_Vors1;
const int Num_Vors2;
const int Num_Faults;

bool Feat_Set;

VorPlane* Planes;
MapFeature* Vor_Points1;
MapFeature* Vor_Points2;
ShiftFault* Faults;


public:
int Sec_Size;

World(int size_in, int secsize_in, int numplanes_in, int numvors1_in, int numvors2_in, int numfaults_in);

void SetFaults(int seed);
void SetPlanes(int span, int center, int seed);
void SetPlanes(int vor_shift, float vor_dist_coef,
int vor_num, int vor_neg_mod,
int perl_from, int perl_to,
int perl_shift, float perl_hfac,
float perl_persist, int plane_seed, int perl_seed);
void SetVors(MapFeature* this_vor, int seed);
int GetFaultSum(int glob_x, int glob_z, int shift, int faultfac);
VorPlane* GetPlane(int glob_x, int glob_z);
float GetVorH(MapFeature* this_vor, int glob_x, int glob_z, int shift, float dist_coef, int num, int neg_mod);
float GetPerlinH(int glob_x, int glob_z, int from, int to, int yShift, float h_fac, float persist, int seed);

int GetGlobX(int seed_coord);
int GetGlobZ(int seed_coord);
int SeedCoord(int glob_x, int glob_z, int seed);

float GetElev(int glob_x, int glob_z);

World operator= (World);
};


float World::GetPerlinH(int glob_x, int glob_z, int from, int to, int yShift, float h_fac, float persist, int seed)
{
srand(SeedCoord(glob_x, glob_z, seed));

int* seedList = new int[N+1];
float* fList = new float[N+1];

for (int i = 0; i <= to; i++) {
seedList = (rand()+yShift);
}

for (int F = 0 ; F <= to ; F++) {
int base = int(Sz_2powN/pow(2.0f, F));
int xmod = glob_x%base;
int zmod = glob_z%base;

if ( (xmod == 0) && (zmod == 0) ) {
fList[F] = seedList[F] * h_fac * pow(2.0f, -pow((float)F,persist));
continue;
}

else {
srand(SeedCoord(glob_x - xmod,
glob_z - zmod + base,
seed));
for (int i = 0; i < F; i++) {
rand();
}
float elevA = (rand()+yShift) * h_fac * pow(2.0f, -pow((float)F,persist));

srand(SeedCoord(glob_x - xmod, glob_z - zmod, seed));
for (int i = 0; i < F; i++) {
rand();
}
float elevC = (rand()+yShift) * h_fac * pow(2.0f, -pow((float)F,persist));

float top = 0;
float bottom = 0;

if ( xmod == 0 ) {
top = elevA;
bottom = elevC;
}
else {
srand(SeedCoord(glob_x - xmod + base,
glob_z- zmod + base,
seed));
for (int i = 0; i < F; i++) {
rand();
}
float elevB = (rand()+yShift) * h_fac * pow(2.0f, -pow((float)F,persist));

srand(SeedCoord(glob_x - xmod + base,
glob_z - zmod,
seed));
for (int i = 0; i < F; i++) {
rand();
}
float elevD = (rand()+yShift) * h_fac * pow(2.0f, -pow((float)F,persist));

top = elevA + xmod*(elevB-elevA)/base;
bottom = elevC + xmod*(elevD-elevC)/base;
}

if ( zmod == 0 ) {
fList[F] = bottom;
}
else {
fList[F] = bottom + zmod*(top - bottom)/base;
}
}
}

float finalOut = 0;

for (int i = from; i <= to; i++) {
finalOut += fList;
}

delete [] seedList;
delete [] fList;

return finalOut;
}
World::World(int size_in, int secsize_in, int numplanes_in, int numvors1_in, int numvors2_in, int numfaults_in)
: N (size_in),
Sz_2powN ((int)pow(2.0f, N)),
Sz_2powN_plus1 ((int)pow(2.0f, N)+1),
Half_Sz_2powN (Sz_2powN/2),
Last_Seed ((Sz_2powN_plus1*Sz_2powN_plus1)-1),
Sec_Size (secsize_in),
Num_Vors1 (numvors1_in),
Num_Vors2 (numvors2_in),
Num_Planes (numplanes_in),
Num_Faults (numfaults_in)
{
Feat_Set = false;
Planes = new VorPlane[Num_Planes];
Vor_Points1 = new MapFeature[Num_Vors1];
Vor_Points2 = new MapFeature[Num_Vors2];
Faults = new ShiftFault[Num_Faults];
}[/spoiler]


I included the constructor and the class definition so maybe you can figure out what the member variables should be initialized with. the GetPerlinH() function returns a height value given an x, y. from and to is a range of levels that are included in the final averaged height (0-max levels), yShift is an absolute offset, h_fac is a multiplier based on height (higher value will accentuate values further from the 0 level, persist is a value that determines how much higher frequency samples are included (should be in the range of 0.5-0.7 to start), and providing a different seed will give you different results.

I'm very interested in procedurally generated content for games and one area where not much work has been done is indoor environment generation. I just did a dissertation on it and it might be interesting to some people:

[attachment=1249:CompleteFinalDraft.pdf]

Basically, it describes a way to hierarchically subdivide spaces into meaningful subdivisions of predefined characteristics. e.g. rooms of certain sizes etc. Warning: it's rather lengthy!

I'm very interested in procedurally generated content for games and one area where not much work has been done is indoor environment generation. I just did a dissertation on it and it might be interesting to some people:

[attachment=1249:CompleteFinalDraft.pdf]

I just had a quick look -- very nice! Thanks for posting that!

If you're up for it, I think it would make a nice article (or series of articles) on GD.net.

Im looking for some kind of Noise function that takes two float values x and y and returns a value in between -1 and 1. I've been googling around for Perlin Noise, but I all I find is where people use it for images and creating the same bitmaps with width and height as parameters.

Does anyone know a good site or even more simple, have anyone written such a function?

You can check out libnoise. It is an open source noise library that is structured along the idea of chaining different noise functions together to create complex patterns out of simple building blocks. So for example, you can take a noise function, chain it with a turbulence function that has as auxiliary inputs 3 other noise functions, and the result is the initial function with domain distortion applied to modify the output. The concept of chaining functions together is a very powerful one, and I use the same methodology in my own personal library. In this journal post of mine, I detail how I generate an island, complete with grass and desert areas, mountains, and areas of forest, using nothing but a complex tree of various functions. The basis of it begins as a "fuzzy disk" function, a function that uses the distance of a given point from the designated center to generate a value in the range [0,1]. This function is distorted using domain turbulence so that the shape is more 'island-y', then various other fractal and turbulence functions are used to designate areas of mountain, snowy mountain, grassland, etc... I prepared a small demo available here that demonstrates the idea; it presents a scrolling view of an isometric game world with a button labeled Generate that will build a new island for you to view. You can left click on the map to scroll it "Diablo-style". The source is available via the Lua scripts in the root directory; pay particular attention to the islandtree.lua and levelgenerator.lua files as they form the 'guts' of the island generator, with islandtree.lua holding the table that structures the tree of functions, and levelgenerator.lua using that information to actually construct the map.


Calling noise functions via floats (or even doubles, for extra large worlds) is actually a very good idea, if for no other reason than that if you want to 'zoom in' on the map you can do so merely by sampling a smaller domain of the function and if the function is well-structured (ie, you have sufficient octaves of layered noise, etc) then the result is a continuous level of detail down to very small areas of the domain.

I have found the use of noise, and especially turbulence, to be useful in all sorts of applications, including indoor areas and street-maps. I have done street maps before where I laid down a regular grid of streets, then applied some low-octave fractal noise turbulence to move the streets around and give the whole thing some curvature, kind of noise-up the grid a bit. It is also good for cave levels, where, for example, you can multiply a couple of Ridged Multifractal fractal functions and apply some turbulence, as I did in the Minecraft-style generation journal entries I linked earlier.

First off, thanks for all the good answers, keep 'em comming Im reading with eager eyes as soon as a new reply shows up!

[quote name='Doggolainen' timestamp='1296576826' post='4767994']
Im looking for some kind of Noise function that takes two float values x and y and returns a value in between -1 and 1. I've been googling around for Perlin Noise, but I all I find is where people use it for images and creating the same bitmaps with width and height as parameters.

Does anyone know a good site or even more simple, have anyone written such a function?

Calling noise functions via floats (or even doubles, for extra large worlds) is actually a very good idea, if for no other reason than that if you want to 'zoom in' on the map you can do so merely by sampling a smaller domain of the function and if the function is well-structured (ie, you have sufficient octaves of layered noise, etc) then the result is a continuous level of detail down to very small areas of the domain.
[/quote]


This is an issue where my brain is really stuck right now. I've managed to generate a world that looks great from a distance, but as I zoom in the borders in between the tiles form straight edges etc. Could you describe more on how one can zoom into some kind noise function and genereate the noise there with a better "resolution"?