# check if there are planets in the vicinity [duplicate]

I'm trying to make a random galaxy map in gamemaker, with several planets at random places. The problem I have run into is that some planets will be too close together. I need a way to put a minimum distance between them, but I can't figure out how to do it, or where I'm going wrong in the code.

I use the following script to make the map (argument0=amount of planets of this type to create and argument1=the object under which this type is located):

var i;
var MinDistance
var ToCloseFlag
var planetx, planety

for (i=0;i!=argument0;i+=1)
{
do
{
do
{
do{
planetx=random(room_width);
}
until(planetx<room_width-64 && planetx>64);
do {
planety=random(room_height);
}
until(planety<room_height-64 && planety>64);
}
until(place_empty(planetx,planety))
MinDistance=400;
ToCloseFlag = 0;

with(argument1){
if (point_distance(planetx,planety,other.x,other.y)<MinDistance)
{
ToCloseFlag=1;
}
}
}
until (ToCloseFlag=0);

if place_empty(planetx,planety)
{
instance_create(planetx,planety,argument1);
}


}

Any help would be greatly appreciated.

You need to use some spatial partitioning in order to check for distance before consider a random position "good". Binary space partitioning can be useful: you construct a tree structure that you query before adding a position to get the closest one; if the closest is far enough you put the position into the tree so it will checked against the next position. If the current position is not far enough you reject it.

Take into the account that as you insert positions, the probability to reject the next position increases...

A differen aproach is to "cheat" by partition space before computing position. You can create a dense grid where each position is far enough from its neighbor, then you place randomly your planets in this grid. If the number of grid is large compared to the planets, you wont see the trick.

You can add some randomness to your grid by putting extra space between contiguous cells:

Let say you want L to be your minimal distance, then you can put your grid cells apart by L+2*e; When you choose a cell, you can set the position of the planet to the center of the cell adding some random noise (at most e). In the worst case of two consecutige cells chosen and maximum random displace applied one toward the other, you will get L as distance.

In the above picture you can see how wider grids allow for random position within an area that assure you the required minimum distance even if position are placed the nearest possibile.

The tradeoff of this aproach is that adding randomness (e) you loose available cells and vice versa.

• This is exactly what I needed. I made the grid and randomly added or subtracted 10 pixels from the starting position of the planets. It works. It works beautifully. Thank you for your answer. – Twistervise Jan 20 '14 at 21:10