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

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;

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;
}

}
}


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.

• Given that the planets have a random radius, you would need one grid for each radius, and even then you have to make sure that are not too aggressive with the grid sizes or else you end up removing entire grid squares that have some valid places. – Neil G May 24 '11 at 3:30
• The grid is only to provide a discrete list of points. A world can take up an arbitrary size. It doesn't have to be set up such that the spacing between grid units is the same as the radius of a world. – Tetrad May 24 '11 at 3:48
• Let's say that you don't have one validGridCoords for every radius, but you still want any point chosen from validGridCoords to be valid for an arbitrarily-sized planet. That means that you have to be very aggressive when pruning points. You have to prune them as if you are inserting the largest planet. Then, this will distribute small planets much more sparsely than they would otherwise be distributed — and possibly require more computations: O(PG) where G is the number of grid points and P the number of planets. Considering his solution is O(P^2 / p), I'm not sure this is better. – Neil G May 24 '11 at 4:03
• I've used that kind of solution for my own 2D space game random generation (nextstopnowhere.wordpress.com), and it can really work fine. Tetrad's proposed solution could be further improved by using space partitioning techniques to refine it, but I didn't need it. – jv42 May 24 '11 at 8:41
• Thanks for the responses, will give the grid approach a try! – omgnoseat May 25 '11 at 20:21

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.

• Well the problem is that my solution isn´t working at all, it doesn´t calculate any new locations. It just takes the first location and even if it is in the range it will still be placed. I was really wondering if there are any other methods to do this than the one I use. – omgnoseat May 25 '11 at 20:24
• @Martino: Your method is good; you just need to debug your code. Why don't you start by removing the recursion, and writing an iterative solution? (There is no reason why calculatePlanetLocation needs to call itself.) – Neil G May 25 '11 at 22:00

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
}