Project Octant Part 7:Slopes

By Shamus
on May 14, 2012
Filed under:
Programming

Now that we have a world based entirely around the idea of cubes, you know what we need? Slopes. This is something that’s been on my mind for ages. I’ve run around the Minecraft landscape and wondered, “What would this look like if the cubes could slope to form beveled outlines?”

octant6_14.jpg

Slopes aren’t really a foreign idea to an octree-based world. Minecraft has steps, which are basically slopes for the purposes of blocking light (they don’t) and collision. I want to take this one further and make slopes a part of the natural landscape. Like a lot of the stuff with this project, I’m not sure how well this will work out.

The trick here will be that the software needs to be able to look at a landscape and figure out which blocks should be turned into ramps, which ones should be turned into corners, which ones should remain cubes, and which way the slopes should face.

First, I need to set some parameters:

  1. Slopes should happen automatically. I’m picturing some sort of special block that has auto-sloping properties associated with it. For my tests here, I’ll be doing it on grass, but I imagine it would also apply to sand, gravel, and that sort of thing. I’ll be calling these blocks “soft” blocks. So now there are three states for a cube of space: It’s either solid (like stone) soft (like grass) or empty. (Like, air, see?)
  2. No deep analysis. When analyzing which way to slope, individual blocks can only examine their immediate neighbors, and not look at more distant blocks. Two reasons for this: First, there’s a tiny bit of overhead to looking up blocks. Alone, it’s not a big deal. But if every soft block needs to look two or three spaces away, then we’re talking about a LOT of lookups. Also, if the orientation of a block can change based on stuff happening three blocks away, then this might lead to madness and confusion for a player. Example: You change/remove a block in front of you, and 3 meters away a bunch of landscape suddenly changes. Yuck.
  3. Soft blocks must be blind to the orientation of other soft blocks. I want to orient all soft blocks in a single pass. If block A needs to know what block B is doing (is it sloping away from me? Towards me?) then that means I need to do block B first. But what if B isn’t done yet? What if B is waiting on C? What if B doesn’t exist yet because it’s on the edge where terrain is still being created / loaded? Since we’re doing this with an octree, we can’t count on blocks appearing in any particular order.
  4. These slopes are only for making hills. Walls will still run at ninety degree angles and we’re not going to slope ceilings. While it might be kind of interesting to make some kind of NURBS-based scenery, that’s not what I’m after today. Still, that would make for an amazing experiment. It’s insane how, over a year after Minecraft became a mega-hit, we’re still not seeing more people at least play around with these ideas. I think you could spend a year pumping out different octree-based cube prototypes and still not see everything this technology has to offer. I mean, check out Sea of Memes, where Michael Goodfellow was remixing Minecraft like a DJ. You could read through that series and run off with half a dozen game designs.

The solution I came up with is that the program will make one quick pass over the scenery. It looks for soft blocks.

octant7_1.jpg

Overhead view. Green = soft blocks. Red=hard blocks. White = empty space. It looks like this:

octant7_4.jpg

I apologize for how hard it is to make out shapes. This will stop being a problem once we have proper lighting.

It examines each soft block. If there’s another block on top of it, it’s marked as solid. If it’s surrounded on four sides by other blocks (soft or solid) then it’s marked as solid.

octant7_2.jpg

Now it runs through the soft blocks again, this time making them “lean” against any nearby solids.

octant7_3.jpg

This was kind of crazy. I spent a lot of time experimenting with rules for which blocks would slope, and under what circumstances.

Sadly, I got pretty wrapped up in the process and forgot about taking screenshots, so I can’t show you all the ways that this went hilariously wrong and stupid and was broken in ways that I hadn’t even considered. Here’s one example:

octant7_5.jpg

Two opposing slopes wound up next to each other. The resulting gap in the scenery lets you see through the ground to the… lava. (Disclosure: Not really lava, from a gameplay perspective. I just re-colored my checkerboard base with a lava texture for fun, and found it was super-helpful in letting me spot gaps in the terrain at a distance.)

Remember that when slopes are being created, they can’t query each other and see which way the others are facing, because those other slopes might not be in position yet. I could have it look for neighbors that have been set, but that would create relationships that are difficult or impossible for the player to understand. You’d wind up with stuff like, “If you’re building on an odd-numbered block on the world grid then the south-most or west-most neighbor dictates which way the slope will go, while on even-numbered blocks you’ll get…” And so on.

The upshot is that if slopes are decided by looking at neighbors, then a player would be able to build the same exact arrangement of blocks in 4 different places and end up getting 4 different results, depending on where their structures fell on the world grid and the powers-of-two scale. Madness. No, if this is going to work, then soft blocks have to make their decisions without regard to what other soft blocks are doing.

Not to keep you in suspense, I do manage to come up with a working set of rules that produces slopes and (so far) doesn’t seem to leave holes in the terrain. The result is a set of rules that is so complicated I can barely follow them. If I have to come back to this in six months I’m going to hate myself. Here is my little test scene, now with slopes:

octant7_6.jpg

