Sign in to follow this  
SirWeeble

Hoping for help - smooth 2d Terrain.

Recommended Posts

I'm working on a sidescroller. Tile based infinite terrain using perlin noise. That part works fine. Easy. I'm having issues with my method of smoothing the terrain tiles.

 

Right now, I'm using a method that pulls the neighboring terrain info as a bool - then putting it in a bool[5,5]. Then decide which terrain tile to use (as in the shape of the slope, not whether it's dirt/rock etc), I need to check these bools.

 

My resulting code looks like this. This is just a random example, the numbers i put are just random meaningless, but the structure is the same in my code.

int GetSlope( bool[,] ter )
{
int returnData
if( ter[1,3] & ter[3,1] ) returnData = 1;
if( ter[5,3] & ter[5,2] & !ter[4,2] & !ter[4,1] ) returnData = 2 ;
if( term[5,3] & ter[5,2] & !ter[1,1] & ![ter[2,1] ) returnData = 3 ;
and on.. 
and on.. 
}

The the return data gives me a number that indicates which tile-shape to use. Another bit of code (based on the perlin) gives me the soil type (like dirt/rock/etc)

 

The problem being, I'm checking a bool[5,5] to decide what tile to use. I've done this before with a bool[3,3] and it took FOREVER. There are hundreds of combinations with a [3,3]. Even more with a bool[5,5].

 

Just to further explain, I made a visual representation.smooth_Terrain_Explain.png

The black spot is the current-terrain that needs a tile texture. Green = neighbor is terrain. Red = neighbor is empty. Grey = either/or. 

 

So, the problem isn't how to do it.. but how to do it better. If I go forward with this, I'm going to spend weeks typing out the seemingly infinite permutations. It took several mind-numbing days to do it with a [3,3].

 

Hopefully my explanation of what I'm doing is good enough to understand. I feel like it's not. If not, ill try to elaborate.

 

The only other idea I have is somehow calculating the slope, but I can't figure out how'd I'd even start to do that without resorting to an endless bool check again.

 

If anyone has a better idea of how to approach this, I would be eternally grateful.

Share this post


Link to post
Share on other sites
Hmm, "eternally grateful" eh? That's a long time smile.png

I can see you have lots of on/off patterns (2^24 on first sight, which is 16,777,216), not something you'd even consider doing by hand.
In case like this, I usually start writing scripts and other short programs to help me in generating some sort of table (like the one you started in the post).
After I am done, I then have some code lines I insert into my program.

As for your problem, you didn't explain how you get values 1, 2, 3, etc in the returnData. I assume they are tile numbers of some kind, but how many do you have, and what forms exist?
If you have a rule when one tile fits on a pattern, you can program it, and test each tile against each possible pattern automagically. Depending on which tile fits, you can generate an "if" line like you showed.
(However, there exist much smarter ways to do the selection. But first just worry about bit patterns to tiles. Once that is solved you can focus on smart tile selection.)

Another direction you can consider is to work in reverse order. For each tile, can you give a general 5x5 bit pattern where some must be on, some must be off, and other 'dont care'? (Depends highly on the number of tiles that you have.)
If you do that, add the decisions into some table, then try each of the 16,777,216 patterns to check if you missed some patterns (and how many).

Share this post


Link to post
Share on other sites

I think I'd do something with this general process.

 

1) Get a list of all edge tiles of a certain terrain type.

 

2) For each tile, calculate the slope of a line from tiles a certain distance to the left and right. Lets say we have tiles A-E, with coordinates [0,0], [1,1], [2,2], [3,2], [4,3] respectively, we can get the slope at tile C by considering tiles B and D: (2 - 1) / (3 - 1) = 1/2

 

3) Assign tile C a certain tile image according to it's slope

 

I haven't tried this before but I think this is a good start. You'd probably have to tweak the way slopes are calculated. Here's another option:

 

i) Find the slope from tile C to all other edge tiles within a certain range, then assign C the average of those slopes. Since your terrain tiles would be selected based on slope, and an average might not give a simple fraction, choose the terrain tile whose corresponding slope is closest to the average.

 

The choice between these really comes down to the level of detail you need. In general, the more tiles or information you consider, the smoother your edges will look.

Edited by jdean300

Share this post


Link to post
Share on other sites

