Project Frontier #2: Paging Data

By Shamus Posted Wednesday Jun 8, 2011

Filed under: Programming 81 comments

Coming up with rules and systems and algorithms to generate content is hard enough, but added to that challenge is the fact that we don’t have the benefit of any sort of pre-processing. If you’ve ever used a level editor, you know those things can eat a ton of time. They can take the data, cull out what isn’t needed, pre-compute the expensive stuff, and package things in a nice, organized way so that when the game is running, it can pull data off the disk and put it right to work.

With procedural stuff, you’ve got to do that work while the game is running. Without slowing things down. This moves all of that complexity into the game, and makes the system more complicated by requiring that it be done piecemeal. If you’ve played Minecraft, you’ve probably noticed the heavy lurch you get when the game has to generate some new landscape for you. I’m going to face that same problem with this project.

But I’m getting ahead of myself. First, a bit about how my program creates the terrain. First, it takes that low-level topography I generated in the previous step:

frontier2_3.jpg

Very bland, of course. We don’t want to generate an entire continent of endless speed bumps, so we also have some topographical data stretched out over a much larger scale:

frontier2_4.jpg

Note how this looks kind of mechanical. You can see large, flat surfaces everywhere. By itself, this would make the continent feel sort of like the whole world was made from geometric primitives. But if we combine the two data sets:

frontier2_5.jpg

I’ve exaggerated the hills for effect. The large hills give the world shape, the small ones give it detail. Together they make something roughly presentable. From now on, I’ll be calling these two sets the “topography” and the “detail”.

How it works is this:

The world is divided into regions. Some regions will have strong topography, normal detail. Others will have muted topography, but strong detail. I can exaggerate one data set over the other to create different landscapes. (Low rolling hills, flat deserts, spiky mountains.) Each region also has an overall height bias, so that I can shove some of them into the sea and lift others up. Right now the regions are hard-coded, but eventually I’ll have some sort of logic to generate them as well. Eventually, regions will also have different coloring.

As you move around the world, it generates this landscape. Some logic goes into figuring out what the surfaces should be. Flat spots should be grassy. Hilly spots should be dirt. Steep bits should be rock. Stuff touching the water should be sand. These sections of terrain are generated in pages. Eventually, they’ll be saved to disk once they’re generated, in much the same way that Minecraft does.

Then it comes time to turn this data into actual polygons for rendering.

Currently, the program will just add more terrain as you run along, forever. Well, not forever. But it will happily churn them out until you run out of memory. It doesn’t clean out data yet, so once something is in memory, it stays there. Josh joked that it’s now officially a game. “See how far you get before it crashes. You want to play on easy mode? Buy more memory.”

Running out of memory is kind of abrupt. The program runs fine until the moment I have too much texture data, at which point the framerate drops from 90, to 5. I pushed it once and nearly brought down my machine. It took a loooong time to bring up the task manager and kill the program.

Still, that means I got the high score!

frontier2_6.jpg

Yes, I am aware that it looks horrible and bland. Next time we’ll liven it up with proper variety. And maybe look into fixing that memory hoarding problem.

 


From The Archives:
 

