The Procedural World, Part 2

By Shamus
on Aug 8, 2006
Filed under:
Programming

In my previous post I mentioned the way .kkrieger uses procedural objects, instead of using pre-fab objects built by an artist.

I guess I should warn you that I have a passion for this subject.

A few years ago I made a program that made procedural trees. I got tired of the fact that all of the trees in our software looked identical. (Because they were all copies of the exact same object.) So I came up with some code that would let you plug in some numbers and it would spit out a tree object. By adjusting the numbers that controlled the distance between the ground and the lowest branch, the length and thickness of the banches, how much they sagged, how crooked they were, how tall the tree was overall, and what textures to use, you could come up with all sorts of different trees. You then just change the random number seed to come up with more trees of the same type. So, you could design an “oak”, and then generate an unlimited number of unique oak trees. On top of this the program could make the trees smoothly grow from sprout to full-size, although I never got around to adding seasonal changes.

It was a cool little project, but in the end I found out other people aren’t nearly as excited about these sorts of ideas as I am. Sadly, it ended up as a novelty that was never put into use. Sigh.


Procedural methods have a lot to offer game developers, not because they save disk space (which is cheap and plentiful) as in the case of kkreiger, but to save on development time. Generating textures, weapons, and monsters is amusing but impractical for a real game, but procedural gamespace is something worth looking into.

Wolfenstein 3D
Wolfenstein 3D, 1992

