Help with random distribution script

[Lars-Kristian]

Hi everyone.

I am making a simple script that distributes game objects randomly inside a rectangle. I intend to share it with the community, but before I do so, I have to make sure the script runs nicely in every condition.

The main feature of this script is that the objects can be distributed using a density map (Texture 2D).

This is done by picking a random position and then get it’s corresponding value in the density map. The value is then compared against the threshold. If the position is valid, the object gets created, but if it’s not then a new attempt is made. This is done for every object until the desired amount of object is reached.

If the density map is really small or not existing at all, this approach fails or uses to much time to complete, since the algorithm wants to reach a specific amount of objects.

So my question is:
Is there a better way to solve this problem? Does it have a name?

Here is a picture of a 250 objects distribution with a density map shaped like the letter “A”.

[mgear]

Looking forward for that solution also…

I think somehow you would calculate density map pixel values in first pass,
then divide equal amount for each “density pixel” from the total amount… Oo

i’ve tried to do grass pieces distribution over mesh,
but currently there is no way to limit total max amount (expect stopping early when it hits the limit, but then some areas are empty)

ping: @hpjohn is usually the answer for math problems…

[Lars-Kristian]

Thanks for your reply.

I have tinkered some more with the script, but I have not been able to come up with a good and simple solution. The way it works now is more like a mask than a density map. The object placement is done during runtime so I think I am going to keep it this way for now.

Nice script, how do you do the on surface placement? ray casting from above?

[mgear]

yeap, currently its raycasting to surface (with random noise on the position)…

some ideas to check:
uniform distribution inside polygon (think mask as polygon area…),
blue noise / halton sequence,using tesselation/voronoi ?

[Lars-Kristian]

Thanks a lot.
Now I have a starting point.

[Lars-Kristian]

Awesome! I was able to create the desired result by using the Halton sequence.

[Lars-Kristian]

For those of you who are interested in this asset, here is a link to the download.

[Free]Random Distribution Tool

[hpjohn]

@mgear

ping: @hpjohn is usually the answer for math problems…

Hah, uhh okay

So i guess the problem you (were) trying to avoid is discarding positions that the randomiser gives you. With a mask with a lot of low chance areas, you get alot of retries. Without doing any research, I’d probably go for the methed I’ve posted about before, which is making an array of values, and then trying to match a random value to the array
For the linear case this might look like this:

But by changing the values in the array, you can make elements get picked more often, eg 0.0, 0.7,0.8,0.9,1.0
Any Random.Value from 0 to 0.7 picks the first element.

So for an image source, you would just construct the number line from your mask (converting to a cumulative 0->1 total), place a random value to get an index, then convert index to x and y position.

Would work like this:
Demo: __https://dl.dropboxusercontent.com/u/157182894/Builds/RandomMask/RandomMask.html__
Code:

Texture2D tex;
Color[] cols = tex.GetPixels();
float[] values = new float[cols.Length];
float total = 0;
for ( int i = 0; i < values.Length; i++ ) {
   values[i] = cols[i].r; // or g, b, alpha, etc
   total += values[i];
}
float cumulative = 0;
for ( int i = 0; i < values.Length; i++ ) {
   cumulative += values[i] / total;
   values[i] = cumulative;
}
float[] randomValues = new float[desiredCount];
for ( int i = 0; i < desiredCount; i++ ) {
   randomValues[i] = Random.value;
}
System.Array.Sort( randomValues );
Vector3[] resultPositions = new Vector3[desiredCount];
int placingIndex = 0;
for ( int i = 0; i < values.Length; i++ ) {
   if ( randomValues[placingIndex] < values[i] ) {
     resultPositions[placingIndex] = new Vector3( ( i % tex.width ) / (float) tex.width, ( i / tex.height ) / (float) tex.height, 0 );
     placingIndex++;
     if ( placingIndex == desiredCount ) break;
   }
}

resultPositons now contains desiredCount # vector3s , assuming the texture occupies space from 0->1 on x and y world axes

[Lars-Kristian]

Thanks you so much for using your time to create this algorithm.
It is a very nice solution to the problem, and it works in most cases.
This algorithm places object based on pixel position. So if a texture is 4x4 you only have 16 different positions to chose from?

If I understand your code the correct way?

1. Create cumulative values for every pixel.
2. Create number of random values. (same as number of objects)
3. Scan cumulative values until random value / threshold is reached.
4. Convert array index into position.

I also think it induces one small problem since we only have 255 values in one color channel.

1. If 2 values from the random value array are close to each other.
2. If the amount of cumulative values above 0 is small.
   Then the chance of 2 or more objects getting the same position is high.

This happens sometime in the demo you provided. But it can also just be a random thing.
Do you get a nicer result if you do not sort the random values?
But I guess the algorithm would be a lot slower then.

I am not trying to be rude or anything, I just wonder if there is some truth in my assumptions.
Thanks again for providing this code.

[hpjohn]

• Yes, places only on pixels, and only on the lower left corner of pixels at that. Additional randomisation could be easily implemented if you have really big pixels, but then you may get problems from …

• You can never get 2 in the exact same pixel position (even if they are big pixels) because the primary iterating loop is the pixel values, even if it places one on that pixel, it can;t place another until the next iteration. This does mean that if you try to place more than width*height objects, it will not get through them all.

• 255 values per pixel - yeah, but each value in the cumulative array only occupies a very small float disribution, do to the division by total on line 11, for a 256x map, each pixel takes a share of 65536 (for a completely white map).

• The effect of them getting placed very close is just a result of using a Random Value, sometimes you get close numbers. You have to use psudorandom to avoid this (which you do with halton sequence), I just haven’t come up with a way to use them in this way.

It’s a ways off perfect, but was interesting to apply this approach

[Lars-Kristian]

Maybe I do not fully understand the algorithm, but it is Nice to see a different approach to the problem.

EDIT:
My bad. I read.

cumulative += values[i] / total;

as

cumulative = values[i] / total;