Maybe not eternally grateful, maybe one lifetime of gratitude. After that, all bets are off.

 


As for your problem, you didn't explain how you get values 1, 2, 3, etc in the returnData. I assume they are tile numbers of some kind, but how many do you have, and what forms exist?

 

You're right about the tile number. It's just the index of a split-up image. I don't know the number of sprites I'll have. From previous experience with my 3x3, it ended up being alot more than i thought, which made me go back, add more, re-number the indexes, etc. Rinse, repeat. So now, I have 128 indexed images, the majority are blank and I planned on adding them as I slowly wrote the possible combinations. The program just doesn't know they're blank, so i can alter the file as-needed.

 

All in all, its not really 2^24 combinations. At least not hand-written. Any that i don't specify if it requires ter[x,y] as true or false just default to "doesn't matter". there's also some overlaps where I only need to check one difference since it falls through to the next check. Regardless, it's a lot of combinations and confusing to sit here and write in boolanese for hours on end.

 

I'm trying to have tiles for the angles with slopes of 1/1, 2/1, 1/2. Of course the 2/1 and 1/2 each require 2 tiles.  There will also be rounded corners, single tiles, nothing-above/nothing-below tiles, and the various permutations of that. Basically a lot of tiles and alot of combinations.

 

While you didn't specifically say it.. you did give me a bit of an idea with your approach to the issue. I'm trying to find a coding solution, but perhaps it's more of a tools solution. I could, for the time being, make my program read from an external text which holds the bools in some format. Then I could make a tool that manually adjusts those conditions via clicking buttons to set the "bool grid" to true/false or grey - so it will update real-time in the program. However, that's alot of work, but it's probably much less work than sitting here typing in boolanese for weeks.

 

dJean: I thought about something like this, and i can find "edges" by seeing if a tile exists, and the above tile does not. However, the problem arises that sometimes there's overhanging tiles in the 5x5 grid Maybe I have a flat terrain and then a single tile poking down in the middle of the grid. So something like this is possible, but I'd have to check for adjacent tiles in relation to the origin tile so I can ignore the free-floating ones. This is a possible solution too if i can figure it out..

Share this post


Link to post
Share on other sites

One lifetime is enough tongue.png
 

there's also some overlaps where I only need to check one difference since it falls through to the next check

Indeed, I expect lots of overlap in the bit patterns. This is what I meant with "Smart selection methods". In general, you want the computer to figure this out for you rather than do it yourself.
(working hard to avoid work smile.png )
 

I'm trying to have tiles for the angles with slopes of 1/1, 2/1, 1/2. Of course the 2/1 and 1/2 each require 2 tiles. There will also be rounded corners, single tiles, nothing-above/nothing-below tiles, and the various permutations of that. Basically a lot of tiles and alot of combinations.

You can do such matching automagically too.
Assume some line with a slope. try to fit it on every pixel (or every few pixels) in the bit pattern by computing which bits are 'bad' (not covered), and giving out penalties for such bits, for example some value multiplied with the squared distance of the bit with the line.
Similarly, you can punish 'missing' bits. If you then pick the bit pattern with the lowest penalty, you should have a good match. for the sloped line at the position you started with.
 

make my program read from an external text which holds the bools in some format.

Oh definitely do that. I wouldn't build a "click buttons" program, but ymmv.
You can also generate "if" lines from your file, just use "print" to output text that looks like the program smile.png
 

Share this post


Link to post
Share on other sites


You can also generate "if" lines from your file, just use "print" to output text that looks like the program

 

Ah! Genius. Make my program write my boring code for me. When it's all setup right, copy-paste into the source.

 

The automagic style line-tester system might be a good place to start before i try to go off and make a one-off tool for this problem. I could probably fit the majority of the tiles into this kind of system and use a penalty idea like you mentioned. Then i can deal with the trouble-makers by hand.

 

If i get it working right, ill post some screenshots. Thanks for the tips and the fresh perspective!

Share this post


Link to post
Share on other sites

Instead of using arrays of bools, realize that an integer already is an array of bools.

Imagine for a second that you had a 3x3 bool grid of neighbors - that's 9 neighbors. Except, the center pos is ignored; a tile is not it's own neighbor. So you have 8 neighbors.

8 bools is a uint8_t. i.e. a single byte worth of bits:

