Filling in gaps in a grid

Question

I have a set of terrain sprites available to represent terrain:

• Flat
• North-South Straight Cliff (x 2 allowing for slope direction either way)
• West-East Straight Cliff (x 2 allowing for slope direction either way)
• Convex North West Cliff
• Convex North East Cliff
• Convex South East Cliff
• Convex South West Cliff
• Concave North West Cliff
• Concave North East Cliff
• Concave South East Cliff
• Concave South West Cliff

There source for my terrain is a height map that I am looking to represent with contours made up from above sprites. The cliff tiles would be placed on the below-threshold tiles that border the above-threshold ones. However when I split the height map by threshold I get terrain features that are impossible to represent with the tile set, for example:

    .....
... 1 1 1 ...
... 0 0 0 ...
... 1 1 1 ...
    .....

Where 1's represent tiles that are above the threshold and 0-tiles are below. My sprite set lacks the tile to represent either immediate neighbors (in this case North and South neighbors) being above threshold.

I am looking for a good approach to get rid of these cases. I have already tried just looping through all columns/rows looking for 1 0 1 combinations and changing the height map value to be above the threshold. In the end, I don't really mind the way the "gaps" are filled in, as long as the end result can be represented with my tile set.

Remember cases with diagonal gaps must be considered. For example:

    .....
... 0 0 1 ...
... 0 0 0 ...
... 1 0 0 ...
    .....

Also cannot be represented with my tiles set.

Finally, I'm also looking for a scalable solution to this problem. If I require to use and even more restrictive tile set that requires 1 (0 x n) 1 gaps to be filled in, as in the two above-threshold tiles can be n below-threshold tiles away from each other.

P.S. Apologies for my previous poorly worded question.

Answer 1

One solution is to start the terrain with one type only (e.g. all 0s or all 1s), and "paint" the other type on progressively, noting the ones that you need to change into "cliffs" or "transitions". If you ever need to make an impossible cliff, resolve it by either "promoting" the cliff or discarding the thing you're trying to paint and move on.

For example, you can start with 0s:

0 0 0
0 0 0
0 0 0

Start painting the 1s, noting the cliffs you have to make

(1)c 0      1(1)c      1 1(1)
 c c 0  ->  c c 0  ->  c c c  -> ...
 0 0 0      0 0 0      0 0 0

Then when you find that you need to make an impossible cliff (e.g. both north and south facing):

 1 1 1
 ? c c
(1)c 0

You can either promote the impossible cliff to a 1 (noting that this could set off a recursive process due to the promoted 1 creating new impossible cliffs):

 1 1 1
(1)c c
 1 c 0

or you can cancel placing that 1 and move on:

 1 1 1
 c c c
(0)0 0

Answer 2

In the case you are still looking for a postprocess you could do it like this : What is different here is that it looks for [0] values instead of [1]

//Enclose this in a for loop of all your values(or just use an index of the [0] at 
//creation
if(yourValueAtIndex == 0) {
    int[] sourroundingsOneValues = selectSurroundingOnes(); // only the [1]
    int counter = 0;
    for(int i = 0; i < sourroundingsOneValues.length; i++) {
        //for each [1] value
        if (AllneigboursVal != 1) //direct neighbours is only 2 values in a conf of 8
            counter++

        if (counter >2) { // if i have at least 2 ones alone around my 0
            yourValueAtIndex = 1; // then i set my zero to 1 to connect them
            break;
        }
    }
}

This is a stripped down version of what you could implement