The Procedural World, Part 1

By Shamus Posted Monday Aug 7, 2006

Filed under: Programming 38 comments

Via Augury I found out about .kkrieger, a first-person shooter game which is only 97k in size. That means the entire game, sound effects, graphics, code, and everything, all within 97k. That is preposterously small, yet the game still looks quite good and at first glance it can pass for a cutting-edge shooter.

.kkrieger Screenshot


Remember these things?

Yeah. That disk holds about 370k, which means this game could fit on this disk three times and still have “plenty” of space left over. Unreal Tournament 2004 comes on 6 CDs. If it came on floppies, you would need a truck loaded with about 10,000 floppy discs. To put it another way, Unreal Tournament is around Forty Thousand times larger than .kkreiger.

.kkrieger Screenshot

So this game is small. Ridiculously small. But what makes games like UT 2004 so big in the first place? Take a look at the gun you see in the screenshot.

I’m going to show how I come up with how big the gun would be. Feel free to skip this bit if you’d rather cut to the chase.

So how big would that gun be if we had to store it on disk?

Let’s assume that it’s not quite as detailed as it looks. (I think bump-mapping is adding a lot of the surface detail.) Let’s say the gun is 100 polygons and 150 verticies. The weapons in today’s games are much more detailed, but let’s assume we’re being frugal:

Each vertex needs at minimum 3 spatial values (x, y, and z), two texture-mapping values, and three normal vector values (for lighting). That’s a total of 8 values per vertex. Normally each of those values is 4 bytes, so we need 4 bytes x 8 values x 150 verticies = 4,800 bytes. Each polygon is a triangle which connects 3 vertices. So assuming each index is 2 bytes we need 2 bytes x 3 indexes x 100 polygons = 600 bytes. The texture is made up of two images: the color map and the bump-map. For a texture on something that close to the camera, you probably can’t get away with anything less than 128 x 128 pixels. Each pixel is three values, red, green, and blue. (for the bump map, these color values are converted into spatial values). Each value is one byte. 1 byte per value x 3 values per pixel x 128 pixels wide x 128 pixels high x 2 images = 98,304 bytes.

So even if we are very conservative, our total size for the gun is 4,800 + 600 + 98,304 = 103,704 bytes, or 101k!

So the gun you see there in the screenshot would be about 101k, which is bigger than the entire kkreiger program! And yet within the 97k of the program it has not just one gun but several, plus enemies to fight, rooms to fight in, and music to listen to while you’re fighting. All of that plus the code that drives the game fits within a space smaller than the size of just one weapon!

.kkrieger Screenshot

As the original article points out, this is done using procedural methods. Instead of storing the 101k gun and its textures, just come up with some code that can generate a gun on the fly. This takes away a great deal of artist freedom, as you can no longer design a gun just the way you want, you can only control the parameters used to generate it. Remember spirograph? It’s a bit like that. You can’t just draw anything you want, but you CAN draw pleasing shapes and patterns with a great deal of precision. In the applet I just linked, you see that I can re-create anything you draw as long as you send me the exact settings you used. If you want to show me an image you made, instead of sending me a screenshot, you could send the 3 numbers you chose and I would be able to re-create what you made by simply plugging in those same values.

So, instead of storing a 101k gun with your program, you can write a gun-generating spirograph, find some numbers that look good, and then plug those numbers in when the program runs. That’s the tradeoff: This game has a long loading time, because it’s sitting there cranking numbers through the various generators, making guns and monsters and rooms.

This is a fun demonstration of what can be done with procedural objects, although it has a lot of implications for the future of game development. I’m not talking about saving hard drive space, though. This sort of thing is far more useful for combating the growing cost of content creation, which I’ll leave for the next post.

 


From The Archives:
 

