1

I am generating a 2D "world map" in Unity which I use C# and Perlin noise for. I have a Tile object that holds the graphic of the tile and position. There are a few more attributes to this class, but they are not of importance here. I have provided the base implementation below:

public class Tile()
{
    public GameObject tileObject;
    public Vector2 position; //Related to actual in-Unity position.
    public int Region;
}

I then generate a map by making two for loops fill an empty array with new Tile objects and instantiate the graphics. In this case there is a Tile[100,100]. The type of Tile is decided by checking the outcome of a Perlin Noise lookup.

Let's say that if the value is lower than 0.5, the tile is land and if it's higher than 0.5, it's sea.

We now have 10.000 objects inside of this array and I want to detect different regions now, such as region 1 and region 2. By regions I mean areas of land enclosed and separated by sea tiles. In the image below I have marked two of these regions in red and green:

enter image description here

Given an array[ , ], what is a good way to identify distinct regions of elements?

I tried to come up with an efficient solution but so far I have none, I have tried to implement the below process but the code was not suitable to post here:

Scan every row, [0,0] to [0,99]. [1,0] to [1,99] and so forth. Start with region number x.

  • Whenever a first land tile is found, check the region of the tile above it.
  • If there is none, or if it is a sea tile, or the above region is the same as x, assign its region to x.
  • When in the same row a sea tile is found, increment the region (x+1) . Then, when a land tile is found again, assign its region to the new x. and so on. If the land tile above is of a different number, assign that number to the region of the Tile.
  • Then, do the same but scan the columns first instead of the rows.

A different solution I thought of was to do the perlin map in smaller segments and instead of generating everything at once, do multiple generations of pieces of land (regions) and paste them on a sea map. But that would require another level of overhead and I'm quite interested in finding an efficient way of doing this.

2
  • 2
    You should be able to do this using the standard flood fill algorithm. Simply repeat it with an arbitrary land tile as seed (it'll be more efficient if it's in the middle of region, so perhaps use randomly chosen tiles?) using a different region number until all land tiles have been allocated to a region.
    – Jules
    Jul 19, 2016 at 12:34
  • That looks very promising indeed. Going to check it out straight away.
    – Zimano
    Jul 19, 2016 at 12:37

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.