Update

[less_retarded_wiki.git] / procgen.md

# Procedural Generation

Procedural generation (procgen, also PCG -- *procedural content generation* -- not to be confused with [procedural programming](imperative.md), but see also [RNG](rng.md)) refers to creation of [data](data.md) (and in rarer cases maybe even [programs](program.md)), such as [art](art.md) assets in [games](game.md) or test data for data processing software, by using [algorithms](algorithm.md), [mathematical](math.md) formulas and [randomness](randomness.md) rather than creating them manually or measuring them in the [real world](irl.md) (e.g. by taking photographs, 3D scans etc.). This can be used for example for automatic generation of [textures](texture.md), texts, [music](music.md), game levels or 3D models but also practically anything else, e.g. test [databases](database.md), 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](good_enough.md) 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](3d_texture.md)). It's also [fun](fun.md) for the programmer. 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.

Procedural generation basically means randomly generating things with some added cleverness, i.e. some kind of algorithm and parameter tuning. Randomly generating something isn't that hard, provided we have a good (pseudo)random number generator -- for example to generate random loot in an RPG game may be as simple as generating a single random number representing the item ID -- this isn't yet procedural generation. The process becomes procedural generation if we throw in more rules and cleverness: for example once we start randomly generating cities so that their layout makes some sense (i.e. there are no unreachable streets, buildings in middle of the roads etc.). While doing this it's important to retain in mind all the rules of handling randomness with computers, i.e. we don't really want to employ true randomness but rather [deterministic](determinism.md) [pseudorandomness](pseudorandomness.md)! The whole thing, no matter how big, will be generated just from a single seed number. The same seed must always generate the same thing. And so on and so forth.

