Thursday, August 18, 2011

The case for procedural generation

John Carmack recently said procedural techniques are nothing more than a crappy form of compression. This is while he was asked about the Unlimited Detail tech. To be fair, this should be taken only in the context of that question and runtime-engines, which is anyway a bit strange since Unlimited Detail is not really using anything procedural, it is mostly tiling instances of unique detail. Still, is he right about that? Is procedural generation just crappy compression?

Others have said that procedural generation in games inevitably leads to large, bland scenarios. Or maddening repetitive dungeons and corridors. As they put it, humans can only be engaged by content that was created by other humans.

I actually agree with them. And yes, you are still reading Procedural World.

Despite of what we naysayers may believe, procedural techniques have seen a lot of success already. It is not really in your face, not a household name, but it has been instrumental producing content that otherwise would simply not exist.

Take a look at this image:


Well thanks, it does looks like the shinny things I'm trying to do, but this is Pandora from the Avatar movie. Now, do you think this was entirely handcrafted?

Pandora is mostly procedural. They have synthetic noises everywhere, L-systems for plants and ground cover, it is actually a textbook example for procedural techniques. A lot of people went to visit it, and it made heaps of money. If you define success on those terms, this baby takes the cake. And it is thanks to procedural generation. Without it Pandora would have looked like this:


So clearly proceduralism can help creating appealing content. As Carmack says, it is some form of compression. What got compressed in this case was not information over the wire, or over the bus to the graphics card, it is the amount of work artists needed to do. Instead of worrying about every little fern, they could spend their effort somewhere else.

What is wrong with this? Now imagine it was a game and you were marooned in this huge Pandora place. You would probably get bored after a while, besides staying alive there is not much to do. If there is a thing we humans can do is we can get bored anywhere, all the time.

We need this sort of battle-is-brewing, storm-is-coming thing lurking in the horizon. We need a sense of purpose and destiny, or a mystery for the lack of it. Is this something that only other humans can create for us?

At this point it becomes about Artificial Intelligence. Think of a variation of the Turing Test, where a human player would not be able to tell whether a game was designed by another human or by a computer. This is the real frontier for pure Procedural Content generation.

In the field of physics there are two theories that are very successful in explaining the two halves of the real world: Quantum Physics and General Relativity. They don't get along at all. There is a discontinuity where one theory ends and the other starts.

A similar scenario can be found in Procedural generation. On one side you have the Roguelike-Dwarf Fortress type of games which can generate compelling experiences, but lack any visual appeal. These games use text or ASCII screens. It is like never jacking into the Matrix and keep staring at the floating text. Can you see the woman in the red dress?


Then any attempt to visualize the worlds they describe, the magic dies. You realize it was better when it was all ASCII, which is sad cause only weirdos play ASCII games.

The other side is rich visual worlds like Pandora. With the advent of computing as a commodity -the cloud- bigger and richer worlds will become available, even for devices with limited power like mobiles and tablets. But they lack the drama. Even a Pocahontas remix is beyond what they can do.

Triple A studios have realized this. It is better to use procedural techniques at what they do best: terrain filler, trees, texturing, and leave the creative work for the humans. They do not have a reason to invest in this type of AI, they won't push this front if it was up to them.

I do believe it is possible to marry these two opposed ends. Someone with an unique vision into both fields will be able to come up with a unified theory of procedural generation. And I think it will be the Unlimited Detail guys.



