Project Frontier #3: Adding Variety

By Shamus Posted Friday Jun 10, 2011

Filed under: Programming 62 comments

I mentioned earlier that the program is comprised of a bunch of different systems. There are three systems we’re interested in right now:

  1. Regions are abstract areas that have certain properties. Like, “stuff within these boundaries should be very hilly, moderately high, have bright green grass, etc”. It doesn’t contain any elevation or polygon data. It’s just an area of rules.
  2. Pages are blocks of elevation data. Right now, these are generated in one go. When a given page is requested, the program drops what it’s doing and generates it. This takes a while, leading to really annoying quarter-second lockups as you move around the world. Somebody should probably look into doing something about that.
  3. Terrains take the pages of data and make the polygons and textures.

Here is an overhead view:

frontier3_1.jpg

I was careful to keep these systems independent of each other with regard to size. I can make regions tiny if I need to. It might be silly to have a sixteen-meter desert, but it’s good for testing.

I can make a page hold a lot of data, or a little. If I make them big, then I won’t need to generate them very often, but it will take a really long time when I do. If I make them small, they will be quick to create but I’ll need a lot of them, which might lead to sorting difficulties later when I need to figure out which of the hundreds of pages I should build first. I can experiment with different sizes for these systems by just changing a few variables.

In the above screenshot, we’re looking at a circle of terrains. I’ve put a red outline around a single terrain. You can also see the effect of regions, since each region has a different grass color. Eventually regions will represent different climates (a bit like Minecraft biomes) and so we’ll want them to feel kind of big. Here I’ve made regions 64 meters across, which is absurdly small, but it lets us see a lot of them at once.

Looking closer…

frontier3_2.jpg

I don’t think you’ll need to squint very hard to see the seams between the regions. What you’re seeing is the corner where four different regions meet, and each region has its own grass color. Right now these are just randomly chosen from a band of greens and yellows. Someday I’ll have them determined by climate, but for now it’s just a crapshoot.

This great big seam is obviously ugly. We can alleviate this by fading from one color to another.

frontier3_3.jpg

That helps, but it also makes things a bit bland. If regions were normal sized (maybe four or eight times larger than they are now) the color changes would be so slight that you’d hardly see them. I don’t want to obliterate the region boundaries like this, I just want them to be less of a hard edge.

In my program I have a function to look up a region. “For the position x=63, y= 112, what region is that in and what does that region look like?” I just added a couple of lines of code to scatter these results. So, when you look up x=63, y= 112, you might actually get the results for x=52, y=100. These offsets are deterministic, meaning you’ll always get the same result for the same input numbers. They also follow a bell curve, giving a scatter of results with a few outliers. The result:

frontier3_4.jpg

You can still see the region boundaries, which is good. It’s no good making unique areas and then blending them together in a big mush so that everything looks the same. So this is close to what I want. However, the scattered dots look a little ugly. They’re better than the seam, but let’s see what it looks like when we combine the scattering with the blending:

frontier3_5.jpg

I like that. It keeps the “blocky” thing I’m going for, it breaks up that quilt-like grass texture, and preserves the variety between regions.

We’re nowhere near the point of being ready to optimize the program yet, but I do want to add a few basic things just to ease the development process. The program really chugs when I first start it up, and it shouldn’t need to. I hate having to wait ten or fifteen seconds to see the results every time I make a small change to the program. So let’s do some easy optimizations.

Right now I’m taking the polygons and throwing them at the graphics card every single frame. I’ve talked before about how monstrously slow that process can be.

Sending data to your graphics card is slow. (Relatively speaking.) Your graphics card is sort of like another computer. It has its own memory and its own processors. Your PC sends it a fat wad of data describing the position of the polygons in the world, and the GPU (your graphics card) has a jolly good think. When it's done, it sends back the finished image. (Basically.) The problem is: There's a limit to how fast data can be moved between the two. It's like two bustling cities with vast ten-lane highway systems, but between the two is just a dirt lane.

The answer for this problem is to use vertex buffers. You pack up the polygons and send them to live on the graphics card. It’s like having them move to the city so they don’t need to take that dirt road commute every frame. The cost is that this eats up a bit of graphics memory. Hang on, let me figure out how much…