```
xc,.....,:cco,,,';,;o:':l:kkkxoooxkkc:',..'.xocxxx  ,,:lccoxxkkkx;',;:;lck ,;;, xcl;::,':xkkkxxoccl;,'
kx:,:'.'.'':;'...ooXkxl:xXXxocccccokkxkx;;',l:cXoX  :,::lcoxxkkXKKK:'',;lx :,,;.xc;:'',KKKXkkxxocl::,,
kcc;:':','.......::XkXckkxkxocccooxkkXkXXxco:clkkX  lll:,:lcoxxxkXKXc'',;o :;;; ol,''lXKXkkxxocl:,:lll
xx;;:'lo;.........;ckxxXkxxoooccooxkkkkkkoXkoxokxk  ccoll:,;loccoxXxoo;.,l,:::;,l:.;ooxXxoccol;,:;locc
x:'.:,;xl'.......',;;xXkkxxxxoooooxkkkkkXxXkkxkkkk  xxxocll::loooxXxocoo:..,;:,'.,xocoxXxoool::llcoxoo
o:,:xXXkk:.........:'Kkxxxkkkkxxxkxkkkkxkokcl',XxX  xkXxxxccl;;cxkXxolccoo, ,: ,ooccloxXkxc;;lccxxkXkx
:''cokkkX,........','0kxoxkxkkkkkkkxkkkkkXo:..,ll;  kkXkxxcoxcl;cxKxo;llccol',loccll;oxKxcllcxocxxkKkk
..;'';l,'........lXkXXxxxxkkxxkkkkkkx;;occ,.....'.  ,o0XkkoxxxxoccXkx;;;llccooccll;;;xkXccoxxoxokkX0x,
..'''.........,',0kxoooxxxoocoxkkkkx:,:',:,.......  ':;XKKkkkkkXKXXxloccllccooccllccoloXXKXkkkkkKKK;:.
..:c::.....':olc'Kxocooxxxoocoxkkkx;'.'c:;'.......  :,'.:kooccllllclkkK;::::;;;:::;KXXccllllccock;'',,
kkKXkoc;cXxKKXXxcXkxoxkkkkkkkxokxxk;..;':'.....,lc  ;;:,'.loccll;;;kko:xoc..''..cok:okk;;;llccol'',::;
xxxxxxxkkkXkkkkkxkxoooxxkkkcl:;xkk;.........';kKkk  cccl;:,'loccll;l:;xkKccllllccKXxl:l;lllcoc'':;lccc
ooxxxkokkkkkkxxxkxxooxxkc::';:,,cl'','.....c0kkooc  ''''.':, 'oocclc;:,:cKWMkxMWMc:'::cllcox,.':,.''''
cooooxk;'xkxxkkkxkkxoxoc;kXc'',,,'',,......cXxcccc  ::l;;:;:;'.;oocol:.'oX0oK0o0Xx, :locool'';;::;:l::
oxkkxk;.'oXkxkkkxkxkkx',;okxccx;';c:.'.....xXxxooo  :lc:;;;::''lcoool:.'okKo0Mo0Xx,.:loooo;'';:;;;,ll,
;,:,'''.'lkkxxxooxxok''',:oXkxkkkko'...;;,:,cccxcl  ''''',:, 'oocclc;:',c0WWxxMW0c:'::cllcoo' ,::'''''
..........;;;XkxxXc,;.....oKxoocook,'.:::;'l:,c'..  cccl;:,'loccll;l:;xkKccccccccXXxl,l;llccol'':;lccc
.............lxlc:o:'.....'Xkxooookx:,'...::kXo'..  ;;:,'.;occll;;;kxo:koo......coX:oxk;;;llcco;.',:;;
............',::;Xkol......cXkoocoxkl,''xx:,kX,...  :,'.:kccccllllllXkKl::::;;::::;KkXccllllcccok:.',,
..........,cKl,;,xxl.....,,kkkxooxookXXXkkkk;,::..  ',;kKXxkkkkkXXXolocc;lcccoccllccolcXkXkkkkkxXKX;,.
'........'kXxkk;,;,,..,'l',cXkxxooxxooxkkkkco,:l,x  'o0XkkoxxxkxocXkk;;;llccooccll;;;xkXooxxxxxokkX0o'
,,''''...:xkxkk,;;',':,;c,'ookkkxxxxocooxxxkX:c;::  kkKkxxcooollcxKko;llccoc,'loccll;oxKxcllcxocxxkKkk
xkcll,'..'xXxko;',l;:'.cxl,:okkkkkxoooooooooxkoxcl  xkXkxxccl;;cxkXxollcoo, ,, ,oocllcxXkxc;;lccxxkXkx
oxxl;.'..,cXkkc:'olxc.'l;':ckXkkkkxooooooooxkocccl  xxxoccl::lcooxXxocco;..:l;:..,xccoxXxoool::llcoxxo
':'',,l;clolxllooxxxX:...',0xxxoooxxkkkkkxxol.....  ccoll:,;loccooXxool',;::::;:;,.;ooxXooccol;,:llocc
.','''clcl:',;;ccxokkc....oKxoooooxkkkoc:;,.......  lll:,:lcoxxxkXKXo,.,;o :;;: o;,''cXKXkxxxocl:,:lll
'......',,,:oxxXooo;,'..'lMkokkxxxkx:.,..''llocl:.  ;:::;coxxkkXXK0:'',;lx :,,;.xc;,'':0KXXkkxxocl::,:
:'......';l;o;'';,:''.'ox:,cxkXkkkkoc,......:lxxx;  ',:;lcooxkkkkl',:,;lcx ,l;:.xcl;:::';xkkkxoocl;:,'
```

*Some procedural textures.*

As [neural](neural_net.md) [AI](ai.md) approaches human level of creativity, we may see computers actually replacing many artists in near [future](future.md), however it is debatable whether AI generated content should be called procedural generation as AI models are quite different from the traditional hand-made procedural algorithms -- AI art is still seen as a separate approach than traditional procedural generation. For this we'll only be considering the traditional approach from now on.

[Minecraft](minecraft.md) (or, for the real chads, [Minetest](minetest.md)) is a popular, relatively recent example of a [game](game.md) completely based on procedural generation, in which the world is wholly procedurally generated, which allows it to have near-[infinite](infinity.md) worlds -- size of such a world is in practice limited only by ranges of [data types](data_type.md) rather than available storage memory. [Roguelikes](roguelike.md) 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 (perhaps more so that there was so little storage memory available). 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 potential for saving space procedural generation is popular a lot in [demoscene](demo.md) where programmers try to create as small programs as possible. German programmers made a full fledged 3D shooter called [.kkrieger](kkrieger.md) that fits into just 96 kB! It was thanks to heavy use of procedural generation for the whole game content. [Bytebeat](bytebeat.md) is a simple method of generating procedural "8bit" music, it is used e.g. in [Anarch](anarch.md). 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](compression.md) 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](john_carmack.md) himself called procgen "basically a shitty compression".