At the release of Quake ]I[ Arena, I remember an interview with John Carmack where he said that the levels for Wolfenstein 3D (1992) took 6 weeks, the levels for Doom (1993) took nine months and the levels for Quake (1996) took two years. Keep in mind also that while the time required to create these game worlds was going up, the number of people used to accomplish the task was increasing, and the total real estate being produced was decreasing. Old-school shooters could boast about 40 hours of gameplay, but modern games often only last between 10 and 20. Having messed around with level editors for the various generations of games, I can see this inflation of man-hours is still going on, and that ever larger teams are needed to produce that same fifteen or so hours worth of territory.

So we started with one guy working for six weeks to make 40 hours worth of gameworld, and we ended with (say) five people working for two years to make 15 hours of gameworld. This is obviously a bad trend. When people talk about “barriers to entry” and “the increasing cost of game development“, this is a big part of what makes the new games so expensive. Creating gamespace is horrifyingly time consuming, because the job is so much larger and more complex than it was at the dawn of 3d gaming.

Doom
Doom, 1993

In the oldest games the designer could just place simple building blocks together and call it a level. The floors were level and featureless and the world had no real lighting. There was almost nothing you could do wrong. Now level design is part architecture, part construction, part interior decorating, and part scripting. Today the artist must design the building, the floorplan, the doorframes, place furniture, set things so that the wood floor sounds different from the concrete floor when you walk over it, and arrange the lights. They have to set up moving doors and elevators and also the controls the players will use to manipulate them. They must place ambient sounds and write scripts to animate the various NPC’s in the game. They must set path markers or other invisible cues for the enemies in the game to use so they don’t get lost or stuck while chasing the player. They must do all of this with an eye on performance, making sure they pull all of this off without unduly harming framerate.

Quake
Quake, 1996

In Wolfenstein, you could make a playable room in under a minute. In today’s games, you might spend several hours or more on a room. This is going to continue to get worse as graphics engines get more advanced. Every new feature requires some work from the artist to put it to use. This explains why games are getting shorter even as budgets are getting bigger. Even with more people and better tools, it’s still an uphill battle to build game worlds as large as they used to be.

Quake 4
Quake 4, 2006

Part of the problem is that for the most part level editors offer too much freedom. I can sit down with the Doom editor and make a house. Or a space station. Or a nightmarish Tim Burton world of sloped walls and crooked doorways. But for the most part the level designer is only going to be making one of these types of spaces. While you can imagine a game that would require the artist to make all of the above, for the most part a game needs only a few distinct doors, used over and over again. A good level designer can handle this with copy & paste, but that misses the point. If your level designer is making a warehouse, then he’s going to be making lots and lots of plain-jane two-meter doorways. Since this is such a common thing in game worlds, it could be worth the time required to handle it procedurally. So, the artist would have a “door” tool. Click on a wall, and the tool cuts the hole in the wall, adds the doorframe, places a door with a doorknob in it, sets the hinge parameters, adds the sound effects, and places the markers that will tell the NPC’s how to use the door.

Now take that same idea and apply it to the rest of the job. I’m looking forward to the day when level design is just about designing the layout of a place, where the artist can throw down a floorplan of simple lines and let the software worry about setting up the floor, ceiling, carpet edges, archways, pillars, baseboards, doorframes, doors, windows, and all of those other little details that make the world more real but devour so much artist time.

Tamriel
The world of Tamriel.

But procedural development has even more to offer “outdoor” worlds. I’m actually astounded there are still game houses out there which are building their outdoor worlds by hand. Huge worlds like the one in Oblivion are brutally time consuming and expensive to build. An artist must sit down and create the terrain, and then populate it with flowers, trees, mushrooms, rocks, and so on. When you’re dealing with an area of sixteen square miles, manually placing every rock and shrub becomes a daunting task. We’re talking many hundreds of hours of artists’ time.

But the whole thing can be made in about ten minutes if you’re willing to write some code first. If I’d been given the task of realizing the world of Tamriel, I wouldn’t have even looked at the editor. I would have written a program that let me divide the world into regions. Then I’d add some code to control plant placement. Such as: This plant likes to grow in tight bunches, near rocks, and it only grows in the swampy regions. Or: This plant likes to grow sparsely by the water in the coastal region. Similar code can be used for spreading rocks around, placing the wildlife, and so on. Once this code is written, it can crank out a whole new version of the world every couple of minutes if you like. Or – more importantly – it can make a much larger version of the world at no additional cost. Suddenly you can decide how much gamespace you need for the game to be fun (you can have too much of a good thing) instead of how much you can afford.

Once the world was generated, then I’d turn artists loose and let them use it as a canvas on which to build the game. Istead of starting with a blank slate, they would start with a world full of detail where they could just clear stuff out to place cities, castles, wrecked spaceships, or whatever the particular game called for.

I’ve been expecting game tools to move in this direction for some time, but it hasn’t happened yet. It takes some investment up-front, but I’m convinced the time spent will pay for itself by the end of the project. Several months ago I was messing around with the DOOM engine, working on a proof-of-concept of this idea. The levels are stored in a lovely text format which makes it easy to have an external program (like mine) generate a level. Sadly, I got stuck on an implementation detail: The DOOM maps use some bizzare system for defining UV values (the values that tell the game how to put a texture on a wall) and I couldn’t make any sense of it. I may dig that project out of mothballs now that I’m thinking about it again.

Even if I don’t get it working, sooner or later someone will make this idea work, and then everyone will be doing it.

Enjoyed this post? Please share!



20121 comments. Blackjack!

From the Archives:

  1. Cineris says:

    ESPECIALLY with outdoor areas procedural generation isn’t just the most efficient way to go, it’s likely to be the most realistic way to go. I’ve made some small outdoor scenes in Maya using their procedural generation tools (PaintFX). In some ways it seems too easy – But the results looked great, much better than I could possibly model by hand and far less resource intensive (both in creation time and rendering time).

    I think indoor areas are less likely to be easily procedurally generated… But I can see some promise in procedurally generating layouts for competitive (1 on 1) Deathmatch style games. The hardcore contingent already talks about maps in terms of their powerups (Does it have 2 Yellow Armors?, or 1 Red Armor and a Yellow Armor?, or 1 Red Armor and a Megahealth?, etc.). It probably wouldn’t be too difficult to generate a layout from certain set parameters.

    Say that your input parameters are Red Armor 1, Danger Value 3. Megahealth 1, Danger Value 4. Health Pickups 2, Danger value 1… Etc. Using simple cubes it wouldn’t be all that tough to generate “rooms” for these pickups. The danger value would be the number of adjacent “rooms” or “corridors” that opened up onto the pickup (thus you’re more exposed if you want to collect it).

    Later on you’d need someone to go over the cube layout and make it attractive looking, but that’s pretty much exactly how modern mapmaking works (start with simple untextured layout, build up). It’s a lot easier to handle populating the level when the layout is set, though.

  2. I’ve been wracking my brain trying to remember the name of a game I used to play on my Amiga about 20 years ago. It was a space game. You started with a small ship on the planet Earth, and could go out and engage in interstellar trade, fighting off bandits along the way and trying to accumulate money which you could use to upgrade your ship or buy better equipment and weapons for it. The thing that was interesting about it was that most of the star systems, including names, layout of planets, and presence (or absence) of populations and things to trade, was algorithmically generated. (The program placed a few specific star systems from a database included in it.)

    It fit on a single DD floppy IIRC. Included in the box was a big poster you could put up on your wall which showed a map of star systems in a huge area, but it was possible to travel off the edge of the map, and pretty much go forever until you ran out of money or fuel. (Areas off the edge of the map weren’t very rich, but they were there.)

    I later owned a version of it for the PC, in the early 1990’s I think. I can see the box in my mind, but I can’t read the label on it. (Sometimes I envy my brother for his photographic memory.)

  3. Nathan H. says:

    Could that game be Elite, flying your Cobra Mk III?

  4. Actually, it was “Frontier: Elite 2” that I played.

  5. […] When I read this at Slashdot today, I couldn’t help but reminded of this old post by Shamus. […]

  6. gedece says:

    I played Elite on my Commodore 64, I had lots of fun with that program. Part of that feel then went into the Privateer series.

  7. lanael says:

    I’m 8 month late, but about the Doom 3 (Radiant engine ) texture matrix, I got a simple autofit() function to work for my unfinished Citadel project ( http://lanael.free.fr/dotclear ).
    ( In fact, I borrowed parts from the qeradiant sources. )

  8. DanD. says:

    Hi, I enjoy your musings and they hit on a lot of my own interests. This is the first time I’ve posted here, with just a couple thoughts.

    I don’t know if you’re aware of it, but since you didn’t mention it I’ll assume (sorry :) ) you aren’t. The 2nd Elder Scrolls game, Daggerfall (the one before Morrowind) DID have a procedurally-generated world. Unfortunately, it was obviously generated — all the wilderness was a generic slightly hilly plain, and all the towns, although they numbered in the thousands, were clearly variations on a few basic layouts.

    Originally Morrowind was going to be procedurally-generated too, but they ditched that idea in favor of a hand-crafted world. It ended up being a good choice, IMO — Morrowind still has one of the finest, most well-realized gameworlds I’ve experienced in a game.

    Bethesda may also have looked at procedural generation for Oblivion too. I read an article which discussed how they consulted with an environmental scientist / naturalist for the science behind vegetation growth patterns, land erosion, and all that good stuff, possibly for a procedural solution. But clearly they believe a hand-crafted world is still a better fit for the modern Elder Scrolls franchise.

  9. Turgid Bolk says:

    The maps of Dwarf Fortress (bay12games.com/dwarves) are completely procedurally generated as far as I know. It seems the developer is looking to procedurally generate stuff like creatures, religions, civilizations, and magic eventually, too.

    It’s fun to watch the world generator do its thing. Of course, it’s all ASCII, so maybe not as hard to generate as “real” graphics, but the gameplay is great.

  10. Carra says:

    It sure has nice possibilities.

    Age of Kings was using this to create their maps. Never get to play the same map twice! Could get a map with islands, one where you’re surrounded by forest,… Even came with a system to write your own random maps.

  11. TalrogSmash says:

    Gets me thinking about my favorite, Civilization. Wonder if they were procedurally producing the random worlds and if you could search the code for simple things about it.

  12. Kennebel says:

    If any recalls a game in the 1995 to 1997 time frame called, “Rise Of The Triad” (or ROTT as we called it), it had a multiplayer feature where everyone agreed on an integer, put that in to the appropriate box, and the system generated a random level, and then let you join the game. As long as everyone put the same number in, they could all join and play a new, (pseudo)unique map.

  13. Greg says:

    It’s not clear to me from this article whether or not you’re aware that the Oblivion editor DOES use procedural generation for its flowers, trees, mushrooms, and rocks. You can go and manually reposition things later, but the initial process is all automated by region definitions. See http://cs.elderscrolls.com/constwiki/index.php/Regions

  14. illiterate says:

    This article got me thinking about procedurally generated RP..

    As your character walks through the quasi-randomly generated town of Tendaaari, a small family of gnomes brushes past. The youngest looks like the mother, the older two children are a closer match for the variations in the base gnome model that their father was apported.

    The game system decides that they are not going to be a quest-bearing object, and they do not proactively contact the player. If the player were to engage them in conversation, the mother will respond with any of 100 heuristically created conversation items possible, based on recent events within the game world. The father may be interested in selling you some tanned leather he has on his person. If you engage any of the children, they will run behind their parents except the youngest that will follow you until she reaches the comfort radius of her parents and be called back.

    Possibly a bit processor intensive, but it creates an endless supply of fairly believable encounters for our fictitious game world.

  15. Eugene says:

    Shamus – I note that the icon that showed up when I posted this is the same icon that showed up the last time I posted a response…which begs the question: are we being procedurally generated? :D

    Turgid – Dwarf Fortress might not be complex visually, but the level of technical detail involved in its procedural generations goes well beyond what most ‘real’ games do these days. It’s actually quite complex, taking into consideration things such as temperature, regional biology, and even the cultural migration of religions. You could easily take it’s underlying structure (once it’s officially done, that is) and drop it into a 3D worldspace.

    illiterate – I like where you’re going here. It sort of brings up the scary idea of procedurally generating Stories. Considering that Joseph Campbell and Karl Jung seemed to be pretty spot on with their universal story concept, I bet it might even be possible.

  16. Neil says:

    I know noone is likely to read this at this point, but I have to agree with Greg. I don’t know how the dungeons are stored to the disk, but they obviously developed building block style. The Aylied (sp?) ruins, for example, have about a dozen standard parts: straight hall, left turn, staircase, large room, etc. The developer just has to copypaste these to make all the dungeons in that style. Most of the main quest dungeons had one or two unique rooms and features in those rooms, but the side dungeons were all copypaste. It does hurt immersion a little once you catch on, but I think it was justifiable based on the size of the world they wanted and the time budget they were obviously constrained by.

  17. Johan says:

    While reading this I remembered about a game that’s in development at the moment where most of the environment will be procedural.

    http://www.infinity-universe.com/Infinity/index.php?option=com_content&task=view&id=12&Itemid=33

    I hope more tools will be available for game developers to create their content procedurally in the future where you easily can create and populate worlds with content also procedurally created. Taking spore just a bit further and beyond.

    What is even more cool about this game is that it’s a single guy programming it.

  18. Purely says:

    What programmers now spend time on is allowing the user to create new levels with easy to use level editors. The user spends all this time to create and then upload it on Xbox live for all of his buddies (and the world) to see his greatness. He has no idea he is actually working for free for the game company. You think a light would go on inside of these gamers heads and request some form of royalty if their custom level gains a certain level of play. Do you agree?

  19. vm says:

    but one could generate worlds procedurally in a software like maya or houdini, and then export them to the game engine. you use the proceduralism of houdini for example, and then use any game engine to store/use those assets. and you don’t generate the content while loading, which would take way too much in the case of large and complex environments.

  20. Low-Level DM says:

    Eugene brings up an interesting point about Joseph Cambell’s work relating to the “procedurally generated story”. What’s interesting to me is the theoretical potential of a game that did embrace that style of story creation, perhaps in the same method Shamus talks about creating the world for such a game: procedurally “laying the groundwork” and then creating the “main content” of the game by hand on top of it. This would, potentially, create a much more realistic living world, without the time and work requirements of building, say, the conversation for each NPC. It would, at the very least, be a better compromise than Oblivion’s “Rumors” text for every speaking NPC in the game.

  21. WJS says:

    The trend described doesn’t seem to be continuing; I don’t haven’t actually worked with it, but I’ve heard that Unreal Engine 4 is supposed to require noticeably less time to set up a game area than UE3 did. A big part of this is the lighting. Up until recently, computers couldn’t render realistic ambient lighting, requiring time consuming setup of “fake” lights to fake it. Apparently this is changing, and simply sticking lights on things that should logically be producing light is becoming a viable lighting method. (This never looked right in the past).
    Example? Point a spotlight at one wall. In real life, this would light up the rest of the room too; in most games it wouldn’t.

One Trackback

  1. By reality is real-time at Haibane.info on August 29, 2006 at 8:40 am

    […] When I read this at Slashdot today, I couldn’t help but reminded of this old post by Shamus. […]

Leave a Reply

Comments are moderated and may not be posted immediately. Required fields are marked *

*
*

Thanks for joining the discussion. Be nice, don't post angry, and enjoy yourself. This is supposed to be fun.

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>