Here is what that looks like in my example drawing:

octant7_3.jpg

Note the block in column 4, row 3. That’s an inside corner. To give you an idea of the complexity involved, here are the rules controlling this block:

  1. The northwest block must be empty.
  2. The north and west blocks must be soft. (We can’t know which way they’re facing, but we know they’re soft.)
  3. The northeast and southeast blocks must be non-empty. (Solid or soft.)
  4. The east, south, and southeast neighbors must be solid.

In code, it looks like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  //The diagrams below represent this cell (center) and the cells directly
  //adjacent to it.
  //# Indicates a cell that MUST be solid.
  //@ Indicates a cell must be non-empty. (Solid or soft.)
  //x Indicates a cell that MUST be empty.
  //? Indicates the contents of the cell are ignored.
  //S The cell MUST be soft.
 
  //    xS@
  //    S/#
  //    @##
  if (cell[C_NORTHWEST].Empty () && cell[C_NORTH].Soft () &&
             !cell[C_NORTHEAST].Empty () && cell[C_WEST].Soft () &&
             cell[C_EAST].Solid () && !cell[C_SOUTHWEST].Empty () &&
             cell[C_SOUTH].Solid () && cell[C_SOUTHEAST].Solid ()) {
    facing = FACING_NW_INNER;
    //etc... 
  }

Yes, those comments are really part of the code. The code on lines 13-17 might be the most complicated conditional statement I’ve ever personally written.

In practice, the world looks like this:

octant7_7.jpg

(Ignore the stray single floating blocks. I built those as part of my testing / screwing around process.)

octant7_8.jpg

Was it worth it? I dunno. It’s kind of different. I think the gameplay fares better than the visual aspect of the thing. You can run up and down these hills without needing to hop like Q-Bert, which makes getting around kind of fun.

octant7_9.jpg
Enjoyed this post? Please share!



2020202017There are now 97 comments. Almost a hundred!

