I've been googling alot; looking for good sites that cover procedural generated content (i.e. Minecraft). All I run into is very basic maze algorithms, fractals and noise for texture generation, etc. What I am looking for is more of a big picture archictecture on how to divide and connect different procedural genereted content. Also I want to find some kind of "approach" on how to create an algorithm that generates something. I reckon Minecraft or similar games are not just one big code-block with thousands of nested loops that generates everything from clouds to the branches of a tree. There must be some kind of structure, for instance:

World generator generates forest
Forest generator generates trees
Trees generate branches


I know there isn't a "by the book approach" and Im not planning to make another Minecraft, but I do want to get inspiration and see how others have made it - so I dont have to tackle problems that have been solved a hundread times before.

So, any suggestions for a URL, game or blog that I could read?

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

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.