How can I generate random positions without them being too close to each other?

[1mpek]

Intro

Hello,
so I was working on a little project where there are bananas that you need to count, they appear on the screen and it’s random. But sometimes those bananas overlap or are very close so it’s hard to count.

Godot Version

So this is the code for spawning the banana.

Question

I don't know how to spawn them randomly and having them far enough from each others. I've tried raycast and failed, doing by hand with keeping the last banana position but it wasn't efficient with many bananas and collision so it would self-collide but it wouldn't work

---

Sometimes the bananas spawn far enough like this one:

---

But sometimes they can spawn too close:

I can provide more info if needed, but my code and many things are very messy…

[iOSxcOder]

Maybe use array to store x pos , then check new random x if < x + tolerance > , if so add to array else new rand number , after queue_free delete from array to free up x range for new rand number ?

[1mpek]

Oh so if I understood well you want to check each x position each time its generated with the array? I just want to be sure i understood your help.

[soapspangledgames]

There are a variety of ways with a variety of difficulties. The easiest way I can think of that still provides a degree of perceived, but controlled, randomness is to place a bunch of markers at appropriate locations where bananas can potentially spawn (thereby guaranteeing they can never overlap), then randomly choose markers when generating your problems.

[flaxRabbit]

This has been inspiring and it made me discover Halton sequences. I shared the code here on the forum but I think it’s an overshoot for your project.
What I would use in your case is a accept/reject sampling, with a decreasing distance threshold over time.

2D Halton Sequence in GDScript

Hi! With the help of Claude.ai I (it?) created a script that will fill the viewport of random points according to Halton Sequence. They are used to reduce clustering in uniform sampling → the points are distributed more “uniformly”. For normal people, I recall that true uniform distribution naturally generates clusters, so to avoid them we must avoid uniform sampling. To use the code, you can create a new 2D scene, add the script to it and start the game. It will print instructions on startu…

[bulentbaday]

I think you can split the frame into grid cells. For example, if your window size is (800, 600), generate a random number in range 0..8 than multiply it by 100. And apply the same to y axis. This way, you can ensure that the positions are far enough apart.

The only problem is that more than one sprite can be in the same cell, you can manage it by saving previously generated positions into an array and chek them.

The second problem is that they are all placed in an orderly manner, which may not look appealing. To address this, you can add or subtract a smaller random number. This way, you’ll get a more scattered appearance.

[iOSxcOder]

Yes , for each new position you check if is not overlap with existing . I’m sure there are more methods , but with randomness only way to check not hit twice same number is to check is number was previously used .

[lastbender]

@bulentbaday

I think you can split the frame into grid cells. For example, if your window size is (800, 600), generate a random number in range 0..8 than multiply it by 100. And apply the same to y axis. This way, you can ensure that the positions are far enough apart.

The only problem is that more than one sprite can be in the same cell, you can manage it by saving previously generated positions into an array and chek them.

The second problem is that they are all placed in an orderly manner, which may not look appealing. To address this, you can add or subtract a smaller random number. This way, you’ll get a more scattered appearance.

I think this solution is the best way for you. Just to build on it, to make it more structured, here is my suggestion. Please note that I didn’t try it. I’m just ballparking. You may have to do some adjustments.

• Decide the mininum distance between each banana, make it a variable like var min_dist : float = 100

• Then decide your banana spawning window boundary var boundary : Rect2 = Rect2(position, size)

• Create an array to save the cells that already has a banana var used_cells : Array[Vector2i]

• Then generate a random integer for each axis from 0 to floor(size.x/(2 * min_dist)) and 0 to floor(size.y/(2*min_dist)). Save is as a Vector2i. Let’s call it grid_pos : Vector2i .Do this in a while loop until the generated grid_pos is not in used_cells.

• Add (append) the randomly generated grid_pos in used_cells

• Now to fine tune the position of banana, so that it won’t always appear on the grid line, generate a random float for each axis from - min_dist/2 to + min_dist/2. Let’s call this offset_pos:Vector2

• Last step to calculate the actual position of the banana position = Rect2.position + grid_pos * 2 * min_dist + Vector2(min_dist, min_dist) + offset_pos

[PotatoArmor]

@1mpek You could add an area node to the banana scene. The area node will be used to check if it is within another banana’s area node. If the area nodes are intersecting then the bananas are too close and they should select another random position.

[iOSxcOder]

Just quick demonstration from my experience because used randomness in chunk creating and this it one of the thing :

14x14 grid , used randf with 3 variables - at least two color are placed next to each other

(0.8826, 0.6614, 0.3815, 1.0)
(0.9853, 0.6359, 0.6957, 1.0)
(0.5272, 0.3878, 0.3977, 1.0)
(0.6718, 0.3829, 0.9983, 1.0)
(0.5067, 0.8293, 0.6158, 1.0)
(0.4544, 0.6597, 0.6227, 1.0)

[OleNic]

BlockquoteThere are a variety of ways with a variety of difficulties. The easiest way I can think of that still provides a degree of perceived, but controlled, randomness is to place a bunch of markers at appropriate locations where bananas can potentially spawn (thereby guaranteeing they can never overlap), then randomly choose markers when generating your problems.

Randomize which marker and then randomIze a small offset from the marker, to add a little spice to your approach
Cheers !

[1mpek]

Well it worked for me (for now- we never know)

TIPS
just don’t be stupid like me and don’t use float, because the numbers can be really close to each other. (it can give like 300.25 and 300.84) so yeah do not use float

also don’t put a separation that is too big because in my case my canva was 1000px and the separation was 150 and there can be 10 bananas so it won’t work as 1000/150= 6.6
6.6<10 so it would crash since it can’t find a number.
(won’t mark as the answer since i’ll try the other methods)