Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

As a personal project, I'm trying to make a terrain generator that will create terrain looking something like the Castle Story smooth terrain.

If you haven't seen it before, here: enter image description here

So as you can see, it's combination of blocks and "smooth" blocks.

What I've tried to do to emulate this look is to give each surface block a mini heightmap. This generally works, but there are some issues, yielding a terrain like this:

enter image description here

The problem is is that each block is 1x1x1, but sometimes the height at a particular location is negative or > 1. In that case, I clip it and set the height to 0 or 1.

To better illustrate what I mean, here's a diagram: enter image description here

To generate the height, I basically do:

genColumn(int x, int z)
{
    int highestBlockY = (int)noise2d(x, z);

    bool is_surface = true;

    for(int y = max_height - 1; y >= 0; y--)
    {
        Block b;

        if(is_surface)
        {
            b = Block.Grass;
            b.HasHeightMap = true;

            // generate heightmap
            for(int ix = 0; ix < 5; ix++)
            {
                for(int iz = 0; iz < 5; iz++)
                {
                    float heightHere = noise2d(x + ix / 4, z + iz / 4) - y;

                    // clip heights
                    if(heightHere > 1)
                        heightHere = 1;

                    if(heightHere < 0)
                        heightHere = 0;

                    b.HeightMap[ix][iz] = heightHere;
                }
            }

            is_surface = false;
        }
        else
        {
            b = Block.Dirt;
        }

        setBlock(x, y, z, b);
    }
}

Perhaps I'm approaching this incorrectly by using the "true" perlin noise value?

Any help would be greatly appreciated!

share|improve this question
add comment

1 Answer 1

up vote 10 down vote accepted

Castle Story looks like this due to technical constraints: Were there to be a heightmap per each voxel in the entire volume, rather than only a heightmap per each surface voxel, storage cost would be vastly greater, on the order of O(n^3) which can be prohibitive, as opposed to a more favourable O(n^2), where n is the side length of a cubic voxel space representing your world. Bear in mind that heightmap information for subterranean voxels is implicit in the grid structure, so heightmap info need only be explicitly stored for those voxels which lie on the surface. So the Castle Story guys have snapped vertices to grid interstices to save on storage cost and mesh-construction complexity... read on.

First off, let's look at your options:

enter image description here

(1) is going to make things difficult for you, since in a single voxel column you only want mini-heightmap information for the topmost voxel -- refer back to the first paragraph for the reasons why. Looking at (1), the column on the right has heightmap information for both the topmost and the second-from-top (and this could apply to the third-from-top and so on, if the slope were extreme enough.). This is no good.

(2) Is probably a better option then; that is, ensuring that corner vertices snap to voxel grid interstices. But how then do we address the extreme slope issue? Well, we need to pick some gradient where we simply snap to a vertical column and thus ensure we have no gradients than can crosscut through n topmost voxels. A 45 degree gradient is the natural cutoff for reasons I explain below. So instead of (3), we'd have (4):

enter image description here

(4) Snapping the voxel's corner vertex to the nearest grid interstice is the solution. The visual effect -- diagonal aliasing -- can be seen in your screenshot of Castle Story. The cutoff slope for the voxels is a 1:1 gradient, or 45 degrees (as viewed orthogonally). Working backward from the solution, let's look at the reasons:

  • The only way we could have an unbroken, extreme slope, is if a voxel were vertically elongated...
  • .... But no voxel's mesh can exceed it's bounding area, irrespective of it's actual smoothed shape; a voxel needs to sit in a defined space in a 3D grid which accounts, if not for it's exact form, then at least for it's axis-aligned bounding box.

Another reason to approach it this way is that, as you've already discovered, not using snapping (discretization) leads to a range of geometrically complex surface smoothing scenarios, which are best avoided altogether... games of this sort generally do not require the degree of accuracy that a proper CSG algorithm would provide, which is the whole reason we are using voxels in the first place: Voxels make it far easier to work incrementally with volumes, than floating-point (continuous) polygon intersection / CSG algorithms do.

share|improve this answer
1  
+1 Well done as usual. –  Byte56 Dec 27 '12 at 15:30
    
Amazingly detailed! Thank you. –  untitled Dec 27 '12 at 20:18
    
I just tried implementing this, and I ran into some confusion - what do you mean by "interstices?" Do you mean the integral grid coordinates? –  untitled Dec 28 '12 at 5:49
    
@ThomasBradworth. "A space that intervenes between things." For 2D, if you have a n x n grid of cells, you will have (n+1)x(n+1) interstices. This extends directly to 3D. They are the "vertices" which bound each cell, which are mostly shared between multiple cells / voxels. If you boil it down to 1D (a line) then if both the cells and the interstices are represented as array, then cell 0 is bounded by interstice 0 and interstice 1, while cell 1 is bounded by interstice 1 and interstice 2... etc. –  Nick Wiggill Dec 28 '12 at 10:39
1  
That cleared things up! Thanks. –  untitled Dec 29 '12 at 20:59
show 5 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.