Procedural generation (procgen, also PCG -- procedural content generation -- not to be confused with procedural programming) refers to creation of data, such as art assets in games or test data for data processing software, by using algorithms and mathematical formulas rather than creating it manually or measuring it in the real world (e.g. by taking photographs). This can be used for example for automatic generation of textures, texts, music, game levels or 3D models but also practically anything else, e.g. test databases, animations or even computer programs. Such data are also called synthetic. Procedural art currently doesn't reach artistic qualities of a skilled human artist, but it can be good enough or even necessary (e.g. for creating extremely large worlds), it may be preferred e.g. for its extreme save of storage memory, it can help add detail to human work, be a good filler, a substitute, an addition to or a basis for manually created art. Procedural generation has many advantages such as saving space (instead of large data we only store small code of the algorithm that generates it), saving artist's time (once we have an algorithm we can generate a lot data extremely quickly), parameterization (we can tweak parameters of the algorithm to control the result or create animation, often in real-time), increasing resolution practically to infinity or extending data to more dimensions (e.g. 3D textures). Procedural generation can also be used as a helper and guidance, e.g. an artist may use a procedurally generated game level as a starting point and fine tune it manually, or vice versa, procedural algorithm may create a level by algorithmically assembling manually created building blocks.
As neural AI approaches human level of creativity, we may see computers actually replacing many artists in near future, however it is debatable whether AI generated content should be called procedural generation as AI models are quite different from the traditional hand-made algorithms -- AI art is still seen as a separate approach than procedural generation. For this we'll only be considering the traditional approach from now on.
Minecraft (or Minetest) is a popular example of a game in which the world is generated procedurally, which allows it to have near-infinite worlds -- size of such a world is in practice limited only by ranges of data types rather than available memory. Roguelikes also heavily utilize procgen. However this is nothing new, for example the old game called Daggerfall was known for its extremely vast procedurally generated world, and even much older games used this approach. Some amount of procedural generation can be seen probably in most mainstream games, e.g. clouds, vegetation or NPCs are often made procedurally.
For its extreme save of space procedural generation is extremely popular in demoscene where programmers try to create as small programs as possible. German programmers made a full fledged 3D shooter called .kkrieger that fits into just 96 kB! It was thanks to heavy use of procedural generation for the whole game content. Bytebeat is a simple method of generating procedural "8bit" music, it is used e.g. in Anarch. Procedural generation is generally popular in indie game dev thanks to offering a way of generating huge amounts of content quickly and without having to pay artists.
We may see procgen as being similar to compression algorithms: we have large data and are looking for an algorithm that's much smaller while being able to reproduce the data (but here we normally go the other way around, we start with the algorithm and see what data it produces rather than searching for an algorithm that produces given data). John Carmack himself called procgen "basically a shitty compression".
Using fractals (e.g. those in a form of L-system) is a popular technique in procgen because fractals basically perfectly fit the definition perfectly: a fractal is defined by a simple equation or a set of a few rules that yield an infinitely complex shape. Nature is also full of fractals such as clouds, mountain or trees, so fractals look organic.
There are also other techniques such as wave function collapse which is used especially in tile map generation. Here we basically have some constraints set (such as which tiles can be neighbors) and then consider the initial map a superposition of all possible maps that satisfy these constraints -- we then set a random tile (chosen from those with lowest entropy, i.e. fewest possible options) to a random specific value and propagate the consequences of it to other tiles causing a cascading effect of collapsing the whole map into one of the possible solutions.
A good example to think of is generating procedural textures -- similar techniques may also be used to create procedural terrain heightmaps etc. This is generally done by first generating a basis image or multiple images, e.g. with noise functions such as Perlin noise (it gives us a grayscale image that looks a bit like clouds). We then further process this base image(s) and combine the results in various ways, for example we may use different transformations, modulations, blending, adding color using color ramps etc. The whole texture is therefore described by a graph in which nodes represent the operations we apply; this can literally be done visually in software like Blender (see its shader editor). The nice thing is that we can now for example generalize the texture to 3 dimensions, i.e. not only have a flat image, but have a whole volume of a texture that can extremely easily be mapped to 3D objects simply by intersecting it with their surfaces which will yield a completely smooth texturing without any seams; this is quite often used along with raytracing -- we can texture an object by simply taking the coordinates of the ray hit as the 3D texture coordinates, it's that simple. Or we can animate a 2D texture by doing a moving cross section of 3D texture. We can also write the algorithm so that the generated texture has no seams if repeated side-by-side (by using modular "wrap-around" coordinates). We can also generate the texture at any arbitrary resolution as we have a continuous mathematical description of it; we may perform an infinite zoom into it if we want. As if that's not enough, we can also generate almost infinitely many slightly different versions of this texture by simply changing the seed of pseudorandom generator we use.
We use procedural generation mainly in two ways:
Indeed we may also do something "in between", e.g. generate procedural assets into temporary files or RAM caches at run time and depending on the situation, for example when purely realtime generation of such assets would be too slow.
The following are some techniques and concepts often used in procedural generation:
Here are some cool ASCII renderings of procedurally generated pictures:
....,':..:.,.c;:,,.,'M0....',:c.,c,'o:xcx.',.'l:,;'.:.,
...''.'..:.,.;,''x0Xoc;:::::;lo.':o,c;;c..:l.,''..,...,
.',......',;':',oKxl:'.........',;cX:o0k.'l':''......,.
.;........''';l.:x;,Kkocl;::::;lcxX':cX;'o',,.........,
.:.'........'l;.Kc:Xol:,'.......'':;ck0c'.l',.'.......'
l.'.''.....'.:..XlXo;,'..xooccooxkXKMW.'.:,:..,'..',.,,
...,;,....,.:,.olcxl:'.cl;::,,,::;;coklxolcl..',';'::,'
'':c:.;'.:'l,..oxo:;,.l:,''......'',:.,...'',;;c..c:o;c
x.''.l':k'.l,..oc;;;,;:''.....xxkXK0xKxxxxxk.''''',:.,'
xlc00lkl,.xc;.Xxl::,,:,'...;;;llccol;l;;lllxxxxxkkK;ck'
c:kX:x:klWKxl.KXc;,,'.'..,,,,,,::;,,,,:,:,cooxkK,:;cxKW
oo':o,kl,Kxl:'MKk;;,'....''..''''''''','''',,:;coX0,;oX
c.,o,Xc,.kc;,.Kkoc;:'...............''',,:;c..',;ck.';o
.:.:.o:'.xl:'..xc;:,''..................'',:lo..,:ck.:c
;.l'.l,..o;,'..ol;,''..............'',;...',:lx..,lx.,c
'x:.xl,..o;:'...l:,''...... ......'',:l...':;o..,lx.:x
.c,.xl,..xl:,'...;,''..............'',;lo..',;o..,l.'l.
.c:.kc:,..ol:,''..................'',:;cx..':lx.':o.:.:
0o;'.kc;,'..c;:,,'''...............':;cokK.,;ck.,cX,o,.
'Xo;,0Xoc;:,,'''','''''''''..''....',;;kKM':lxK,lk,o:'o
:WKxc;:,Kkxooc,:,:,,,,;::,,,,,,..'.',,;cXK.lxKWlk:x:Xk:
:'kc;Kkkxxxxxlll;;l;loccll;;;...',:,,::lxX.;cx.,lkl00cl
:',.:,'''''.kxxxxxKx0KXkxx.....'':;,;;;co..,l.'k:'l.''.
oc;o:c..c;;,''...,.:,''......'',:l.,;:oxo..,l':.';.:c:'
,',::';','..lcloxlkoc;;::,,,::;lc.':lxclo.,:.,....,;,..
',,.,'..',..:,:.'.WMKXkxooccoox..',;oXlX..:.'.....''.'.
;'.......'.,'l.'c0kc;:''.......',:loX:cK.;l'........'.:
,,.........,,'o';Xc:'Xxcl;::::;lcokK,;x:.l;'''........;
..,......'':'l'.k0o:Xc;,'.........':lxKo,':';,'......,'
.,...,..'',.l:..c;;c,o:'.ol;:::::;coX0x'',;.,.:..'.''..
0KXXkkxxooooccccccoxo;:,'...',:;lcoxXWKXkkxxxooooccccco
XMXxxooocccclllllllllcl:,'...',:;lcokK0Xxxoooccclllllll
kK0Xxocccllll;;;;;;;;;;l;,'..'',:;lcxk0Kkooccclll;;;;;;
xXMKkocllll;;;;:::::::::;;,'..',:;lcoxXMXxoclll;;;;;:::
okKKkxclll;;;;:::::::,:::;:'..'',:;loxXMXkocll;;;;:::::
okK0kxcll;;;;:::::::,,,::::,...',:;lcxX0Kkocll;;;;:::::
xk0Kkoclll;;;;:::::::::::;:'..',,:;coxXWXxoclll;;;;::::
xXWXxocclll;;;;;;:::::;;l:,...',:;lcokK0kxocclll;;;;;::
k0Kkxooccclllll;;;;;;lll:,'..',:;lcoxXMXkooocccllll;;;;
K0Xkxxxoooccccclllccoc;:,'..',,:;lcxk0Kkkxxooocccccllll
W0KXXkkxxxoooooooxkol;,''..',,:;lcokKM0KXXkkxxxooooooox
K0MM0KXXXkkkkkXK0kcl:,''..'',:;lcokXXK0W00KXXXkkkkkXKMx
kXXK00WMM00MW0k0xcl:,''..'',:;lcoxxxkkXKK0MWM000MMKkXol
xkkkXXXKKKXXxkKxcl;:,'...',,:;lccooxxxkkXXXKKKKXkxXXoc;
xxxkkkkkkkxoxMkol;:,''..'',:;llcccoooxxxkkkkkkkxckKxcl;
oxxxxkkkkxolk0xcl;:,'...'',:;llcccooooxxxxkkkxxooKXxcl;
oxxxkkkkkxxck0kol;:,'...'',:;llcccoooxxxxkkkkkxocXKxcl;
xxkkkXXXXXkxcKXoc;:,''...',::;lccoooxxxkkkXXXXXkxxWkol;
kkXXKK000000XkKkol;:,'...'',:;lcooxxxkkXXKK00000KXoMxcl
XKK0W00KKXXXXK0XXol;:,'. .',::;lcxkkXXK0MM0KKKXXXKKWXkc
0W0KKXkkkxxxxxxxkKxc;:,'...',:;;coxXK0M0KXXkkkxxxxxxxkM
0KXkkxxxooooccccccoxol:,'...',:;lcoxXMKXkkxxxoooccccccc
XMXkxooocccllllllllllcc;,'...',:;lcokK0Xxxoooccclllllll
kK0Xxocccllll;;;;;;;;;;l;,'..'',:;lcxk0Kkxoccllll;;;;;;
xX0Kkocllll;;;;:::::::::;;,'..',:;lcoxXMXxoclll;;;;;:::
okKKkxclll;;;;:::::::,:::;:'..'',:;loxXMXkocll;;;;:::::
okK0kxclll;;;:::::::,,,::::,...',:;lcxX0Kkocll;;;;:::::
xk0Kkoclll;;;;:::::::::::;:'..',,:;coxXWXxoclll;;;;::::
xXWXxoccllll;;;;;:::::;;c:,...',:;lcokK0kxocclll;;;;;::
k0Kkxooccclllll;;;;;;lcl:,'..',:;lcoxXWXxooocccllll;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
ll;;;;;;;;;;;;llllll;;;;;;;;;;;;llcxolllcXocl;;;;;;;;;;
.',ol;;;;;;lol:,,,,,;Kl;;;;;;lo:'...........',ll;;;;;;l
....:c;;;;lc,'.......':c;;;;ll'....':;ll:,'....,o;;;;lK
;'...;l;;;l;'.........,o;;;;x'...,xl;;;;;;ll'...:l;;;ll
c:...'c;;;;o,'.......'cl;;;l:...'xl;;;;;;;;l;'..'0;;;;c
x,...';l;;;;lcc:,,:;xl;;;;;K'...';cl;;;;;;lx,'...:l;;;;
'.....';l;;;;;;;;;;;;;;;;lW,.....',;xoookc:,'....':c;;;
.......',:ocll;;;;;;llck;,'..........''''.........',:co
...........''''''''''''...............................'
.......................................................
'''.............................'',,:::::,,,''.........
;lcl,'......',:;;l;:,''......':xl;;;;;;;;;;;lcc,'......
;;;;l;'...':Wll;;;;;lo;'....,x;;;;;;;;;;;;;;;;;ll'....,
l;;;;l,...,kl;;;;;;;;;c:...'k;;;;lo:,'''',ll;;;;l:...'l
:c;;;;c'..'ll;;;;;;;;;o,...:l;;;lc'.......',o;;;;o'..';
:o;;;;l,...':ol;;;;lll,...'X;;;;l;'.......',Xl;;;l:...'
xl;;;;;c:'.....'''''.....'ol;;;;;cl,''''',:Wl;;;;;l:'..
;;;;;;;;lo;,'........'':xl;;;;;;;;;llccccll;;;;;;;;lcl,
;;;;;;;;;;;;llllllllll;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
:coll;;;;;;;;;;;;;;;;;;;;;;;;;lck;,,'''''',:lxll;;;;;;;
...';l;;;;;;lloxllckcl;;;;;;lW,'..............':c;;;;;;
'....:l;;;;lo,'....',;c;;;;;X'...',ocllllo;,....,c;;;;l
l;'..'0;;;;c:'......',k;;;;l,...,o;;;;;;;;;ll'..'l;;;;l
;c,...:l;;;;o:''...',ol;;;;o'..'cl;;;;;;;;;;c:...,c;;;;
lX,...'ll;;;;;llcccl;;;;;;o,...';l;;;;;;;;;lo,...';l;;;
;,'....':cl;;;;;;;;;;;;;lc,.....':Kcllllllcl,'....':xl;
'........'',;cKoccoxo;:,'........''',,,,,,''.... ...'',
These were created in extremely simple way, without even using any noise -- each picture here has each pixel computed by plugging the x and y coordinate to a quite simple equation using basic functions like sine, square root, absolute value, triangle wave etc. More complex methods will probably iteratively apply various filters, they may employ things like cellular automata and so on, however here you see even a very simple approach may often be good enough. The C code to generate the pictures above is following (for simplicity using floats and math.h, which in serious programs should be avoided):
{ NOTE: The equations for the functions were made by me when I was playing around with another project. I have uploaded them to Wikimedia Commons, you can find actual png pictures there. ~drummyfish }
#include <stdio.h>
#include <math.h>
#define W 55
#define H 30
// helper stuff:
char palette[] = "WM0KXkxocl;:,'. ";
double min(double a, double b) { return a < b ? a : b; }
double max(double a, double b) { return a > b ? a : b; }
double absMy(double x) { return x < 0 ? -1 * x : x; }
double gauss(double x) { return exp((-1 * x * x) / 2); }
double tri(double x)
{
x = absMy(x);
int whole = x;
double frac = x - whole;
return whole % 2 ? 1 - frac : frac;
}
void drawFunction(double (*f)(double, double), double xFrom, double yFrom,
double xTo, double yTo)
{
double v1 = 0xffffffff, v2 = -1 * v1;
double sX = (xTo - xFrom) / W, sY = (yTo - yFrom) / H;
for (int y = 0; y < H; ++y)
for (int x = 0; x < W; ++x)
{
double v = f(xFrom + x * sX,yFrom + y * sY);
if (v > v2)
v2 = v;
if (v < v1)
v1 = v;
}
v2 -= v1;
if (v2 == 0)
v2 = 0.0001;
for (int y = 0; y < H; ++y)
{
for (int x = 0; x < W; ++x)
putchar(palette[(int) (15 *
((min(v2,max(0,f(xFrom + x * sX,yFrom + y * sY) - v1))) / v2))]);
putchar('\n');
}
}
// ==== ACTUAL INTERESTING FUNCTIONS HERE ===
double fSnakes(double x, double y)
{
return sqrt(tri(x + sqrt(tri(x + 0.4 * sin(y*3)))));
}
double fYinYang(double x, double y)
{
double r = sin(1.2 * y + 2.5 * sin(x) + 2 * cos(2.25 * y) * sin(x));
return log(2 * sqrt(absMy(r)) - r);
}
double fSwirl(double x, double y)
{
return gauss(
fmod((x * x),(absMy(sin(x + y)) + 0.001)) +
fmod((y * y),(absMy(sin(x - y)) + 0.001)));
}
int main(void)
{
drawFunction(fSwirl,-2,-2,2,2);
putchar('\n');
drawFunction(fSnakes,-1,-1,2,2);
putchar('\n');
drawFunction(fYinYang,-4,-4,4,4);
}
Now let's take a look at some iterative algorithm: an extremely simple dungeon generator. This is so called constructive algorithm, a simple kind of method that simply "constructs" something according to given rules, without evaluating how good it's work actually is etc. All it's going to do is just randomly choose a cardinal direction (up, right, down, left), draw a line of random length, and repeat the same from the line's endpoint, until predefined number of lines has been drawn (a kind of random walk). Here is the C code:
#include <stdio.h>
#define W 30 // world width
#define H 30 // world height
char world[H * W]; // 2D world array
unsigned int r = 12345; // random seed here
unsigned int random()
{
r = r * 321 + 29;
return r >> 4;
}
void generateWorld()
{
int steps = 100; // draw this many lines
int pos = 0;
int add = 1; // movement offset
int nextLineIn = 1;
for (int i = 0; i < H * W; ++i)
world[i] = ' ';
while (steps)
{
world[pos] = 'X';
nextLineIn--;
int nextPos = pos + add;
if (nextPos < 0 || nextPos >= W * H || // going over world edge?
(add == 1 && nextPos % W == 0) ||
(add == -1 && nextPos % W == W - 1))
nextLineIn = 0;
else
pos = nextPos;
if (nextLineIn <= 0)
{
steps--;
nextLineIn = W / 5 + random() % (W / 3);
add = (random() & 0x10) ? W : 1;
if (rand() & 0x80)
add *= -1;
}
}
}
int main(void)
{
generateWorld();
for (int i = 0; i < H * W; ++i) // draw
{
char c = world[i];
putchar(c);
putchar(c);
if ((i + 1) % W == 0)
putchar('\n');
}
return 0;
}
And here is one possible output of the program:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXX XXXX XX XXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXX XXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXX XXXX XX XX XXXX XX XX X
XXXX XXXX XX XX XXXX XX XX X
XXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XX X
XXXX XXXX XX XX XX XXXX XX XX X
XXXX XXXX XX XX XX XXXX XX X
XXXX XXXX XX XX XX XXXX XX X
XXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X
XX XX XX XX XX XXXX XX X
XX XX XX XX XX XXXX XX X
XXXXXXXXXXXXXX XX XX XXXX X
XX XX XX XX XX XXXX X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X
XXXXXXXXXXXXXXXXXXXXXX XX X
XX XX XX XX XX X
XX XX XX XX XX X
XX XX XX XX XX X
XX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X
XX XX XX XX XX X
XX XX XX XX XX X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X
XX XX XX XX XX XX X
XX XX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XX XX XX XX XX XX X
XX XX XX XXXXXXXXXXXXXXXXXXXXXXXXXXX
XX XX XX XX
XX XX XX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XX
TODO: some example with noise
Powered by nothing. All content available under CC0 1.0 (public domain). Send comments and corrections to drummyfish at disroot dot org.