Project Hex Part 3 – Things Get Hilly

By Shamus Posted Wednesday Nov 3, 2010

Filed under: Programming 106 comments

I didn’t post about the project last week. You didn’t miss much. I needed to add non-visual stuff like camera controls, a debug log, play a bunch of minecraft and that sort of thing.

So now we have a hex grid based world.

hex_hills1.jpg

I’ve got this bit of code which takes a simple integer and returns a color value. It’s set up to be deterministic (the same number always returns the same color) but irregular (the colors for 37 and 38 will be very different) so that it will produce the above “kaleidoscope puke” effect. It’s not pretty, but it’s really handy for debugging. I say this as someone who has spent a lot of time squinting at rolling green hills, trying to find that one bad spot I was looking at last time I ran the program.

Time for some depth. Because the back end is really just a regular grid, I can easily pull in some elevation data. And the quickest way to do this is to bring in an image and use it as a heightmap. I just take some random image of bumpy white stuff:

hex_topo.jpg

And import it into my program, using the color values as height values. The brighter the pixel, the higher the point. Take all of the elevations below a certain level and flatten them out, which will produce an “ocean”. The result:

hex_hills2.jpg

Now, the game is going to be played from a fairly close-in view. The player will never see this much scenery at once. But for development, I want to be able to pull back and see what everything looks like.

Note that much later in the project I’ll want to generate the world procedurally. I’ll be making mountains, valleys, plateaus, lakes, etc. by generating them at startup. But that’s a whole lot of complex stuff and I’d prefer to have the basics done first, which is why we’re using the heightmap for now. For those of you squinting at the previous two images and trying to reconcile them, note that I’m only using one quarter of the heightmap for now.

Now let’s see about making this look more like a landscape and less like a Care Bear took a dump on it.

This is pretty familiar work for me. You can make a visually convincing landscape with a few simple rules…

Anything at or below the water level is water. Anything above water level that is touching water is beach. Anything point that’s on a slope steeper than 45 degrees is a cliff, where grass doesn’t grow. Anything above a certain elevation is rock. Anything above another, higher elevation is snow. Everything else is grass.

This is not a simplification. The previous paragraph could just as easily work as pseudocode, because this is all I’m doing. Follow these rules and you’ll wind up with the same results I do. Again, this will be a lot more sophisticated later, but we’re taking baby steps.

Let’s see how it looks:

hex_hills3.jpg

Note that I’m applying the above rules on a per-point basis, but I’m drawing the world on a per-hex basis. So, there’s additional detail in the points that make up the borders of hexes that’s not being shown. Here is what it “really” looks like under the hexes:

hex_hills4.jpg

That’s more interesting, obviously. But it will be irrelevant once we get the real artwork into place. Here is another look at the terrain, without drawing the hex boundaries:

hex_hills5.jpg

Yawn. Without lighting or contour lines, the surface is very flat looking and it’s tough to get feel for the shape.

Now let’s import the entire heightmap and have a look from higher up.

hex_hills6.jpg

Let’s do one more. I’m going to feed it a larger heightmap and turn the world up to 512×512 points. (The previous screenshot was a 256×256 world, and all previous ones were 128×128.) This largest size is probably the size of the world in the final game.

hex_hills7.jpg

A 512×512 grid of points yields a 255×388 grid of hexes. (388? Man, working in hexes is strange.) Each hex is 6 triangles. So we’re drawing 593,640 triangles. And it is stupid slow.

Of course, the player will never see more than a fraction of this at a time. About this much:

hex_hills8.jpg

Somewhere between 20,000 and 30,000 polygons, assuming I don’t do any optimizations at all.

I could nitpick a lot about how the world looks right now, but this is good enough as a starting point. Next time I’m going to go about implementing the texturing system I have in mind, and from there the look of the program should start to take shape.

 


From The Archives:
 

