Recursive Procedural

  By Shamus   Jul 21, 2010   111 comments

Talking about procedural content, Bobknight asks:

wouldn’t the vast majority of the content be(by definition) random? or do you mean that instead of specifying each individual ‘box’ they just point to an area and go ‘mountain here.’ or ‘desert here’ and use the appropriate algorithm for each one? If that is true, wouldn’t he algorithm become increasingly/impossibly more complex if you want to put any kind of detail(the kind of detail that most RPG/sandbox games demand) in it?

I mean, how does this help to make something like fallout?(where you have the dead janitor on the ground with his two bits of meat and a can of beer)? Would the resulting game world be merely a HUGE collection of randomized terrain that has absolutely nothing on it?

So far my approach to this – and I’m sure FUEL does this as well – is to make procedural systems recursive. A system produces data, and that data is used as input for another system. One level carves up the world into geographic regions. That data is used to generate the topography of the world. The topography is used to decide where to place cities. Those locations are used to build street systems. The streets are used as a guide for placing buildings. The buildings can then be filled with hallways. Hallways are filled with dudes. Rooms connect to hallways. Furniture goes in rooms. Objects go on furniture. Player is given a gun and told to go kill some dudes and get some objects.

Each system is a set of rules and depends on good input. In 2003 or so I wrote a program (and the source is gone, I keep meaning to re-write it, dangit) to take some topographic data and attempt to plot a road across it. The rules governing roads – while not set in stone – are fairly reliable and observable. Roads will curve in response to hills to keep from becoming too steep. When a road is navigating around a hill, the inside of the curve should bite into the hill and the outside should lift it up. (In the real world, engineers displace dirt from one side to add to the other, which produces the familiar banks on either side and the distinctive not-dumping-you-into-a-ravine horizontal flatness for which roads have become so popular.) In my system, the road was willing to go up and down steeply in direct proportion to how far off course it was. My road wanted to go north, but would veer to either side to avoid hills. But as it came closer to heading due east or west, it would be willing to climb or drop to a much greater degree. This produced a very convincing road. (However, the system would occasionally encounter topography that was not solvable with the given rules, and the result usually looked hilariously bad.)

You can see this at work in FUEL. If you go out to the perfectly flat zone in the northeast you can see the roads basically form a grid. In the hilly parts of the game, the roads bend around quite a bit. In the really hilly sections, the roads get crazy twisted. Sometimes you’ll see a road get “trapped” by unworkable input data and it will either climb a sheer cliff or simply give up and end abruptly. Note that the roads in FUEL had the added challenge of needing to intersect with one another at reasonable angles, which was something I never attempted.

The point is, FUEL is recursive. It generates topography. (And I suspect even the topography generation is a multi-stage deal.) Then it places roads. Then it places debris on the roads and buildings alongside them. If you’re trying to make “procedurally generated Fallout 3″, the next step is to add more stages. This becomes really easy if you decide to take the Bethesda shortcut and make exterior doors into magic teleporters that will move the player into the building without needing to worry about a smooth transition between the two. (This solves tons of problems. You don’t need your interior floor plan to precisely match the exterior of the building, and you don’t have to worry about the complex culling problems you get when the player starts seeing through multiple windows at once.)

As for the “dead janitor” problem: You can have artists design special set pieces and simply make their placement exceptionally rare. The artist will make a group of objects like the janitor, his mop bucket, and his beer, and specify rules like “this thing only goes in hallways” and “this should never appear more than once in the same building” and “this should only appear in 1 out of every 50″ buildings. Then the game will drop in the janitor every now and again. As far as the game is concerned, he’s just “furniture”.

The move to a procedurally generated would wouldn’t mean that the world would have to be dull and sterile. With the right rules you can make places just as vibrant and interesting as those in Fallout 3. You just need to make the up-front investment of building the system (no small thing, I’ll grant you) and change how your artists approach their work. If the world feels monotonous then it means your rules aren’t robust enough or your artists haven’t added enough variety yet.

I’m convinced this this has been do-able for the last several years. I just wish I could earn a paycheck proving it.

