Defining a random irregular shape in a bool array

Question

I need to find out how to populate an array bool[x,y] with a random filled shape.

lets say I want a triangle depicted in my array i would define an area within the array and set all points to "true" that exist within the defined by 3 key points.

Now lets say my array is ... bool[100, 100] I want to define a shape with N(random) number of sides.

1. Plot N number of points within the array and set their values to true
2. set all points that represent a line between the current point and the next point to true
3. fill the shape by setting all inside points to true

Any ideas? I'm using C# and if it helps anyone Unity too. This is part of a much bigger problem so it doesn't sound like much but it will hugely help.

Thanks guys.

Answer 1

There are several things you can try for generating random shapes that are meant to represent islands.

You could modify your algorithm to make sure the resulting shape is convex. Although it's not required for the islands to be convex, I have a feeling that using it vanilla will lead to shapes that look odd as islands.

But more organic shapes are possible. Here are two suggestions:

Method 1

1. Generate one random point.
2. For each point in the array with at least one empty neighbor that you have not already processed, fill each empty neighbor with some probability.
3. Repeat step 2 until desired.

You can control the shapes and sizes of the islands with the value p that you choose. You need not keep p constant, it may work well to decrease it as you go on. You may also make it depend on the number of neighbors (for instance, make it proportional to the number of neighbors of the pixel you are processing).

You can (probably) make the algorithm more efficient by maintaining a list of border pixels, and another list of processed pixels. It becomes then something like this:

1. Generate a random point, and add it to processed list and border list.
2. While the border list is not empty and some other stop condition is not met: 1 Take the next point in it.
   1. Add the point to the processed list.
   2. For each neighbor of that point not in the processed list:
      1. Fill that neighbor with probability p.
      2. Add the neighbor to the border list.
   3. Remove the point from the border list

(Other possibilities are also possible if this is too slow.)

Method 2

Generate cloudy noise (or Perlin noise, as some people* mistakenly calls it) in an array of the same size, and then use a threshold function to make the island.

Check this out for generating the noise:

http://devmag.org.za/2009/04/25/perlin-noise/

http://devmag.org.za/2011/06/25/implementing-and-debugging-the-perlin-noise-algorithm/

To generate islands, you can use this algorithm

noiseArray = MakeNoise(100, 100)
for each pixel in noiseArray
   noiseArray[pixel] = noiseArray[pixel]^somePower //adjusts the gamma
   if noiseArray[pixel] < someThreshold
      boolArray[pixel] = true

You can control the shapes of the islands using the persistence value of the noise, the value of somePower, and the threshold value you choose.

You will need to modify it somehow to make sure you only get one island. You will have to play around a bit; one idea is to start in the middle, and do a spiral search until you find a filled pixel, and then make a new array, and fill it with pixels that are filled in the bool array only if they are connected to the first pixel (the one you found in the spiral search).

(*Including me in the article :( )