81 thoughts on “Project Frontier #2: Paging Data

  1. S. Richmond says:

    Looks good. Question is – Do you plan to make this terrain modifiable in real-time?

    1. MrWhales says:

      You mean, to add more to the Minecraft comparisons?

      1. psivamp says:

        Actually, with realistic terrain, should we be drawing parallels to From Dust instead?

      2. Drexer says:

        I have yet to understand why so many people jumped directly to the minecraft comparison in the last post. Is the concept of a generating world that alien to most people that they can only identify it with minecraft?

        1. psivamp says:

          I think it’s just the highest profile thing right now with procedurally generated worlds.

          1. Jeff says:

            I actually thought of .kkrieger initially, when Shamus mentioned FPS.

            1. GM says:

              I played a bit Kkrieger but did not get far.

            2. psivamp says:

              I thought of .kkrieger recently, and I can’t for the life of me remember why… And, now, .kkrieger brings up Krieger from Archer in my mind…

              1. psivamp says:

                So, you didn’t make a virtual anime wife so realistic that the state of New York is going to allow you to legally marry it? And, also probably not one of the boys from Brazil?

  2. Daemian Lucifer says:

    Ah,endless data.Reminds me of that one mod for empire earth that allows for unlimited units,and your goal becomes to crush the ai before he crashes your computer.Good times.

    1. Alexander The 1st says:

      Huh – instead of installing the 3 laws of Robotics into our AI, perhaps we should remove their memory management – make them dependent on humans removing memory for them.

      “Oh No! Our centralised AI is trying to take over the Nuclear system!”

      “Quick! Open up 80 Bit torrent downloads, turn on Fallout: New Vegas, Minecraft, and Dragon Age: Origins! On MAX SETTINGS!”

      1. Fists says:

        you’re a genius, just get bethesda to write a simple program that makes coffee or something and link it to an ’emergency override’ switch, turn that sucker on and the memory leak will deal with the robot uprising.

  3. Nevermind says:

    You ARE aware of fractal noise functions, right? Because what you describe seems like ghetto version of fractal noise to me. Or is it just simplification on your part?

    1. Simon Buchan says:

      Heck, perlin noise is even a builtin function for shaders. You don’t even need to push (unmodified) height data to the card!

      1. MichaelG says:

        Does that even work? It’s in the documentation, but I got nothing but zeros from the noise function when I tried it.

        1. Simon Buchan says:

          Huh.

          “What is the HLSL noise() intrinsic for?

          The noise intrinsic function generates perlin noise as defined by Ken Perlin. The HLSL function can currently only be used to fill textures in texture shaders as current h/w does not support the method natively. Texture shaders are used in conjuction with the D3DXFill*Texture() functions which are useful helper functions to generate procedurally defined textures during load time.”

          So *thats* useless. Perlin noise isn’t too hard to do (~8 lines), not including the psuedorandom vectors, which if you’re doing textures you probably want to provide externally anyway to get tiling. I wonder if anyone has a decent cheap stateless psuedorandom generator…

          1. MichaelG says:

            I’m working under OpenGL, and the GLSL spec has a noise function that should do exactly what you want — be completely general purpose. But there’s an old NVidia note around somewhere that they never implemented the functions. I guess they haven’t in the more recent drivers either.

            I implemented Simplex noise in a shader, but it was too slow to use. I don’t have a small Perlin implementation.

          2. decius says:

            I’ve got quite a few that use true analog manual input as a seed. They only generate integers from 1 to their maximum of 4, 6, 8, 10, 12, or 20.

    2. Jattenalle says:

      “ghetto version of fractal noise” I’ll have to remember to use that line sometime ;)

    3. Shamus says:

      Fractal noise is slow (compared to looking up values in a table) and it tends to not look a lot like hills. (And I want more control of the data.)

      1. Nevermind says:

        You can populate the table with noise to begin with. And noise (specifically Musgrave’s multifractal noise) looks much more like hills than your simple approach. Usually (-8

        Although tweaking noise functions is much, much harder than tweaking some tables, that’s for sure.

  4. DanMan says:

    I really love your explanations of this kind of programming. I’ve only ever made web page applications and small GUI desktop apps. You know, the normal screen with buttons and text boxes.

    I have exactly zero experience with graphics and terrain and polygons. Now so much theory that I learned in high school and college actually seems to apply to things. Math that I understood, but had no use for has actual real-world application.

    This is truly a delight to read. Keep it up.

  5. MichaelG says:

    Shamus, are you going to handle caves, or keep everything as a height map? The advantage of Minecraft cubes is he can do arbitrary shapes. If you don’t do that, I’m a bit stuck on what you do instead.

    1. Shamus says:

      Nope. No underground. Yeah, it’s all-heighmaps-all-the-time.

      1. Adam P says:

        One thing I notice in games that use heightmaps (Bethesda games, WoW), is that cliffs don’t look natural. They just have steep hills with an overhanging cliff object to decorate it. Heightmaps are usually grayscale, right? Different value of gray makes different height; That’s only 1 byte/pixel when an image can have up to 4 bytes/pixel (including alpha).

        So, if you used the RGB values for XYZ data, then couldn’t you shift the polygons on the non-height axises?

        1. HeroOfHyla says:

          “So, if you used the RGB values for XYZ data, then couldn't you shift the polygons on the non-height axises?”
          That’s how normal mapping works, isn’t it?

          1. WJS says:

            Only so far as both are re-purposing the RGB channels to store a vector. Which is to say, not really.

      2. Sydney says:

        Ever since your first terrain project, I’ve been wondering how overhangs would work (without needing to insert them manually later on). Is there a reasonable way to do it, or is it too much of a divergence from the height-map approach to be practical?

        (non-coder; maybe this is a dumb question)

        1. Kell says:

          Heightmaps don’t let you have overhangs, because every point on the grid has only a single altitude. To create overhangs, you’d need multiple points existing above and below each other, which the heightmap method simply cannot do.

          In many games that use heightmaps – e.g. WoW and Guild Wars – cliffs are indeed usually separate map objects placed on appropriate locations by the mapper.

          Minecraft has caves because Notch uses voxels to model the world, instead of heightmaps. Although I assume there is some sort of more complex alchemy going on that involves deriving data from heightmaps, converting it to voxels, and then modifying it with further procedural algorithms ( i.e. ‘tunneling’ through the world follwing procedural rules ). I’m not a coder, so I can’t comment on the specifics.

          From what Shamus has posted so far, I infer he is more influenced by FUEL for this latest project than Minecraft.
          The absence of overhangs is not necessarily a loss.

          1. Adam P says:

            It’s a peeve of mine when people refer to voxels in Minecraft. The world isn’t rendered with voxels, it’s rendered with polygons. Many, many polygons.

            1. NeoSonic says:

              It’s rendered with polygons, but it’s generated with voxels.

          2. Mephane says:

            This is one of my main gripes with current graphics engines. I mean, using a height map to store and load terrain is a brilliant idea, really, but it has this single major shortcoming – no cliffs, no hangovers, no caves. Just like in the movie contact when they combined the weirdly almost-fitting pages of data by organizing them around imaginary 3-dimensional cubes, and suddenly *click* all comes together and the riddle is solved. Heh.

        2. mike says:

          Adding cliffs is as simple as adding another step to the terrain generating process.
          1. Find faces that meet a steepness criteria (much like Shumus currently uses a rock texture when terrain is steep enough) and add it to a list
          2a. Check neighboring faces and see if they also meet the criteria
          2b. Add the neighbors meeting the criteria, repeat from 2a for the ones you’ve just added
          3a. using the normal of each face (or vertex), move it “away” from the normal on the x and y axis (leave them at the same height)
          3b. You want to move the vertices at the top less than the vertices at the bottom.
          4. Clean up. You want to subdivide the polygons that have been stretched at the foot of the cliff
          5. apply 3D noise to all vertices modified (or added)

          Bam. You have a cliff.

          1. K says:

            You will have problems with mapping though. You can no longer say “put a chest at X/Y”, because that now specifies two different sensible locations. Sure, it can be solved, but the simplicity of the height map is its advantage, which is now gone.

            1. mike says:

              That’s not really a problem. Imagine you are placing all different kinds of content on the terrain: chests, trees, rocks, logs, statues, crates, etc. – You’d have to mark those areas as occupied so you don’t place 5 things at the same coordinate.
              You just mark coordinates in the modified space an occupied, and you’re done. Not extra code. No extra problem solving.
              This is the same sort of technique you’d use when marking a body of water or a piece of terrain that is too sloped to place objects like chests.

  6. Kell says:

    This is cool stuff. I have more than a passing interest in procedural generation and 3D rendering, though I’m not a coder at all. I’ve used Terragen on and off for years, and built maps with Quake-lineage engines, including Source.
    I particularly enjoyed your posts about FUEL, and also found the racing elements of the game less interesting than the open world exploration. My GF and I were out for a drive just last night :P

    What I’m curious about, Shamus, is what your intention with this engine is? Open world shooter? Open world RPG? Are you thinking along the lines of FUEL + L4D = ZOMBIEWORLD, and the frustration that no-one else is making it is driving you to code it yourself? WILL IT HAVE MOTORBIKES?

  7. Zeta Kai says:

    He just wants a procedurally-generated landscape to use as the foundation for his Pixel City. ;)

    1. MrWhales says:

      procedural world for a procedural city… I do want….. badly..

      1. psivamp says:

        Then we can attempt to have procedurally generated NPCs and quests — they can’t be more bland or nonsensical than the ones in AAA games. WAIT! That weirdness can BE the selling point!

        1. Zehavn says:

          Check out Yahtzee Crawshaw’s book, ‘Mogworld’ It’s a great read!

          Z

          1. psivamp says:

            It’s on my shelf. I thought it was pretty funny. I liked the “real world” part of the story with the game developers.

        2. HeroOfHyla says:

          You’ve just described Dwarf Fortress’s Adventurer mode.

          1. psivamp says:

            I’ve never played DF.

            1. Sekundaari says:

              Obligatory. Check out the 06/05/2011 entry, it basically has one procedurally generated NPC’s story (with mentions of other procedural stuff like towns and factions) showcasing some of the newest added features. Plus the bit in the end is silly.

          2. K says:

            If DF was a game, and not an exercise in patience, you’d have a point. ;)

            One of these days, I’ll get rich and famous by blatantly copying all that makes DF great, but adding a decent GUI on top of it and selling it on Steam for 10 bucks.

            1. Kell says:

              You do realise that is essentially what led Notch to make Minecraft? Though Infiniminer was probably as much an influence as DF.

              Now the creators of Infiniminer and Dwarf Fortress continue to languish in indie obscurity, while Notch is fast becoming a household name and is sitting atop a pile of cash higher than his house.
              There is a lot to be said for making something that doesn’t repel everyone but the most clinically nerdy.

  8. Tizzy says:

    A small nitpick, but I’m beginning to resent seeing what seems to be every computer game ever assuming that the sea always rolls on long nice sandy beaches. Because, you know, it’s not always the case.

    1. Drexer says:

      If Shamus keeps his terrain rules the same then that will happen normally. If you have a gentle rolling hill that gets near sea level it should be coloured with sand.

      If you have a steep cliff even if right next to the water it should be coloured just as Shamus defines cliffs to be(which he hasn’t yet if I’m not mistaken, his whole world is quite a bit continuous smooth function).

      But this does remind me of something Shamus, are you gonna dedicate a post to explain how do you make the edges from a surface which you approach from two different directions fit?

      I can mentally understand most of the other software implementations for all of the rest, but getting a proper fit of different generated chunks is a challenge which I have yet to properly mentally explore and solve.

      1. Tizzy says:

        Yes, I can see how his setup should allow him to do that, though it’s the
        “Stuff touching the water should be sand.” sentence that I thought was over-simplification. Ultimately, my comment was only marginally about the post and more about how reading this sentence reminded me of those countless games I’ve seen that oversell the sand.

    2. Steve C says:

      Beaches tend to be sandy the closer you are to the equator, and more rocky and steep as you move towards the poles because of standard wind patterns. This is due to longshore current which is a form of erosion. Hopefully that info might be of some small use since you are procedurally generating Hex by erosion.

      1. Tizzy says:

        Indeed, this may be the general trend. But on top of that, you have local factors that complicate everything. The D-Day beaches of Normandy are endless expanses of dunes nowhere near the equator, and the sandy tropical beaches I’ve been on were rockier than anything I’ve seen in a video game…

  9. MadTinkerer says:

    What genre are you thinking of making this into? If we’re talking RPGs, you should check out The Blind Mapmaker if you haven’t already.

    I also have a few ideas regarding procgen RPG worlds, but Sean already has his all written up, and I’m still working on writing mine.

  10. Zock says:

    So… at the moment you’re calculating the heights with a function like:

    Height = (A * Topo) + (B * Detail), where A and B are predefined constants?

    I was wondering how it would turn out if you’d add some kind of a (smooth) blending layer, turning the height function to something like:

    Height = (Blend * Topo) + ((1 – Blend) * Detail), where Blend has a range of [0,1]

    I’d guess that this kind of tweaking turns into a bottomless pit very quickly, and you’d be better of with some already proven fractal functions.

    1. decius says:

      Height = (A * Topo) + (B * Detail) + global bias
      Where global bias is the average height of the region.

      Also, depositation might not make a huge difference when eroding hills, but it is the primary factor in river deltas and the related littoral topography. Various other factors relate to the generation of canyons vs river valleys, or windswept areas.

  11. ProudCynic says:

    The very last picture reminds me a bit of Jurassic Park: Operation Genesis. Am I the only one who remembers that game? Just add in some wandering dinosaurs and remove the wireframe and it’ll be just like it.

    1. Drexer says:

      Now that you’ve mentioned it yeah. It does look a lot like the default island textures as you first start the game.

    2. anaphysik says:

      Yes, Shamus. Needs more dinosaurs. Can’t have enough dinosaurs. We’ve got a fever and the only cure is more dinosaurs.

  12. Adam P says:

    Very bland, of course. We don't want to generate an entire continent of endless speed bumps, so we also have some topographical data stretched out over a much larger scale:

    Note how this looks kind of mechanical. You can see large, flat surfaces everywhere. By itself, this would make the continent feel sort of like the whole world was made from geometric primitives. But if we combine the two data sets:

    I've exaggerated the hills for effect. The large hills give the world shape, the small ones give it detail. Together they make something roughly presentable. From now on, I'll be calling these two sets the “topography” and the “detail”.

    Weird, I watched your video review on FUEL just last night and you had said pretty much the same thing then.

    1. X2-Eliah says:

      This can only mean that the real Shamus has been imprisoned and impersonated.

      1. GM says:

        Nah he is Copy Pasting Himself :)

        1. Fists says:

          Procedurally generated blog content?

          1. psivamp says:

            Wasn’t there a blog post about that?

            Edit: added link.

  13. TehShrike says:

    Have you played Frozen Synapse? It has awesome procedurally-generated maps, and it’s also the best game I’ve played since Portal 2.

  14. Eric says:

    You are making some very clear and obvious strides in only the course of a couple of days. Great work, and keep it up!

  15. psivamp says:

    I love the coding projects, Shamus. I enjoy Spoiler Warning and everything else, but I really like reading about the code more.

    Just want to throw that out since the coding updates seem to get less of a following in the comments.

  16. X2-Eliah says:

    Dear Shamus.

    If you want quality landscape-profiles, you should check out that newfangled game, Mass Effect 1. I heard it had some mostly amazing generated hills.

    That is all.

    1. Even says:

      I was actually reminded of those dreaded hills the moment I saw the first jagged cliffs. I wouldn’t be surprised if it was somewhat similar to this what most of them did when generating the terrain for the game, if only being obviously lazy about it.

      Now all we need is an arbitrarily “fenced” area, random map objects in the most unreachable of places, a Mako and some hilariously broken physics and call it the “Mako Simulator”. Nobody would be the wiser.

      1. Jeff says:

        Don’t forget a stamp tool for sticking in giant underground worms in a circular flat clearing.

  17. RPharazon says:

    Was anyone else reminded of the Tribes 2 landscapes when viewing these screenshots? Anyone?
    I swear, the colour palette is almost exactly the same…

    1. mike says:

      I have to admit: it came to mind.
      Tribes… dude. Why must we be without you!?

      Worst thing is, I’ve seen some fan attempts to revive Tribes, but they never seem to hit the mark.
      It may be the rose-tinted glasses I’m wearing.

  18. Peter H. Coffin says:

    Eventually, this will come back around to rock climbing.

  19. chiefnewo says:

    Here’s a link to another interesting procedural world project: http://procworld.blogspot.com/

    This guy is making his world out of voxels and procedurally generating just about everything from trees to buildings.

    1. psivamp says:

      I want to say that this project was linked from here before, but it may also have been linked from MichaelG’s Sea of Memes, or maybe I stumbled on it around the same time as SoM and I just link these three sites in my head.

  20. Hey Shamus, later when you are going to store the terrain as savedata,
    do you plan to generate terrain as mini-chunks and save the seed for that mini-chunk?

    Just asking because I can’t think of a more effective way that uses minimal amount of memory.

    1. Will It Work says:

      It would depend on if playstyle could modify landscape. If the FPS had, for example, a bomb which left a crater instead of a decal, then seeds would be untenable.

      1. Not necessarily, the “crater” could be a seed modifier. (terrainchunk seed + crater seed)

  21. Fists says:

    Have you considered or experimented with using music for the data map? its more of an expansion on your original sine-wave build. Music isn’t random like your noise but I think the patterns should be broad enough that they aren’t discernible once layered in topography and detail as above.

  22. Mogatrat says:

    While this is interesting, usually these posts are posted along with Spoiler Warning – did Josh not finish the editing or something? What’s up?

  23. NeesonLiam says:

    Awhile back I posted a blog post about using Perlin noise functions at http://www.gamedev.net/blog/33/entry-2227887-more-on-minecraft-type-world-gen/ that might be of interest. It generates caves, overhangs, etc… in a cube-style world. Generates kinda slow though, a consequence of using several Perlin functions bound to Lua without any parallelization.

    That procworld blog someone linked to earlier is awesome, awesome. Shamus, keep us updated about how this project goes. I love reading these coding updates.

  24. rspencer says:

    Firstly, thank you for a very interesting series of blog entries. I enjoy the way in which the descriptions give just enough information to code it without baby sitting you through actual source.

    However, I would like to know how you generate your “topography” layer. I presume the detail is just smoothed out noise, but if I blow that up to a big scale, I do not get anything quite like your rolling hills of the second picture.

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

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

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

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

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

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

Leave a Reply to MadTinkerer Cancel reply

Your email address will not be published.