Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
1  
The algorithm you describe is basically sound. There are a few technicalities that you need to take care of, but before you do that, you need to consider what exactly you mean with "random" shape. Is self-intersection allowed? Concave? Do you want (really need) a total uniform distribution of all polygons in that area? Are there other nice properties you'd prefer the polygons to have (or not have)? Also check stackoverflow.com/questions/6758083/… , but beware, (if they even work), they all generate polygons that tend to "look a certain way". –  Herman Tulleken Mar 31 '13 at 18:18
    
I think I rendered the problem outside my requirements by solving the issue another way ... essentially I am generating "floating islands" think avatar and you're on the right track, i needed to generate something with a random shape to add to my dynamic procedural world but i found a smarter way to handle it ... however I think the situation may apply to others ... I would say that the shape should not include excessively large angles between any of the sides and should form something that represents the edge of a land mass for a small island in a body of water. –  Wardy Apr 1 '13 at 22:29
    
OK, that makes things a little easier :) I will make a few suggestions in an answer below. –  Herman Tulleken Apr 2 '13 at 5:53

1 Answer 1

up vote 2 down vote accepted

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 :( )

share|improve this answer
    
interesting couple of solutions there, i'm already using a perlin noise type approach for generating the heightmap data in my island but the reason I needed the shape was to determine which parts of the x by z grid i wanted to cull to leave an irregular shape terrain. A terrain sat in a body of water would "automatically" by the lay of the water surrounding it get a nice "islandy" looking shape but I have this scenario without the body of water (hense my scenario for this question). –  Wardy Apr 2 '13 at 12:35
    
my problem was solved by generating 2 heightmaps "top map" and "bottom map" and i effectively invert the bottom map, when both maps are 0 then draw nothing, when 1 or more map is not 0 generate vertex information for that part of the island. This results in a nice irregular shaped island. But the problem of simply "generating an irregular shape" remained despite my solution. –  Wardy Apr 2 '13 at 12:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.