Using **[fractals](fractal.md)** (e.g. those in a form of [L-system](l_system.md)) 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](wave_function.md) 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](superposition.md) of all possible maps that satisfy these constraints -- we then set a random tile (chosen from those with lowest [entropy](entropy.md), 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](texture.md) -- similar techniques may also be used to create procedural terrain [heightmaps](heightmap.md) etc. This is generally done by first generating a basis image or multiple images, e.g. with **[noise](noise.md) functions** such as [Perlin noise](perlin_noise.md) (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](modulation.md), blending, adding color using [color ramps](color_ramp.md) etc. The whole texture is therefore described by a [graph](graph.md) in which nodes represent the operations we apply; this can literally be done visually in software like [Blender](blender.md) (see its [shader](shader.md) 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](raytracing.md) -- 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](seed.md) of [pseudorandom](pseudorandom.md) generator we use.

We use procedural generation mainly in two ways:

- **offline/explicit**: We pre-generate the data before we run the program, i.e. we let the algorithm create our art, save it to a file and then use it as we would use traditionally created art.
- **realtime/implicit**: We generate the data on the fly and only parts of it that we currently need (this of course requires an algorithm that is able to generate any part of the data independently of its other parts; for example for a procedural texture each pixel's color should only be determined by its coordinates). For example with a procedural texture mapped onto a 3D model, we would only compute the texture pixels ([texels](texel.md)) that we are actually drawing: this has the advantage of giving an infinite resolution of the texture because no matter how close-up we view the model, we can always compute exactly the pixels we need. This would typically be implemented inside a fragment/pixel [shader](shader.md) program. This is also used in the voxel games that generate the world only in the area the player currently occupies.

Indeed we may also do something "in between", e.g. generate procedural assets into temporary files or RAM [caches](cache.md) at run time and depending on the situation, for example when purely realtime generation of such assets would be too slow.

## Notable Techniques/Concepts

The following are some techniques and concepts often used in procedural generation:

- **[noise](noise.md)**: Noise is often used as a basis for generation or for modulation, it can be seen as kind of "RNG taken to the next level" -- noise is greatly random but also usually has some structure, for example it may resemble smoke or water ripples. There are great many types of noise and algorithms for its generation; the simplest [white noise](white_noise.md) is actually not very useful, more common are various forms of fractal noise, often used noises are [Perlin noise](perlin_noise.md), [simplex noise](simplex_noise.md) etc., other ones are [Voronoi](voronoi.md) diagrams, coin flip noise, midpoint displacement, spot noise, cosine noise, fault formation, Brownian motion etcetc.
- **[random number generators](rng.md)**: To make random decisions we use random number generators -- here we actually don't have to have the best generators, we aren't dealing with "security" or anything critical, however the generator should at least have a great period so that it's not limited to just generating few different results, and its useful to be able to choose [probability distribution](probability_distribution.md).
- **[modulation](modulation.md)**: Using previously generated procedural data, for example noise, to somehow affect another data -- for example imagine we already have some basic procedural texture but want to make it more interesting by randomly displacing its individual pixels to warp it a little bit. If we use a simple random number generator for each pixel, the result will just look too chaotic, so it's better if we e.g. use two additional Perlin noise textures, which together say for each pixel by what distance and angle we'll displace the pixel. As Perlin noise is more continuous, gradual noise, then also the distortion will be kind of continuous and nice. A famous example of this is marble texture that can be generated by horizontally modulating a texture of vertical black and white stripes with Perlin noise.
- **simulations resembling natural/biological phenomena**: E.g. [cellular automata](cellular_automaton.md), [particle systems](particle_system.md), erosion simulation, [agent systems](agent_system.md) (letting virtual "workers" collaborate on creating something) ...
- **[fractals](fractal.md)**: Fractals can resemble nature, they create "content" on all scales and are very simple to define. Popular types of fractals are e.g. [L-systems](l_system.md) that draw fractals with [turtle graphics](turtle_graphics.md).
- **coloring**: To get colors from simple numeric values we may use e.g. color mapping of the values to some [palette](palette.md) or using three different arrays as [RGB](rgb.md) channels. We may also use [flood fill](flood_fill.md) and other things of course.
- **[state search](state_search.md)**: This is an approach similar to e.g. how computers play games such as [chess](chess.md). Imagine we for example want to generate a procedural city: any constructed city represents a state and these states are connected (e.g. one state leads to another by placing a building somewhere), forming a [graph](graph.md) (sometimes even a [tree](tree.md)) of states: the state space. The idea is to create an evaluation function that takes any given state (any specific city) and says how "good" it is (e.g. how realistic it looks, i.e. for example there shouldn't be more hospitals than actual houses of people, buildings should be reachable by roads etc.); then we also implement a search function (e.g. [minimax](minimax.md), [monte carlo](monte_carlo.md), ...) that uses the evaluation function to search for some good enough state we take as the result. [Evolutionary](evolutionary.md) search is often used here.
- **constructive approach**: The "obvious" approach, an algorithm that simply constructs something according to some rules from start to finish, without performing advanced things like evaluating the quality of the generated output, letting different outputs compete, combining several different outputs etc. Example may be for example [recursive](recursion.md) [space partitioning](space_partitioning.md) for the creation of game dungeons.
- **wave function collapse**: Analogy to quantum mechanics, often used for generating tile maps.
- **combining intermediate results**: For example when creating procedural textures we may actually create two separate textures and then somehow [blend](blending.md) them together to get a more interesting result.
- **wrap-around coordinates**: Wrap around (modular) coordinates help us make tiling data.
- **mathematical [functions](function.md)**: Nice structures can be generated just by combining basic mathematical functions such as [sine](sin.md), [cosine](cos.md), [square root](sqrt.md), minimum/maximum, [logarithm](log.md) etc. We take these functions and make an expression that transforms input coordinates (i.e. for example *x*, *y* and *time* for an animated picture) to the final generated value. The functions may be composed (put on input of other functions), added, multiplied etc.
- **higher [dimensionality](dimension.md)**: Equations used for procedural generation are often generalized to higher dimensions so that we can for example create smooth animation by taking the extra dimension as time.
- **[filters](filter.md)**: We may utilize traditional graphic filters such as Gaussian blur, [median](median.md) blur, general [convolution](convolution.md), color adjustments etc.
- **[stochastic](stochastic.md) models**: Stochastic mathematical models describe the generated result in terms of probabilities, which is convenient for us as we can take the model and just use random number generators to make decisions with given probabilities to obtain a specific result. For example [Markov chains](markov_chain.md) can be used to easily generate random procedural text by knowing probabilities with which any word is followed by another word, this may also be used to generate linear game levels etc. Similarly we may utilize various non-[deterministic](determinism.md) finite state automata, [decision trees](decision_tree.md) etc.
- **constraint solving**: Many times the problem of procedural generation can be described as a constraint solving problem, i.e. we have a set of constraints such as "we want 10 to 20 rooms" and "each room must be reachable from other rooms" and then we want to find a solution that just satisfies the constraints (without somehow rating how good the solution is). The advantage of formulating the problem this way is that there exist a number of algorithms for solving such problems, e.g. [ASP](asp.md), some heuristic searches etc.
- ...

## Examples

Here are some cool [ASCII renderings](ascii_art.md) 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](noise.md) -- each picture here has each pixel computed by plugging the *x* and *y* coordinate to a quite simple equation using basic functions like [sine](sin.md), [square root](sqrt.md), absolute value, triangle wave etc. More complex methods will probably iteratively apply various filters, they may employ things like [cellular automata](cellular_automaton.md) and so on, however here you see even a very [simple](kiss.md) approach may often be [good enough](good_enough.md). The [C](c.md) code to generate the pictures above is following (for simplicity using [floats](float.md) 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](random_walk.md)). 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

## See Also

- [algorithmic art](algorithmic_art.md)