[Solved] Randomly Generated Objects that do not Overlap?

Newbie & Debugging Questions
#1 
  What I'm trying to accomplish is to have planets with randomly generated positions, but are at least 400 pixels away from each other. In the code below what I'm trying to do is create an object, iterate through the whole list making sure none of the objects collide, and if so set a new position and check again. All that nonsense that starts with Math.sqrt is the distance formula so that I can check how far away it is. The code below is also NOT in an infinite loop, it is done upon creation of another object.

for (int i = 0; i < 300; i++) {
			planetList.add(new Planet(
					rand.nextInt(40000 - (0 - 40000) + 1) + 0 - 40000, rand
							.nextInt(40000 - (0 - 40000) + 1) + 0 - 40000, PlanetSelect,
					planetWhiteRegion, planetGreenRegion, planetRedRegion));

			for (Iterator<Planet> planetIter = planetList.iterator(); planetIter
					.hasNext();) {
				Planet planet = planetIter.next();

				if (Math.sqrt(planetList.get(i).getX() - planet.getX())
						* (planetList.get(i).getX() - planet.getX())
						+ (planetList.get(i).getY() - planet.getY())
						* (planetList.get(i).getY() - planet.getY()) < 400) {

					planetList.get(i).setPosition(
							rand.nextInt(40000 - (0 - 40000) + 1) + 0 - 40000,
							rand.nextInt(40000 - (0 - 40000) + 1) + 0 - 40000);
					}
				}
			}
#2

The trial-and-error approach can work, but may not be fast or yield a good looking result.

The ‘best’ way to get evenly-spread minimum-distance sampling is poission disc sampling:


The easier way is ‘blue noise’ sampling:

#3

Thank you for the sources! This is much better than getting straight up answers! ;D
And that Youtube channel has all sorts of different videos on game development math, I LIKE IT!

#4

Remembered another way: plot points on a grid and randomly jitter them a little bit. Square grid is easiest, but a hex grid often looks closer to what you get with poisson:

This is equivalent to the blue noise approach in the video, in the case of a square grid.

#5

Well good sir, I have tried and failed at doing math. Could you possibly point out and explain what is wrong? My planets are 240 in width and height, and I’ve tried my best to adjust all this math to fit that, but I just don’t fully understand it. I also wanted to create exactly 300 planets, but I ended up with 225 because again, I don’t understand this math at all. Many planets come close to intersecting or intersect, and so I would like a nice padding of at least 100 pixels which I’ve been trying to figure out how to do for the past 6 hours. Also, I’m using the Blue Noise method since its exactly the style of generation I was looking for.


		for(int i = 0; i < 15 ; i++){
			float x_min = -30000 + cellSize*i;
			float x_max = -30000 + cellSize *(i+245);
			
			x_min += 300;
			x_max -= 300;
			
			for(int j = 0; j < 15; j++){
				float y_min = -30000 + cellSize*j;
				float y_max = -30000 + cellSize *(j+245);
				
				y_min += 300;
				y_max -= 300;
				
				planetList.add(new Planet(rand.nextInt( (int) ((x_max - x_min) + 1)) + x_min, rand.nextInt((int) (y_max - y_min) + 1) + y_min, PlanetSelect, planetWhiteRegion, planetGreenRegion, planetRedRegion));
			}
		}
#6

Blue noise is hard. Sobel is easy.

#7

I have tried improvising on what I DO understand from the Blue Noise method, and ended up making a grid. All I’m trying to do now is figure out how to seperate each grid by at least 300 pixels in between each, because as of now they are all tightly compacted. Do you know of a way to seperate the grids?

int cellWidth = 480;
		int cellHeight = 480;
		
		for (int i = 0; i < 15; i++){
			int cellX = cellWidth*i-cellWidth;
			int cellX_Max = cellX + 480;
			
			for(int j = 0; j < 15; j++){
				int cellY = cellHeight*j-cellHeight;
				int cellY_Max = cellY + 480;
				int randX = rand.nextInt(cellX_Max-240 - (cellX+240)+1) + cellX+240;
				int randY = rand.nextInt(cellY_Max-240 - (cellY+240)+1) + cellY+240;
				
				planetList.add(new Planet(randX, randY, PlanetSelect, planetWhiteRegion, planetGreenRegion, planetRedRegion));
			}
		}
#8

Alright well I figured it out after some bit of testing, thank you all for the help! All I did to seperate the grid squares was increment the j and i variables by the amount of seperation I wanted instead of just i++. Thanks again for the help!

	int cellWidth = 480;
		int cellHeight = 480;
		
		for (int i = 0; i < 100; i+=5){
			int cellX = cellWidth*i-cellWidth;
			int cellX_Max = cellX + 1200;
			
			for(int j = 0; j < 100; j+=5){
				int cellY = cellHeight*j-cellHeight;
				int cellY_Max = cellY + 1200;
				int randX = rand.nextInt(cellX_Max - (cellX)+1) + cellX;
				int randY = rand.nextInt(cellY_Max - (cellY)+1) + cellY;
				
				planetList.add(new Planet(randX, randY, PlanetSelect, planetWhiteRegion, planetGreenRegion, planetRedRegion));
			}
		}

What this looks like (Basically a Scattered grid):

#9

Aside: Breaking space into a grid and generating uniformly random points inside is not blue noise. It’s not uniform either. It’s not even close to either.

#10

Either way, I still improvised from what I understood and made it work for my needs! ;D

#11

Well, I’ve been testing more on how to generate stuffs withought intersection, but I cant for the love of me figure out how to generate the planets in a circular motion. In other words, not have the square and pointed edges that I currently have. I HAVE created a way to make them not intersect and that works correctly, but I want to see how much better it looks in a more galaxy feel way. Any resources or tips?

#12

Instead of sampling in Cartesian space (x,y coordinates), try polar. Random angle between 0-2π, random radius (distance from center of cluster) between 0 and whatever the radius of your cluster is. That will give a circular cloud of uniform density, and you can play with probability distributions to get non-uniform densities.

Alternatively take your rectangular clusters and trim them into whatever shape you want. (i.e. filter by distance from center, perhaps with a soft threshold) This would actually be easier.

#13

Sorry for replying back to you so late, how exactly would you make this in a rand method and how would I calculate it to be more dense? I’m sorry if this question is exactly what you answered I just need it in an actual rand method to see what you’re talking about. :clue: I’m sorry for being a doofus.

#14

BurntPizza: your design will not produce uniform density.

Take the set of points that is in the lowest 10% of the radius: these will be spread over a circle with an area 1% of the full circle.
Take the set of points that is in the highest 10% of the radius: these will be spread over a ring with an area 19% of the full circle.

#15