Scatter Algorithm

Question

I need to randomly scatter a variable number of objects in a Flash movie. Just randomly choosing locations doesn't result in a visually pleasing output. Objects end up on top of each other, all clumped together on one side, etc.

I'm looking for something similar to the algorithm that Photoshop uses to create a Difussion Dither when converting an image to Bitmap mode.

Answer 1

A low-cost method: generate some sort of underlying repeating pattern (e.g. a grid) and then perturb the locations. This will give the appearance of randomness with some regularity included:

Pseudocode ahoy:

for(x=0; x<max; x+=step) {
    for(y=0; y<max; y+=step) {
       location = x*step+random(randsize), y*step+random(randsize);
    }
}

Experiment with step size and randsize until it looks good to you.

Note this doesn't preclude overlaps; to do that, add a random amount between adjacent x's, or look into something like a Voronoi graph of random points, or generate a series of random points and remove overlappers, or...

Answer 2

Random is never random enough, is it? :) It might be worthwhile to explore a pseudo-random number generator. There is an excellent implementation/example here: http://lab.polygonal.de/2007/04/21/a-good-pseudo-random-number-generator-prng/

Try it out with some seeds until you find something that is visually pleasing. Good luck!

Answer 3

If you don't have that many objects, this is crude but workable:

var myObjects:Array;

...

for (var i = 0; i < myObjects.length; ++i) {
    var overlaps:Boolean = true;
    while (overlaps) {
        // Pick a random location
        myObjects[i]._x = Math.random() * WIDTH;
        myObjects[i]._y = Math.random() * HEIGHT;

        // Make sure it doesn't overlap any object that has been placed
        overlaps = false;
        for (var j = 0; j < i; ++j) {
            if (myObjects[i].hitTest(myObjects[j])) {
                overlaps = true;
                break;
            }
        }
    }
}

Some caveats:

• If you have a lot of objects (thousands or more), this might take a while, since it has to check all the other objects.
• It's possible this method will result in an arrangement where the next object cannot be placed anywhere because all possible locations result in an overlap. In that case, the program will hang. This problem is more likely when there are more objects and/or the objects are large.

Edit: Revised code slightly so it's for AS2, not AS3