A Hundred!11111 comments. Quick! Add another to see if this message changes!


  1. Kreek says:

    is this the part where people say first?

    anyway, why not just let the programs procedurally generate the landscape and buildings, and then go in, place things manually and just tell the thing, okay make it and add this exactly right here?

    if you program the thing so that it generates the same landscape every time, as i suspect a lot of procedural games do, then it will end up looking fine when its all done

    Edit: also, as a side note, what happened to spoiler warning this week? did i miss something saying its not going to happen?, or were you too busy playing wow?

    • eri says:

      Pretty sure Bethesda did this for Oblivion, with hand-placing of all NPCs/objects/buildings/dungeons, and probably some minor tweaks for the purposes of aesthetics. The interior layouts are created using room presets stuck together, but there isn’t too much variety available, so they all tend to look very samey.

    • Alan De Smet says:

      I gather that hybrid design is common. If you see a game’s credits include SpeedTree, they’re using procedurally generated trees, but frequently they’re placed by hand. For a large outdoor environment, a designer might mark a large zone as “fill with random bushes,” then he’ll add or prune specific bushes to fill his needs.

      • Tizzy says:

        It’s too bad that by using procedurally generated trees, many game designers appear to miss the forest: procedural generation does not need to be restricted to trees.

        • eri says:

          Well, SpeedTree is extremely easy to plug into your engine, and it’s a major time-saver to not have to place everything by hand. I think at this point procedural content generation is seen as a way of making level designers’ lives easier rather than actually augmenting gameplay.

    • pneuma08 says:

      If you procedurally generate something and then have to save a specific instance of it, that kind of defeats some of the point of procedural generation – the space-saving and the different-experience-for-each-person; even if the latter is unimportant, as soon as you start placing things by hand and saying, “this goes *here*” you have to save that data somewhere.

      Now what you’re talking about can be applied, but it would essentially boil down to a very good (if the map is minimally tweaked) form of compression, but it would be very difficult to build something that is the same all the time – it would be a pretty nasty algorithm to solve, and since games come on DVDs nowadays it makes sense to just pay the disc cost instead.

      Now it is possible to do a hybrid of sorts, too. If Fallout 3 were procedurally generated, for instance, they could say, “okay, Megaton looks like *this* and goes at 10×13 and must be in a crater” but it doesn’t matter if the crater is in the side of a mountain or in the middle of a flat plain. It’s not *quite* so simple as that since they have to resolve seams and such.

      (Of course, since Fallout 3 takes place by DC, they probably took great pains to measure the terrain of the area – in which case they couldn’t just generate it. And, if they’re going to place all the landmarks by hand, that kind of defeats whatever benefit procedural generation provides. A better example would be Borderlands, which would be better procedurally generated since you wouldn’t have to slog through all the same areas when you make a new character and since it isn’t tied down to real-world topography. But I digress.)

      • Blake says:

        We’re not talking about randomly generated we’re talking about procedurally generated.
        Basically every computer random number generator will generate the same series of outputs given the same input.
        To try to randomize things we tend to set the seed number to something like the number of milliseconds since Jan 1, 1970.

        For procedural content like this basically all you need to save is the initial seed number (I imagine the designer would hit ‘randomize’ a heap of times until he finds something decent then tells everyone that that’s what they’re starting with) then apply your changes afterwards.

        • pneuma08 says:

          While true, but in my view it kind of defeats the whole purpose of building a whole algorithm if you’re only going to use one output. I suppose the point is that it makes storage of the game much, much smaller – but even then, once you start placing specific things at specific places, the procedural algorithm becomes less and less relevant. And if you have to generate a huge area and fill that area with fluff by hand, I don’t even know if it would save dev time even with a prebuilt algorithm.

          • Hamilton-Lovecraft says:

            There are three major reasons for considering procedural content. One is saving artist-hours, two is saving disk space, three is playthrough variety. To you the last is the important one, but to the people with the money, the first is.

  2. Benjamin Orchard says:

    Isn’t this the sort of thing that Blizzard does with the Diablo series? And not only that, but from what I understand, they do it pretty darn well…

    Not perfectly, of course, but my understanding was that they designed the engine to accept parameters and use specific tile-sets to build various things, which then resulted in a world that was ever changing without seeming stupidly random.

    Additionally, if I’m not mistaken, the game .kkreiger (the one that fits in a mere 96kb…) uses procedural (but non-random) level generation to fit into a ridiculously small space.

    It would lovely to see the same sort of thing applied to a tactical shooter, but whatever.

    • eri says:

      The problem with Diablo (the first two anyway) is that the dungeons and environments all tend to look identical. They can do things like say “there will be more rocks in this place” or “this area will have more houses” but there are still a few places where they have to throw their random levels out the window in favour of fixed ones to get the desired results. Honestly, if it wasn’t for those, the games would be extremely monotonous.

      Diablo III is sort of continuing that, from what I understand, but the world is a bit less random – there are set “vistas” or what have you that are always going to be there, but the roads connecting those areas will be random. Those road pieces are also a bit more interesting than “cave floor” as well; Blizzard can incorporate things like collapsing walls, giant boss enemies that smash through scenery, etc. to spice it up. If you’ve played Torchlight, it sounds like it’s one step ahead of what’s seen there.

      • Low-Level DM says:

        I expect it will rather be a large one step than a small one, between the two, but many of the design and production styles/schemes are supposed to be quite similar, yes. I hope they make more extensive use of that interactive scenery you mentioned, though, than in Torchlight – it’s more like a “look what we can do!” that shows up once or twice and never again, there. And, for the record, all the levels in the same tileset for Torchlight do feel exactly identical, just as you mentioned afflicted Diablos I and II.

  3. eri says:

    The only real downside is that you miss out, to some degree, on the sort of detail that actual level design is capable of. This works all well and good for producing “realistic” terrain and buildings, but it really does not work very well if you want to have very specific scenes, locations, etc. Of course, it’s also totally possible to build that stuff by hand if you want to, if you need it.

    The other question about procedural content I have is that, at what point does it start to deliver diminishing returns? It’s well and good to have a giant game world, but if that isn’t your game’s focus, then is it really efficient to create a system to auto-generate everything for you? You might end up spending more time building that stuff than just picking the nearest middleware and building it by hand. I actually think it could work really well for a smaller game world, but if you only need 100 or so areas/levels in your game, with good tools you’d possibly get better results creating it yourself. You can also do far, far more tweaking that way for the sake of play-testing.

    • Bear says:

      Since I foresee a wall-o-text…
      TL;DR – procedural DOES NOT EQUAL auto-generated (meant in the nicest way possible ;)

      1) specific scenes, et al.
      This will depend on the level of granularity in your original input to the procedural system… or, stated differently, the more information you give the procedural system, the more control you have over the output. To illustrate.
      – A simple deathmatch game might only require 3 numbers to generate a playfield. 1) overall terrain roughness, 2) amount of obstacles and 3) type of obstacle (trees, rocks, buildings). With this you could generate many different playfields and if you make the numbers random, the player might never see the same area twice.
      – A more complex game, say FUEL, might start with a matrix. Let’s say a 100 x 100 matrix, with each number representing the average elevation of a square mile. That would give you a 100 mile x 100 mile play area. Since there are very few placed items, we could generate everything needed off of the elevation matrix. (for instance, take the average difference of any grouping of 4 square miles… a city would be placed if the difference was 0 [indicating a leveled area], a grassy plain would be placed if the difference was between 0.1 and 1, a forest for 1.1 to 5, and rocky outcroppings for anything greater than 5). Does this satisfy every possible real-world outcome? No, someplace like San Fransisco or Pittsburgh could not be generated, but it would be a workable area. And as long as the matrix is hard coded, you get the same play area each time you run the procedural algorithms.
      – Now to do a crafted game, like Fallout 3… you might want more resolution on topography, let’s say a 1000 x 1000 matrix for a game area of 20 square miles. You also want more control on placing other items, so for each additional class of item (terrain style [city, forest, etc.], lootable objects or unique objects) you add an additional matrix of the same size. The unique object matrix would be where you specify anything that you don’t want run through the procedure, ie. a unique building like the Nuka-Cola factory.
      – In the end, the more layered your inputs, the more crafted the environment will be.

      2) diminishing returns…
      I can’t really see where a procedural world would be worse than a hand crafted alternative… it really is like trying to discuss the differences of programming in basic and visual basic. Yeah basic had a lot more freedom, but visual basic has repeatability and optimization at its core. (note, that doesn’t mean I actually like visual basic…) Eventually someone will put out the middleware to allow procedural design kinda like Valve did with the Source engine. With the push for larger and larger games (both single player and MMO), procedural content has a hands-down advantage of data density and optimization.

      3) non-open world games
      Even a game like Portal could be procedurally generated… just with a different procedure. Instead of starting with a topo map, you would start with the basic obstacle course and let the procedures tile in the background information. Again, the goal is to optimize the data by letting the procedure fill in data that is either repetative or not important.

      So after that… did I help, hurt, or just avoid the questions?

      • pneuma08 says:

        I don’t see how Portal could be procedurally generated. Sure, you could fill in the “unimportant gaps” – but how much of that game is unimportant? Every space is used, and in fact some of the most memorable moments are of the artists filling up the unused spaces. If the “unimportant” were procedurally generated, that would be a waste in building the procedural methods since it would only be used on a tiny segment of the game.

        A better example would be Left 4 Dead, which is starting to use some generated content in the sequel (e.g. the Cemetery in the Parish). It would be entirely possible to leave the setpieces intact while generating the traversed middle.

        That said, I believe what eri is touching on is applying the art to level design, which would be very difficult to do procedurally. Things such as ease of navigation through maps, manipulating player focus, and so on. Valve is the poster child for this, and if you check out the commentary of any of their games, they’ll go on and on about it.

        • krellen says:

          Didn’t the guy preface the whole thing with procedural =/= random? A procedure does not mean random. It means the work is done on-demand, not before-hand. If you provide the right input, you get the same output every time, meaning it’s not random, and you can decide precisely where everything is – but since you’re just providing the parts and the instructions, and not a pre-built level, you can pack it in a smaller box, with the small side effect of requiring the end-user to do a bit of the work themselves.

          In the case of a procedural Portal, this would mean they’d give you all the different walls and turrets and modules and other pieces used to build levels and a list of how those parts go together to make the level, but then leave it to the machine itself to do the assembly. So for 10 levels, you get one copy of parts and 10 sets of instructions, which takes up significantly less space than 10 copies of parts pre-assembled as designed.

          • Blackbird71 says:

            That’s actually a really good analogy for procedural content: furniture that you assemble yourself. It comes in a box much smaller than the finished product, and consists of all the pieces you need and a set of instructions. The same instructions won’t give you a 5-shelf bookcase one time and then a desk the next. Unless you use different instructions, you will build the same piece of furniture every time.

          • pneuma08 says:

            Even if it’s not “random” in the end user space, it needs to be “random” in the design space, that is, before it’s nailed down (for instance, when someone decides that seed 5720031 is appropriate). For example, trees – trees are commonly procedurally generated because it doesn’t make sense to lay them all by hand. If for some reason that trees do need to be laid by hand (for instance, if you wanted a ring of trees surrounding a clearing, at a specific point on the map), it doesn’t make sense to build an algorithm such that it will generate said ring at the specific point. (It would be possible to configure a workaround like pre-building the object and stamping it on the map, but every time this happens, the area-building algorithm becomes less and less valuable.)

            Basically, it doesn’t make sense to design an area then build an algorithm to solve for the area you want. That would be terrible (and horrific to just modify something tiny within it).

            Now, with a game like Portal, or Valve games in general, everything is placed with purpose – every alcove, every turret, every pit trap – so it doesn’t make sense to have it be procedurally built. This makes procedural design the antithesis of what Valve is doing.

            For something like Fallout 3 where the topography is modeled after the real world, so it doesn’t make sense to generate something similar to it via a generic algorithm at the design stage, and it doesn’t make sense to build an algorithm to specifically generate the DC area.

            • Shoku says:

              I disagree with your Portal assessment- we see pgc for just simulating realish world stuff a lot but you can even more easily make algorithms for creating a winding path with interesting nooks and crannies.

              With the way that Valve actually does extensive playtesting so they can go back and tweak things they are unsatified with the end result is better than what a reasonable ammount of effort into pcg would give but the first draft of a level is very much the sort of walking between two lines thing that procedural generation should be good for.

              If you play through a level making note of every single action you must take and then draw that as lines and nodes you should have no reason to think a computer couldn’t approximate an endless number of variations of that.

            • Elec0 says:

              You’re still missing the main point of procedural generation: to have less hand-placing and storing of exact position information and to have more general, this type of thing goes here deal. It’s to save disc space at the expense of processing time. (Take a look at .kkrieger (which has probably already been mentioned), for example. Extremely small, but still has all the major parts of a game.)

  4. Nick says:

    An interesting example of this is Introversion’s next game, Subversion. Chris Delay has posted some really interesting posts about procedural generating a city, including working doors, elevators and the like.

    Hopefully the game bit will stand up to the cool geek tech bit.

    • swimon says:

      Really everyone should see the cities they made procedurally (I don’t know whether they will be used in game or not and I don’t think they know wither but still). Especially check out part 3 it’s mostly a road generator on an almost flat surface but it’s gorgeous and it really look like the map of different cities.

      http://www.introversion.co.uk/subversion/

  5. Svick says:

    One amazing example of procedurally generated content is Dwarf Fortress. Not only does it create huge world with lots of details, but also the world’s history. It’s even more amazing when you realize it’s written by just one guy.

    • Deoxy says:

      Dwarf Fortress is absolutely amazing in this regard… but the level of detail is,hmm, I was going to say “low”, but really, “different” fits better. It keeps up with an amazing number of things (far more than most games), but it DOESN’T keep up with many things other games do (every boulder looks exactly the same, for instance).

      But yeah, the world generation stuff is utterly astounding. Somebody was testing it recently and modified the terrain generation to the topography of Europe, and the game placed all the major rivers in Europe almost exactly where they actually are.

      • Senji says:

        To be honest that’s easy. If you have the same elevation of mountains lakes and rivers will be always through the routes of least resistance. It’s no wonder it matched so well, having said that it just goes to show how good the DwarfFortress guy is.

      • SatansBestBuddy says:

        every boulder looks the same, for instance

        I read that and thought to myself, “Oop, there’s a guy who’s never played a Zelda before.”

        Yeah, okay, I get what you’re saying, but boulders?

        Really?

      • Ragnar says:

        No, every boulder doesn’t look the same. Boulders come in lots of different materials.

    • gkscotty says:

      For an example of how in-depth DF can be, check out the info on Lesno, a minor NPC trader who turned up during a Something Awful succession game (Syrupleaf)

  6. Raygereio says:

    I’m convinced this has been do-able for the last several years. I just wish I could earn a paycheck proving it.

    I agree with that assessment. It is do-able. Just like having some sort of AI routine generate quests or even the world on the fly is do-able.

    It really is a question of funding. I remember an interview with a game developer who said things like this are possible. The technology is there. But if you were to wrap this up into a proposal and go to a publisher, they will get frightened and run away because it’s something new and stuff like this doesn’t appeal to the big crowd. Yeah, the line “fully procedural generated content” or “endlessly continually generated world” on the back of game box would certainly pique my interest; but I’m also the kind of guy who doesn’t pay any attention to screenshots and I’m fairly sure I’m the minority in this.

    • eri says:

      Actually I’d say the reason has far more to do with publishers wanting to follow industry trends to the letter. The games industry is an extremely creative place, and I’m sure most game developers are more than capable of building games in which white dudes shoot foreign dudes in the face, but publishers, who are generally run by shareholders that have no interest in or understanding of games, are the ones who decide what gets made and what doesn’t. Procedural content could be great if you were proposing an RPG provided that you had plenty of other things to sell the game on, like the prerequisite “epic, dark quest” and “hot lady elves”.

      • Raygereio says:

        Yeah, you could try and suger coat your proposals like that. You could promise monkeys… heck, one should always promise monkeys. Everything is better with monkeys.

        However the problem of funding is still there. Money that would normally go into pimping their engine until it supports HDR and flashey bloom, would now have to go into the development of actually useful things. And by the great flying spaghetti monster, we can’t have that! No, we must have ugly bloom effects (honestly, who likes that?) and 128x full-scene anti-aliasing because we can shove that into nice screenshots and because the braindead zombies that form the large horde of game consumers only care about flashy pictures, not actual content.

        • SatansBestBuddy says:

          You know, I’m fairly sure anti-aliasing has been cut from most games budgets; look at any game with 720p, and you’ll be able to count the pixels, not one of which will be anti-aliased, and more than a few of which are actually 620 or something.

          • eri says:

            This is a byproduct of the supposed “next gen” consoles not having the horsepower to deliver visuals in HD. Most people simply don’t have either the equipment or the eyes to benefit from running in HD, so developers are more concerned with delivering detailed visuals rather than high resolutions. It’s not like playing on a PC monitor where you’re up close – on a TV, from far away, and with all the post processing the image gets, the difference isn’t as apparent as you’d think.

  7. matt says:

    :D This is the kind of post I’ve been missing from you recently Shamus!

    And couldn’t you earn a paycheck doing it if you went into making games? I’d love to see something like this, even if it was just a small sideproject.

  8. Eric Meyer says:

    And the important bit which you don’t state here, Shamus– possibly because you took it for granted– is that the content will in fact NOT be random in the sense of changing every time. You can in principle create an entire world from one number because computers aren’t actually random. If you seed the “random” number generator in a programming language the same way twice, it will yield the same “random” number both times. So it isn’t random at all, obviously.

    The previously-cited Subversion is one example of this, as is Fuel; so was “Elite”, back in the day. Even I once wrote (long ago) a small 2D star cluster generator (~300 stars) where every star had its own detailed planetary system. The whole thing grew out of one number– the cluster’s seed number. These days, you could create a fully 3D cluster of many thousands of stars, with each star having a very detailed set of 3D asteroids and planets and moons, each with its own climate and resources and some having cities and mercantile traffic… all off of a single number.

    • Will says:

      That’s what i was going to suggest; if you base your procedural generation off seed numbers then you can store those seed numbers somewhere and use them all the time; you end up with the compact advantages of procedural generation combined with the ability to create set pieces.

      Almost all games that use procedural generation do this to some degree; Dwarf Fortress is the only one off the top of my head that (by default) never uses the same seed numbers twice. Although you can tell it to use a seed number and regenerate the same world if you want.

      Eric, you might want to look at Infinity – http://www.infinity-universe.com/Infinity/ – it’s still in production, but it’s basically a space MMO ala EVE Online, except with an entire universe procedurally generated; you can fly around in space, land on planets, explore said planets, go back into space, land on the moon, stop by on an asteroid, etc etc.

      I seem to recall numbers in the millions and billions being thrown around for star\planet counts, but if those guys pull Infinity off (and it looks like they will, slowly, but surely) it should be a pretty amazing example of procedural generation in action.

    • Mephane says:

      What if the real universe was created just like that? We even would already know the seed number, heh. Obviously, it is 42.

  9. Shimmin says:

    Rather than have a fixed group of objects, couldn’t you also have “associated” objects which appear in response to certain others? So your corpse randomly generates 0-5 objects from a set list of “personal items” that lie within X distance of them. It’d save the problem of hand-placing them, and also avoid there always being a janitor with the same stuff somewhere in the game. I’d have thought you could do it with similar rules to those controlling the relationships between other terrain features, although I know nothing about it.

    • Robyrt says:

      Actually, if Bioshock 2 had used this system to strew corpses, crates and broken furniture about, I honestly wouldn’t have noticed. That would probably have saved them months of level designers’ time.

  10. wtrmute says:

    So far my approach to this – and I’m sure FUEL does this as well – is to make procedural systems recursive. A system produces data, and that data is used as input for another system.

    I think you’ve got your terminology mixed up: Recursive is when the output of a system feeds into the same system. I think what you mean is layered rather than recursive.

    (Otherwise, great article. I love your stuff about procedural content.)

  11. Patrick says:

    I wanted to do something sdimilar with Shadowrun. The idea would be to make stages random and very complex, but not to have to do them over and over. I got the idea from the Sega Genesis video-game version of Shadowrun, which featured random quests.

    So if you get on this, please tell them to hire me!

  12. SatansBestBuddy says:

    Have we fallen into a time portal to back when Fuel was the tech topic of the hour and Shamus wrote about cool problem solving stuff instead of bitching about Fallout 3 for 30 minute intervals?

    Anyway, so far as I’m aware, procedural content isn’t widely used because it’s not widely shared; as useful as it is for saving devlopment time, it still takes a fair bit of time to create the program itself, and so far as I’m aware, games like Fuel and Dwarf Fortress don’t loan out their tech to anyone who wants to use it.

    Another point I’d like to make is that the worlds generated by this stuff would simply be too huge; I’m all for exploring vast worlds and all, but when you’re creating a game with a story and characters and an epic quest and all the sidequests besides, well, there’s gotta be an end at some point, and having a world so huge that driving across it takes hours (or however long it takes to get from one end to the other in Fuel, but I don’t think it’s a 20 minute round trip), then seriously, where does it end?

    I don’t think any sane person is gonna want to grind to level 2000 and beyond, most games cap out for a reason, because there’s simply nothing left to offer, and don’t get me wrong, the thought of playing a game so epic it’s literally the size of a small country, with thousands towns, NPC’s, quests, and dozens of endings, is something I really would like to play, but it takes serious talent and effort to craft a world that huge, and I don’t think many companies can pull it off.

    • 2tm says:

      or however long it takes to get from one end to the other in Fuel, but I don’t think it’s a 20 minute round trip

      The playable chunk of the game is about 75 miles square. There aren’t a whole lot of roads that go straight for any amount of time, and a number of the ones that do go diagonally through the game.

      There is a reasonably straight highway on the bottom of the game that goes about 60% of the way across east->west. If you were good at staying on the road, didn’t hit any trucks, took the fastest street car and didn’t look around for any scenery I suspect that you could traverse the map in about 40 minutes, maybe a little less. I don’t think that I could do it that quickly, because I tend to run off the road a bit when going over 115mph or so, and the good street cars are rubbish of road, but it’s possible.

      If you were taking country roads or off-roading it I suspect that you wouldn’t be able to do it in less than 2 hours, and that would assume that you stayed on task and were taking a direct route avoiding any of the bit impassible things like lakes, or that you were using the hover craft to cross the lakes (which gives you a nice, straight ride at nearly 80mph; if you cut through a big lake that way you might be able to do less than two hours).

      I have raced my brother from the clifs in Stargazers heights to the top of the little island in the big lake in Big Cauldron’s Edge, both of us with all the vehicles unlocked and no rules on what we were allowed to drive and clocked in at a little under an hour, maybe 45-50 min.

      A bit off topic, but Fuel is awesome.

      Have we fallen into a time portal to back when Fuel was the tech topic of the hour and Shamus wrote about cool problem solving stuff instead of bitching about Fallout 3 for 30 minute intervals?

      I actually started this comment to post about this, because I like our little time pocket we’ve run across. I miss when this blog was mostly about cool tech and problem solving stuff rather that all the fallout stuff and Lets Play’s. That’s not to say that I don’t think those are good, I do, but is to say that I thought all of the techy talk and problem solving stuff was another step up from those and is ALWAYS what I like the most about this blog.

      I started reading this blog during Procedural City and have greatly missed that type of stuff recently, though the discussions on Fuel and procedural generation have made me pretty happy and I do admit I have still read everything that’s gone up here anyway.

      Shamus,
      you mentioned sometime in the last month how time consuming things like the Fuel video was compared to your write-ups and let’s play stories, and I can’t fault you for that, I understand completely. I do want you to know though that I’ve always liked those and things like your procedural city far more than anything else you post or write on your blog or ever at the Escapist.

    • CrushU says:

      My good sir, welcome to Mount & Blade. (Go look it up on Steam.)

    • Nathan says:

      You don’t think people will want to grind to level 2000? You obviously are unfamiliar with Nippon Ichi Software and the Disgaea series. You can beat those games by getting to level 60 or so, but the level cap is 9999. People really do grind all the way up to that level. In fact, to totally optimize a character in Disgaea, you need to grind up to that high of a level seven or more times for each character, then dive multiple times through massive 100-floor randomly generated dungeons in order to steal ultimate weapons from level 9999 enemies. They start using scientific notation to describe the amount of damage you start doing at some point. They advertise this grindfest as a selling point of the game, using the word “grindfest” no less!

      Needless to say, the Disgaea series has quite the cult following.

      • Shoku says:

        Well yeah, but you’re gaining 50 levels off of killing one enemy by the time you’re several hundred up. The way it was phrased was the actual 2000 unique experience bars that you whittle away at for at least an hour but probably many.

  13. Duffy says:

    Any thoughts about using such a system for a fantasy based MMO? Several programming buddies and I have thrown the idea around (as we all suck at graphics) that it might be an “easier” route to create terrain for game worlds, assuming that aside from say NPC capital cities most the of the game world will contain random elements or just wilderness.

  14. Aisamanra says:

    If you want to look up more details on the specifics of exactly how this random multi-layer system is achieved, you’ll want to look up cellular automata and L-systems. They’re both deterministic mathematical systems that are used to generate complicated systems from very simple beginnings (and it’s pretty easy to extrapolate a non-deterministic system out of the deterministic ones.) Cellular automata are used in things like random maps for Roguelikes and L-systems are used as the basis for Subversion’s city generation, as inspired by Müller &al’s papers on the topic of city generation.

    I’d guess that even systems which aren’t consciously described in terms of L-systems or cellular automata could still be expressed in terms of them, or in terms of related concepts such as formal grammars.

  15. Bobknight says:

    Interesting read, I should like to see the results(if not the source) of this road generator of yours. have you tried to use it on a real topography and compare to actual roads built upon it?

    On janitors: wouldn’t it be much simpler(and more genuine) to just… place the objects by hand? I mean, if you have a predictable pattern to object placement, people will recognize it eventually. That would probably ruin the immersion a bit..

    • wtrmute says:

      Much simpler, if you need to place 100 janitors. But what if you need to place 1000? 10000? As for being “genuine”, I call shenanigans. If you find a dead janitor in real life, he’s not there because some one thought it would be a good place to put one, it’s because it’s where he happened to have a stroke or catch a stray bullet. Thus, placing janitors “randomly” (with due constraints on where they’re likely to be) is probably better than placing them by hand.

      Also, there is something to be said about predictability. After all, if you’re going to find a janitor somewhere, it’s better that it be somewhere you’d expect to find one — or could reasonably construct an explanation for why he’d end up there. That means that even hand-placed janitors will be in a “predictable” pattern. That’s just verisimilitude, though…

      • Roll-a-die says:

        Of course if you were placing that many you have to make it variable so that it didn’t eventually become repetitive, you have something like an array or sub-class, like

        PSEUDO CODE
        Janitor = TJB(normal janitor)

        array = TJVA (TJV1, TJV2, TJV3); parent = TJB;
        {
        TJV1 = Janitor-penis bottle ;
        {
        feature1 = bottle sticking neck down on top of janitor's groin;
        }
        TJV2 = Janitor screwing someone;
        {
        feature1 = booze bottles strewn about;
        feature2 = another corpse straddling janitor;
        variantfeature1 = second corpse straddling the back of non janitor corpse1;
        }
        TJV3 = janitor with stuffed animals;
        {
        feature1 = janitor encased in a mass of stuffed animals;
        }
        }
        if num TJB => 20{
        place TJV1
        }
        if num TJV1 => 20{
        place TJV2
        }
        if num TJV2 => 20{
        place TJV3
        }
        if num TJV3 => 20{
        seek (next feature)
        }

  16. Glazius says:

    Hmm.

    Here’s the thing.

    What is the procedural content going to support? I mean, finding a janitor with some bits of food and booze is an interesting world detail, and you can definitely put a bunch of “interesting world detail goes here” points into a procedural landscape.

    But how does the game interact with these interesting details? Or maybe a better question, how do you use a procedural engine to make a game where you could potentially find a keycard you need on the janitor’s body?

    • mewse says:

      The usual approach is to have a “Game Layout” system which is in charge of setting up the functional structure of the map. That is, where the walls are, where the player begins, where the player needs to get to, where the obstacles are, etc. This system usually runs first, and feeds its generated data through to the systems which build the renderable world geometry. (Alternately, it can run after the world geometry generation process, and instead feed its data through to a “blocker” system which would add walls or other structures to the world geometry, as necessary. Games which take place inside structures would generally have the “Game Layout” system run first, whereas games which take place outside would generally have the “Game Layout” system run after the broad world generation)

      Once world geometry and blockers have been set and the automatic object generation process has occurred (placing the Janitor and his mop and booze, for example), then control returns to the Game Layout system. For each locked door (or equivalent) that it has placed in the required player path, it finds an object placement in the game which the player can reach without passing that door (preferring placements at certain distance from the locked door — say, 100-200 meters away), and will randomly replace one object placement with its key object. In most games, you’ll have a few extra rules about which objects are legal for replacement (for example, key objects can’t be replaced. Objects inside locked containers can’t be replaced.. or if they can, then a key for the locked container has to be placed somewhere else, etc.)

      So if your game systems happened to procedurally place a janitor’s body in the right range from the locked door, any of the objects he’s carrying might be replaced by the key to the door. Or alternately it could be anywhere else that you can find an object.

      side note: replacing an existing object with a key is better than adding a key object for several reasons, but chiefly because it keeps the number of objects in the world the same, no matter how many locks there are in the game; you don’t wind up violating your engine’s “maximum renderable objects” allowances.

      The important thing to note is that this isn’t terribly unusual — there are plenty of games which work exactly this way (or at least, I’ve worked on a few). The difference is that most of them do this as an off-line process which takes a few days to run. We then bake the results into static mesh and object placements, and tweak from there by hand. That gives all the benefits — big procedurally generated world, but still with lots of human touches, and without roads that abruptly decide to run straight up cliffs (because we, as humans, can remove those roads before the end-users see them).

    • Shamus says:

      You’d mark certain furniture objects as containers. You’d also specify if a particular container should contain the following types of loot:

      * Useless trash
      * Common useful items (like ammo or potions or whatnot)
      * Rare items
      * Plot items

      You’d create a manifest for buildings:

      * This manifest only appears in such-and-such part of the world.
      * This manifest is only used on (say) office buildings and not houses, government, or industrial buildings
      * It contains 10 container objects, 4 of which are easy locks, 2 of which a hard locks, and 1 of which require the gold key.
      * This manifest contains between 1 and 4 rare loot items from loot table A3, 20 common items, and 75 bits of trash. It also contains one gold key.

      When a building is placed, the game will choose a manifest for it and use that to fill the place with loot and furniture.

      • Glazius says:

        Okay. I didn’t quite get the initial question out well enough.

        Fallout 3 had a plot, with notable locations and progression, in addition to a multitude of sidequests which may or may not be linked together.

        How do you create a world where a plot can happen and the events in the plot make sense? I mean, part of the fun of Dwarf Fortress is seeing the places and people it spits out, but how do you tell the difference between plot/setting details you have to account for in the procedural engine and plot/setting details you can pick out of or add into the results?

        Or more broadly, given how the layers of the engine are interrelated, how do you determine what elements of a game each layer of the engine is responsible for?

        • Will says:

          Whatever elements you want it to be responsible for.

          DF is an example of almost everything being procedural; the only things in DF that are not procedural are the world-gen settings and the creatures, although with the addition of templates many critters like foomen have become semi-procedural.

          But if you don’t want, say the quests to be procedural, you can just take them away from your generator and do them by hand, then the engine just pokes them in at the appropriate time instead of generating them procedurally.

          • Shoku says:

            You can have those special locations and things all the early posters seemed to think you can’t just by having layers above the topography.

            Yeah you can go landscape, cities, roads, people but the thing that’s bigger than all of that is the story with its twists and turns. Generating the whole thing is probably undesirable and I know I wouldn’t want to have to pass the Turing test from scratch but if you feed it the cliff notes sort of thing and probably insert most of the dialogue after everything else is set up you could easily have some engine say that the main characters attend a party, round up party members, meet various dudes, quarrel with each other and split up, and so on right up to where they finally toss the ring with a certain character into the volcano.

            Give it the vocabulary to produce a dark character who is having a pet the dog moment and in some later layer it can easily make sure to place a locale with a bunch of connotations that all make (enough) sense for the scene. You could easily get cliffs overlooking a grove or some catacomb with a fountain of blood and a jerk in it’s deepest chamber almost as soon as you give the system a dictionary/thesaurus.

            The time to iron it out becomes the only big deal but by just using particular seeds that skip merrily past the issues you could survive without.

            Now, what we’re used to seeing in these systems is real world simulation. You make a lot of open ended land and just place buildings where we’d actually place them and so forth but being quite astute you’ve no doubt realized this is a bad way to deal with something like a narrative. It’s looking at those other sorts of things we can generate where the process starts making sense.

            We’re all not the least bit surprized to see a maze generator and decades ago people easily built ones that even included series of locks and keys and one way doors and so forth. This is what we’re after.

            The easiest way to make sure all the keys are on the accessible sides of their doors is to start at the exit and place the door there then place the key somewhere in front. If you want to make sure it’s linear you stick another door between the key and entrance and so on but the doors can go anywhere so long as their key is on the first side of them.

            With a story you can do the same. You’ve got the beginning and end and you place a variety of locked doors in the way and throw the keys in appropriately. The pig-man in the pyramid gets taken down by silver arrows so the last lock is getting those arrows and getting inside. The lock to get in is that he breaks a hole in the roof after a fight in a tower. The tower needs seven crystals to open and the cyrstals need a mirror and sword and the sword needs three tokens and you’ve got to be shoved out of your peaceful little bed to start the journey.

            And you can have other layers that throw in converging story arcs where there’s room and then others that fill most of the rest of the place with sidequest things and finally the last recesses of the maze are just little things unlocked by the same set of keys those other layers have populated the maze with, but instead of getting rupees and heart pieces you find out something about the murder that takes the blame off of some character, or something that puts it right back on and makes clear his torment.

            You can feed the process the same thing about how a bunch of siblings go uncovering the web of intrigue behind some foul play in court but with different seeds have the guy who poisoned the king chased up a tower in one or confess while stuck in quicksand in another or even just be overheard while he talks about it to his secret lover.

            Rules for what language works and what doesn’t are of course a bit more elusive than how we place buildings in the gaps between roads and what I’ve described would take a myriad of connections that people may not even know a good way to instill into such a system as of yet but what we can certainly do is start on it. I’ve no doubt that a small vocabulary for proof of concept would easily be right up our alley.

  17. Susie Day says:

    “You can see this at work in FUEL. If you go out to the perfectly flat zone in the northeast you can see the roads basically form a grid.”

    You can see this in work in real life too – go to Iowa and look at their road structure…

    Anyway, I don’t see why this couldn’t be applied to the “zombie janitor” as well .. Why not let it generate lots of different varieties of the same prop (kinda like the gravatars) so that you aren’t running into the same exact piece of furniture all the time?

    • Shamus says:

      Because each “generator” will require a certain investment of code. You want to only make them for things you’ll be doing often. The dead janitor in question was supposed to be this special rare set piece. If we’re just talking about dead guys laying around, then it might make sense.

      The idea is that PG is more of a cost up front, but reaches a break even point once it generates enough content for you to justify the cost of building it.

      • Daemian Lucifer says:

        Well there are tons of bodies in fallout,so you could make them procedurally,and then just change a few parameters.Clothes,items they are holding,limbs missing,etc.

      • Paul Batteiger says:

        I think many people are missing the idea that procedural generation is the future of gaming. Companies constantly argue that games cost $XX amount to build, and that this is causing games to take longer, cost more, and come out shorter and more linear. We will reach a point where the technology is at a level where designing a full world in the traditional, ground-up manner is not cost effective. I think the answer to this is procedural generation, but the next logical step from that is not so much designing a game as teaching the game to design itself. This is really where we are headed. We are talking so far beyond Diablo it’s hardly worth the comparison. If you give a program the ability to design the game as it goes along, with enough ability and capacity to do it well, then you have a game that can be as big as you want. Then you would have a game that could tailor itself, on the fly, to suit the individual player without any input from a designer at all. That is where procedural content leads you.

        • Will says:

          We hit that point ages ago: Why do you think AAA games tend to have such small game worlds, with the occasional exception like Just Cause and soforth.

          The real moneymaker would be procedural graphics; teach the game to design it’s own graphics. Since graphics are where the big bottleneck is at the moment. Unfortunately we’re a way off that yet.

          • Daemian Lucifer says:

            F.e.a.r. gives me hope about this.Ai is not something developers are usually focusing on,yet theres a game with ai at least a decade in front of its competitors.So it is possible to build something advanced basically from scratch.

            Sadly,f.e.a.r. was lacking in everything else,so the most we can hope for is something similar to far cry with procedural graphics(meaning its just a game made to show off new fancy graphics).

  18. Daemian Lucifer says:

    Why do people equate procedural with random?If you make the equations without a single random component,youll get the exact same thing with the same starting values.Unless some cards draw things differently,that is.

    Also,procedural graphics requires less memory than predrawn one.You dont need to store every single object in the memory,you have to store just the one template,and then drop it around as needed.The more objects there are,the less memory used.Which is especially nifty if you do enter some random component in the template,because every new object will be different,but for the same resource cost.

    The problem is writing it so that the computer will always draw a believable object.Human artists can always see if something is wrong while they are drawing it,and correct it.But if something is wrong when the computer generates it,it can easily slip undetected.

    Though,I guess if we were to focus on this method as much as on other forms of manual modeling,in some 5-10 years time,it would be a piece of cake to make fallout 3 with just procedural graphics.

    • Valaqil says:

      I think that the issue stems from equating ‘unknown’ with ‘random’. We don’t know where the janitor, for instance, will be placed. So we call it ‘random’. It doesn’t have to be random, and, as someone notes above, even _with_ a RNG, the placement could remain constant if the seed doesn’t change. But people just aren’t making the distinction.

    • FacelessJ says:

      Also,procedural graphics requires less memory than predrawn one.You dont need to store every single object in the memory,you have to store just the one template,and then drop it around as needed.

      Sorry to burst your bubble, but that’s how game devs normally do it anyway. You have some form of resource manager, that holds a copy of all the resources you need (Textures, models, etc). The in game objects then have a reference id, which they pass to the resource manager, to get access to the resource.

      For instance, the player draw call could be something like:

      void Player::render()
      {
      Texture * playerTexture = ResourceManager::instance()->getTexture(playerTextureId);
      Renderer::Instance()->drawTexture(playerTexture);
      }

      So, the actual texture data is only ever stored once, and is passed around by reference.

      You are right in the fact it will use less memory, but only because you’re storing the algorithm only instead of the picture. However, to achieve this, every time you want to use the picture, you have to generate it from the algorithm (Using more CPU cycles). So, you’d be better off generating it once, and storing the image in ram anyway. The space saving comes from the hard drive, where you write the algorithm down, instead of the image.

  19. Daf says:

    “However, the system would occasionally encounter topography that was not solvable with the given rules, and the result usually looked hilariously bad.”
    No doubling back with hair-pin turns to get up/down a mountainside, then? :(

    • Shamus says:

      Oh, it does this. But hairpin turns can only climb so much so fast. The hairpin itself is actually where things tend to go wrong.

      • Stringycustard says:

        It think this is when you get to the point of cutting tunnels into hills or alternatively just shifting out huge chunks of the hill. That’s what ends up happening in the real world, but slicing geometry in an engine is obviously a far more complex scenario. Even simple geometry slicing ends up being overly complex.

        I’ve always wished there was a nice simple way of doing things like masking stuff in 3D so that it adds planes to the cut content (thus finishing it off instead of having 2 unattached sides of an object visible when that object has a thickness – currently each “cut” has to be a separate 3D entity). I’m forever doing masking in 2D but naturally that 3rd dimension completely alters how one has to approach the problem.

        • Shamus says:

          You’re right. Also, a proper engineer would start attempting to navigate around the mountain before they got too close. My system was simply reactive, and by the time it was at the foot of the mountain it was already too late to plot an intelligent solution.

          Deciding when to build bridges, when to go down into a valley, and when to circumnavigate is another case that requires planning ahead and careful analysis.

          FUEL actually has handmade bridges that perfectly fit the required span and connect to the procedurally generated roads. I’m kind of curious how they handled these cases. My guess is that the generator simply give up when it hit a canyon, jumped to the other side and began laying down road, and output a note for the artists, “At coords x,y I left a mess. You might want to have a look at that and stick a bridge in there if you get a moment.”

          • Will says:

            A proper engineer would size up the hill and determine if he needs to go through it or not before the road is even built.

            Actually it shouldn’t be too hard to have the game plan out the roads before actually making them and thus using the information to determine where it needs bridges or tunnels.

            • Shamus says:

              “Actually it shouldn’t be too hard to[…]”

              Clearly you work in management. :)

              I found that the “planning ahead” code was significantly more complex than the reactive code, since it needs to be able to look at large areas at once. Actually, it might need to quad tree the world looking for trouble spots ahead, since the size of the mountain also determines how far away you need to begin routing around it. For a massive mountain, you’d need to start miles before things got steep.

              • Will says:

                The planning ahead code should be the same as the normal roadmapping code; it just doesn’t actually -make- the roads. It plots out all the roads and then looks for areas that are beyond certain tolerances, which you’d probably need to hand set, in those areas it draws a straight line between where it is and where it wants to go and if the ground is too high it punches through it, too low it bridges over it.

                Ovbiously it still wouldn’t be perfect, but it would be a step in the right direction.

                Ideally what you’d probably want to do is have it plot thousands of possible roads from point A to point B and compare them all to each other, then plot an ‘impossible’ road to determine straight line distance and decide if it’s worth tunneling\bridging or not. It should even be possible to get it to do an evaluation of the elevation values and mark appropriately ‘major’ landmarks like large mountain ranges and chasms as a single object.

                If you’re trying to get it to actually plan as intelligently as a human, yeah it’s not going to work, but it really shouldn’t be that much harder to get it to add tunnels and bridges to it’s dumb computer planning.

  20. Joe says:

    I think actually the way you talked about it in this post (http://www.shamusyoung.com/twentysidedtale/?p=542) makes more sense. Read down a bit, and you (that is to say Shamus) mention how you could make the outdoor world procedurally, then letting the artists loose to clear and place cities. This doesn’t have the advantages for the user’s system, but as far as cost-cutting and whatnot, it works brilliantly. It also means that you’re far less likely to run into what-in-the-name-of-all-that-is-bright-and-good-was-this-person-thinking bits of terrain, like with your “hilariously bad” roadway problem.
    It also makes it easier to talk about the game. Something like fallout gets most of it’s word of mouth around from the moments inside, like the dead janitor, or the rad shelter with the wine and destroyed manikin. Placing these procedurally means that they might not show up as well, and almost never in the same spot. Meaning that your buddy can’t show you where it is. Also, as somebody pointed out earlier, there needs to be rhyme and reason to these locations. His story doesn’t make as much sense, for instance, if you see him in the middle of a house, or wandering the wasteland. I’m not saying procedural content couldn’t do this, I’m just saying that it’d be harder than just setting the world procedurally.

    • Glazius says:

      You’re confusing procedural creation with procedural generation.

      What’s the difference? I’ll start by saying this: when your computer generates random numbers it doesn’t use thermal noise or anything genuinely random; it uses a sequence generated by an algorithm sufficiently complex that a human can’t detect any patterns in it. So even if something is procedurally generated, as long as the algorithm is fed the same inputs it will produce the same outputs.

      But procedural creation has extra steps not present in procedural generation: evaluation and pruning. Let’s say that you’re creating a Final Fantasy-type game with a procedural world generator that you’ve modeled to include the generation and spread of elemental taint, in addition to cities and civilizations. What do you need for Final Fantasy? Four elementally-tainted areas – one each of earth, fire, air, and water – with a surviving town somewhere nearby, a starting area and town that aren’t elementally tainted at all, and a ring of untainted mountains or islands from which the final dungeon will emerge.

      You don’t need to include those in the procedural world generator – you can just run the world generator, again and again, until it creates those features, at which point you look at the seed from the successful run and save it. You don’t even have to look at the output yourself — you can write a program to examine it and rerun the generator until it’s made something satisfactory.

      Even if the game procedurally renders the terrain, it always starts with the same seed and everyone’s system renders it identically, with the same landmarks and the same cities in the same places. The systems don’t have to go through the process of screening the result and re-randomizing if it isn’t satisfactory — that was all done on the developer’s end.

  21. Will says:

    “Note that the roads in FUEL had the added challenge of needing to intersect with one another at reasonable angles, which was something I never attempted.”

    Not neccessarily true Shamus. Having seen some of the intersections that exist in real life, roads absolutely do not need to intersect at even remotely reasonable or sensible angles. And if the intersection gets really out of hand you just put a roundabout in it.

    In preplanned cities, the roads make sense, you can see that in alot of recent cities that were deliberately planned and built as cities where the roads will usually be straight, flat and clean. But in older cities, especially european and chinese cities, the roads go all over the goddamn place, because the roads grew out from paths, which grew out from trails, and often they just don’t make any sense, at all, ever.

    I would actually find utterly nonsensical intersections that make me pull up to them and spend 5 minutes trying to work out how the hell you’re supposed to navigate through this abomination more realistic than having no nonsensical intersections, mostly because i have in fact encountered intersections in real life where i did exactly that.

      • krellen says:

        We don’t have many roundabouts in these parts, so I have to ask: How are you supposed to navigate that?

        • Raygereio says:

          At high speeds.
          It can get more stupid then that:
          http://www.rijnvos.nl/foto/keizerkarel.jpg
          That’s a semi-infamous roundabout in the Netherlands. It has 4 lanes and 7 busy roads leading to it. The fun part: all the traffic lights leading to it turn green at the same moment.
          If you find yourself in the inner lane during rush hours, you’re pretty much stuck there for the next hour or so unless someone takes pity on you.

        • Xavin says:

          The short answer is: by driving on the left side of the road; orbiting the roundabouts in a clockwise direction; and ,when joining a roundabout, giving way to traffic already on it.

          More helpfully (this description works best with the first image):
          To begin with, just imagine that it’s an ordinary roundabout – remove the mini-roundabouts (the smaller white circles) and the 5 bits of irregularly shaped islands between them, but keep the central circular island.
          Now imagine that you are approaching from the road in the top right, and want to exit along the one on the lower left side. You give way to traffic already on the roundabout (approaching from the right from the driver’s point of view, crossing left to right as we view it in the photo). Enter the roundabout when safe to do so, orbiting in a clockwise direction as viewed from above (i.e. initially swinging left from the driver’s point of view). Pass the first (middle right as viewed in the photo) and second (bottom, as viewed in the photo) exits. Signal left and take the third exit.

          OK – so that’s how a normal roundabout works. Now, add the mini roundabouts and islands back in and what you create is effectively a very small circle of 2-way road with 5 roundabout junctions on it. The outer lanes of the circle move clockwise, the inner lanes move anticlockwise. Each of the 5 roundabouts operate on the same principle as the larger one we just imagined.

          You can still perform essentially the same manoeuvre as described above, except that you now negotiate 4 small roundabouts instead of 1 big one – you take the 1st exit at the first roundabout, 2nd exit at the second and third roundabouts, and finally the 1st exit at the fourth roundabout.

          However, you now also have the alternative of going the other way around the central island – take the 2nd exit at the first roundabout (moving right to left across the photo, above the central island), 1st exit at the second roundabout (turning left to move down the photo to the left of the central island), then lastly take the 2nd exit at the third roundabout (turning right, to move right to left on the photo).

          The (supposed) advantage of this comes when the exit road you want is closer in an anti-clockwise direction around the central island to the entry road than in a clockwise direction (e.g. if you approach from the middle right road in the photo but want to leave by the top right your route is shorter this way).
          Sometimes it’s successful in practice, but often it just confuses people. There are quite a few of them around though – the one pictured is in Swindon and I didn’t know about that one, but I can think of at least 3 relatively local to me.

          Then there’s the interesting junction design not 4 miles from my house – point Google Earth (or your preferred alternative) at 51°29’51″N 0°27’11″W to see what I mean (and bear in mind that if you’ve just flown into Heathrow and picked up your hire car then this could be one of the first UK road junctions that you encounter)

    • Ian says:

      It’s not just about insane connections. It’s making the textures line up nicely too.

      • Will says:

        In the case of a road that shouldn’t be too difficult; you’d need a way to draw the lines procedurally as well, but if you’re designing procedural roads too it shouldn’t be much more to make the lines procedural as well.

  22. GTRichey says:

    Having a procedurally created world doesn’t necessitate that the entire game be so. The way I understand it you could create the “open world” this way and still place major areas yourself. This would be good for open world RPGs like Oblivion or Fallout where you want to have largely empty spaces in between major cities. You could place minor areas in this fashion as well. In this way you could create a much larger game world using less disc space, leaving space for more vital areas so that your world doesn’t feel completely empty. You could potentially even create a world with varied climate, flora and fauna simply by using slightly different algorithms for different areas of your world.

  23. Bobknight says:

    I think it defeats the purpose of the generator when the janitor would have a keycard on him to open a door. That lies within the realm of world design, not world generation.

  24. Nathan says:

    While procedural content certainly is a major part of the modern games industry, and will undoubtably become a bigger part of it in the future, it really isn’t the magic bullet solution that a lot of people here are advocating. Game companies are not avoiding wholesale adoption of the technology because they are foolish, they are avoiding it because it isn’t really workable (at least not yet).

    For one thing, it should be noted that creating a large procedurally-generated virtual world for a game is a lot more complex of a task than creating a big fancy 3D model of a world. For example, Shamus’s city-generation program is rather interesting at creating rows of skyscrapers, but it would probably be totally unfeasible to use it for even a simple game, for all manner of reasons such as AI-pathing, collision detection, etc. The program has to do far more than just generate art assets, it has to generate a great many other things in order to allow for a functioning program. It doesn’t help the game if you auto-generate a beautiful road which is filled with invisible holes the player will fall through or random spots of grass that act like trampolines. Of course, this is a solvable issue, but it does mean that the game industry has to do more work to implement this technology than many other industries.

    Also, any arguments that procedural techniques save disk space are misguided. Procdurally generated content can save disk space, but it does so at the expense of computer processing power, and computer processing power is far, far more valuable and important than hard disk space. FUEL shows that it is possible, and potentially valuable, but I am certain that the game designers had to make some pretty big tradeoffs with other parts of the game in order to achieve their goals.

    And of course, one really big issue with procedurally generated content is that the amount of work it can save is limited. You can’t just magically click a button and get a forest. I’m no expert on the program, but I think the SpeedTree program requires upwards of two dozen different adjustable parameters and at least five seed values to be input by the artist in order to create a single tree, and simply randomizing or automating that process would create far more undesirable results than is practical. Creating anything significantly more complicated than a tree (like the main character of a game) with procedural generation would probably be significantly harder than old-fashioned methods. Sure, you can theoretically just keep feeding random values into a procedural world generation system until you get the world you want, but it is probably just faster to just design the world and then use procedural generation to fill in the details.

    So, the technology has promise, but I don’t think we are at (or ever really will be at) the point where you can automate world creation to any significant degree. And I never want to see a world where quests and player goals are randomly generated (they can get boring enough as it is)!

    • Duffy says:

      I think you are underestimating and focusing too much on random, procedural =/= random.

      The advantage of procedural graphic generation are generally:
      1. Ease of Use – Once the engine has been setup you only need an artist to add new algorithms/textures once and awhile instead of constantly crafting each model.

      2. Disk footprint – Obviously decreasing the required file size is considered an advantage, but has the trade off you mentioned of costing more CPU. A compromise is probably the best choice: certain key models/textures are stored locally in their entirety while others are generated based on the engine.

      3. Re-usability – a well built engine can be used for multiple games with little to no extra assets required, it can generate a racing game’s track as easily as a fantasy kingdom, just change some settings. Practical application would probably require additional models and textures to meet our above compromise, but the world generation would require little tweaking to the engine.

      And yes, you can click a button and get a forest, it depends how much control you want. You could specify nothing and get trees that vary wildly (Giant oaks and Palm Trees next to each other) or you could tell it to use the numbers that will only generate Northern European Forests. Either way you aren’t doing it by hand.

      The biggest hurdle of course is creating this engine in the first place. Graphic engines, regardless of type, are big time and money investments. In the video games business what are you going to do? Buy the latest Unreal engine or take a gamble on creating your own? Use what you know or use what could be better with time? It might not be procedural engine’s time yet, but it certainly might be the future.

      • Nathan says:

        I really don’t think I mentioned much about the randomness. I think you may be using that as a counter-argument against criticism far too much.

        You sound like you are trying to teach me something about procedural generation, but I don’t think you are addressing the limitations I brought up very well at all.

        Also, I will disagree with you that re-usability is a feature of procedurally generated content. Sure, you might be able to create an art program to create both urban and fantastic environments (though I doubt it, since the task of creating a modern city is a very different task than creating a floating sky castle), but that is a very different thing than creating a general game engine capable of running wildly different genres of games. A linear RPG where you never interact with the terrain would have very different needs out of a procedural content engine than an inFamous-style open world where you can climb every telephone pole. A game which needs to create 12,000,000+ procedurally generated dungeons for the player like the .hack//G.U. games has very different needs than a game which needs a single static world. You practically would have to build an engine for each game if you want to use procedural generation for anything past asset-creation middleware like SpeedTree.

  25. Steve C says:

    So, the technology has promise, but I don’t think we are at (or ever really will be at) the point where you can automate world creation to any significant degree.

    I disagree. I think this is the technology of the future. The sort of stuff that will do wondrous things not only for game design but for humanity as a whole.

    The trick is combining procedurally generated content with evolutionary automated design. What is evolutionary automated design? It’s where you use biologically inspired evolutionary computational techniques to design and optimize complex systems. The easiest way to explain it is that you take random things and then compete them against each other. Best one wins. Rinse and repeat x 10^n where n= a large number.

    This is already being done with real world applications. For example NASA spacecraft power systems. Excerpt:

    The results are competed and selected down to a smaller sub-set of parents that provide the basis (using genetic operators of mutation and genecross-over) for the design parameters of the next generation. Given a large enough population, sufficient generations and the right conditions for evolution, we have demonstrated the feasibility of automatically optimizing simulated design.

    In the case of a video game you wouldn’t just create a tree. You would use a procedural tree generator tree program that had been competed against other procedural tree generator programs to create trees. Competition would occur probably by automatically comparing program output to pictures of real trees. It would do this again and again until you had an extremely robust tool that always produced a great looking tree. The procedural program with the best results wouldn’t need 2 dozen adjustments or 5 seed values. The game designer would just click the “create a forest” button and presto… a great looking forest.

    Another way of looking at is to feed random values into a procedural world generation system AND have the output automatically compared to Fallout 3. Do that 100 times. Take the top 10 of those and input new random data. Compare the result to Fallout 3. Take the best ones and repeat enough times and you’ll end up with a world that looks a hell of a lot like Fallout 3 but can be the size of FUEL.

    Procedural generated content has far more potential. The trick is getting it whipped into a finely honed tool via CAutoD. The process of making those really good tools is already happening now. But it should be happening in the game industry more just because of how well evolutionary design and procedurally generated content synergizes.

    • Nathan says:

      You know, I think you are beginning to wander into territory that really is totally unfeasible for game design.

      First off, you say that technology might be created that allows you to just click one button and get a great looking forest, but that is something that wouldn’t help game design at all. SpeedTree doesn’t require all kinds of inoputs because it is a bad program, it requires all kinds of inputs because it is a necessary step in allowing the game artist to get the kind of tree that is needed for the game. These inputs determine fairly important things like “how tall is the tree?”, “is it a flowering plant or a confier?”, “do the branches spread out or all droop towards the ground?”, “does the trunk go up straight or branch?”, and other such things. There is no one-size-fits-all tree design, since individual trees need to fit the particular environment they will be placed in and the mood the game is going for. Trees lining the city streets in a beautiful castle town can’t look just like the trees in the creepy haunted graveyard.

      Also, the techniques of evolutionary design may be useful for all kinds of purposes, but it will certainly have its limitations. You can’t possibly expect a computer to understand and manage reasonable expectations of abstract, non-numeric idea like how fun something is or how well one character model fits into the overall aesthetics of a game world. You can only get that kind of analysis with a human perspective, so it would be impossible to run the 10^n permutations needed to get that kind of model to work in any feasible amount of time. It may be great for engineering and mathematic problems where something approaching a single ideal solution exists, but game design is a very, very different beast than that.

      • Steve C says:

        There is no one-size-fits-all tree design, since individual trees need to fit the particular environment they will be placed in and the mood the game is going for.

        I think you misunderstand how procedural generation would make terrain. You are thinking too micro and not macro enough. And someone else said it well in a reply to you:

        The advantage of procedural graphic generation are generally:
        1. Ease of Use – Once the engine has been setup you only need an artist to add new algorithms/textures once and awhile instead of constantly crafting each model.

        Procedural generation is so you DON’T have to craft each model. You wouldn’t be making one-tree-fits-all. Or even one-forest-fits-all. You would be making a mathematical model that automatically creates a tree appropriate to the terrain and the art style of the game. You don’t pick a “graveyard tree” you probably don’t even pick the graveyard. The graveyard is something that was procedurally generated because there was a church. The church determines there’s a graveyard. The graveyard determines that there is soil suitable for trees. The type of tree is determined by the type of church and the type of graveyard.

        None of those elements were determined by a human being. In the same way that a grid road system is the natural result of a flat landscape, or that on/off ramps automatically occur for freeways in FUEL, so will be the kind of tree suitable to the terrain.

        If the procedural generated system is working correctly then humans are only involved in 1) game design (inserting the fun and style) 2) important set locations, 3) squashing bugs (finding and fixing where the model screwed up like the hairpin turns and bridges above)

        • Nathan says:

          I am beginning to think we are talking past each other a little. Maybe I should step back and actually say something that has been sitting at the back of my mind…

          The kind of macro level creation you are talking about is itself the problem. You say that the graveyard would be auto-generated with the church, and that the game designers just need to sit back and watch their world get created for them, but that is not a reasonably useful system for creating a game world. You don’t add the game into the world once you have a world, you create a world so that its every detail matches the needs of the game design. Many aspects of how you imagine that graveyard being designed are far from ideal for a game developer. Graveyards don’t need to have appropriate trees for appropriate soil. Graveyards don’t need to be built next to a church and be appropriately sized for the needs of a local community in a deterministic manner. Graveyards need to exist solely for the purpose of being spooky places for the hero to fight ghosts and zombies. The graveyard only needs to exist (indeed, only should exist), if the game designers specifically created it to fulfill a particular role in the game.

          Creating a large world according to a massively complicated procedural system like you are describing is an interesting achievement, certainly, but it is not something that is actually useful for many games. In many ways, I imagine that such a totally procedurally generated game would be a pure “programmer’s game”. It would certainly attract the attention of various programmers who would all applaud its technical marvel, but it would probably flop as a game.

          Generally, the simple truth is that simulation is a game design trap. Creating the perfect simulation of something is a far cry from making a widely enjoyable game. Just because a game world is realistic does not mean it is good or fun. It may be possible for procedural generation to create a large and varied world, but so far and for the foreseeable future it is simply not possible for the kind of marco-scale procedural generation you have been talking about to create a world that is as fun and interesting as a hand-crafted world.

          I really am not sure if I cam getting my sentiments across correctly. Sorry about that… Ii is just that the way you describe this technology it sounds more like a giant “create a world” simulation than a useful tool for creating the kind of content game designers actually want to create, and that rubs me the wrong way.

          • Kell says:

            I think you are getting your sentiments across; at least, I follow what you mean and I agree – you don’t just put a graveyard in your game because someone decided the procedural algorithm should simulate that. You put stuff in a game because you believe it will be fun.

            However I think you’re also misunderstanding because you percieve procedural generation as being an attempt at simulation. Of course games are not simulators, simulators are not games, and anyone who doesn’t understand the difference has no business making either.
            But if your game is an open-world zombie apocalypse shooter ( like Left 4 Dead on a big terrain map ) you might want multiple graveyards scattered around the landscape, so the hero will encounter them in an appropriate way, at appropriate intervals. You might want them to vary in size, within appropriate limits. You might want some graveyards to contain more zombies than others, within appropriate limits. And by “appropriate” I mean “fun and believable in the context of the game”. Procedural generation is ideal for this.

            Really, check out FUEL. Or L4D; you do know the zombies in that game are procedurally placed, right?

            • Nathan says:

              I think I am getting you a little better, then.

              I guess all I can say is that I don’t really think that the technology will ever be able to get past the point where you need top adjust a few dozen options and who knows how many seed values in order to get the actual resources and assets that you want. I have never once denied that it is an important and valuable technology (after all, who wants to spend years designing a single great-looking tree, and it is really the only way to create huge amounts of content for something like an EVE Online-style MMO), but I just don’t ever see it being any more than one tool among many in the game designer/artists toolbelt.

              Mostly, I just don’t like seeing some of the people on this thread insulting all the people in the game industry as being closeminded and foolish for not adopting procedural generation technology, even though the industry has already done so to the greatest extent such technology is actually feasible at its present level of development.

              Also, I didn’t know that about Left 4 Dead. I haven’t played the game myself, though. As much as I am a fan of great co-op gameplay, I’m far from being a big fan of zombie stuff… I suppose the same could be said for racing games like FUEL.

              • Shoku says:

                L4D spawns the typical sort of fairly mobile zombies in positions that don’t seem wrong at all but went further by judging how the team was doing and things like how tense they should be from the pacing and throws less stuff at them for awhile.

                It got a little weird with how it could spawn things in places so long as you couldn’t see them but the little dead end bathrooms and things were used sparringly and you’d only rarely see some big fatty waltz out after you’d looked in that room already.

                And they did some other pacing control things.

            • Shoku says:

              If you can tell another person in what ways your gameworld should deviate from reality it should also be possible to tell a simulator how to do it too.

              We usually base the framework of a game in reality because we have so much vocabulary and knowledge about it that it conveys a lot of information simply. Sure you could make a number increaser game where the player chooses interest generators with a long list of bonusses and penalties during different phases and all those long tables of information for how it works could be in the manual, but you hardly need to explain anything at all if you instead have the player planting crops as the seasons change.

              Likewise a graveyard means there are bodies in the ground and we expect those bodies to more or less have a believable source available. If a player has an actual reason to go there you can have some layer generate the thing but if the player doesn’t you could perhaps have one slowly scrolling by in the background as he travels along so street, especially if overlooking a graveyard matches the tone that particular stretch should have. If it doesn’t you could put it further away or not have it at all, and a sufficient engine could deal with all of those possibilities.

              Though this literary element is probably not something we’re going to see before people can push the simulation angle quite a bit further.

  26. Kdansky says:

    I completely forgot to mention this until now, but it will probably be of quite some interest to you. There is a Swiss company called Procedural (.com) and they do exactly that. I urge you do play around with their city software and post pretty pictures and some text about it. They’ll probably read the review with interest.

  27. Neko says:

    What I’m interested in is, how do you make a road-layout algorithm or a city-generating algorithm which can also work on discrete patches of land? If you use procedural algorithms to generate a huge world, that’s great, but to actually explore that huge world in a game you need to ‘load’ (read:generate) patches of it bit by bit. And if you do that, how do you ensure the road leaving the north end of patch (10,10) lines up with the part that enters the south end of patch (10,11)?

    • Will says:

      See the previous comments about procedural not meaning random.

      • Dan Efran says:

        No, that’s a good question: if you want to regenerate the world one patch at a time, directly from the procedural algorithm(s) and seed(s), what are good ways to ensure continuity between the independently regenerated patches, without having to explicitly drill down to them from a wider-scale (e.g. global) generation algorithm. (It may be easier to visualize the analogous problem in procedurally generated graphics textures: making them tile seamlessly while maintaining the (procedural) look you want throughout.)

        • Shoku says:

          Or just ignore hard drive space because you just needed to fit the tool onto a disk before it generates any of this. I see no problem generating one patch and the slicing it up and throwing that into memory (or whichever order.)

  28. Niriel says:

    I think that the procedural generation need not be limited to the geography. The scenario itself can be procedurally generated. At its simplest form you get a random quest generator like the one featured in Daggerfall: trying to make the scenario fit into the pregenerated landscape. But we can go the other way around: create the scenario first, and then make the world fit into it. I haven’t seen anything like that yet, but it does not have to be that hard. Many games are all bout blocking your progress until you have the right object/skill or have done the right thing. The scenario looks like a tree, more or less linear: find objects in a node to unlock branches. It should be possible to spread that tree on a plane and grow a world from it.

    • Daemian Lucifer says:

      Isnt that something like diablo?You have this item to find,or this monster to kill,and then there is this huge random dungeon built around it.

      • Shoku says:

        Well no. Diablo could do something like place the hammerer before the soul forge but it had that particular area before Diablo’s cathedral in a very static way that people had made.

        Really what diablo did was take a big library of tiles and join them together with matching ends while making sure not to overlap anything so you got these winding paths that lead up to this thing or that.

        It’s really no landscape at all and in order to avoid the path looping back on itself they sent you through caves where you could pop out in an entirely disconnected part of the world. They wiped the slate clean rather than actually make a world with actual places for things.

        Something like Zelda or Chrono Trigger where the paths constantly cross back over each other could never get away with this.

  29. Phoenix says:

    It was mentioned above, but maybe there are people who don’t know it:

    http://www.theprodukkt.com/kkrieger

    A completely procedurally created FPS (guns, textures, level, everything), overall download size 96K, flashy graphics, and a good example to show that procedural content isn’t random at all if you don’t want it to be random.

    Have fun ;)

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!