From the Archives:

  1. Uscias says:

    I think there is a lot to be said for terrain that can be traversed without bunny-hopping like a madman. Also i wonder if and how this would work with ceilings (like in caves).

    • Adam says:

      Spoiler Warning: Minecraft! It must happen!

      • X2Eliah says:

        Ugh, no… There are already a buhzillion minecraft videos out there, why waste a SW season covering the game that literally has every single bit of it filmed and refilmed countless times.

        • ps238principal says:

          While the basics of the game (as well as any new features) get videoed to heck and back, new mods and “adventures” are being made all the time. Spoiler Warning could download one and let the crew have at it, giving everyone something to watch they might not have seen before.

          • X2Eliah says:

            There are also a buhmillion videos of all kinds of permutations of mods and adventure maps. Beyond the initial novelty (omg one single new thingie we can show for a whole 4 minutes!!), the progress and event-flow is exactly the same.

            • Elilupe says:

              They could do a one-off special episode in between seasons where Josh could start a new vanilla world and try to survive while the rest of the cast answer fan questions or something. Even though Minecraft videos have been done to death, watching Josh play it in his twisted way would still be hilarious.

  2. Primogenitor says:

    *cough* typo “insame” *cough*

  3. Benjamin says:

    Cool!

    Did you experiment with having soft blocks that touch no solids potentially leaning against nearby soft blocks?

    • Shamus says:

      Yes. In fact, that’s what I was originally hoping would work. It led to too many defective cases, and it made the terrain kind of “jumpy”. As you built, there would be a lot more shifting around.

      I’m not convinced that slopes without solids is *impossible*, but it does seem to be a more complicated problem.

      • Demo says:

        Have you looked at how some older sprite based games (Open TTD being the example that springs to mind) handle the problem?

        Their method is to compare each corner separately and then pick the appropriate sprite (or model in this case) that fits. Just mark each corner as ‘raised’ if the three adjacent blocks are non-empty and they put the appropriate model in place.

        The drawback of using this as written is that a block needs to be in a 2×2 region of non-empty to be seen, but this could be worked around by calculating slopes one level lower in the octree, or equivalently also comparing the centres of edges, marking it as raised if the adjacent block is non-empty.

        • Demo says:

          On further consideration this can be improved be finding heights for corners, then edges, then the centre.

          A corner has height 0 or 1 according to whether there is an empty block adjacent to it or not.

          An edge has height 0 if it is adjacent to an empty block, 1 if it is adjacent to a non-empty block and both of its end-points have height 1 and height 0.5 if it is adjacent to a non-empty block and at least one end-point has height 0.

          The centre has height 0.5 if at least one edge has height not 1 and height 1 otherwise.

          • decius says:

            How does that handle two blocks touching only at one corner? That corner has height 1, the edge is height 0, and the center is height .5.

            Considering all three neighbors, give the corner height 1 only if all adjacent cubes are filled, or if the two orthogonal squares are solid, otherwise 0. Give the midpoint of the edge value 1 if the adjacent cube is solid or both corners are 1. Else, If the adjacent cube is soft, the edge midpoint is .5. If the adjacent cube is empty the midpoint of the edge is 0. Give the center height .5 unless THIS block is solid. (Change the definition of solid to ‘hard or all eight adjacent cubes are filled’)

            A single block by itself becomes a small pile. A line one square wide is a half-height pile, while a line two wide is a full-height mound. Two diagonally adjacent

            A 3×3 plus shape becomes a half-height plus shape, while the 4×4 version
            OXXO
            XXXX
            XXXX
            OXXO
            produces a similar shape, but with full height.

            I see no reason to permit soft material being placed directly over nonsolid material- if soft material would be placed over soft material, move it to one of the empty adjacent squares (and iterate).

            Now piling sand gives us a pyramid of sand, rather than an obelisk.

            Also: terminology update is needed to describe soft blocks that are not solid. I suggest ‘granular’ or ‘nonsolid’.

            • Demo says:

              I possibly phrased that poorly. If there is an empty block then the corner has height 0. If not it has height 1.

              So the case

              10
              01

              would give a small valley.

              I really think that the soft/solid distinction is a logical trap which Shamus has dug himself into, so an algorithm which doesn’t rely on it is to be vastly preferred.

              Having stacked soft material ‘fall off’ to an empty space definitely sounds like the most sensible idea. If not then the above algorithm should still work, you would just get a hard edge like the one at (6,5) on the screenshot.

              • decius says:

                I don’t think there would be any vertical edge there. The inside corner cube would integrate seamlessly.

                Also, none of this applies to blocks flying in space. Mining out under and around soft blocks needs to happen in a possible manner, and that can handle tunneling up into the center of a big pile of sand. Collapsing the sand into the (arbitrarily deep) hole in the middle would be awesome, but beyond the current scope.

        • +1, Demo. SimCity 2000 was the first thing that came to mind when I started reading the article. Changing one block there could have… *cough* unexpected effects, but it was always cool. And the landscape looked really, really well.

      • Benjamin says:

        One of those things that seems like a good idea until you try it out and it falls on its face, I suppose.

  4. kikito says:

    Regarding the “The code on lines 13-17”, the problem of “using the right facing” has already been investigated.

    The “lots of ugly ifs” is one possible solution. But look at this:

    http://www.saltgames.com/2010/a-bitwise-method-for-applying-tilemaps/

    Up is 1, right is 2, down is 4, left is 8. That convention (and 4 additions) can replace all those ifs.

    • Caffiene says:

      I like it!

      Although it does seem like that tutorial page messed up the maths for their trinary example…

    • Tuck says:

      I use a bitwise method in a tile-based project for both selection of tiles (pretty much identical to what Shamus is doing, albeit in a 2D rather than 3D context) and at a later stage for collision detection.

      But it’s even harder to read the code.

      Day and night shots of a scene that could be (but isn’t, in this case) procedurally generated. Unfortunately I don’t really have the time to take this project much further.

      • kikito says:

        I’m doing one 2d tiles project too! That’s why I knew about the bit-wise stuff – I’ve reached the point on which I’d like to implement tile transitions, and I’ve been doing some research.

        Is the source code of your project available somewhere? I’d love to give it a look.

        EDIT: BTW, my code is here https://github.com/kikito/battle-cry

        • Tuck says:

          It isn’t, because I may pick it up again in the future. I have a lot of plans for it.

          • kikito says:

            I understand. Would you consider sharing only the bitwise method that you used for the tiles, then? That’s the part I’m interested in. I mean, the one I linked is cook with two kinds of terrain, but it doesn’t scale very well. I’m still looking for alternatives.

            • Tuck says:

              1. assign bits 1,2,4,8 to NSEW edges. I also use 16 and 32 for NW and NE corners — you may need SE and SW depending on your tileset.

              2. for each tile, check the if the tiles surrounding it (8 checks in all) are higher elevation to get a single edge value for the tile being processed.

              3. pull the tile from your tileset based on the single edge value — it’ll be different for every combination of edges on the tile. Note you can use this value as a modifier of your base tile(s) for the tile type, so you can use the same method for all different types with elevation changes.

              For example, a grass tile with a higher elevation to the north, northeast and east will have bits 1, 4, and 32 set — its single edge value will be 37. This will pull grass tile 1 + 37 (or more likely some conversion of that number) from the tileset.

              A dirt tile with elevations to the south, east and west will be 2, 4, 8 = 12, dirt tile 2 + 12. No need to use different bits, the changes in elevation are the same regardless of the tile type.

              The code is messy and only very roughly implemented or I’d copy and paste it for you. :P

    • Blake says:

      Very interesting, but I wonder how well it would translate into 3d since each edge would have 3 neighbours rather than one.
      You’d still need to check each neighbouring cube but you still might be able to add up points on each vertex or something and work it out that way.

  5. Tony says:

    Looking at the comments for the code, it looks like you could write a simple algorithm to check for that pattern rather than writing all the conditions yourself. Something like

    if (terrainAroundPositionMatches(x, y, “xS@S/#@##”)){
    facing = FACING_NW_INNER;
    }

    Would probably run somewhat slower than the conditions, though.

  6. ENC says:

    Actually looks a lot more natural now, great job.

    That was always a problem with MC where the terrain never looked good for ‘slopey’ hills so everything felt like a forest instead of expansive hills and the likes.

    Now it just makes me want to play some Tribes: Ascend…

  7. Daemian Lucifer says:

    In that second drawing,after this sentence “If it’s surrounded on four sides by other blocks (soft or solid) then it’s marked as solid.”,shouldnt the two blocks in 5th row from the top,in 4th and 5th column be solid as well?They are surrounded on 4 sides,but do have gaps diagonal to them.

    • jwwzeke says:

      Wondering the same thing as well. Either those two should also be marked solid, or you’re checking for all 8 surrounding blocks… or I have completely misunderstood something.

  8. Psithief says:

    Oh dear. That link to Sea of Memes led me to the part where he abandons the Oct-tree.

    Do you see any upcoming brick walls in your current project?

    • Blake says:

      The project is to make an oct-tree based world not make something of maximal efficiency.
      Learning which brick walls exist is largely the point I’d imagine.

  9. Jabor says:

    Perhaps a better approach would be to do slopes based on vertices rather than on tiles.

    Essentially each “soft” tile has four corners, and the trick is deciding whether each of those corners should be high or low. Each corner also borders three other tiles – two “neighbours” and one “diagonal”.

    Then for each corner, you have 18 cases to consider to determine the height of that corner.

    • Viktor says:

      This was my thought. You don’t care about the block as a whole until after you figure out where each corner(and the center) should go. Each corner touches 3 blocks. If any are air, that corner is down, if all are solid or soft, that corner is up. The center is up if all 4 corners are down or if all 4 corners are up, otherwise it is in the middle. Then you just make the system call the right block for each set of corners.

  10. Primogenitor says:

    I’m not sure I follow that example, e.g. why is that 2×3 platform not sloped?

    • Shamus says:

      Soft blocks must be leaning against solids to be sloped. This is for two reasons:

      1) Allowing a cluster of softs to slope without a supporting solid led to all sorts of gaps like the one above where you could see through the side of some triangle. There are a LOT of configurations of blocks that lead to messy outcomes.
      2) It looks kind of strange to place four cubes together and have them all collapse into a single spike.

      • Piflik says:

        So this is one part design and one part don’t-know-how-to-fix-it?

        I would do this in two passes. First determine which blocks (empty, solid, soft) are where, and second which block to draw on a soft tile. That way you would just have to test if the 8 surrounding blocks are empty (solid or soft doesn’t matter) to choose which type of slope to use, and it shouldn’t create any stray slopes in between.

        But since my whole programming experience are about 4000 lines of Javascript, I have no idea if this is too slow for your taste. Also at the far distance there would probably be some problems with wrong slopes that disappear when further blocks are loaded, but it should be barely noticeable and can easily be hidden in the distance fog…

      • TSi says:

        Why not break your sloped blocks into a more complex shaped block ? It would increase the polycount but at the same time erase most of your problems with these rules ( 2nd point). Either divide your cube vertically in both angles or also add an horizontal divide making it look like it’s made of 8 smaller cubes.

        Or your could also go for the Marching Cubes algorithm that looks quite interesting..

  11. Vorp says:

    I have been playing around with beveling, if you apply it in 3D in all directions it looks like this:
    Not so blocky

  12. Sumanai says:

    There’s a game on Desura called 3079 that has some kind of slopes. Don’t know if they have a practical effect since I think you can run up one block walls anyway. Although jumping seemed faster. Don’t know right now since I haven’t played it after the maker added an annoying penalty for dying (random item from your inventory is lost).

  13. Didero says:

    I don’t entirely understand how it works, but wouldn’t the Marching Cubes algorithm be suitable for this situation?

    • Nick says:

      Based on a quick look through that article, it’s way way over the top for what we’re trying to do here.

      The linked algorithm is trying to work on a field of continuous data (by which I mean values that can range between integers, 1.2 or 2.3), whereas in Shamus’ world things are in fixed block locations. Linear interpolation is really overkill and would take way too long.

      Basically, this algorithm is designed to have plenty of time to sit there and come up with a visual representation of a real-world piece of data like an MRI or other imaging scan. Shamus, on the other hand, is designing an algorithm that needs to run a lot of times per minute to update frames to the player.

      Hopefully that made sense to the non hacker…

      • Simon Buchan says:

        Actually, it’s a quantification of a linear field: essentially it throws away all data but “inside the surface” or “outside the surface” – so it’s pretty close to Minecraft style ground, except the “fill” values are at the corners of the cubes, unlike minecraft’s center. It’s also trivial to implement, roughly: for-each cube create an index, one bit from each corner, then lookup from a pre-arranged table what polygons to put there – simpler, in fact, than rendering regular cubes minecraft style.
        What Shamus has done here is close to be replacing the 2^(2*2*2) = 256 possibilities with what might be a 3^(3×3) lookup, but probably something like 2^(3x3x2) times greater to handle vertical arrangements correctly. Since that’s a ~5 billion item table (though probably far less with symmetry taken into account), I’m not surprised he’s had trouble with it :P.

  14. MadTinkerer says:

    “It’s insane how, over a year after Minecraft became a mega-hit, we’re still not seeing more people at least play around with these ideas.”

    I can think of at least three good examples to the contrary.

    There’s also some other voxel terrain based multiplayer game editor thingy I can’t seem to find the link for now.

  15. Simon Buchan says:

    Yeah, this looks like a job for a data table lookup, rather than custom code per case :|. I’m not sure how I would solve this exactly, but I get the feeling there must be a simpler breakdown: the “tiles” on the corner of blocks perhaps?.

  16. BvG says:

    Hmm…

    I don’t like your implementation. First, consecutive slopes still look jagged, because each sloped block also has some horizontal area, they’re not sloped completely. So the Hill example at the end still looks weirdly and “unrealistically” jagged. Same goes for your rule to simplify the code, yes it does not produce harder corner cases, but it also does not produce pretty terrain. Said that, this problem is actually a pre-3d one, solved many times in isometric landscaping. For example sim city 2000, which also cut some corners (harr harr) to ease the required amount of corner cases (In addition the terrain generator would often shy away from consecutive slopes, probably because it’s not possible to build road crossings on slopes):
    http://i1-games.softpedia-static.com/screenshots/Sim-City-2000_2.jpg

    When sloping as I would do it, you need 21 kind of slopes:

    The easy ones:
    straight outward north
    straight outward west
    straight outward south
    straight outward east

    corner to connect easy ones that meet at a right angle:
    corner outwards nw
    corner outwards sw
    corner outwards ne
    corner outwards se

    when there’s a single tile that connects two parallel slopes:
    corner outward tripple nws
    corner outward tripple wse
    corner outward tripple sen
    corner outward tripple enw

    sloping a single standing corner (note: most approaches disallow these, but use four inward corners to simulate a “single” top). Sadly i couldn’t find a single slope top example, but there’s a four by two sized one here:
    http://www.extensions.in.th/post_2008/open/tycoon2.jpg
    A-train is an exception, because the slopes where always unbuildable, so a large flat surface was not required (they also used very strongly rounded slopes, which makes for a nice visual effect):
    http://upload.wikimedia.org/wikipedia/en/9/99/Maxis_a-train_on_mac1.jpg
    corner slope all the way nwse

    then you have the inverted slope, which you need when two slopes meet at an inverted right angle, for them to connect to each other:
    corner inward nw
    corner inward sw
    corner inward ne
    corner inward se

    same with parallel depressions that meet at a single tile:
    corner inward tripple nws
    corner inward tripple wse
    corner inward tripple sen
    corner inward tripple enw

    As you might notice, some cases are not covered. For example shearing sites, like in your lava-see trough example. Those are soetimes covered by the terrain creation algorithm, and weeded out by not allowing that kind of slopes to show up in the terrain. Other implementations add a simple slope, producing no see trough terrain, but showing a pointy edge towards the nonmatching slope. A third approach, and most used is to have the terrain blocks actually be blocks, so sides are automatically covered with cliff faces, when exposed.

    For further inspiration, fire up roller coaster tycoon, and use the landscaping tools to create different kind of slopes.

    More examples:
    transport tycoon:
    http://users.informatik.uni-halle.de/~krause/Kassel%20Transport,%202.%20Nov%201924_4.png
    roller coaster tycoon:
    http://www.firingsquad.com/games/rct/images/out.jpg
    (note how one game is very flat, the other extremely hilly, both made by the same dev team within a short time period. This is probably because one focus on connecting long stretches, where the other is all about building vertically complex stuff)

    people creating visualizers for dwarf fortress have similar problems:
    http://www.mojang.com/notch/misc/rubydung/6.jpg
    http://www.minecraftforum.net/topic/178850-minecraft-seed-list/page__st__220

    • Shamus says:

      Actually, sloped blocks are simple 45 degree slopes. The effect you’re seeing is that I’ve colored the edges to seem rounded. Remember that we don’t have a lighting model, so if I didn’t have the fake edge the entire landscape would seem flat-shaded.

      Your proposal sounds like you’re suggesting each tile should have all the bevels it needs, like Tetris pieces. I shied away from this because this would make 1 tile > one triangle pair. But this might actually be a better technique. I’ll have to think about it.

      • decius says:

        Wait, you’re trying to save a couple of polygons per meter?! Are you designing for hardware from the late 90’s?

        The ‘hole’ case you pictured looks like it would be solved by treating sloped blocks as ‘clear’ for the purpose of deciding which sides to occlude based on being embedded in other blocks. I think that every block which fills less than the entire cube should be this way- you still get the major benefit of ignoring lots of stuff beneath the mountain.

        • Shamus says:

          “Are you designing for hardware from the late 90′s?”

          Do you live in a future world where rendering is free?

          Breaking the top of a cube into (say) five triangle pairs instead of one is a 5x increase in polycount on those surfaces. If you’re going for a long draw distance, that is not a move to be done lightly.

          “The ‘hole’ case you pictured looks like it would be solved by treating sloped blocks as ‘clear’ for the purpose of deciding which sides to occlude based on being embedded in other blocks.”

          That would fix the problem of seeing through into the void, but you’d still see through. In this case, you’d see through to the dirt block on the other side, which is still gonna look wrong. Unless you put sides on all the ramps, in which case now you’ve got even MORE extra polygons. Soft blocks will have tens of thousands of polygons facing each other beneath the surface, and under that you’ll have tens of thousands of dirt blocks being needlessly drawn.

          • decius says:

            Rendering isn’t free, but it costs what it has to.

            I think I was suggesting a maximum of five polygons for the top of sloped blocks (case
            xxx
            x/s
            xxx
            )
            Most cases would use fewer. There would be no change to solid blocks.

            As far as edges goes, I was wrong. If the height of any given corner is the same for each of the four blocks using that corner, then slope edges are never visible. That leaves the case of hard blocks adjacent to slopes, and whether they should have a zero, one, or two polygon side. I don’t see a way to make that determination faster than drawing two polygons.

    • Duncan says:

      Thanks for at least mentioning dwarf fortress. It bothers me that minecraft gets all the credit for this entire genre.

      • Dragomok says:

        Dwarf Fortress is a 2D (with top-down vision and ASCII graphics) tile- and layer-based is a total dwarven colony simulator with procedurally generated landscape, nations and history of surrounding world, where you play as an immortal, incorporeal overseer of such colony. In traditional sense, you cannot win, but you can lose.
        Minecraft is a 3D (with first person vision pixelated textures) block-based sandox game with emphasis on building and/or survival, where you play as a 1,7 blocks high chunky person. In traditional sense, you can neither win or lose, unless you’re playing in seperate ‘Hardcore’ game mode – then you can lose it.

        I don’t quite see how these two games can really fit into a single genre.

        • X2Eliah says:

          Indie games with low-end graphics, both use procedural generation techniques, both have no “game-end victory” conditions, both sufficiently different from mainstream aaa games.

          Broad definition, but still a valid bag to put them both into. Obviously not a genre, but then again, nobody in their right mind can call things like “rpg” or “action” a genre anyway…

        • Duncan says:

          Randomly generated voxel worlds with digging and building. I also include Terraria and a few others. Yes perhaps it would be nice to invent words for each as a sub-genre as they are all very different, but the genre hasn’t developed enough to have more than one game in each sub-genre. Also DF has adventure mode where you play a 1 blocks high chunky person with emphasis on survival. Building being added soon.

      • Darkness says:

        And it looks … terrible. Really. I have to put welders googles on to look at screen shots but then it is too dark to play. Which is a blessing.

  17. swenson says:

    I really like the last few images. Already it’s starting to look less Minecraft-y, if you were concerned about that. Still looks a bit odd in places, but that’s to be expected at this point.

  18. rrgg says:

    It still looks sort of odd and steppy doesn’t it?

    What if you tried treating the soft blocks as a single point .5 meters from each side and 1.0 meters off the ground (assuming the same size as minecraft blocks)? Then you could tell it to check for soft blocks in each of the 4 directions and draw a straight line between their centers.

  19. Lord Honk says:

    Well, this is a nice throwback to RollerCoaster Tycoon for me. Granted, those were only isometric but still, those slopes seem to work quite nicely in 3D as well. A step above simple blocks while still keeping a very stylized look. Looking forward to how navigating those will feel.

    Anyways, a very enjoyable to read post, hope your interest in the project keeps up so we can continue to feed on your musings.

  20. Anachronist says:

    One crude solution I thought of a while back is simply to ignore any cube vertex not touching anything and interpolate between the vertices that are touching other cubes, using a rough 2-triangle interpolation. Then just render the triangles.

  21. silver Harloe says:

    1. Slopes should happen automatically.
    2. No deep analysis.
    3. Soft blocks must be blind to the orientation of other soft blocks.

    This reminds of Conway’s Life in a lot of ways – except only doing one iteration. I saw an old version of it that could do arbitrary rule sets (i.e. rules other than Conway’s). The rules themselves were done as little bitmaps similar to the way kikito’s link above worked (except all 8 neighbors are considered). For Life, this meant 9 bits to represent your current state and the state of your neighbors and a 10th bit to represent your result state.

    For your terrain, have to replace the bit map with a something a little more complicated because you have 3 states (sold, soft, empty) and a gillion output states. On the other hand, we already know the value of the middle square (always soft) so yay.

    Say we go with:

    00 = empty
    01 = soft
    10 = solid

    Your example rule:

    // xS@
    // S/#
    // @##

    becomes the following 4 rules:

    00 01 01 01 10 01 10 10
    00 01 10 01 10 01 10 10
    00 01 01 01 10 10 10 10
    00 01 10 01 10 10 10 10

    Because @ means 2 rules (and ? means 3 rules)

    This may initially seem more complicated because you have to fill in all 6561 rules (you can use your ifs for that, though, or make a little app that displays all 6561 states and lets you pick the output)

    On the other hand, once you’re done, the rules themselves become numbers and you can do a single table lookup to determine output state.

    I guess it worked better for the Life app because there were only the 512 rules and they made a compact array of 512 bits. Our rule counting system here only uses 10% of the bit space for inputs, and requires more than a bit for output, so takes a little more space (either you waste 90% of an array, or make a hashtable).

  22. Retsam says:

    So, with this system, the terrain is generated, then it goes about making the top level of the generated terrain sloped, right? Would it be any easier if instead, after the terrain was generated, another layer of sloped blocks was laid on top?

    • Chargone says:

      to my complete lack of knowledge it sounds like it should be… though those ‘sloped’ blocks would need to include ‘not slopped at all, actually’ when the situation arises that one block needs to slope in opposing directions…

  23. Even says:

    Would using half-blocks to the same effect be out of the question? They wouldn’t obviously be visually all there, but they would solve the manuvering problem all the same.

  24. Volfram says:

    I think part of the problem seeing edges is because your textures are extremely noisy, and honestly… don’t look that great.

    Since this is the R&D portion of the experiment, I would imagine a texture which is more informative and less eye-candy would probably be in order. If you make your “soft” blocks a green field with a grid outline, and your “hard” blocks a brown or gray field with a grid outline, it would probably both be easier on the eyes(mine, anyway), and easier to tell exactly what’s going on with your blocks.

    I actually have a grid-like texture that I use for exactly this sort of thing, and I’d be happy to send you a copy if you’d like.(Warning: it’s purple.)

  25. Demo says:

    The more I think about your method the worse it seems to me. That you yourself don’t seem to be entirely clear on what is solid and what is soft suggests that you possibly attacked the problem backwards. That is

    1) Find out which blocks won’t be sloped.
    2) Put appropriate slopes on all the other blocks.

    The issue here is that you are looking at the result of the first step when trying the second. However since some block types and be flagged as not sloping (solid) despite being in a position where they would slope were they a soft block leads to oddness like that bug screenshot and also some rather ugly patching up, which is what I assume is why the block at (2,3) is a full height cube despite being on the edge of the soft area.

    Consider instead the properties we want in our sloping blocks. We are after some smooth looking scenery which can be run over without hitting an edge unless there is a height change of 2 or more. Therefore we would like the following rules to be obeyed.

    1) If a block is non-empty then it must have a point which is not at height 0.

    2) For a sufficiently large n by n square, the central (n – 2) by (n – 2) square should be of height 1.

    3) The scenery should be of continuous height. That is if any two blocks have a common point then that point should have the same height in both blocks.

    The first rule is fairly trivial to implement by requiring the centre point to have non-zero height and then filling in any other conditions around that.

    The second seems to have been your main focus. How you defined solid blocks before suggests that you were trying to optimise for the case of large flat regions before having dealt with the edges.

    However this has lead to major failures with the third rule. Relying on solid blocks to ‘lean against’ means that 2- or 1-thin ridges are just raised blocks, and also presumably lead to weirdness around non-sloping blocks. I don’t think there’s any way around that whilst relying on the notion of a solid block as being a reliable point of reference, and I would strongly suggest dumping the notion.

    • Demo says:

      Oh, also your method doesn’t satisfy your own second condition; that the orientation of blocks should only be affected by its immediate neighbours.

      Consider the arrangement

      0000000
      0111110
      0111110
      011×110
      0111110
      0111110
      0000000

      Then changing whether there is a block at x currently changes all of the blocks on the perimeter from cubes (if x isn’t there) to slopes (if it is). Whilst 2.8 metres isn’t quite 3 metres it is still the case that the exact behaviour you didn’t want is going to happen.

  26. Scott Richmond says:

    Oh man, this has been a problem i have been trying to solve in my head for probably a good year. There are solutions. Many. But I’ve yet to find an elegant one that covers all bases.
    The closest I’ve come is Marching Cubes or one of its more complicated cousins like Dual Contouring.
    The problem here is that the ruleset you need to apply is indeed very big. For your solution, I would probably think the best way to do it is to have a hash flag for every tile that is calculated based on its surrounding ~6 blocks. During render you look the hash up in a hash table for the correct ‘block model’ to use.

    Other than that, you need to deep dive Dual Contouring which is a wholely procedural way of taking your octree volume and spitting out a polygon-based shell. There are papers that describe flagging edges of blocks as soft or hard and the algorithm will smooth those edges over several blocks to create a hill in a blocky landscape.
    I’ve yet to see anyone take the time to pull this off correctly. :/

  27. Arkady says:

    I can’t help but think this problem is being over-thought.

    The key concept here is that we want top corners of soft blocks to match up with surrounding corners.

    I suggest doing this:

    Each block is hard or soft:*
    Each face of each block can be visible or hidden.
    Each corner of each soft block can be high or low. Each corner of each hard block is high.

    Pass 1:
    For each soft block:
    if each corner has a neighbour, mark that block as hard.

    Pass 2:
    For each corner of each soft block:
    If that corner has a hard neighbour, that corner is high.
    If that corner has two or three soft neighors, that corner is high.
    Else, mark that corner as low.

    Pass 3:
    For every side on every block:
    If there is a neighbour on that side, the side is obscured.
    If both corners are low, the side is obscured.
    If one corner is low and the other high, draw one triangle instead of two.

    That ought to make all the corners match up. The downside is that solitary soft blocks disappear (and cause z-fighting…probably best to make them a special case and just remove them altogether)

    It will give those four-block spikes that Shamus doesn’t like, but that is the behaviour I’d intuitively expect. If that isn’t the behaviour you’re looking for, how would you expect a quad of four soft blocks to look?

    *GET YOUR MIND OUT OF THE GUTTER!

    • Demo says:

      Pass 1:

      If you only require one neighbour of each corner to mark a block as hard then the following configuration

      1100
      1100
      0011
      0011

      (where 1 is a block, 0 is empty) would have the blocks at (2,2) and (3,3) both being hard, so you’d have a ridge.

      Pass 2:

      If you allow for only two soft neighbours to give you a high corner then the following configuration

      0000
      0010
      0110
      0000

      has a ridge around (2,2).

      Also you yourself mention the problem of solitary blocks being invisible. The problem is actually slightly worse in that an 2 by 1 ridge would also be invisible and for an n by 1 ridge you could only see the central (n – 2) blocks.

      • Arkady says:

        Your comments on Pass 1:

        Good point. How about:
        – If a corner has a hard neigbour, that corner is hard.
        – If a corner has two or three soft neighbours, that corner is hard.
        – Else that corner is soft.

        If a block has four hard corners, it is hard.

        Pass 2:

        I guess a face-to-face neighbour would have to make both corners on that face high. That would make 2 x 1 (and n x 1) ridges work. A corner neighbour would make that corner high only if that block is hard.

        I think that sorts out both problems you point out, but it’s much easier to spot problems in other people’s work.

        How about a 1 x 1 soft block creates a pyriamid shape with height 0.5?

        • Demo says:

          Fixing pass 1 has made the problem with pass 2 worse, since now none of the ridge if hard, so every corner only has one soft neighbour and all the corners are low. If you try and give a special case of two blocks forming an inverted V then you’re going to have ridges to the two sides of it.

          I’m not sure exactly what you mean by “A corner neighbour would make that corner high only if that block is hard.”, so I don’t know if that’s fixed the other issue with the second pass or not.

          A half height pyramid for a lone block does seem the most sensible behaviour. Really though we would like to see this behaviour emerge from our rules on the heights of various points of the block, rather than needing to pre-program these special cases as that is much more likely to work in all cases, rather than finding some weird other case which hasn’t been considered. I think the method I discussed near the top of this thread works from that point of view, though of course there may be issues I haven’t thought of.

          • Arkady says:

            I think I’ve missed what we mean by “ridge” here. In cases like:

            EEEE
            EESE
            ESSE
            EEEE

            I’m really not sure what it should look like, let alone how to define it. Yes, the point where all three blocks meet will be high, but that’s OK as they all sort of lean on each other.

  28. Jon says:

    This reminds me of when somebody first added slopes to the doom engine. (I think it was the ZDoom engine). For a while, trying to figure out how to add them to levels using existing tools, you’d get weird half-slopes and clashes all over the place.

  29. Andy L says:

    You could have saved a lot of head ache by tracking corners instead of blocks then you could have applied one of the simple variations of The Marching Cubes.

    In its simplest form Marching Cubes is just a simple lookup table that returns polygons based on the solid/not-solid status of the corners. (Notice that a cube has 8 corners that can be on or off, so the lookup key is a handy 8bits)

  30. Mr Guy says:

    I’m sure it’s a “cross when you come to it,” but I wonder if these slopes will make a 3rd person character difficult to render…

  31. void says:

    Sauerbraten doesn’t really get enough notice out there amongst indie game developers. They built a really frikkin’ amazing octree based engine… It supports real-time multiplayer alteration of meshes, sloped surfaces (to a surprising number of degrees), and is generally keen. … such a shame they mostly waste it on a Quake 3 clone.

    I keep toying with the idea of doing something with their renderer, but the state of the infrastructure in their engine has always been pretty tragic.

  32. Alex says:

    I was thinking, wouldn’t it be possible to calculate blocks based on height? You run calculations on the highest block in each hill. The game would calculate in “height level”, and the first (highest) block it comes across is solid. It then calculates the next “height level”, and sees if there are new blocks that are not adjacent to the previous highest block. It then makes these blocks solid. Any adjacent blocks to our first set of “highest” blocks are soft, sloped up to the highest block.
    This contintues on down.

    However, this would create that same tearing effect, where lava pokes through, especially at places where two slopes meet at the bottom of two hills ^^

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!

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