Each vertex has an x, y, and z value. Each of those values takes up 4 bytes. Then each vertex has a normal to go with it, giving us another x, y, and z value. Then we need another pair of numbers to describe which part of the texture we’re using. Each terrain is 33×33 vertices. So 33 x 33 x (3 x 4 + 3 x 4 + 2 x 4) = 34,848 bytes. Thirty-four kilobytes of video memory. For contrast, the texture on several of these terrains is 3,145,728, or three megabytes. So, these vertex buffers are really, really trivial in size.

The speed increase is rather striking. The program still runs like a dog when it’s generating new pages, but at rest the framerate was around 50. Now it’s 350.

To give to a sense of scale, here is a shot from eye-level.

frontier3_6.jpg

It’s still very barren, bit it’s a solid improvement over where were were last time around.

Onward.

 


From The Archives:
 

62 thoughts on “Project Frontier #3: Adding Variety

  1. Fede says:

    Thank you Shamus, this series of posts is really interesting. There is one thing that i didn’t undersand, what happened to project hex? It is linked to this one, or is a separate thing and you moved on to project frontier?

    Also, minor nitpick, a typo: last line of the third paragraph, “Somebody should probably look into dong”. It could be embarassing…

    1. Caffiene says:

      Heh.

      Time-to-penis is a well respected metric for a game’s popularity. A negative time (measured from project release) can only mean that this will be the best, most popular game ever.

      1. “Time-to-penis is a well respected metric for a game's popularity.”

        HAhahahahahhahah! Thank you for making me spew water all over my keyboard.

      2. Brandon says:

        I’m not so sure. I feel like time-to-penis is more likely a measure of unpopularity. It sound like the time it takes for someone to put the game down and go amuse themselves out of boredom.

        1. Michael says:

          Well, anything that measures unpopularity, by definition, also measures popularity.

          A negative time-to-penis means that a consumer will never put the game down. It means that they like the game so much, that they amuse themselves before they start the game to eliminate any distractions.

          Ultimately, this is what developers want. A negative score, or an extremely large positive one.

          Or, at least I’ve heard. I’m not a games reviewer, and as such, I don’t know all the jargon.

    2. Shamus says:

      This is a branch of Hex. Hex is still there if I decide to go back to it. But this is my obsession for now.

  2. Goatcathead says:

    part #4 turning it into a minecraft terrain generator.
    But seriously it’s looking good shamus!

    P.S. you could make a minecraft terrain generator

    1. Alexander The 1st says:

      He doesn’t have to though. Not everything procedural has to be Minecraft, you know. :p

      With the way it’s looking, I’d say it’s more of a Bethesda-esque engine. Only, you know, without bugs yet (Or have you found bugs in it yet?).

      1. theLameBrain says:

        Everything procedural does not have to be Minecraft. It could be Dwarf Fortress!

        1. Akhier says:

          Maybe we can get lucky but for some reason I don’t think he wants to spend years of his life making a Dwarf Fortress clone with better graphics.

          1. Goatcathead says:

            Years? for some people it only takes hours!

      2. niconorsk says:

        All software that’s at least somewhat complex has bugs.

  3. CTrees says:

    See, the version with the big, obvious seams? It looks like farmland, to me. If you decided this should be a farm-themed game, you wouldn’t’ve had to change anything.

    You’re just making it harder on yourself.

    1. decius says:

      So, a cross between Minecraft and Farmville? Mineville? Farmcraft?
      Or, to bring Dwarf Fortress into it: FarmFortCraft!

      1. Skye says:

        I would play that.

    2. Alexander The 1st says:

      Obviously, the farmland you see every day isn’t realistic enough. [/Reality Is Photoshopped]

      But yeah, frontier3_2.jpg is what things start to look like in most farms, especially from airplane heights (Where everything starts to look like that, but whatever), so if you are planning to have farmers to be NPCs in this procedural FPS-esque game Shamus, then you should add in capability to do this with the engine – enforce some sort of flag like this, or something?

      It would also help with clear-cutting forests, which happens in real life too. Or like forest fires, as well. Full-on grid-like blocks in the forest that are completely devoid of trees.

  4. Caffiene says:

    I love these articles. As a programmer, but only an “informed bystander” at game programming, you manage to give an overview that is apparently simple enough for a layman to understand but that also gives me enough ideas that I feel I could make a start on putting something together myself.

    On Frontier, though, Im feeling a little bit like youre skipping over things a little more than in previous series. I know there are always details that dont get mentioned, but its feeling like this time some things that are mentioned arent being discussed. For example, youve mentioned paging in parts 2 and 3, but glossed over how youre doing it apart from to say that the page size is variable. More details, or side-bars and digressions, are always welcome!

    1. Shamus says:

      It’s true, I skipped a lot.

      The thing is, I BINGED on this project last week before deciding to to a series of posts about it. So, I’m trying to get the series caught up to where I’m working. I’ve been going back to old versions for these screenshots. (I do daily snapshots of the thing.) This series should gain a little focus once it’s covering the stuff I’m working on right now.

      We’re still a couple of entries from caught up. If only I didn’t need to sleep.

      1. Svick says:

        Daily snapshots? You mean you don’t use source control?

        1. Shamus says:

          Nope. I haven’t found a platform I like. The free ones are all varying degrees of horrible / clunky / over-integration. I used Perforce back when I had a day job, and I miss that.

          And right now I don’t want to blow an afternoon poking around for one, installing them, trying them, etc.

          Right now I am using dropbox, which gives me-off site backups.

          1. Nathon says:

            Read this: http://hginit.com/

            It’s amazingly lightweight and easy to use for small stuff (I use it for all my personal projects and my web site) but can handle the big stuff well (our repository at work has about 28,000 commits).

            1. Shamus says:

              Interesting. The article sold me on it. I tried to get it. Am I blind, or does this page:

              http://mercurial.selenic.com/downloads/

              Claim you can download binaries WHICH DON’T EXIST ANYWHERE ON THE SITE?

              1. Peter says:

                they work just fine over here. might want to try again?

                love these posts by the way, always a fun read.

              2. AlfieUK says:

                Did you try the TortoiseHg link (http://tortoisehg.bitbucket.org/) from that page? It includes Mercurial, the required version Python libraries and the Tortoise GUI which integrates with Explorer in x32 and x64 flavours for Windows.

              3. Nathon says:

                I see a bunch of links that say “download” when I follow that link. http://mercurial.selenic.com/release/windows/Mercurial-1.8.4-x64.exe

                That’s the x86-64 Windows one, and http://mercurial.selenic.com/release/windows/Mercurial-1.8.4.exe is the 32-bit Windows one.

                Oh, but you probably want the tortoiseHg anyway, which is at the bottom of the list. Maybe something’s wrong with your browser?

                1. Shamus says:

                  Ah! I have Javascript off by default.

                  It really is shocking how many things are done with Javascript. Simple things. I managed to download it and it’s working already. Pretty nice so far.

                  1. Nathon says:

                    If you get to the point where you’re ready to share it, https://bitbucket.org/ is the Mercurial equivalent of github. It’s also free for open source projects.

                    1. ksleet says:

                      I’m very happy with Mercurial myself. My source code needs are minor — I mostly just need a way to revert changes when I horribly screw up an implementation attempt — and Mercurial is so refreshing in how it JUST DOES WHAT I WANT WITHOUT ENDLESS DRAMA. Being able to move my work, including the source code repository, to another machine simply by copying the directory is nice too.

                  2. decius says:

                    If only the internet inherently supported some protocol to transfer files. For lack of a better term, call it a… Transfer Protocol System.

                    So, how’s those TPS:// reports coming along?

                  3. Rowan says:

                    Now you just need to port your book to (La)TeX and you can write just like you code!

                    (No, seriously. LaTeX lets you concentrate on the writing instead of formatting. And you get the easy source-control integration that comes from having a plain-text file. Or multiple files.)

          2. Alexander The 1st says:

            PERFORCE! Yeah, I just started using it at work, and it is awesome.

            If only it didn’t cost $900/user (For the first 20 users).

            On the other hand, can’t you get the trial version that only works with 2 users (I remember it on their site, IIRC)?

            1. Shamus says:

              Man, I didn’t know how good I had it. Perforce, with an off-site server, and it fully integrated with my version of Visual Studio. I could do check outs / commits right from Dev Studio. Those were the days.

              Now I have no server. Now I’m using Visual Studio 2010: Hippie Freeloader Edition, which doesn’t have built-in support for that stuff.

              Also I’m broke. There’s that, too. I guess that’s more serious than the others. But I still miss Perforce.

              1. Alexander The 1st says:

                It is so much better than TortoiseSVN, but…yeah, Perforce kind of knows that.

                They’re like the Adobe of Version Control Systems – way too good and professional for professionals to willingly go elsewhere, but nobody but corporations can afford their products.

              2. Chris says:

                We use Perforce at work and I love it, and I’ve started using it at home for personal projects too. You can use it with 2 people for free, and the server doesn’t require anything fancy. I’ve run it on linux and on windows, and on my development machine and a dedicated server — no problems either way.

              3. Groboclown says:

                Perforce allows for unlimited free use of its software for up to 2 users. After that, it’s a payment thing unless you apply for an open source project license.

                1. Mistwraithe says:

                  Yeah, no charge for 2 users and 5 workspaces which realistically should be more than enough for a single developer working on their own.

          3. Simplex says:

            Wow, I thought using version control in a programming project is a given. I am not a programmers myself but I work with programmers and they use SVN or GIT to maintain projects.

          4. William Newman says:

            Very different strokes for different folks, evidently. For me, even distinctly clunky source control (like cvs) is much better than nothing at all. Having a trivially small cost for recording a backup state every time I make tangible progress, many times a day, and being able to do operations like “diff” between backup states seems to save me multiple hours per month directly. It also seems to help significantly by reducing the number of things that I need to carefully keep track of in my short-term memory, and by making it safe for me to work in patterns that would sometimes lead to confusion if I couldn’t refer back to my magical record of preceding states. So to me cvs and many of its popular free successors also (e.g., svn, hg, darcs, and git, the last of which I use) seem good enough to be very helpful for most projects.

            Not to say that source code control software can’t be sufficiently bad that I’d prefer to use nothing at all, but the kinds of problems that make it sufficiently bad for me are things like “loses data” or “unusably slow”.

            1. Nathon says:

              CVS falls into the sufficiently bad category for me, since it can lose data. Of course, I used it at work for 3 years before convincing the company to switch.

        2. Fukiku says:

          Funny, how this post got me somehow thinking about the question whether Shamus uses source control and if yes, then what exactly and what’s his take on the topic as a whole. I googled around and found, that he had even written a whole post about it back in 2009 (which conveniently fell into the year I didn’t have access to internet and explains, why I hadn’t read it). But I am surprised, that he didn’t find a suitable solution back then and is still doing without.

          I’m trying to figure out a solution for myself also to use on hobby projects – probably going to try git, mercurial or something from that bunch. Quite different from CVS (legacy clients not willing to migrate) and SVN at the day job.

      2. Caffiene says:

        If only I didn’t need to sleep.

        Makes the internet sound like a new child. :D

        “Im so tired, and I barely have any free time… but I have to keep getting up in the middle of the night to feed it or it gets very upset.”

  5. Nathon says:

    Typo alert:
    “…and each region has it's own grass color”

  6. Nevermind says:

    (Shameless self-promotion follows)

    I made a little “procedural terrain” project of my own this winter. And I had the same thing with regions. I used blending, and while it indeed makes boundary invisible, it’s not actually bad. As a result, you can go and not notice any abrupt change, and then be like “I was on a plain and now there are mountains everywhere, how did it happen”?

    Take a look at it here, if you’d like http://nevermind.wikidot.com/local–files/_unity:roentgen/WebPlayer.html (requires Unity Web Player).

  7. Nathon says:

    I’m a bit confused by this project. On the surface, it looks an awful lot like the terrain engine you wrote a while ago. I saw your absurdly optimistic list of goals, so why not adapt the terrain project for this? Is it the SDL/OpenGL porting aspect?

    1. Shamus says:

      Basically, this project is a union of the Terrain-making aspects of the original project, and the texture-making aspects of Hex. And then, if all goes well, we can add the Cool Stuff.

  8. Brandon says:

    Love to see another coding project from you Shamus! Every time you start doing stuff like this, I always end up thinking that I really need to start doing game-ish programming again. I always have lots of fun when I do it, I just don’t want to use the C++ Win32 library anymore (Which is the only graphics library I’m familiar with.)

    I’m debating trying out SDL, I’ve never really given it a fair shake. Either that or making the jump to 3D and giving OpenGL a shot. Maybe once I had some more free time.

    1. Simon Buchan says:

      I assume you mean you used GDI – SetPen(), BitBlt(), ExtTextOut() and friends?

      I’d say using 3D right off the bat is probably going to be too confusing, learning how to use the API is going to be difficult enough without trying to learn how to design for 3D at the same time. I’d still reccommend picking up OpenGL or Direct3D, I preffer to learn them raw rather than using a support library like SDL, in which case I’d reccomend Direct3D 9 as being the simplest version to learn (for Windows, obviously – OpenGL 2 is easy for linux and mac). However, there are plenty of good support libraries out there that can give you simplicity and platform independance – I did like the look of an SDL replacement with a 4 letter acronymn name I think was from Google, but I can’t find it now :(.

  9. Alan says:

    I like that last screenshot, it looks a bit like the default desktop of Windows. I wonder if that is how they did it?

    Shamus, I know you were a graphics programmer as a day job before, but how much of what you are doing in this project is new to you, or is it all things which you have done before?

    1. Shamus says:

      A lot of my work was on (old) systems designed by others. So nearly all of this is new to me. This is basically the fruit of my thinking and ranting about procedural content for the last four years.

      1. Kell says:

        Which is why it’s looking really interesting. Procedural generation isn’t the future of game design, but it is a future of game design. Open worlds and emergent gameplay are the two main fruits that might be gathered from procedural generation.

        I would like to play a game based on this sort of engine.

  10. Jeff says:

    I’m kind of interested in how the overhead view changes with the various blending techniques. Any chance we could see that?

  11. cyber_andyy says:

    I have no idea why, but describing the graphics card as ‘having a jolly good think’ made me laugh really hard.

  12. Ander the Halfling Rogue says:

    As someone who knows almost nothing about programming (my only knowledge coming from you), that last screenshot looks great, especially for 3 posts in.

  13. Narida says:

    Next up: procedural trees? The landscape still looks a bit bland as you said: :-P

  14. jamie says:

    Generating pages in a separate thread might be a good plan, you’d only have to hitch if the page you want wasn’t finished yet.

  15. thenoob says:

    ‘Procedural generation isn't the future of game design, but it is a future of game design.’

    I think it will be an integral part in gaming, someday, Shamus is just ahead of the curve.

    In a few years, ES: Skyrim could go from random quest locations finally in a mainstream game, accommodating each one to the specific dungeon.

    Or Left 4 Dead. Although my biggest gripe was how linear the maps were, I was hoping for randomised goals.

    Although this all can’t have a decent storyline written by a real writer…. yet.

    Procedurally generated physics, no doubt, the future of gaming.

    1. Jeff says:

      Actually, both of those games you mention oppose your view.

      Bethesda says that one of the major failings in Oblivion/Fallout 3 was procedurally generated terrain, which they intend to correct in Skyrim. I didn’t even notice, myself.

      Left4Dead 1 actually started off as a Sandbox, but play-testing (one of the things Valve excels at) made them close off paths so it was more linear, which improved gameplay.

      1. WJS says:

        Yeah, I’m highly sceptical about that L4D story; going from “sandbox” to “linear shooter” is a huge change in gameplay, and the only way I can see it happening is on a project that didn’t really have a clue what kind of game they actually wanted to make. What I suspect is more likely is that this guy doesn’t know the difference between “sandbox” and “open map”.

  16. confanity says:

    Right off the bat, “The program comprises…” or “The program is composed of…”

  17. mbue says:

    I might be a bit late… but I’m wondering… how does the erosion simulation cope with page boundaries? As far as I understand your architecture, erosion can only happen on a single page, because neighboring pages might be loaded at a different time. Doesn’t this lead to noticeable artifacts? Isn’t this problem similar to the one mention later with Terrain boundaries, when you apply that Quadtree algorithm?

    Cheers!

  18. D-Frame says:

    I keep coming back to this project once in a while and I just realized there is one thing I never understood. How do you actually create the elevation data for new pages? More specifically, how do you make the edges of different pages match with already existing ones?

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 decius Cancel reply

Your email address will not be published.