//One byte:
0000 0000

//Is:
000
0 0
000

Now, you're talking about 5x5. So, you have 24 bits. A uint32_t integer is 32 bits - more than enough.

00000
00000
00 00
00000
00000

A single 32 integer:
0000 0000, 0000 0000, 0000 0000, xxxx xxxx (last byte ignored)

Basically, then your comparisons are just int to int comparisons. Computers have been specializing in those since the dawn of computing. wink.png

 

You can then use a 2^24 array to map your neighboring to your result. Such an array would be 64 megabytes.

 

Your function could then look like this:

int GetSlope( uint32_t neighbors )
{
    //Make sure the caller is ignoring the top byte.
    neighbors &= 0x00FFFFFF;
    
    return lookupTable[neighbors];
}

Then you have a file that your editor loads that looks like this:

00000
00011
11x11    = 53 //The tile to use.
11111
00000

00000
11000
11x11    = 158
11111
00000

00000
00011
00x11    = etc..
00011
00000

00000
00010
11x10    = etc...
11000
00000

Any slope not described in the editor is auto-initialized to an error tile, so you can see it in the editor easily.

 

The editor could have an easy to use interface for adding new mappings of neighboring-to-tile.

 

If you want, you could also auto-detect mirrors of a pattern if it's not defined, and by-default just mirror (horizontally and/or vertically) the tile you place down.

Share this post


Link to post
Share on other sites

Servant: interesting solution. This kind of method hadn't crossed my mind. The problem with it is it will require a full-on 2^24 solutions, since I'm using true,false, and "doesn't matter", which allows more catch-alls.

 

Regardless, I've got the code functioning now. I just used good old-fashioned if/else, structured cleverly as to catch as many combos as possible when falling through to the next statement. It ended up being about 70 lines compared to my old 3x3 one what was written poorly and had several hundred. I also had more tiles in the 3x3 one. 

 

There are still a few straggler tiles that get caught with a texture they shouldn't have or i don't have a tile for yet. Seems like only a few, but that could balloon as i progress or find graphical combinations that don't work. If so, i'll have to retreat and try a more sophisticated method.

 

Link to the prototype. Ugly colors so I can see what's messed up and what's working.

 

http://postimg.org/image/jvs8tolmt/

 

The red tiles have 6 variants (hard to see) a "no-neighbor" left, right, top, bottom, left/bottom, right/bottom. The bottom tiles will have a jagged appearance to them, while the top ones will be smooth. I'm going to be using oversized tiles to eliminate the need for separate single-row tiles and rounded-corner tiles. The red tiles will appear flat when lined up in a row, but their overlapped edges will be rounded. So if a single one is floating in space by itself, it will look like a different tile.

Edited by SirWeeble

Share this post


Link to post
Share on other sites

Servant: interesting solution. This kind of method hadn't crossed my mind. The problem with it is it will require a full-on 2^24 solutions, since I'm using true,false, and "doesn't matter", which allows more catch-alls.

 
If you are only using a few options, you'd just use a std::unordered_map<NeighboringBits, TileToUse>;
 
However, since you want to ignore certain tiles, you can use a uint32_t for the neighbors to match, and a second uint32_t for the neighbors you care about to use as a mask by ANDing the mask to the map's neighbors.
 
So you're still passing in 32 bits of neighbors, but do a lookup like this:

//First 32 bits = mask, second 32 bits = neighboring
typedef uint64_t NeighborsAndMask;
typedef unsigned TileID;

const TileID NoMatchingSlope = TileID(-1);

struct SlopeMatch
{
    uint32_t mask; //Every '1' is a neighbor we care about.
    uint32_t neighbors; //If '1', must be a neighbor, if '0' must be no neighbor.
    TileID tile; //What tile to use, if this is a match.
};

std::vector<SlopeMatch> Slopes;

constexpr bool MatchesSlope(SlopeMatch match, uint32_t neighborsInMap)
{
    //Compare just the bits we care about.
    //NOTE: You can skip the first '& match.mask' if you make sure
    //      'match.neighbors' already contains 0's for tiles it doesn't care about.
    return (match.neighbors & match.mask) == (neighborsInMap & match.mask);
}

