# Filling in gaps in a grid

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.

• Fill the 0s in what way? Replace them with 1s? What are you trying to accomplish? What have you tried already? Please edit the question with more information. Dec 17, 2013 at 22:14
• It sounds like you're just asking for a flood fill algorithm. Dec 17, 2013 at 22:18
• Had a look at flood fill and it's not quite what I'm looking for. I'm not looking to fill the area, but to get rid of/fill in gaps between cells with value 1
– Sash
Dec 17, 2013 at 23:16
• So, you want to connect the 1s? So that every 1 has a path to every other 1, without touching a 0? Dec 17, 2013 at 23:16
• No, not necessarily. My goal is to map sprites onto this grid and having two 1's (tiles above threshold) one "0" tile away from each other is not allowed by the tile sprite set I have, as in I am unable to represent such an arrangement with my sprites.
– Sash
Dec 17, 2013 at 23:22

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.

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
• Woah, haven't thought of it that way. I already have an algorithm to generate the contours but didn't consider editing the terrain at that point. have always thought of it as a pre-processor step. Thanks!
– Sash
Dec 18, 2013 at 23:52

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