Saturday, January 19, 2008

Procedural Generation in Games

Ever wondered why, in games like Grand Theft Auto, you generally can't get into the buildings of cities to explore their interiors? Usually, it's a matter of time and memory, but these restrictions may change in the near future thanks to new techniques in procedural generation.

If a designer were forced to meticulously create the interiors of each and every building in an urban sandbox game like GTA, the game would no doubt end up well over budget. Even if the time were allotted, a typical game or DVD disc might not even have the capacity to hold all the models. So what if, instead, you could build up the models as they are required based on only a small, unique piece of information? That's what the second talk I saw for the candidates of a faculty position here at Carleton was all about (the first talk being on research in computational video). It was called "Generation P: The P Stands for Simulation" and given by Dr. Anthony Whitehead, who currently works in the School of Information Technology here at Carleton.

Procedural generation is all about creating objects and behaviors from some set of rules rather than explicit control from designers and developers. This makes the content available on demand, and not only reduces development time for a game, but can also add to the realism (since no two objects will be the same), unpredictability, and freedom of action on the part of the gamer.

There are some recent games that are out (or almost out) using procedural generation. In fact, the latest Grand Theft Auto (IV), which is allegedly going to be released sometime between February and April 2008, is said to use procedural generation to increase the number of explorable building interiors. The upcoming game Spore is almost completely procedural based, and many other simulation games like The Sims tend to use a lot of this technique. Other titles that made (or will make) use of procedural generation of some kind include Oblivion: The Elder Scrolls IV, kkreiger, Elite, and Diablo I and II.

You can almost think of procedural generation as a sneaky method for compression. After all, just one small seed value can be used to build the rest of an entire building, making use of the fact that a certain random number generation will always produce the same sequence of numbers. It is by using this fact that developers can ensure the same building is rebuilt every time it is needed.

However, there lies a small challenge still: if a building is destroyed and rebuilt several times during a gaming session, what happens to the changes that the gamer has made due to interactions within? The proven solution turns out to be as simple as you might imagine. A simple hash table is all that is required to persist the interactions.

You can learn more about procedural generation for buildings, with change persistence, in the paper Dr Whitehead co-authored: Lazy Generation of Building Interiors in Realtime.

It's not hard to imagine how procedurally generated content could be applied to many other aspects beyond graphical models. For instance, music in games could be algorithmically generated rather than composed, which could allow, for instance, easier mechanisms for transitioning between different areas on a map that require music of different moods. It will be interesting to see whether games continue along this path and what the results will be.

10 comments:

Anonymous said...

I am really looking forward to Spore. I think it will really rock!

Christian Muise said...

Spore is indeed going to rock...especially since we'll be playing it on our wii's ;).

About generating music on the fly...not so easy. I've done music blending before though - a much easier concept to grasp. You compose the music and give it features (defining its mood, state, etc). I think it was a vector of a size of roughly 20+ elements (too lazy to go dig up the notes).

After that, rules would change the music depending on the mood you input. The more styles you program in (ie. a version for sad, then a version for happy, etc) then the easier it is to interpolate between them. The result was a continuous composition that changed dynamically with the mood (could be hooked up to environment triggers or character states in a game).

But dynamic composition - hard as hell to make anything sound decent/uncanned :p.

Gail Carmichael said...

Yeah, Spore does look cool, hope it comes out in the next decade! ;0)

Actually Haz, that seminar about games audio held here in the fall talked a bit about that. Definitely does not look easy, but interesting nonetheless. Lots of potential even though the more complicated stuff may be a long time off yet.

Christian Muise said...

Well define long way off. I think many tracks of research are a long way off reaching their goals, but progress still happens.

The quest of just generating "good" music is far too broad/subjective. Specific sounds/results can be achieved ( http://www.haz.ca/FFSC/ ), but if you don't enjoy my taste in jazz, or if you want any other type of music generated, then it needs to be reprogrammed.

You could the statistical modeling/analysis of different genres but many have tried, and most have failed :p.

Anonymous said...

Neither Diablo 1 or 2 use procedural generation. Neither does Oblivion.

Spore certainly isn't completely based off of it either, because it was dumbed down for younger audiences.

To be fair, this article is pretty old so you couldn't have known Spore would turn out to be a piece of shit, especially when it did have a lot of potential.

Gail Carmichael said...

Hey 'anonymous', I'm just going by what I found with some good old fashioned Wikipedia research. You'll notice the statement was that these games have or will use 'some kind' of procedural generation. I have no idea if they actually did, but I'm sure it's not impossible that there are at least some minor aspects of each game that use the concept in some small, non-ground breaking kind of way. As for Spore, I actually never ended up playing it. Would like to give it a fair chance and try it at some point, despite the unfortunate mess of copy protection.

Anonymous said...

Anonymous, I'm not sure where you got the idea that Diablo 1 and 2 didn't use procedural generation from, but you're a bit off the mark. True none of the media was generated procedurally, but the maps themselves are definitely generated procedurally.

Procedural content generation encompasses a broad spectrum of ideas ranging from simple map generation to realistic textures and models, music, behaviours, etc.

Gail Carmichael said...

Adrien, I'm glad to see that my research wasn't off the mark. Thanks for commenting.

Daniel said...

Just to clear up the comments made by Anonymous.

Diablo 1 and 2 both famously use procedural generation to create the maps.

The development team for Oblivion used procedural techniques to create the main landscape initially but this isn't part of the game, where everything is static.

Spore uses procedural generation for its planets and star systems, as well as selecting suitable creatures for the player to encounter based on their own creatures development. The creatures, buildings, vehicles and plants are not procedurally generated, however the creatures do use procedural techniques for animation.

Gail Carmichael said...

Thanks for taking the time to clarify things Daniel, much appreciated!

Post a Comment

Comments are moderated - please be patient while I approve yours.

Note: Only a member of this blog may post a comment.