TileID GetTileFromNeighbors(uint32_t neighborsInMap)
{
   for(SlopeMatch match : slopes)
   {
      if(MatchesSlope(match, neighborsInMap))
      {
          return match.tile;
      }
   }

   return NoMatchingSlope;
}

 
Your text file describing these can be:

'-' = ignored	'o' = empty	'x' = object

-----
oooXX
oo.XX = 53
--oXX
-----

 
Basically, you're doing this:

int GetSlope( bool[,] ter )
{
    int returnData
    if( ter[1,3] & ter[3,1] ) returnData = 1;
    if( ter[5,3] & ter[5,2] & !ter[4,2] & !ter[4,1] ) returnData = 2 ;
    if( term[5,3] & ter[5,2] & !ter[1,1] & ![ter[2,1] ) returnData = 3 ;
    and on.. 
    and on.. 
}

 
I'm suggesting you do this:

int GetSlope( uint32_t ter )
{
    int returnData
    if( ter == 0101010101011 ) returnData = 1;
    if( ter == 1110101111111 ) returnData = 2 ;
    if( ter == 1110100000001 ) returnData = 3 ;
    and on.. 
    and on.. 
}

But with the '001010101011' stuff being loaded from file, so it's data-driven (but you can hardcode it if you want to).

And then I suggest you do this:

int GetSlope( uint32_t ter )
{
    for(potentialSlopes)
    {
       if(ter == potentialSlope) return 1;
    }

    return NoMatchingSlope;
}

However, if your current solution is working fine for you, good!

 

I'd still suggest you make this optimization to your current code:

int GetSlope( bool[,] ter )
{
    and on..
    and on.. 
         if( term[5,3] & ter[5,2] & !ter[1,1] & ![ter[2,1] ) return 3;
    else if( ter[5,3] & ter[5,2] & !ter[4,2] & !ter[4,1] ) return 2;
    else if( ter[1,3] & ter[3,1] ) return 1;
}

...because there's no need to continue checking every 'if' once you find a match.

Share this post


Link to post
Share on other sites

With 128 possible tiles you only need one byte per entry in your lookup table which is just 16 MB, not 64 MB. That doesn't seem like a bad trade off to get O(1) lookup times.

 

That said, if the lookup table approach uses too much RAM then we should be able to get O(log n) lookup with some clever nesting of the "if" statements. The idea here is to design a kind of binary search algorithm where at each step you examine a particular cell and narrow down the potential patterns until you reach the one and only pattern left. The cells that are examined will be different depending on which branches get executed but a given cell should never be examined more than once. Any cells that don't matter to the final pattern may not be examined at all. The result should be a monster set of nested if statements like so:

if (ter[1,1]) {
    if (ter[1,2]) {
        if (ter[2,1]) {
            return 1;
        }
        else {
            ...            
        }
    }
    else {
        return 2;
    }
}
else {
    if (ter[2,1]) {
        return 3;
    }
    else {
        if (ter[3,1]) {
            ...
        }
        else {
            ...
        }
    }
}

The trick to making this work, of course, is figuring out the optimum order to do your checks. I would not want to do that by hand -- I'd suggest you write a tool to do that for you. The tool should examine the possible patterns, figure out which cell position results in the most even split of the possibilities, and output an "if" statement. Then it can recurse for the case where the cell is filled and the case where the cell is empty, using the smaller set of possible patterns each time. Note that if the chosen cell doesn't matter to a particular pattern then it will be included as a possibility on both sides of the branch. When the set of possibilities is narrowed to a single pattern, output a "return" statement for that tile number.

Share this post


Link to post
Share on other sites

Starfarer:

 

This is what i basically ended up doing after a lot of bumbling. As the script grew, it became more unmanageable and I ended up playing wack-a-mole with various ill-fitting terrain pieces. Change one, another would get screwed up. So I had to remove problem pieces 1 at a time and go back with a system like you mentioned above.

 

I also ended up using a blocky style of art, which helped with the transition between different tiles. I originally wanted to do a shadowed style that faded into black, but there were too many combinations that had the exact same neighbors (as in on/off neighbor, not graphic), and their only different was the neighbor's tile image - which I didn't want to store, access, and read.

 

The script is still ugly and fairly difficult to read, but the important part is that it works and it's also fast.

 

Link to a screen-grab of part of the terrain:

 

http://postimg.org/image/3nnm5uk4v/

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this