Procedural Generation

February 14, 2010 9:27 PM

Looking for a good book or detailed online guide to applying procedural generation in the creation of video games.

I would like to learn more about how one might go about employing procedural generation in the creation of terrain, 3d models, AI, etc. I have done some searching on the web, and while there are references to games that use such technology such as Spore and kkreiger, I have not been able to find a good guide to using these techniques. Most available tools (open source and otherwise) for game creation rely exclusively on precompiled resources, if there any out there that support procedural generation, I would love to hear about those as well.

posted by sophist to technology (8 answers total)

The Algorithmic Beauty of Plants (scroll down for the PDF) is a good place to start.
posted by b1tr0t at 9:32 PM on February 14, 2010

A Survey of Procedural Methods in Entertainment Computing (NB: last updated August 2007) has lots of article references

There's a whole wiki on the subject, which actually appears to have a fair amount of information and references on it.

Most of the Game Programming Gems books have some procedural content articles.
posted by jedicus at 9:50 PM on February 14, 2010 [1 favorite]

I don't have a general guide, but I use the Diamond-Square algorithm routinely for generating gorgeous terrain. The simplification to 2D is straightforward. These are of a class of algorithm that generates a midpoint displacement fractal. Textures can then be applied from a height-based heuristic. Both of those algorithms are very easy to use, and have a very nice property for multiplayer: namely, multiple players can generate the same arbitrary-size terrain by sharing only a common random seed and the heightmap seed values--very efficient. Of course, there are definite disadvantages to using a heightmap for level representation: overhangs and holes in the level are impossible, without significant work.

But, basically, what most people in the games industry mean when they say "procedural" is that they generated a resource at run-time with code as opposed to with a static file. So, for instance, instead of having a texture for a model, they'll apply a shader to it. Or, instead of having a model for a building, they'll generate the mesh in code. Or, instead of having the quest be in a script somewhere, a set of locations and objectives will be selected from a table. It sounds really sexy, but in reality, it's just code... where you'd use a resource file, you figure out a way to do it in code. Not particularly general, really, which is why not many specifics are usually given.

Also, I'll note that it's much easier to use a procedural approach for graphics in 2D-rendered games. The 3D pipeline has lots and lots of places where a slightly bad mesh or texture can turn out looking fucking terrible. A self-intersection, or a seam on an edge, or a triangle wound the wrong way will all result in unprofessional-looking graphics. And fixing the algorithms so that they generate only well-formed models generally takes such an enormous amount of work that it's not worth it.

So, for instance, Borderlands used a random-procedural model for loot and enemies, but not to actually generate terrain or character models (although it did seem to cobble together multiple sub-meshes for character outfits).
posted by Netzapper at 12:27 AM on February 15, 2010

Not the guide you're looking for, but Shamus Young has done some good blog writing on procedural generation. There's his Pixel City, also his critique of Fuel. I imagine if you wrote and asked him, he'd have some references for you.
posted by Nelson at 8:20 AM on February 15, 2010

You'll need to do some sorting on your own to decide what's relevant to you, but there's been a lot of stuff on Gamedev.net about procedural content over the years.
posted by ecurtz at 8:49 AM on February 15, 2010

I also remember this pdf article by the guy who did the terrain for Tribal Trouble to be a pretty decent beginners guide to procedural terrain. And it looks like they've released their source code now as well if you want something to look at.
posted by ecurtz at 9:00 AM on February 15, 2010

Great resources all. Source code and tutorials are really what I am looking for, and marked as best answer for such. The Diamond-Square paper looks great but somewhat beyond my level right now. I do realize that generating 3D models and terrain procedurally is prone to massive failure, but there seems like so much potential there I wanted to look deeper at what was involved. Plenty to read over here, thanks very much to everyone!
posted by sophist at 4:19 PM on February 15, 2010

Seen Diamond-Square mentioned a few other places since, and it seems like a very important resource for procedural terrain generation. Also, with your excellent clarification I am starting to see how this technique might be applied.
posted by sophist at 5:20 AM on February 21, 2010