Generating random values, keep trying till value within bounds are generated

Question

Sorry for the strange topic name, couldn´t think of a good way to describe it. I´m basically trying to achieve the following:

I'm placing items randomly on the screen, but these items shouldn't be placed near eachother at a given distance. This is the process I have in my head right now:

• generate a random location
• check if this location is not near any other objects
• it is near -> start the process over to generate a new item (till it is not near anymore)

I've run into this scenario multiple times but could never think of a way to efficiently do this, while I do feel that there is a simple way to do it. Here is the implementation I have right now. I feel like I should use a while loop but I can't get my around how to do it. The code is in AS3 but that shouldn't matter.

public function generatePlanetsFromXML(xml:XML):void 
    {
        planets = new Array();

        for (var i:int = 0; i < xml.projects.project.length(); i++) {

            var planet:Planet = new Planet();
            planet.data = xml.projects.project[i];
            planet.radius = (Math.random() * 20) + 20;
            addChild(planet);
            addObject(planet);

            planets.push(planet);

            calculatePlanetLocation(planet, i);
        }

    }

    private function calculatePlanetLocation(planet:Planet, i:int):void 
    {
        var randomX:int = (Math.random() * (worldwidth - planet.width)) + 20;
        var randomY:int = (Math.random() * (worldheight - planet.height)) + 20;

            //get a location that isn't close to another planet
            //keep looping till the distance is higher than minimum distance
            for (var j:int = 0; j < planets.length; j++) {

                if (i != j) {

                    var dx:int = planets[j].x - randomX;
                    var dy:int = planets[j].y - randomY;
                    var distance:int = Math.sqrt((dx * dx) + (dy * dy));


                    if (distance < minPlanetDistance) {

                        trace("retry getting location..");
                        planet.alpha = 0.3;
                        calculatePlanetLocation(planet, i);

                    }else {

                        //distance is fine, planet can be placed!
                        planet.x = randomX;
                        planet.y = randomY;
                    }


                }else if (i == 0) {

                    //first planet should always be placed
                    planet.x = randomX;
                    planet.y = randomY;
                }

            }
    }

Answer 1

As you can probably imagine, the biggest problem with that approach is that you don't have any idea how long it's going to take to populate the world. If you're unlucky, the random number generator can make you do several times the amount of calculations than you would need to do given a strict iterative approach.

One way you could work around it in this situation is by using a grid. Maintain a list of all the valid grid coords to place a world at, and every time you place a new world you remove the coords that are no longer valid from this master list. That way you only have to pick a random spot once since all spots you are picking from are valid.

Basically, the algorithm would look something like this (in really rough pseudo code):

int[] validGridCoords = AllGridCoords();

function PopulateUniverse()
    for( 0..NumPlanetsRequired )
        if ( validGridCoords.Count < 1 )
          break for loop;
        var CoordToPlaceAt = validGridCoords.RandomElement();
        SpawnPlanetAt( CoordToPlaceAt );

function SpawnPlanetAt( int coordToSpawnAt )
    // initialize planet
    var planet = new Planet( coordToSpawnAt );
    foreach( var gridCoord in validGridCoords )
        if( gridCoord is close to new planet )  // you could use Manhattan distance here
            validGridCoords.Remove( gridCoord )

Update: as NeilG rightly is alluding to in the comments, this naive solution has a few problems. For one, if your "is close" number is relatively small (i.e. around the radius of your largest allowed planet) or proportional to the radius of the planet, you can run into situations where you place a "large" planet on the edge of the valid areas and it might reach far enough into the prepopulated area to either overlap into the "too close" area or even overlap an entire planet. There are a handful of fixes for this:

1) Sort your incoming planets by largest to smallest. That way, if your "is close to new planet" distance is at least the radius of the largest planet you won't actually get any overlaps. You might get touching planets though, unless you also do...

2) Instead of picking a single point, pick an area of points that your planet fills. This is more computationally expensive, but the effect is that your planets won't bleed into the prepicked "not valid" areas.

Either way, you probably want to do #1 if your distance between is small and your planets are varying in size dramatically. You'd be doing a lot of computation, but the real value with an iterative algorithm like this is knowing when you can stop. With a pure random solution, if your density is high, your placing function is non-deterministic. Knowing that your map is too full (by not having any valid spots to pick from) means that you can handle that error condition, as opposed to blindly throwing darts at a board.

Answer 2

Your solution is fine provided that you never end up placing so many planets that the number of valid locations falls to, say, below 10% of the locations (which is very very dense.)

Let's figure out how many operations you will end up doing to place a planet given

• x planets already placed
• p the probability that a randomly chosen location is valid.

Then, the number of retries is geometrically distributed with probability p, and therefore the expected number of operations is 1/p.

So, if you keep p above 10%, you expect no more than 10x operations on average for each planet, or 10x^2 in total.

One optimization you can make is to keep the planets sorted by radius, and check in that order. The sorting cost will be offset by the savings from being able to stop early.

Answer 3

This is a really bad question, you are asking about efficiency while your real problem is that your code simply doesn't work.

In applicable situations discard and retry is a great method for heuristic generation. You can't beat the simplicity, and it's not bad performance in all cases.

Basically you try to place the planet when you have done just one check, rather than after doing all the checks. Your code is broken beyond that, but I'll leave out the details.

What you need to do, in pseudocode:

function calculatePlanetLocation(){
    validposition=false
    while(!validposition){
        position=generateposition()
        validposition=true
        for each planet{
            if(too close){
                validposition=false
            }
        }
    }
    planet.position=position
}