Kkreiger! I remember being amazed by that at the time, it's a triumph of procedural generation, fitting a FPS into 96kb.

It's interesting to think of this from an information theoretic perspective as a form of compression. Firstly "compressing" textures into the algorithm that generates them, then cutting away all the parts of the algorithm that don't make any difference to the output.

Kolmogorov complexity?

Something like Turing's busy beaver problem. You can get huge amounts of complexity from very little initial "state" information. https://en.wikipedia.org/wiki/Busy_Beaver_game The pigeonhole principle means there are only a limited number of patterns that you can generate from a few bits. http://atlas.wolfram.com/01/01/ But the complexity of the output means you can often find something useful if you can pick a subset of the output. E.g. http://www.dr-mikes-math-games-for-kids.com/your-name-in-pi....

Of course, describing that subset is itself using bits

https://github.com/philipl/pifs

This feels a lot like profile-guided optimization - it can't be much of a step from PGO observing that a branch is never taken during profiling and so marking the not-taken path cold, to eliminating the not-taken path (and the branch test) entirely. I wonder whether PGO was available in open-source compilers back in 2004?

GCC supports PGO since 3.1.1, released July 25, 2002.