38 thoughts on “The Procedural World, Part 1

  1. kayle says:

    I don’t think this really has much implications for the future of game development. People used to do more generative graphics because texture mapped triangles were large and slow. In this day, its usually cheaper to pay an artist to draw texture maps and make models than it is to pay a programmer to come up with code to procedurally generate complex shapes and textures… but not always (particularly in resource constrained environments).

    Rescue on Fractalus, 1984, Lucas Arts – one of the first commercial games to use fractal terrain.

  2. kayle says:

    Hmm… one more comment. I wonder if the author of .kkrieger knows its possible to tile a plane with a small set of rectangular tiles aperiodically?

  3. swordfish says:

    Really amazing!
    I think the implications can be really interessting for online and network games.

  4. Styrix says:

    I’ve been working on this kind of idea too. It is the random map-generation of things like Diablo II that I think this has the greatest potential. But I’d also like to see random effects generation, like a random fire-spell effect generator, so using a formula, you could generate your own flame-thrower or fireball spell. Finanly, the grand-poo-bah out there is randomly generated music, using set parameters, so you could randomly generate sorrow, excitement, or what-have you.

  5. Izkata says:

    Since this is on StumbleUpon now, I feel I must mention this for anyone who doesn’t know:

    Spore, one of the biggest game releases ever, is entirely procedurally generated. And Spore would not be possible created the “normal” way.

  6. Kory says:

    I played the entire game thinking the whole time, HOW IS THIS POSSIBLE IN 97K?? I am throughly impressed by this! Great Job to the developers!

  7. Icebreaker says:

    The authors are active sceners … they have quite a few 64k intros, so they know how to fit lots of stuff into a small space … be sure to check out more of their prods at http://www.pouet.net … actually 5 of their prods. are in the “all time top”

  8. passing stumbler says:

    kayle – you heard of Spore? your first line of reply is akin to Bill Gate’s memorable “640kb memory” quote…

  9. jamie says:

    im alwasys so impressed with these sort of things. it amazes me that this can be made using less than 100k but then we have the guys who created the new metal gear game complaining that a blu ray disk doesnt hold enough space.

    whats up with that?

    1. WJS says:

      They’re morons? Seriously, I’m not in the industry but I’m about 90% certain that the bulk of the size of games is texture files… or in other words, the absolute easiest thing to do procedurally. You generate your texture files procedurally, you’ve cut most of the bulk of your game right there. 50+ GB games are ridiculous! Makes me sad that digital distribution has allowed these monstrosities. Modern hard drives aren’t that big, you idiots! Imagine if every developer made games that big? You could only have a dozen or so installed at once!

  10. pzero says:

    Very interesting. I hadn’t ever heard of this game before, but it’s very impressive.

    I don’t think this sort of technique has much potential for direct application, any more than all the “do X in one line of pearl” scripts out there do, but it certainly is interesting and sheds a lot of light on the power of runtime generation of content.

  11. Aaron says:

    It would have been nice if their website had said what OS it runs on. Windows only, but it seems to almost run under Wine.

  12. Steffen says:

    Well ya.. ive tried this game and its ok for 97k game… but but but.. when its generating in the long load time it also creates temp files… soo it takes the place on ur harddrive that it should.. only when ur playing though

    1. WJS says:

      Computers have this thing called “RAM” these days. You don’t have to actually write things to disk if you’re using them right now…

  13. roxysteve says:

    That last post is a brilliant illustration of the point of the article delivered as a text metaphor.

    Look at the beauty of it. The compression of “ya”, “ur” and “ive” is destructively outweighed by 300% overuse of “but”, the extra “o” in “soo” and the use of double and triple periods in place of conventional punctuation.

    Clearly the txtspk represents the 97k “.kkreiger”, which is contrasted with the bloaty “Hellsgate:London” as represented by the rest of the post.

    Magnificent use of irony by Steffen.

    Hat off. Kudos granted. Accolades strewn.

    Steve.

  14. Eugene says:

    Wow, three responses claiming that procedural generation has no solid application in game creation? In this day and age? MGS4 nearly maxed out the bluray it comes on. That’s 25 gigs of space!! And Rockstar was saying how future sequels of Grand Theft Auto might not even fit on a single disk.

    Imagine what procedural generation would do to help these developers. Or, more importantly, the developers who don’t have the luxury of tons of cash at their disposal to throw at modelers and texture painters and mo-cap specialists, and the animators who inevitably have to fix the mo-cap because it doesn’t look right, and the general character animators, and the level designers who spend the entire life of the project tweaking, and the programmers who spend the entire life of the project fixing what the designers are screwing up, and on and on. And with every increase in system power, the costs and labor required to develop a single game will go up exponentially.

    Consider the war scenes in Lord of the Rings. You don’t honestly believe each goblin dude was crafted and made to move by hand do you? Hell no! They made a program that could vary the size shape and look of those guys and give them a simple AI, and then they created a program that figured out their interactions. In fact, NONE of the war scenes were so much as touched by an animator! If they hadn’t done that, all of those films might have potentially taken YEARS longer.

    Procedural generation is the future. Or rather, it’s the only future that won’t cause the game industry to collapse in on itself.

    Oh yeah, steve, I like your comment. It was amusing.
    So, if he’s the .kkrieger metaphor, would I be the GTA metaphor then? :p

  15. izzy says:

    So I thought about this a bit, and I have only a couple points to make. 1: It is quite stupid that the code for an entire game takes up less space than that for a gun. 2: Sure you can make games that take up such little space, but there are very complex codes necessary for adequate gaming experience. I think that music plays an essential role for maximum gaming experience. Steady transitions between moods add just that much more excitement to the game. Also, it is better to have opponents that actually THINK instead of just respond. It is fun to just run around killing, but proper battle tactics can be much more rewarding. Graphics can be beautiful, but good AI and proper transitions are what drives this artwork to its full potential.

    1. WJS says:

      My copy of XCOM takes up 18 GB. XComGame.exe is 27 Megabytes. The “codes” are a tiny, tiny part of the game by space.

  16. crowtower says:

    Absolutely amazing! I grew up using a cassette drive for storage where you had to wait 20 minutes just to load a text-based adventure game. So 96k to fit such a beautiful and interesting looking game is a rare feat. Well done!!

  17. Ezio says:

    Hi young peoples,
    did you ever see an old Sinclair Spectrum?
    On our 48K Spectrum my soon (when he was a kid) used to play Hobbit.
    It was a full adventure game with lot of characters responding to your words and action and had perhaps 20 graphic screens, it took months to play it all. It ran in 42K RAM (the “48K” was comprised of 6K video memory). No expanded files, Spectrum only had a cassette tape memory, no HD, no floppy.
    The Hobbit was (obviously) procedural.
    Time passed… My soon is father now, and the Spectrum lies in the cellar.
    The “operating system” of the Spectrum was a 16K ROM (like having OS and BIOS all together). It included a nice BASIC interpreter, with floating point and graphics.
    Maybe Bill minded such “comuters” when said 640K would be enough.
    But then everything was written in Assembly. Not Visual languages. The Spectrum OS had almost no bug; it had to, as once the computer was built, nothing could be changed (the FLASH memory still was not invented).

  18. fuchsto says:

    Old farbrausch production is old :)

    It has been stated perfectly correct before: I prefer a 4-Gig game over a 100k one that has 2 types of enemies, 3 weapons, one random map and no proper collision detection and takes an eternity to produce.
    Apart from that: Yes, the BINARY has just some Kb, but the codes “explodes” into RAM. There are models and textures just like in any other 3D game, but they are build at runtime using lots ofa smart algorithms. That’s the single difference.
    It’s not really a game, it’s a demo, a piece of digital art, so don’t compare it to shooters. Compare it to artworks.

  19. Vladius says:

    .kkrieger isn’t that impressive when it comes to first person shooters. 97k isn’t bad, but there is no animation, no corpses, the powerups float unconvincingly over the ground, and the monsters just stand still. There is also only one kind of effect for any kind of shooting. It’s not fun in the strictest sense, and there are plenty of bugs where I get stuck and can’t move. It’s still an achievement, just less than you let on to.

  20. Bill2k says:

    Simply amazing! I’d like to see what can be accomplished with a full dvd of this type of programming.

    I can not believe people are actually comparing this to a commercial game. That’s like comparing a radio controlled model plane to a commercial airliner.

  21. some random gamer says:

    i played it all the way through and i thought it was a great game! i would like to see this type of thing in future games. great game lots of fun!!

  22. Haha says:

    Isnà„t this game made by these germans “Farbrausch”?

  23. mike says:

    has anybody played spore? all the music and graphics in that are procedurally generated except the buildings and ships which are composites of many smaller objects.

  24. Jon says:

    Some folks are missing the point – if you could carry around a thimble that could magically expand to become an automobile, drive 200MPH @ 80MPG would you complain about the stitching on the leather upholstery or find fault that the stereo system only has 12 speakers? That’s what you’re seeing here.

    It is not a product designed to compete with Quake III. It is a demo of incredibly powerful technology that could (and should, IMO) revolutionize the way software is built. It is not unreasonable to think that this approach could result in the software creating a game world that the programmers/designers could never have imagined.

    One comment here discussed AI code. If you think for a moment about AI code, that is the essence of procedural programming. A small bit of code which can produce very complex behaviour, instead of recording every possible movement a “monster” may ever make. A few thousand bytes (2k) versus hundreds of gigs of pre-recorded playback. Basically, Quake vs. “Space Ace”. Wide-open world vs. limited.

    Put another way, it’s an instruction manual vs. an implementation. DNA is the ultimate procedural code. In every living cell of our body is the complete instructions for building the organism. Certainly takes up less space than the whole creature, and is obviously powerful enough to express a complex idea.

    (Ezio — thanks for the reminder of the Sinclair ZX! What a great little machine. I spent many hours writing games in BASIC on that membrane “chicklet” keyboard. The Apple ][ we bought afterward was pure luxury!)

  25. Salgod says:

    As a new comer to your blog I have been reading over a lot of your psot in no particular order I came across this and your post on fate a game which I havent played in years but throughly enjoyed when I fplayed it.. since then I have dug through my emails and foudn the unlock code and resumed playing it… but the thing that struck me is how useful a procedurally generated world could be in a game along fates lines I think it would not only mke the game easier to produce but give it alot of extra replayability and make it generally more fun

  26. Arthur Goldsmith says:

    I love the first comment:

    “I don't think this really has much implications for the future of game development.”

    The Infinity Game Engine has been in development for years, and creates and ENTIRE GALAXY for users to play in procedurally. From Surface to Space, the game is created on the fly as an MMORPG:

    Here’s the FAQ:
    http://www.infinity-universe.com/Infinity/index.php?option=com_easyfaq&task=cat&catid=14&Itemid=28#faq14

  27. Eric says:

    It’s nice to sit back and peruse the archives, even posts you’ve already read. However, I was reading this, thinking how long ago 2006 seems, with Spore and procedural content, when it hit me:

    Minecraft!

    That “no implications” technology turned out the biggest hit of 2010. Given that it has not yet been fully released, Minecraft will likely take its place as one of the biggest game of all time. Unlike a 97k FPS (can you even measure less than 100k anymore?), Minecraft is a game which is able to generate terrain 8 times larger than the surface of the Earth. Graphics, you ask? Well, fragment-user, Minecraft has some of the worst graphics of anything since maybe 1993, the advent of 3D graphics. Go stick that in your bling-map-shading.

  28. thomas0comer says:

    Now Minecraft is some estimated three times the size of earth before it crashes, but still: Terrain codes dictate patterns that form. Biome codes dictate the types of patterns and where they are. With some 200+ blocks/items in the game, it is not that advanced, but it has a wide range. And it is just a base, a simple platform for mods to build on and exploit, and adventure maps to play through for maximum enjoyment. SDK Gun Mod + Four Towers map + LB Photo Realism texture pack + two-three people on SMP = one of the best FPS’s I’ve ever played.

  29. thomas0comer says:

    Sorry, I meant FPS-Adventure. It’s really both, which fits the diversity of minecraft.

  30. Graagh says:

    Sorry to post on this so late in the game – I just ran across Shamus’ series and am really enjoying exploring all the posts. The problem evidenced by most of the posters here is that you are looking at .kkrieger and assuming that it is all that procedural generation will ever be. It will never be a Quake or a Gears or a Battlefield and so procedural generation is invalid. You are missing the point entirely. the point is not that a 97k game is as good as a 4gb game with all the fancy bells and whistles. The point is that the AAA studios would still churn out 4gb games for your enjoyment, but those games could now have 128gb of content at the same quality level using procedural techniques properly. You guys are being ripped off because your favorite franchises don’t take advantage of this. :-)

  31. Computer Darryl says:

    Awesome post. I just discovered your blog and you sir are doing the Lord’s work :)

    A few tidbits:

    Rescue on Fractalus, Ediolon and Ball Blazer were all high tech games that blew minds back in the day. They were small and used procedural techniques not only for gfx but for gameplay as well. They couldn’t have been done w/o procedural techniques. The programmer who made those went on to help found Pixar and was their main technological innovator. He made Renderman! Designed 25 years ago & still today it is considered the gold standard for rendering still for Film & VFX studios.

    It isn’t that unimaginable to make a game in 97k given that c64 & amiga games were as small as 16k or smaller. Then the gameboy color had it smaller still. There were a few fps on the amiga & sega megadrive.

    farbrausch the german demo group made a lot of these procedural texture demos & I think some of them went to game or VFX industry… I’m not sure, could’ve been another group. RGBA works for pixar & he made worlds in 4k.

    I remember picking up Perlin’s magic book way back when and reading the future. Its all here and its changing everything dramatically!

  32. WJS says:

    A bit of perspective that I’m surprised you didn’t include: This article is more than 97k.
    Also, your “size of the gun” calculations are a bit naà¯ve. That’s assuming zero compression; your image of a floppy is about 128×128, and it takes up less than 4k (not actually possible on most computers these days), not 98.

  33. SG says:

    Interesting that UE4 have substance plugin, that have option to generate textures on first game launch. They will be stored in game cache. In game installer you only have substance file which is much smaller than bitmaps. The downside may be all files are stored on disk c documents folder, instead of game folder. I wouldn’t want 60Gb cache on my disk c.

    That means first game launch may be very slow to generate all textures.

    I noticed similar thing in Natural Selection 2, i dont know what they do. Generating ligthmaps? I rememeber it was super long first launch of my old pc, and slow-ish on new pc. No idea why they did that though.

Thanks for joining the discussion. Be nice, don't post angry, and enjoy yourself. This is supposed to be fun. Your email address will not be published. Required fields are marked*

You can enclose spoilers in <strike> tags like so:
<strike>Darth Vader is Luke's father!</strike>

You can make things italics like this:
Can you imagine having Darth Vader as your <i>father</i>?

You can make things bold like this:
I'm <b>very</b> glad Darth Vader isn't my father.

You can make links like this:
I'm reading about <a href="http://en.wikipedia.org/wiki/Darth_Vader">Darth Vader</a> on Wikipedia!

You can quote someone like this:
Darth Vader said <blockquote>Luke, I am your father.</blockquote>

Leave a Reply to izzy Cancel reply

Your email address will not be published.