106 thoughts on “Project Hex Part 3 – Things Get Hilly

  1. Robyrt says:

    I love this writing style for explaining your technical accomplishments without dumping a bunch of code on me. Keep it up!

  2. Brandon says:

    Only one complaint so far, and that is that certain special environments, like desert, and the distinction between, say, forest and plains, is not yet apparent. Do you have plans for this?

    1. SolkaTruesilver says:

      I’d suggest the Dwarf Fortress approach, with setting a region as the equator, and having the temperature diminishing as you go away. Then from the mountainous landscape and a planetary rotation coreolis effect, you can have some basic wind movement.

      If you go at it determining where the humidity is generated (start with the sea) and where it goes (stops at mountains), I think you can make rough guesses as to where the deserts, jungles and forests have to be that aren’t arbitrary or random.

    2. Clint Olson says:

      *cough*biomes*cough*

      Yeah, Shamus, why can’t you be more like Notch? ;)

      1. Cybron says:

        Toady was doing biomes before it was cool.

        Anyways, such a level of detail may simply not be appropriate for this project. Dorf-Fortress-level obsessive simulationism aside, not every game requires the modeling of such details.

  3. TheBoff says:

    I’m really impressed with how it looks already! If you were going for a cartoony feel then it would already be perfect, but I sort of take it that you’re not…

    My hex based achievements are drawing a 2D grid, so I can wait to see how this turns out!

    I hope this is a going to end up a turn based strategy game, because they’re great and there’s not enough. I wonder if you’ve encountered Battle for Wesnoth yet? It’s one of about 5 really enjoyable Open Source games that I’ve found.

    1. Brandon says:

      For some reason turn-based games have fallen out of favor in the games market. It makes me sad. I think Neverwinter Nights would have been much improved, at least at the single-player level, with a turn-based mode.

      1. Raygereio says:

        Too small of a market I guess. They are still out there though; the obvious one being the Civilization series and there’s stuff like the Disciples or King’s Bounty.

        Also, isn’t there a mod for NWN that added a form of turn based combat? I know there is one for NWN2.

        1. Galad says:

          I’d love to hear the answer to that question myself..

    2. Deoxy says:

      I love Battle for Wesnoth – what are the other 4 games on your list?

      1. TheBoff says:

        TASpring is a very competant RTS: that and BfW are the main ones, really.

        The other three is basically gnometris et al :P.

    3. Falcon_47 says:

      Lol, Battle for Wesnoth was also the first thing that came to my mind once i saw that first terrain grid. Haven’t played that game in a while but i’ve heard that it keeps getting better and better. Might go take another look.

  4. mad_wolf says:

    thanks to you shamus i now have an idea what the bowel movements of a care bear look like

  5. Eldiran says:

    Nice work, Shamus! I am especially intrigued by this series as I am currently making an isometric game (which may or may not be partly inspired by Minecraft) and I have /no idea/ what I’m doing. I’ve never worked with 3D before, so even though I’m doing isometry with sprites, it’s a whole new ballgame for me.

    I’m gleaning all kinds of insight from this series, so please continue!

  6. Cuthalion says:

    Cool. I like how you’re able to explain stuff without alienating either technical or non-technical people.

  7. Gandaug says:

    I have no interest in programming whatsoever, yet I enjoy these series’ you do. Why is that?

    1. Scott says:

      For me, at least, it’s because Shamus makes it accessible.

    2. Matthew says:

      I know! Normally when someone is telling me about coding and stuff, I’m like “Ooookay… so how about that great movie that’s in cinema right now, eh?” whereas in this case I’m like “Oh cool, Shamus. Tell me more!”

  8. omicron says:

    So. Procedural generation:
    I’d suggest you use a series of diamond-square maps. They aren’t the most advanced algorithms on their own, but they’re fast and, in concert, can produce stunning results.
    For example, my own formula goes something like this:
    * First diamond-square map is what I call a “cliff map.” This feeds directly into the next map, and affects the formula: anywhere the cliff map is extremely high, the diamond-square produces plateaus. Anywhere it’s low, it produces craters/canyons. The edges of these regions form pretty good cliffs.
    * Next diamond-square is for heights, with the previously-detailed modifier. I use a bit of a modification where I divide the result (capped at 256) by 16 and square it – this makes mountains more abrupt, and makes most of the map flat. (suitable for construction!)
    * Next diamond square is a fertility map. It’s a straight algorithm (although adding rain-shadow from high mountains would be trivial). In conjunction with the climate map (next!), it allows me to determine the locations of deserts, forests, plains, scrublands, and rainforests.
    * Final diamond-square is the climate map. It’s constrained by elevation, so above a certain point the climate gets markedly colder.

    Anyway, that’s my two cents. It looks great; lookin’ forward to more.

    Edit: Again, I have to wonder if you’re familiar with Empire, which I believe is a game concept that needs a modern import.

    1. HarveyNick says:

      That sounds pretty interesting. Are you using the basic diamond-square algorithm to generate every step, though?

      It sounds like only the second is a perfect fit, which makes me wonder if you’re using a modified version for the other steps…

      1. omicron says:

        Only the second truly matters from a visual sense; but I am given to understand that the diamond-square is among the fastest suitable algorithms, so I use it for the others.
        In truth, however, it is only the first that is completely unmodified. It feeds into the second, which in turn feeds the third and fourth – although the algorithm is the same for all.

    2. Ingvar says:

      If nothing else, XConq is a modern sorta-like-Empire turn-based game and seems to have a Windows port.

  9. Dev Null says:

    some random image of bumpy white stuff

    Ultrasound of your firstborn child?

    1. Michael says:

      It looks more like a moon.

      1. Andy_Panthro says:

        That’s no moon!

        1. Scott says:

          It’s a space station.

          1. Mistwraithe says:

            It’s too big to be a space station.

            1. Drue says:

              I have a bad feeling about this.

              1. Kavonde says:

                Grrraaawr.

                1. Josh says:

                  Turn the ship around.

                2. Irridium says:

                  I can’t, somethings wrong!

      2. Pickly says:

        That’s what I thought as well.

  10. Ateius says:

    I never thought long descriptions of coding could be interesting, but somehow you do it. Eagerly awaiting the next entry.

  11. Friend of Dragons says:

    Interesting. The look of the world kind of reminds me of Scorched3D, a (3D) tanks/artillery game set on a square island, that I enjoyed for a while a couple of years ago. (well, except in that game, you had much more of the bird’s eye view portrayed here rather than the player’s view portrayed here.

  12. eides says:

    I enjoy these, but they make me a little sad too, seeing the (seemingly) effortless way you can take a dream and turn it into a program.

    I had done a significant amount of Basic programming on my Commodore 64 and Vic-20 when I was growing up, then went through a Fortran class in college, and I’m generally decent at technical things, so I thought that for a non-programmer I’d be in decent shape to get into some hobby programming…after toying around in several languages and APIs and dabbling in computer books and online tutorials, I don’t feel like I’m any closer than I was.

    My dreams are too ambitious, the exercises and examples in the books are too pointless to keep my interest, and the online tutorials become obsolete so quickly that I just give up trying to figure out how to make them work. :(

    1. Erik Lundqvist says:

      Try harder?

  13. krellen says:

    Okay, so you’re making a pretty hex map with some thought to how it should be laid out procedurally. But I think a burning question we all want to know is: what are we going to be doing on the pretty hex map? Building civilisations? Fighting monsters? Building towers? Playing with hex-shaped Legos? Assaulting audiences with traffic cones?

    1. BenD says:

      My vote is for that last one all the way. XD

    2. Syal says:

      There’s only one possible answer; randomly generated fetch quests.

      1. Scott says:

        This comment brings back memories of Daggerfall.

    3. Brandon says:

      Hexagon Based Minecraft, obviously. :)

    4. Jarenth says:

      Placing colourful shapes on it to the sound of a cheery upbeat musical theme?

    5. Ssalamanderr says:

      All of the above!

  14. Slothful says:

    You should probably add in something for rivers, unless you want vast expanses of nothing inland. Maybe some swamps too.

  15. Kale says:

    What graphics package are you using?

    1. Nathon says:

      It’s SDL with OpenGL, as I understand it from this.

  16. SteveDJ says:

    Your pseudocode paragraph is missing a condition – water next to land, or something (your image shows light blue vs. dark blue for the rest of the water). Is it that simple, or would your pseudocode describe it differently?

    1. Shamus says:

      Whoops. Yeah. Deep water is any water tile which also has only water as neighbors.

      1. SteveDJ says:

        What? So no sandbars lurking just beneath the water, to wreak havoc on our enemies’ (or our own) ships? (Ok, I have no idea what you are planning, but still…)

  17. Deadfast says:

    A very interesting read, I’m eagerly awaiting the next update. Best of luck with the project in the meantime.

  18. oxford says:

    First time caller, long time listener –

    I’ve really appreciated your explanations of the projects that you’re working on and your breakdown of some of the other procedurally generated stuff that interests you. If any of my profs in college had been as interesting and succinct I probably never would have left. Thanks for taking the time to post these write-ups.

    1. Johnny Hazzard says:

      You know with the experience Shamus has I bet a college would snag him up in a heartbeat. Ever done lectures before?

  19. TSHolden says:

    Why not render the water as a single massive rectangle positioned below the player? That way you can have underwater terrain (sunken castles = win) and if you’re far enough from the ocean, dynamically change the water level to allow for easy lake creation.

    This whole project is reminding me of Cube 1, have you ever checked into it Shamus?

    1. Psivamp says:

      That just makes me think of the movie Cube. Which was awesome.

  20. Pickly says:

    Gee, Shamus, your graphics suck. Especially that multicolored flat hexagon thing. if this represents the quality of the game as a whole, I have no interest in it whatsoever.

    (o.k., in actual seriousness, those images do look pretty cool, even using the bare bones colors. Like one of the comments above, and probably like a lot of people, I am curious what you’ll be doing with it, though I suppose the map will give a small bit to speculate about.)

    Also, (mostly unrelated) have you been checking out Achron at all? It seems an interesting idea for a game, if nothing else.

  21. Duffy says:

    This type of coding still amazes me. I can do win form apps and database work all day, but throw a few graphics concepts at me and I get all flabbergasted.

  22. Zak McKracken says:

    OK, I asked before: What do those hexes look like in close-up?
    They can’t stay planar, and I can’t imagine (read: am too lazy to make a drawing and figure it out myself) what they look like around sharp edges like cliffs or ridges and such.
    Also: If you have a straight cliff in the height map, wouldn’t you get a zigzak pattern in the Hex grid, because you shifted every other column in the cartesian grid to create a hex grid?

    And: Wesnoth FTW!

    1. wtrmute says:

      If you had a straight cliff, then yes, you would get a zigzag pattern. Fortunately, most formations in the game will either not be straight (because they are fractally generated) or they will need to zigzag anyway (like north-south roads, which must link adjacent hexagons).

      1. Pickly says:

        Shamus in previous procedural posts has talked about layering different scale height patterns, so it might be that he’ll do something similar here.

  23. Kdansky says:

    Since you were talking about speed: Please don’t hurt my professional mind by ignoring Knuth:

    “Premature optimisation is the root of all evil.” ;)

    1. Deoxy says:

      That reminds me of something awful, yet funny:

      As everyone knows, to get women takes time and money, so

      Women = time x money

      But then, again, as everyone knows, “time is money”, so

      time = money

      And replacing, we get:

      Women = money x money = money^2

      And, we all know that money is the root of all evil, so

      Money = sqrt(All evil)

      Replacing, we get:

      Women = (sqrt(all evil))^2

      And, simplifying, we get:

      Women = All evil

      It’s an old one, but I’ve been surprised recently by who hadn’t seen it…. heh. As I said, awful… but funny.

      1. Gravebound says:

        The LOVE of money is the root of all evil….but I guess that would ruin the joke. :|

      2. Daemian Lucifer says:

        Its even better if you use “money=sqrt(evil)” because then in the end you get “women=abs(evil)”.

    2. Shamus says:

      These are wise words.

      1. DaveMc says:

        Since we know that your wife reads these, you might want to make it extra-clear that you were replying to the “premature optimization” comment, and *not* the one about women. :)

        1. WJS says:

          What, does she not have a sense of humour or something?

  24. froogger says:

    Glad to see I’m not the only one excited about Shamus current coding-project. Following Procedural City grow into an awesome screensaver was great, and I sense this is going to be an even bigger deal.

    Man, you make it sound so easy – you’re a wizard of our time.

  25. Aelyn says:

    Just for the record, in case you’re wondering, I’ll buy your game the day you make it available. I’ll buy it as much for these posts and the general quality of your blog as much as anything. From you, however, I do expect a game that Does Not Suck.

    So… as you’re working out your budget, you can stick that in there.

    1. rofltehcat says:

      Yeah, Shamus. When can we finally give you our money? :(

      1. Scott says:

        I want to buy a Shamus product!

        1. Newbie says:

          Look at all this money just lying around my house… what can you do with it? BUY SHAMUS’ NEW AWESOME (NOT SURE WHAT IT’S ABOUT YET) HEX GAME! You think you’re under a spell? No that’s a Hex!

  26. HarveyNick says:

    Based on the image you’re using for your height map, I’m inclined to suspect that you’re using a standard square grid for your landscape topography and imposing the hexagons on top of. You’ve got me wondering if there might be anything in using a hexagonal topography to store the landscape data, though…

    1. Pickly says:

      He is, actually. (I think, its definitely a method that folds squares into hexagons.) See here:

      http://www.shamusyoung.com/twentysidedtale/?p=9669

  27. Yar Kramer says:

    I confess that I was among those squinting at the heightmap and trying to reconcile it with the splash of color. :3

    Also, my depth-perception was still sort of superimposing the heights indicated by the hexagrid onto the version without the hexagon-grid, so I didn’t notice how “flat” it looked until Shamus pointed it out.

    1. Aldowyn says:

      it took me forever to figure out the part with the “entire heightmap” went together with the height map. I THINK it’s inverted both dimensions i.e up is down and left is right.

  28. Will says:

    You know, if you keep the Hexagons flat (relative to themselves), you could reduce the Hexes to 4 triangles each instead of 6. I’m not sure if that would actually help rendering or not though.

    1. Miral says:

      You don’t get a point in the centre, then, which is useful to have. Besides, requiring the entire hex to be flat (even only with respect to itself) would make hills etc look weird.

      1. Will says:

        You can still have the point at the center, you just don’t use it to render any polygons.

        Requiring the hex to be flat would give the world a sort of tesselated look, so it would depend on how realistic you want the art style to be.

        1. bit says:

          Hexagonal minecraft?

          1. Will says:

            Hee

            Also; i just realised you wouldn’t need to keep the Hexes flat relative to themselves; in most cases a 4 tri Hex would look alright even when bent, certain circumstances would result in a real wierd looking hex, but those would be rare and probably catchable.

    2. WJS says:

      Creating a non-flat surface out of flat hexagons? I don’t see how that could possibly work.

  29. Fenix says:

    I like the way this is looking already.

  30. Susie Day says:

    The Hex project is really cool – My husband and I have been working on a similar thing but with squares and to be played top down, so it doesn’t need 3D, although I think that would be way cooler. Your posts have given me some ideas on how we could implement a height map. Also, hex is way cooler :-)

  31. Veloxyll says:

    I think the reason that it looks weird without the hexes at the moment is because there’s nothing ON the green ground, no trees or shadows or anything to say there is something on the ground, which would give it that contoured look. Even some sort of toning for different heights might do something – maybe just a brightness modifier, I dunno.

    Still, I do love reading your explanations of how you implement technology. They’re just so interesting and readable :D

  32. silver says:

    Too bad we never get to see the code :(

    1. HeroOfHyla says:

      Hasn’t the code been released for all of the previous projects on here?

      1. silver says:

        If it has been, I totally apologize for missing that – I thought I read everything in detail several times when he did procedural city, but it’s always possible I missed something.

        1. Bryan says:

          The code was made available at the end of both pixel city and the terrain project. Might be nice if the intermediate bits were also released, if you’re trying to figure out how to build something like this yourself — but it’s really not necessary, and it’s a fair bit of work to do that (unless you don’t mind letting them sit forever as-is, which I wouldn’t want to do), so I’m not too worried about it.

  33. omicron says:

    As another suggestion: Make heightmaps proportional to the scaling of the hex-grid. At present, you can see that terrain features predominantly seem to favor the Y-axis, due to the change in tile count. So unless you want all your game worlds to look like Westeros, build the map genrator to take this into consideration.

  34. Raygereio says:

    It’s amazing to me how different pictures 5 and 6 look; while all that’s different is the presence of the hexgrid.

  35. Jack V. says:

    That’s cool!

  36. Jericho says:

    I feel embarrassed to admit I’m a bid disappointed that you didn’t talk about the camera controls.

  37. Shrikezero says:

    How about this becomes a procedurally generated (possibly turn based?)rpg world? You start in “The Town”. Which would be the same for every starting character. All the terrain outside of town is procedurally generated. Mobs would be randomly generated with preset rules governing level/terrain. The game would contain a preset group of NPC towns that get randomly placed as the terrain is mapped. Randomly placed but with a set of distance/terrain rules so your progression of level specific quests would be feasably reachable. As you find towns you get the usual instaport/map point. In between could be completely random NPC towns unrelated to the quest line, but containing a localized sub-quest and unique vendors. If a player gets a really great map they can open it up to their friends and start new toons on the same map.

  38. Theo says:

    It is of absolutely no significance, but reading the posts back to back, I couldn’t help but notice that 388 is both the (vertical?) size of your grid and the number of caps Ms. Garret took from you.

  39. Damian says:

    I am absolutely flabbergasted at how fast you produce output.

  40. Elec0 says:

    This is looking really cool, I can’t wait to see what you do with it.

  41. MrWhales says:

    I remember saying in your last Kex post, i believe, about my curiousity of the accesibility for non-program related people with these posts, and the first 20-30 comments here all pretty much praise you for it, Shamus. I feel psychic now.

  42. xuberfail says:

    I’m sad to not see any cliffs. I hope there will be some non-sand water boundaries in the future.

  43. Blue_Pie_Ninja says:

    Looks great! :) It is giving me ideas to begin coding!

    And 100th COMMENT!!! WOO! XD

  44. WJS says:

    Am I the only one who’s curious about how the code for generating colours works? I’m imagining something like increasing the hue by the golden angle for each tile, but it’s obviously more than that, since I see both light and dark tiles in the image.

    1. WJS says:

      Hehe, after reading this post again, I was coming here to ask the exact same question, only to discover that I already asked it last time I read this. If Shamus ever reads this, I’d love an answer; I’ve actually implemented a similar system myself since last time, and like I said it simply uses a HCL colour model where H = (137.5 * n) % 360, but I’d be interested in seeing how someone else approached the problem.

      1. Shamus says:

        EDIT: Originally this comment stated I couldn’t find it. But then I did some digging. Here is the function, which will return 512 unique colors:

        GLrgba GLrgbaUnique(unsigned i)
        {
        GLrgba c;

        i = color_mix[i % 512];
        c.alpha = 1.0f;
        c.red = 0.3f + ((i & 1) ? 0.15f : 0.0f) + ((i & 8) ? 0.2f : 0.0f) – ((i & 64) ? 0.35f : 0.0f);
        c.green = 0.3f + ((i & 2) ? 0.15f : 0.0f) + ((i & 32) ? 0.2f : 0.0f) – ((i & 128) ? 0.35f : 0.0f);
        c.blue = 0.3f + ((i & 4) ? 0.15f : 0.0f) + ((i & 16) ? 0.2f : 0.0f) – ((i & 256) ? 0.35f : 0.0f);
        return c;
        }

        1. Shamus says:

          Looking at this again:

          Wouldn’t color #448 be BLACK? For example, the red channel starts out at 0.3. The 1 bit is clear, so we add nothing. The 8 bit is clear, so we add nothing. The 64 bit is set, so we… SUBTRACT 0.35? That makes the red channel -0.05. Are those subtraction operations a bug? Hmmm.

          And yet, I’ve seen all 512 colors on display at once, and I’ve never seen black. Not sure what I’m missing here.

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

Your email address will not be published.