8 ms·

Procedural Building Generation in Unreal Engine 3

65 points by grinich 16y ago

bhickey 16y ago
The results look amazing! I've always wished SimCity had done this. The semantics for describing buildings seem a bit clunky. CityEngine uses (or used) shape grammars implemented as stochastic context-free grammars for building generation. Suppose we want to design some buildings: Building ::= [1.0 First Floor + Rest of Floors] First Floor ::= [0.4 Door | 0.6 Door + Windows] Rest of Floors ::= [0.6 Roof | 0.4 Windows + Rest of Floors] With three rules we can churn out buildings, where 60% are 1 story, 24% are 2 story, 14.4% are 3 story, and so on. Here's a video of Pompeii built from a shape grammar. [http://www.youtube.com/watch?v=iDsSrMkW1uc http://www.youtube.com/watch?v=iDsSrMkW1uc]
iwwr 16y ago
Would we be seeing live procedural generation of this sort in games in the near future?
- bonzoesc 16y ago
  If Epic's building it, you can expect it. They're one of the biggest middleware providers for games. IIRC, many games use a procedural foliage generator for trees and shrubberies.
  - bhickey 16y ago
    You do recall correctly. Speed tree brings us shrubbery to plenty of games. [http://www.speedtree.com/ http://www.speedtree.com/]
- teamonkey 16y ago
  I don't think that this is 'live' per se, at least it's not real-time. It's a tool to help level designers design city buildings quickly, as opposed to something like Subversion's procedural city. Either the building mesh is generated procedurally when the level is loaded or it is generated and 'baked' in to the static level mesh at compile time (it's not entirely clear from the doc which method it uses).
johnwatson11218 16y ago
What do people think about the results of procedural generation in terms of information theory? If I get a CD that has code on in that lets me generate level upon level how much information is that CD carrying? For doing data compression has anyone ever heard about using these techniques to generate other things besides 3D game levels?
- deleted 16y ago
  [deleted]
- wmf 16y ago
  It sounds like you're describing fractal compression. It's true that fractals can generate apparently complex output from small input, but if you're trying to compress a specific piece of data (like, say, a map of New York City) they don't seem to be much help.
- partition 16y ago
  You touch on a very interesting and general concept, and that is the correspondence between lossless compression algorithms and probability distributions, and the subsequent correspondence between probability distributions and procedural generation algorithms. Consider the first correspondence. Suppose you knew a certain class of strings arose from a probability distribution. Then you can talk about the strings that are most likely to occur, or, more useful in general, about the individual characters that are most likely to occur given a history of previous characters. Using this, you can make a compression algorithm that will map (symbol, probability) or (symbol + history, conditional probability) starting from the highest probability, to the numbers 0, 1, 2 ... This is arithmetic coding. http://en.wikipedia.org/wiki/Arithmetic_coding http://en.wikipedia.org/wiki/Arithmetic_coding The result is optimal in terms of expected compressed string length assuming the strings you use this on really do come from that distribution. Now consider the other way around. Suppose you have a lossless compression algorithm. Find the (uncompressed symbol, compressed symbol) pair (possibly with context) that achieves the highest compression. Assign that a high probability. Then find the next pair. Assign that a slightly lower probability (This can be done in a more principled manner than I'm alluding here). Then you have yourself a probability distribution. More on data compression theory: http://en.wikipedia.org/wiki/Data_compression http://en.wikipedia.org/wiki/Data_compression But what happens once you have a probability distribution over some data type, is that you may cast the problem of automatically generating instance of that data type as sampling from the distribution. Many procedural generation algorithms that give nondeterministic results (and the useful ones do, otherwise the work the modeler has to do is fundamentally the same) can be re-cast as sampling from a probability distribution; look at what the algorithm is generating and learn the distribution. Note that this is uncomputable in general for the same reason Kolmogorov complexity is. This is known as Solomonoff induction: http://singinst.org/blog/2007/06/25/solomonoff-induction/ http://singinst.org/blog/2007/06/25/solomonoff-induction/ So to answer your original questions: 1. The information (as in information entropy) in the algorithm in the CD is the entropy of the true probability distribution from which your levels originate. 2. And yes, in principle you can use the correspondence between data compression and procedural generation to generate instances of any arbitrary data type, not just 3D game levels. It may be hard to design a probability distribution that will create well-formatted instances though :)
smcl 16y ago
This is a really interesting insight into an aspect of a game I'd normally never give much though to. Very good article indeed. However I noticed something in this that I HATE seeing in real life, variables (ok "properties", here) prepended with a character or characters indicating type (seems only booleans here, bBlah and such). I honestly can't say why it bothers me, but it makes code really tough to read. It really shouldn't, I mean it technically should be useful as it gives a bit more info to the person reading the code, but I find it infuriating. I wonder if anyone else has this possibly irrational hatred.
- wmf 16y ago
  That's http://en.wikipedia.org/wiki/Hungarian_notation http://en.wikipedia.org/wiki/Hungarian_notation — it seems to be popular among Windows programmers.
razh 16y ago
Direct link to the GDC 2010 slides (.pptx): http://unrealtechnology.com/Downloads/Slides/GDC2010_Golding_ArtistDrivenProceduralBuildings.pptx http://unrealtechnology.com/Downloads/Slides/GDC2010_Golding...
wmf 16y ago
If you like that, check out Subversion. Not only does it procedurally generate cities, but they look totally sci-fi. http://forums.introversion.co.uk/introversion/viewtopic.php?t=1837 http://forums.introversion.co.uk/introversion/viewtopic.php?...
spyder 16y ago
Here is an another cool city generator: http://www.youtube.com/watch?v=VnWUp9JnLyc&feature=related http://www.youtube.com/watch?v=VnWUp9JnLyc&feature=relat... This is for the Subversion game that is in development since long ago: http://www.introversion.co.uk/subversion/ http://www.introversion.co.uk/subversion/
d5tryr 16y ago
Interesting read, I'd love to get the same insight in to the Assassin's Creed team's methods...

65 points by grinich 16y ago

The results look amazing! I've always wished SimCity had done this. The semantics for describing buildings seem a bit clunky. CityEngine uses (or used) shape grammars implemented as stochastic context-free grammars for building generation. Suppose we want to design some buildings: Building ::= [1.0 First Floor + Rest of Floors] First Floor ::= [0.4 Door | 0.6 Door + Windows] Rest of Floors ::= [0.6 Roof | 0.4 Windows + Rest of Floors] With three rules we can churn out buildings, where 60% are 1 story, 24% are 2 story, 14.4% are 3 story, and so on. Here's a video of Pompeii built from a shape grammar. [http://www.youtube.com/watch?v=iDsSrMkW1uc http://www.youtube.com/watch?v=iDsSrMkW1uc]

iwwr 16y ago

Would we be seeing live procedural generation of this sort in games in the near future?

bonzoesc 16y ago
If Epic's building it, you can expect it. They're one of the biggest middleware providers for games. IIRC, many games use a procedural foliage generator for trees and shrubberies.
- bhickey 16y ago
  You do recall correctly. Speed tree brings us shrubbery to plenty of games. [http://www.speedtree.com/ http://www.speedtree.com/]
teamonkey 16y ago
I don't think that this is 'live' per se, at least it's not real-time. It's a tool to help level designers design city buildings quickly, as opposed to something like Subversion's procedural city. Either the building mesh is generated procedurally when the level is loaded or it is generated and 'baked' in to the static level mesh at compile time (it's not entirely clear from the doc which method it uses).

johnwatson11218 16y ago

What do people think about the results of procedural generation in terms of information theory? If I get a CD that has code on in that lets me generate level upon level how much information is that CD carrying? For doing data compression has anyone ever heard about using these techniques to generate other things besides 3D game levels?

deleted 16y ago
[deleted]
wmf 16y ago
It sounds like you're describing fractal compression. It's true that fractals can generate apparently complex output from small input, but if you're trying to compress a specific piece of data (like, say, a map of New York City) they don't seem to be much help.
partition 16y ago
You touch on a very interesting and general concept, and that is the correspondence between lossless compression algorithms and probability distributions, and the subsequent correspondence between probability distributions and procedural generation algorithms. Consider the first correspondence. Suppose you knew a certain class of strings arose from a probability distribution. Then you can talk about the strings that are most likely to occur, or, more useful in general, about the individual characters that are most likely to occur given a history of previous characters. Using this, you can make a compression algorithm that will map (symbol, probability) or (symbol + history, conditional probability) starting from the highest probability, to the numbers 0, 1, 2 ... This is arithmetic coding. http://en.wikipedia.org/wiki/Arithmetic_coding http://en.wikipedia.org/wiki/Arithmetic_coding The result is optimal in terms of expected compressed string length assuming the strings you use this on really do come from that distribution. Now consider the other way around. Suppose you have a lossless compression algorithm. Find the (uncompressed symbol, compressed symbol) pair (possibly with context) that achieves the highest compression. Assign that a high probability. Then find the next pair. Assign that a slightly lower probability (This can be done in a more principled manner than I'm alluding here). Then you have yourself a probability distribution. More on data compression theory: http://en.wikipedia.org/wiki/Data_compression http://en.wikipedia.org/wiki/Data_compression But what happens once you have a probability distribution over some data type, is that you may cast the problem of automatically generating instance of that data type as sampling from the distribution. Many procedural generation algorithms that give nondeterministic results (and the useful ones do, otherwise the work the modeler has to do is fundamentally the same) can be re-cast as sampling from a probability distribution; look at what the algorithm is generating and learn the distribution. Note that this is uncomputable in general for the same reason Kolmogorov complexity is. This is known as Solomonoff induction: http://singinst.org/blog/2007/06/25/solomonoff-induction/ http://singinst.org/blog/2007/06/25/solomonoff-induction/ So to answer your original questions: 1. The information (as in information entropy) in the algorithm in the CD is the entropy of the true probability distribution from which your levels originate. 2. And yes, in principle you can use the correspondence between data compression and procedural generation to generate instances of any arbitrary data type, not just 3D game levels. It may be hard to design a probability distribution that will create well-formatted instances though :)

smcl 16y ago

This is a really interesting insight into an aspect of a game I'd normally never give much though to. Very good article indeed. However I noticed something in this that I HATE seeing in real life, variables (ok "properties", here) prepended with a character or characters indicating type (seems only booleans here, bBlah and such). I honestly can't say why it bothers me, but it makes code really tough to read. It really shouldn't, I mean it technically should be useful as it gives a bit more info to the person reading the code, but I find it infuriating. I wonder if anyone else has this possibly irrational hatred.

wmf 16y ago
That's http://en.wikipedia.org/wiki/Hungarian_notation http://en.wikipedia.org/wiki/Hungarian_notation — it seems to be popular among Windows programmers.

razh 16y ago

Direct link to the GDC 2010 slides (.pptx): http://unrealtechnology.com/Downloads/Slides/GDC2010_Golding_ArtistDrivenProceduralBuildings.pptx http://unrealtechnology.com/Downloads/Slides/GDC2010_Golding...

wmf 16y ago

If you like that, check out Subversion. Not only does it procedurally generate cities, but they look totally sci-fi. http://forums.introversion.co.uk/introversion/viewtopic.php?t=1837 http://forums.introversion.co.uk/introversion/viewtopic.php?...

spyder 16y ago

Here is an another cool city generator: http://www.youtube.com/watch?v=VnWUp9JnLyc&feature=related http://www.youtube.com/watch?v=VnWUp9JnLyc&feature=relat... This is for the Subversion game that is in development since long ago: http://www.introversion.co.uk/subversion/ http://www.introversion.co.uk/subversion/

d5tryr 16y ago

Interesting read, I'd love to get the same insight in to the Assassin's Creed team's methods...