(EDIT: OK, OK. I'm kidding about Unlimited Detail. Their next bogus claim could be they made procedural content generation 100,000 times better. It is surprising to me they still can be taken seriously.)

61 comments:

  1. Unlimited detail uses a form of metaballs and primitives + procedural generation and variation to store and show theire "point cloud data".

    A procedurally generated game that would be the same as made by a company would need to simulate the whole universe, and the human being. We're not far away from this, but it will take a while.

    Now what I wanted to say. If a game, no if the whole universe was a mathematical equation, where the K where as the sum of K was the universe. There is no universe where you could calculate K in one shot. You can do it like polygons, in iterations. One more iteration, it's more like the thing. Or like voxels, which is a bit like the ants algorithm. Well not really, maybe much more like K defined in n where this K could be calculated actually, but only in n.

    You will never come close like that. You need to do it different. You need to start with K. An assumption that you want to design K, you know K in the first iteration, but to work with it you'd need to make more and more iterations.

    See where I am going?... Blah I need sleep. ;)

    ReplyDelete
  2. @Dany: From what Unlimited Detail have said and shown, they scan real objects and keep the information as point clouds or voxels. They do not use procedural methods to generate content.

    Also, K = 42

    ReplyDelete
  3. I thought you weren't a major fan of the Unlimited Detail guys and videos?

    ReplyDelete
  4. btw Unlimited Detail they show new video:
    http://www.youtube.com/watch?v=JVB1ayT6Fdc
    now we can see they engine running in RL

    ReplyDelete
  5. It should be trivial to dismantle any claim that humans only find hand-made stuff interesting: Any pretty landscape that was not sculpted by human hands fits the bill. Yet millions of people visit the Grand Canyon or the Niagara Falls.

    As for UD: They are just a scam, nothing more.

    ReplyDelete
  6. @Anonymous: I'm kidding about Unlimited Detail. Their next bogus claim could be they made procedural content generation 100,000 times better.

    ReplyDelete
  7. I've got some thoughts in development here: http://roguelikedeveloper.blogspot.com/2011/08/proceduralism-part-six-architecture.html

    ReplyDelete
  8. @Andrew: Your article is what finally motivated me to write this post. Your conclusion that any game that may arise from Shamus Young project or mine will be doomed from the cradle is not a nice thing to say.

    This is a quote from your post:

    "And all these amazing worlds? Almost everyone is focused on building these curate's eggs - which, if they eventually end up being released as a game, become a disappointing, empty and lifeless one."

    A Curate's Egg? Ouch!

    The challenges are high and the odds are against us, but seriously, how can you have an opinion on something that does not exist yet?

    Anyway your blog is an interesting read. I recommend everyone to check it out.

    ReplyDelete
  9. MCeperoG: I think you should take up Andrew's comment as a challenge, more so than criticism.

    ReplyDelete
  10. "Your conclusion that any game that may arise from Shamus Young project or mine will be doomed from the cradle is not a nice thing to say."

    I'm sorry, I didn't mean for you personally to take it badly. It's something you always forget when writing this sort of opinion piece. I especially shouldn't have generalised from 7 projects to that conclusion: only Spore ended up that way. LoVE just failed to set the world on fire and from what I've seen in the forums has players on most servers in the single digit figures. The Polygon Map Generation project ended up being the generation code for Realm of the Mad God, which is a different story.

    I've been following the procedural generation field for a while and as you're probably aware have been one of its biggest cheerleaders. However, its very easy for people to get excited by the vast progress that PCG can make in the first 20% of the project and forget that going from a beautiful procedural world to a great game has only been done a few times and in very limited ways.

    I hope you do take this up as a challenge and look forward to more of your insights.

    ReplyDelete
  11. Carmack today is not the only big name in the industry. Some folks, like Epic Games, understand the importance of procedural techniques. So they've added a procedural city generation module to UDK. This project (http://www.hawkengame.com/blog/media#) uses it and looks great, IMHO.

    ReplyDelete
  12. @Andrew: It's all good. For the most part I agree with you. It is very easy to stop when you see something pretty coming out of the generation pipe and call it a game. Visuals are just the beginning.

    Now other things like level design, storyline, characters, they don't have to be necessarily procedural.

    Like any tool, it should be used sensibly. If you look at the success stories, what they do best is helping artists improve their work, or minimize the input from an artist. This will continue to improve a lot, while the hairy problem of how to replace a level designer by a robot will remain a topic for little enthusiasts like yourself.

    ReplyDelete
  13. @Cadabra: Those screenshots look great.

    I'm sure Carmack's own id uses procedural techniques. Rage's unique texture is handpainted, but odds are some of the pixels you see in the final megatexture where chosen by an algorithm and not directly by a human. I also bet $5 there is a perlin noise function or similar somewhere in any of the tools they have used.

    Anyway Carmack's statement should not be taken out of context. Many rendering engines use proceduralism as a form of compression. It is faster to send a few seeds and primitive classes to the GPU and generate the content there than to send unique content. As he says it is crappy, cause your art becomes limited by what your algorithms can produce.

    It is interesting is that in other places Carmack claims he is worried about the time and effort that takes to build these huge worlds. As he put it, every game they do is taking twice the amount of time and money than the game before, and this is a trend that has to stop. Then he scratches his head and wonders if there is some kind of technology that could help.

    ReplyDelete
  14. i think main strength of procedural techniques is that when you play again world is changed.
    good example of this is Diablo series, every time you start game you need find places, not like Fallout 1-2 when you can end game in 30min by simply move to last localization that you remember form previous game.

    ReplyDelete
  15. @-=Y=-: Yes, Diablo does it very well.

    ReplyDelete
  16. Procedural generation is wonderful for games. However human designers definitely still need to step in at some point to tweak and modify things; or to setup systems to interpret, modify or sculpt the results in various ways. Procedural generation is like a tool, it is all about how you choose to use it.

    ReplyDelete
  17. This comment has been removed by the author.

    ReplyDelete
  18. I think the perception that procedural processes will always fall short, is just a result of past implementations that utilized shallow or ill-constructed procedures to accomplish their goals, or the computational limitations inherent in complex (read, more realistic) algorithms.

    As you said, and Avatar proves, procedural techniques are VERY good at producing very good simulations of real-world, or fantasy, results.

    Their success, or failure, is more dictated by the time and effort taken to craft the algorithms and techniques used, that will produce the good results, rather than of them being procedural vs. hand crafted.

    [SOAPBOX]
    It is patently stupid of people to ignore the fact that “humans” create the procedures in the first place. Those human’s commitment to the “beauty” or realism of their results is directly proportional to the quality of the experience… just as much as it was with Rembrandt or with CG artists or animators. The ability to “think” procedurally and still obtain those beautiful results (as we have seen Miguel do) is just more rare, and is clearly an emerging field.
    [/SOAPBOX]

    It’s obvious that, as the layers of procedural complexity and “realism of results” increase, further rules and algorithms will be improved or layered to create ever increasingly believable/beautiful results, in all areas of game design.

    This has been impacting non-visual “game” mechanics for years. Games began randomizing loot (procedural), randomizing quests to get the loot (procedural). Then they started applying noise to attributes of characters to ‘simulate’ a varied population (procedural). Then producing populations on the fly, Hello, GTA… It continues today, with relatively advanced procedural constructs to craft a variety of ever increasingly believable interactions in the game, without every facet being hand crafted by a game designer.

    In games, symbolic and logic/rule based Artificial Intelligence systems are very similar to procedural content creation -- or actually, I would say it the other way around, procedural techniques are an effective means of implementing pretty believable AI behavior. Both fields have a lot to give one another!

    In fine art, a blank canvas is looking for a scene to be painted on it, in procedural worlds the scenes there waiting for the algorithms that will create them… Procedural Artists are continually honing their constructs so that the answer looks like a more believable 42 :)

    ReplyDelete
  19. @Jonathan: Thanks for your post. You speak with wisdom and it makes us better.

    You could even argue that NPC AI is some form of proceduralism, only that manifests in time-behavior rather than in space-content.

    Still there are areas of procedural generation that remain largely unexplored, where we have had very little success. For instance, it is not so difficult to generate history for a world. But a technique that creates drama, humor or horror in this world, I don't think anyone has done it.

    ReplyDelete
  20. "But a technique that creates drama, humor or horror in this world"
    its easy :>
    a) crate big kingdom
    b) create small aggressive tribe
    c) give advantage of power to that tribe (e.g. people/monster in that tribe are 10x more powerful than normal people)
    d) let them conquer most of the kingdom
    c) start game when in that kingdom only one city left.
    isnt that dire situation? to made more drama you can track history of couple "sims" that live in this world, and when game starts you can build something around this:
    a) find someone from theirs family (or yours)
    b) vengeance :> if you kill someone theirs relative wont forgive you.
    c) listen to theirs history ("i lost my family in that siege", "i fought in that battle")
    d) weapon can have previous owners, if you are lucky you can find descendant of that person.

    if you look on history from perspective of person you can find many interesting things.
    if you look on group, you will only find statistic.

    ReplyDelete
  21. "Now other things like level design, storyline, characters, they don't have to be necessarily procedural."

    But they can be, and that's where the field of procedural generation is heading and where all the interesting research is occurring... and that's where we'll see the big wins and avoid criticism from the John Carmacks of this world.

    You can also add game design to that list (Yes, people are making games where the entire rule set is procedurally generated).

    ReplyDelete
  22. Jonathan: You're outlining one approach to procedural generation of interesting worlds. There are a number of problems with that approach, three that stand out for me, that are exemplified by Dwarf Fortress:

    1. The amount of time to develop these systems is huge, bigger than any game.
    2. The systems themselves may interact in entirely unexpected ways.
    3. Even if the sytems work perfectly, conveying cause and effect to the person playing the game is an incredible UI challenge.

    I'm not saying that I disagree, but merely pointing out the holes in your soapbox.

    ReplyDelete
  23. Oops. That should read under point 1: 'bigger than any commercial game to date'.

    ReplyDelete
  24. @Andrew I think the fact that Dwarf Fortress is written by one guy is part why its taken so many years, though in fairness its been playable and awesome for a long time.

    When more of the games industry starts to come to grips with the content generation trap they've made for themselves I think even Carmack will come around to procedural content.

    Ironically, in his keynote from the same Quakecon he talked about Rage taking 6 years and that the industry couldn't keep doing things the same way.

    An industry that finds some procedural focus will build libraries of procedural techniques. Hopefully that building process will be accelerated by some appropriate opensourcing.

    ReplyDelete
  25. I think what draws me to procedural content and makes me think it really is the future of compelling gaming is a simple observation.

    Life is awesome, interesting and constantly capable of surprising, horrifying and delighting you.

    Life is procedural. It's the emergent complexity of billions of rules applied an uncountable number of times.

    Even the art and aesthetics that create plot and narrative are bound and driven by rules. Those rules in turn are derived from rules of the mind and the culture its wrapped in. Ad infinitum.

    Now life can have its dull points but tuning your set of procedural libraries to not generate as many of those dull points is the trick, in life as in gaming.

    ReplyDelete
  26. > 2. The systems themselves may interact in entirely unexpected ways.

    This is an absolutely crucial point to the future of procedurally generated game content.

    Much of the emphasis in major game design studios these days concerns the utter and absolute elimination of all surprise. On the one hand, developers are terrified that if a single player is left wondering for a microsecond what he is supposed to do next, he'll decide "this is boring!" quit playing, and tell all his friends that the game is broken. So these devs are now doing everything they can to make sure that every possible system interaction is 100 percent controlled, that there is no moment in which the developer's intentions are not being communicated with perfect fidelity to the player... even if that means limiting the number and span of systems to the point that games become nothing more than "walk" and "shoot enemy" with different textures.

    But many players don't like surprises, either, and developers are giving them what they want. They're designing and playtesting and focus grouping scenarios so that as long as players do the "right" steps in the "right" order (often substituting player skill for in-game character abilities, even in RPGs), they win. After all, you don't want players to quit because they can't win right away, do you?

    What bothers me is that not all gamers appreciate these modern design tropes. Some of us enjoy being surprised! Of course it's not much fun to lose because of randomness, but that is a design issue -- there can be surprises due to untestable interactions between many complex systems that do not result in a broken game, but instead contribute toward the presentation of a gameworld that feels *alive*.

    The quest to eliminate surprise from games needs to be countered in order to prevent games from becoming utterly banal snoozefests. And procedural content generation -- particularly in the area of object behavior -- is one possible path toward achieving the goal of that quest.

    I strongly endorse what Miguel is doing here, and I hope it will inspire other developers to embrace the idea that a little more surprise in their games can actually be a good thing.

    ReplyDelete
  27. @Andrew:

    "that's where the field of procedural generation is heading and where all the interesting research is occurring"

    There is interesting research everywhere regarding procedural generation. Even the posterchild of procedural graphics, terrains, has a long way to go. Realistic terrain goes well beyond a ridged multifractal noise. Those things don't work anymore. If you look at the commercial packages out there, they are all heightmap based. And terrain generation is supposed to be the easy part.

    Take architecture, there are many successful attempts to create city layouts and building volumes and facades, but coming out with buildings that you can inhabit, functional and believable buildings, this is virgin territory. A building that makes sense is as difficult as a story that makes sense.

    In general I get a feeling that you may be too quick to dismiss work in the visuals, and point to the synthetic game design done by roguelikes as where the real challenge is.

    Roguelikes, dwarf fortress and their cousins are highly symbolic. A symbol is something you use to replace a real thing, but still denotes that thing. Your brain decodes the symbol into something that feels tangible, and this is a very powerful thing. If you want to keep imagining things.

    If you want to eventually try to produce a sensory experience: visuals, music, sound, you need to design for it organically, pretty much like a movie director envisions a piece of work. A compelling arrangement of symbols may not even be a part of this process.

    ReplyDelete
  28. "There is interesting research everywhere regarding procedural generation. Even the posterchild of procedural graphics, terrains, has a long way to go. Realistic terrain goes well beyond a ridged multifractal noise. Those things don't work anymore. If you look at the commercial packages out there, they are all heightmap based. And terrain generation is supposed to be the easy part."

    I agree that there is a huge amount left to be done with regards to terrain generation, but I believe there is plenty of low hanging fruit that exists which is not being looked at at all.

    As far as I can see, you're doing a sophisticated blend of a number of well known algorithms which have been used for offline procedural generation for decades, and which have been possible using online generation for at least 5 years, but not with the level of visual fidelity you're using. That's not to sell what you're doing short, by any means. I couldn't do what you're doing, for instance.

    But compare that to the amount of work done spent developing procedural dialog systems, or procedural quests, or procedural enemy types, or procedural particle systems, which people are not writing about at all.

    If you want a specific example, I've spent a lot of time developing dungeon generation in Unangband to fix one specific problem:

    You want to 'theme' areas (rooms in Unangband) so that there is an indication what monster type is in an area. But monster AI requires that they are able to move whereas the rooms are fixed. It is entirely likely that you encounter the monster before you find the room that contains the theme describing the monster. So how do you create interesting levels with the constraints that you should usually encounter themed rooms before monsters?

    ReplyDelete
  29. BTW: I'm not suggesting or implying that you should be the person to solve these problems. But someone should...

    ReplyDelete
  30. @Andrew: Right, I'm the first one to claim I'm not doing anything new here. But this is not about me, I'm the little guy trying to climb on the shoulders of giants.

    To me all sub-systems in procedural generation are created equal. It does not matter if some techniques have been widely used before, or if they got more coverage from the media. I see no bastards here. I celebrate any advance anywhere. And there is low hanging fruit everywhere, even in dialog and quest generation.

    Anyway the particular problem you describe does not seem so hard. I'm sure it can be solved with existing research, or just some old-school ingenuity. Your monsters could incorporate theme and decoration in their pathfinding. It works for me, I for one never set foot in a casino, the carpets there make my eyes twirl.

    ReplyDelete
  31. What I find amusing about Unlimited Detail is that even assuming their claims aren't hokum, their engine lacks basic features and systemically looks like it will make them much harder to implement.

    He says that they're just doing a quick look-up and not running a raytracer, but the only look-up that comes to mind is some kind of oct-tree of voxels, which when combined with the trig to sort out which pixel you're looking up is a kludge-y shortcut raytrace. If that's what they're doing, it sounds like a massive pain to try to get dynamic lighting in there. Also, if they're tracking "atoms" in a model doing skeletal animation doesn't that exponentially increase the number of iterations when doing the transforms for animation?

    Whatever they have now running on a quad-core i7 with hyperthreading in software (4 actual, 4 virtual cores at 2.8+ Ghz) gives them 15-25 fps which isn't an acceptable frame rate for anything barring strategy and that doesn't even have animation, AI, sound, dynamic lights or physics yet. He also seems to think porting that system to the GPU is a trivial process -- which you've told us is anything but and making a GPGPU algorithm work beautifully on one card is no guarantee of similar performance on others.

    Disclaimer: I don't actually know what I'm talking about. Reading Shamus' and Michael Goodfellow's blogs in addition to this one has given me airs of competence which I do not possess. If what I've said here is ridiculous, please enlighten me.

    ReplyDelete
  32. @chirality: I think you are pretty much on the money.

    They describe their approach as a search limited only to the pixels seen on screen, which is what raytracing and its cousins do. But then they say their stuff is not raytracing or anything similar. At the begining they said they did not use voxels, only to admit later that yes, they were using voxels.

    You see with them everything is a matter of what words mean. Eventually they may say, yes we are 100,000 better than polygons, but it really depends on how you define multiplication.

    As you say moving to GPU is not trivial. It will require them to re-do most of their engine. And they will find severe limitations in bandwidth and memory coalescence patterns once they try to get past the mere instancing they show today.

    Regarding animation and dynamic lighting, those are not real drawbacks. You can always have a hybrid system and use polygons for what they do best. If you look at id's Tech5, which is powering Rage, it is also some sort of hybrid. The world scenery is using the megatexture technology, still polygon based, but very static. Everything including lights are pre-baked.

    Anyway Euclideon's outlandish claims have helped. It brought attention into this area, people are noticing good engines in this field like Atomontage.

    The Australian people should make sure their money is put to good use. It is OK to fund research like this, even if it is nothing new. In return Euclideon should act like a serious shop and stop with the bullshit.

    ReplyDelete
  33. Wrt low hanging fruit, I started looking into procedural story/drama/quests a year or so ago but got side tracked.

    To produce anything usable the story needs to know about the world, probably though markup, so then I got sidetracked making a procedural world that generated markup automatically.

    In hindsight I should probably have hand build the world/markup, then I may have something interesting to say by now :P

    In any case, I think procedural stories will come from extending the gameplay found in games like With Fire and Sword, The Sims and Echo Bazaar.

    P.S. If people think only hand crafted content can satisfy then I wonder what they think the people that write algorithms are dong if not hand crafting content?

    ReplyDelete
  34. I recently found this blog, and have read through most of it. I've impressed with what you have achieved so far. You have covered a lot of the topics which I have pondered on but never made the time to implement. I wish that you would make code available, but I understand that writing a hobby project is more fun than becoming free tech support for a bunch of enthusiasts trying to use your code in different ways than it was originally intended. Maybe some day.

    I haven't seen much comment on how you generate your landscapes, apart from discussions of various noise functions. I did see a number of interesting papers on fast erosion simulation which would be voxel compatible, although I gather that you haven't gone that way. Perhaps that might be worth considering when you do implement rivers, as river location needs to look natural. Given that your methods are voxel-based, are there any sub-surface features? I assume no, but I would love to be proven wrong.

    I definitely like that your forest generation and city generation is history based. I think that it is all too easy for a city with no history to look fake. In too many games I have asked myself "but why is this here? what is it's purpose? where does the food come from?". I appreciate your reasons for starting with random settlements, but I would love to see a colonisation based model. Things like the initial location, areas that were abandoned as their purpose become outdated, roads layouts that are strange because two settlements merged, the location of affluent and poor suburbs, they all add a certain authenticity that humans can almost smell.

    That aside, what is the purpose of this project? A tool to make it easier for artists to create game worlds? The engine for purely procedural games? Perhaps a mixture between procedural worlds and scripted action? For any procedural game that doesn't involve human tweaking post-generation, my question is how to combine events with the landscape. For example, if the scripting requires the player see an army marching out of the sunrise from a high vantage point, how could you provide that? Or is the argument that the game should be procedural as well and use what the landscape has to offer rather than vice-versa?

    ReplyDelete
  35. @Dave:

    The large features in the landscape are generated in a very coarse 10m x 10m resolution heightmap. It starts with some noises and then erosion. This phase does not use voxels at all. As you say it would be nice to have voxel-based erosion and sub-surface features but that is beyond the scope of what I want to do.

    Forest generation is history based, but city generation not so much. You will have a lot of unanswered questions while traveling one of these cities.

    The short term purpose of this project is to generate a static virtual world that looks nice and let people explore it. If the technology is successful at that there may be spin-offs like games or even a set of tools so other people can do the same.

    ReplyDelete
  36. Fair enough. I imagine that in future versions your current coarse heightmap based erosion would be kept anyway for speed of generation, and a finer-grained voxel approach could be applied afterwards (but before trees etc). Sub-surface features would probably be somewhat compatible with heightmap erosion, each cell could just have 3 heights, one for each type of rock (assuming a simple layer cake arrangement). The different layers would have different resistance to erosion. And voxel erosion (or another method) could be applied afterwards to create caves etc.

    I think I mis-spoke about cities, I believe it was countries that you applied history to. Growth, annexing, etc. I liked the forest approach, the results I saw look good.

    Your goal makes a lot of sense. Too many people (myself included) have grand goals that never get achieved. Also it may be hard to tell what end purpose it is best suited for until you have the technology sorted out. Maybe for artists as an initial step, maybe for real-time, or maybe for evolving existing landscapes in real-time for MMORPGs. I will watch your progress with interest.

    ReplyDelete
  37. The amount of interesting content a procedural generator can create is bounded by the time spent developing it. We all hope it's greater than a linear tradeoff, where adding procedural subsystem 300 increments interest the same amount adding subsystem 3 did. I doubt it's the exponential number of choices we all like to pretend it is, where each permutation of involved systems is an interesting thing. Quadratic though, perhaps.

    The point though is that you can definitely create interesting worlds with procedural techniques, and even if we can't maintain interest for longer than we might by spending the same amount of time with hand crafting, you still have an infinite amount of stuff. That has a value of its own.

    Anyway, don't let people get you down about the eventual use of the system. Furthering the art is a good goal in and of itself. And I see lots of potential ways to use it, provided pathmaps and all those other gross game conceits can get strongarmed onto the system.

    So when's your next update?

    ReplyDelete
  38. @Squash: Yes, we should not be so hard on procedural generation. Most humans cannot produce interesting content, it is a difficult problem.

    My next update as usual no idea when it will be. I'm not working on visual things right now, I moved to designing the data formats to stream info from server to clients.

    I'm far from done regarding the architecture and city generation, but the experiments I did put my mind at ease. This is not longer a big question, so I moved to what I perceive it is the next critical point: making sure all this data can be sent to clients fast enough. Answering these questions will let me know if I'm still in the right path regarding generation.

    ReplyDelete
  39. I'm looking everyday here for a new post. But don't be in a hurry. It's probably just the fourth thing i'm waiting for in the IT field after battlefield3, minecraft 1.8 and skyrim..

    ReplyDelete
  40. I don’t see the point. You can build piece by piece, from scratch, specifying every detail, every behaviour, at the lowest level possible of abstraction. Or use a higher level approach, building not one tree but a Tree class, and then you will let the machine to generate a forest. No need to hire a colony of human ants to craft every single tree. Machines are meant to work instead of us. They are already doing some easy applications for us. And we can do better. We can teach machines to generate worlds, to entertain us, where there are procedural trees, cities, people, behaviours, even in-game music.. all procedural.
    Why not? After all, reality is procedural. We can guess that everything in this world can be mathematically portrayable, perhaps with a better math. And of course the formula that portrays a reality like this where some humans like us are speaking about a subject like this must be complex for a human mind to handle. So it’s not strange that early approaches lead to “bland” results. As well as it’s not strange that in a time like this, triple A companies prefer not to invest much in research about content procedural generation and go through the well known development process (with the human ants..). Procedural is challenging. Yet procedural is what makes real. And I believe that it will be the natural evolution to reality representations.
    I’m a coder with very small spare time. Yet I could set up a simple terrain generator that can entertain me for hours (gdevice.blogspot.com). I think I’ve spent more time on exploring that world than on coding its algorithm. Imagine what can do a paid team that works full time on that..
    In my own opinion, procedural content generation is very challenging, definitely not a 1 man project. You should not plan to come out with a game entirely procedural, not as first goal. You better complete small games, each one with a little more procedural content than the previous one. Imagine a procedural engine, aside the graphic engine, that will first have only a name generator, then you add a maze generator, then a race generator, a mission generator, a speech generator, and so on..
    In the beginning your game will be partially procedural and partially handcrafted, so your game editing will be like this: here is the terrain (generated) and at this mountain is a castle (handcrafted) with a dungeon (handcrafted) and a treasure chest (handcrafted). When your game will be pure procedural, I imagine that your game editing will be like this: here is a universe with 3% of earth-like planets, each with 30% of mountains, 0.5% of castles and 2% of treasure chests. And you coder won’t know where those will be located. You could even play your own game. Does this make sense?

    ReplyDelete
  41. @Nicola: You may be oversimplifying. The fact that we have succeeded in some areas like terrain and botany should not be extrapolated to all areas of artistic creation. For instance, I don't know of any musical composition entirely made by an algorithm that is appealing to humans.

    Even if you think reality is procedural, then the computer would be the Universe, and it would have been running for billions of years... all this was needed to come up with "A rabi, a priest and a shaman walk into a bar..."

    ReplyDelete
  42. Great post, and great blog in general! As an AI guy with an interest in procedural generation I really admire what you're doing - I wish I could find some time do do something similar myself (too lazy is the answer of course).

    I wish I had something more constructive to say, but I notice you typo'd the Turing test (after Alan Turing) as the Turin test (determining if an image really is the face of Jesus?)

    Well, maybe I can say something. There's a niche waiting to be filled in procedural narrative generation. I'm not saying we'll have an AI writing the script of Planescape Torment, but consider the tired and overused plot device of one of your companions turning against you. This is either usually telegraphed extremely obviously, or at least the player will know exactly what to expect on their second playthrough.

    A fairly trivial change would be to make it one of three (say) of your companions who will betray you, and have two clues and one red herring which occur earlier in the plot to give you a hint if you're paying attention. A human would still need to write all the dialogue for each case, but the classic betrayal suddenly goes from a big yawn to a tense turning point on every playthrough. And once one game does it, there'll be no going back.

    ReplyDelete
  43. A lot of the views I see on the limits and shortcomings of procedural generation focus on the fact that you can't procedurally generate a compelling story or narrative, that it's really hard to build a level which both looks good and has a good flow of gameplay and pacing.

    This is all true, and will remain true for some time (though I'm sure there will come a day when when you can procedurally generate a complete and compelling narrative), but it's also missing the point. It's operating on the assumption that these things that procedural generation fails are things that are actually necessary for a good game.

    However, procedural generation has a long and storied history in excellent games. Minecraft and Dwarf Fortress are the major recent examples, but one people often forget about is Civilization, with it's procedurally generated world maps. Strategy games and God games have frequently used procedurally generated maps.

    The trick to a solid procedurally generated game is coming up with a design that leverages the strengths of procedural generation, and doesn't rely on the things that procedural generation is bad at. The key to such a design seems to be to shift the focus away from the story, and more towards building and creating, be it building structures, or machines, or communities, or whole civilizations. When the world's purpose is shifted away from being a setting for your story, and towards being a resource and an obstacle to your creative endeavors, then procedurally generated worlds start fitting much better.

    ReplyDelete
  44. I'm way late to the discussion but it's a topic I find infinitely fascinating.

    I feel like modern game designers give too little credit to players ability to engage in abstraction. Which is very odd coming from an industry where 4 triangles and some brown and green has meant a tree.

    I think the point of procedural content isn't just to save the artists time, or generate bigger worlds, or extend the length and variety of content. For me the true strength of procedural content is the players become the designers while they are playing the game.

    Procedural content means the game responds to the players dynamically. Dynamic responses are governed by rules. The players learn the rules and explore their ability to get the game to respond differently to different inputs. They reshape the gameworld to their preferred image, and they are doing this not as developers, but as players, the algorithmic responses from the AI, or the geometry, or the mechanics, become abstracted elements for their internal and self directed narrative. The story you make for yourself is always more engaging than the one force fed to you.

    ReplyDelete
  45. I like your vision. A virtuality that is dynamic, and that dynamically responds to player actions, would better resemble reality.
    Apart the graphic aspect, modern games still mime books, not reality.
    I think you are never late for this discussion.

    ReplyDelete
  46. I feel that the key with procedurally interesting worlds is that it needs system that are designed to interact in interesting ways from the start. That is to say, it needs to generate features that have emergent properties. It can then be honed to create these interactions on a regular basis.

    The great part about dwarf fortress is that it creates stories that you can re-tell because of the way that everything interacts and has substance. You can tell a story about how a dwarven mother was killed by her dead baby's reanimated hand, and later how the father went batshit insane and killed everyone.

    The reanimated hand is an interaction of the creature generation system and the material system (dead flesh can become a creature). The fact that the hand can be come dismembered to begin with is a feature of the weapon system interacting with the body simulation. The upset father is an interaction of the emotion system playing itself out with the "jobs" system in the sense that he gets assigned the job of throwing tables around.

    As for it being ascii, there is nothing preventing someone from creating a creature system using a similar grammar system like how you create buildings. Map it to something like spore's creature engine and you can basically make any creature imaginable.

    On an unrelated note: computer generated music is getting quite good: http://www.youtube.com/watch?v=o0tH_mHXR9c

    ReplyDelete
  47. What Carmack said ("procedural techniques are nothing more than a crappy form of compression") indeed ironically relates to compression in terms of the Kolmogorov complexity:

    http://en.wikipedia.org/wiki/Kolmogorov_complexity

    ReplyDelete
    Replies
    1. Yes this is correct. I love you brought it up.

      Carmack in this remark and others in general are quick to equate procedural generation with only the family of "local" methods like Perlin and cellular noise. These functions have very little information in the results they produce, and should be avoided as the core of procedural content.

      There are other procedural techniques that rely on simulation. This is different, because even if it is still generated by a computer, there can be a lot of time and energy going into producing the results. So terrain, plants, architecture, etc that are generated this way may contain a lot more information.

      Also note that simulation, while it is governed by a code (let's say a program and some initial data) can express results that are not directly bound to the code. This is similar to how DNA is the code for a person, but the actual person is the result of running this code for a very long time, in a very complex machine (the world).

      And last, we tend to think of humans as whimsical, unpredictable creatures. In reality content that is created by humans is also bound by real world rules, and most importantly by their experience and the techniques they know and use. Humans bring a lot of redundancy as well. The Kolmogorov complexity of the stuff we create is not as high as we like to think.

      Soon a human will have trouble competing with a computer that has seen every place on Earth, every work of art, every game world ever made.

      Delete
  48. It is an interesting proposition but taken to the extreme.
    Most real human beings still haven't mastered the art of game design, so it will be a while before an algorithm can match human capability.

    ReplyDelete
    Replies
    1. Well most humans still suck at Chess and Jeopardy, but algorithms already surpass the best of human capability.

      I remember a time where people would say, yes computers are fast and whatnot, but they will never beat a human at Chess. Then it happened and we started saying well maybe Chess, but never at a game that relies on intricate linguistics...

      We keep moving the goalposts, until there won't be much to contest.

      I for one salute our robotic overlords. I know they are reading this. Friends?

      Delete
    2. I'm not saying it won't happen. I'm saying it won't happen as "soon" as you seem to be suggesting.

      Right now, a team of developers can make a game in less time than a team of researchers/programmers can make an algorithm that spews out games of the same or similar design. The man-made game will be of higher quality, as well. This will continue to be the case for a very, very long time.

      Delete
    3. Not to mention that a creative, complex field like game design is not really comparable to a problem with definite rules like winning at a board game. I'm not saying we won't achieve sentient AI, but it seem its still a ways off.

      Delete
    4. I never said or implied it would happen soon. From where do you get this?

      Also note you do not need a general purpose AI to tackle the domain specific problem of game design. In that sense it is like Deep Blue and Watson. You could even have AIs specialized on designing a particular genre of game. So the AI that does RPGs would not know how to do FPS.

      Delete
    5. I want to spend a few words in defence of Miguel, firstly because I have great esteem (other than some kind envy) of such people as Miguel because he does what he likes and doesn't fear to pursue a project that may never meet the market or any pecuniary gratification in a world where everybody is hunting money.

      Procedurality requires expensive research and would make games repeatedly playable. That's why I'm not sure that current investors would be willing to pay for this, at least not for games.

      However, I believe that games (at least some) are as fun to play as they resemble reality. This resembling can be restricted to aesthetics, for many reasons, but in my humble opinion, behavioural resembling is the core feature of a game.

      See reality. It is not sandboxed and has not predefined set of cases. See a simple ball how fun to play is for humans and for other species as well. The physics of the ball holds infinite cases, unpredictable cases, allowing the ball to mime a prey or whatever in the mind of the player. Yet it is just a formula.

      Miguel is a creator, one of those who made math his main tool of creation. I believe that procedural generation can undisclose doors to new game mechanics that are now not possible and not even imagined. Here lies the second reason why I esteem Miguel, because he is a visionary and a pioneer. Most of such people have not got fame in history. But I believe that every single drop of progress we have had we owe to these people.

      Delete
    6. please substitute "undisclose" with "unlock" and forgive my bad english, thank you.

      Delete
    7. I am not attacking Miguel so you don't really need to defend him. I love procedurality and it is a fantastic tool. And more necessary each day. It's highly possible that without people like Miguel who push an idea to its radical extreme, the rest of us wouldn't see many avenues that would lead to create actually useful and desirable things, be it for games or any other fields.

      I guess I misinterpreted his enthusiasm, thinkig he believed his goal would be achieved in our lifetimes. That's when I pause to reflect that in all of human history, nobody has yet codified any of the arts (first step to teach an AI is knowing what to teach ourselves) so the claim of a game-generating algorithm that's on par with human work remains a pipe dream. I apologize if my comments seemed hostile.

      Delete
  49. > Procedural content means the game responds to the players dynamically. Dynamic responses are governed by rules.

    IMO procedural generation of content and especially simulated content will prevail in the long run for simply that reason. 90% of all games are almost 99% linear experiences. How often have I asked myself why I can't smash in this window or why is there a garbage truck blocking this street? Why can't I shoot that person and see what happens? And gamers do get bored of genres and want more.

    Procedural generation will surly enter middleware and become more and more complex and sophisticated. It's probably an investment that will have to be amortized over multiple games. But when it becomes available as a tool to many developers, people will do amazing things with it similar to the star trek holodeck, things that would never be possible with hand crafting.

    It would be awesome if there was some kind of standard volume shading language for generating 3D content and a kind of open repository for reusable procedural content. There would be lots of people who would love to contribute to it or moderate it. In the end you might be able to specify something like "Computer: A dinosaur please, green, talking out of his ass". A crappy form of compression, HA!

    Also I enjoyed reading all the comments here and great blog!

    ReplyDelete
  50. You should have a look at Limit Theory. The creator is trying to do exactly what you talk about here. Btw, love your blogs, avid fan. :)

    ReplyDelete
  51. I would use Simplex/Perlin noise to throw in some variation.
    Indeed, you could use those noise algorithms with forward Brownian motion to provide “waves” and “tides” between moments of tension/relaxation/anxiety… It could also be used to effect mood swings in NPC’s and romance(relationship) charts. There are so many applications for seemingly random waves to appear life like and unpredictable. It could also be applied to affect the mood of a virtual artist…
    Human creativity can be procedurally applied if we can define the patterns employed by the artist. Despite their claims, most artists have a pattern of creation. It may be a unique pattern to them, but they spend a lot of effort trying to deviate ever so slightly from their patterns. So if we can identify the factors of their style, then in that sense, a rigid artificial intelligent artist could become a procedural entity?
    But failing that, we can use user/player/participant feedback to alter the content as well. This allows participants to entertain each other to a degree. This would work really well if the average person wasn’t so boring? I imagine for instance, a virtual world, where the players are living in a world of limited in resources and ability, but have unlimited aspirations… this should result in real world politics and could provide some amazing socio-global events and everybody will be a part of it, if only in virtual presence.
    I’ve been toying with procedural and user driven designs for a few months now, mostly because, as a single developer and artist, it would take me a decade to build my own decent virtual experience, if I were to try and do it conventionally.
    But I’m veering off course. I really enjoy it when I come across these philosophies in your blog. I’ve been returning to this blog regularly and your work has been most inspirational and reinforcing. I hope to catch up to this level of applied philosophy someday, though honestly, if Voxel farm was available as a tool for Unity, I would happily use this wheel instead of reinventing it from scratch.

    ReplyDelete
  52. Don't forget how Diablo 1 married unique content and procedural generation. While D2 always has the same hand-made parts on each level, in D1 some hand-made parts were only present if you are lucky. That's still only a few steps in that direction, the potential is bigger.

    ReplyDelete
  53. I think currently yes, large amounts of procedural stuff can lead to games that are repetitive and boring. However, I believe that procedural generation, following the same trend that other innovations in computer graphics have, will eventually reach what I call the infinity barrier.

    Currently, RGBA colors can produce more different colors than the human eye can detect. There is no point in making more colors,because to our eyes, they will have the same effect. In other words, modern color storage methods are just as good as if they could hold infinite colors. The same could be said for unicode text.

    This is what I define as the infinity barrier: the point at which it is useless to improve upon a technique because it already at or beyond the point where a human user can detect such an improvement.

    Eventually, I can see procedural generation methods reaching this point. While humans can pick up on quite a few variations, there is still a limit to the number of differences we can see. Think of a leaf on a tree. If the tree only has 1 or 2 leaf shapes that are repeated, it is certain that someone will notice. If the tree has say 50 leaf shapes, it will be much harder to see such repetition, but eventually, after seeing the same 50 leaves on the same tree, you will get the impression that the trees are not real. But when a point comes that the tree can create hundreds or thousands of leaf variations, nobody will notice that one leaf here looks exactly the same as another leaf there.

    I must also disagree with the idea that procedural content lacks the sense of adventure needed for a game. There are plenty of interesting features, such as caves, volcanoes, ruins, etc. that can all be made procedurally and work just as well with the surrounding environment. But there is an infinity barrier here too, in a way. Players are unlikely to venture extremely far distances in games, so if such features are sparse, the player is unlikely to run across more than one of them. Also, due to their extreme differences, if a player did run across two ruins, for instance, they would look so different that they would tell a completely different story.

    ReplyDelete