koobas.hobune.stream
Can't get game objects to instantiate at random positions without overlap - please help!
So I actually have posted this a couple of places and am going to try my luck here. First I apologize for the very long post -- just wanted to be thorough. There is a TL;DR at the end if you just want to look at that and the code.
A friend and I are working on a game that starts off by randomly spawning some planets into a scene. Further, we would like to spawn each object such that it does not touch or overlap with any other already placed game object (planet). We have scoured the forums and other resources and tried many different things but no matter what, even if it works perfectly several times in a row, there will always eventually be a layout where planets overlap. First, some code:
public class Game_Controller : MonoBehaviour
{
public List<GameObject> planets;
public GameObject planetPrefab;
public float MinY = -120;
public float MinX = -500;
public float MaxX = 600;
public float MaxY = 640;
float x;
float y;
float sizeX;
float sizeY;
float mass;
float rotation;
Vector3 position;
Vector3 size;
private void Start()
{
CreatePlanets();
}
void CreateRanges()
{
//Creates random position for planets, stored in "position"
x = Random.Range(MinX, MaxX);
y = Random.Range(MinY, MaxY);
position = new Vector3(x, y, 0);
rotation = Random.Range(0, 360);
//Creates random sizes for planets transform.scale
sizeX = Random.Range(10, 70);
sizeY = sizeX;
size = new Vector3(sizeX, sizeY, 1);
//Check to see if any planets will collide with this position. This is where we are having issues.
position = CheckPlanetPosition(position, (sizeX*2));
mass = Random.Range(100, 2000);
}
// CreatePlanets() generates and instantiates the planets
void CreatePlanets()
{
for (int i = 1; i <= 15; i++)
{
//Debug.Log(i);
CreateRanges();
GameObject newPlanet = Instantiate(planetPrefab, position, Quaternion.Euler(0, 0, rotation));
newPlanet.name = "Planet " + i;
newPlanet.transform.localScale = size;
newPlanet.GetComponentInChildren<Rigidbody2D>().mass = mass;
planets.Add(newPlanet);
}
}
private Vector3 CheckPlanetPosition(Vector3 oldPos, float sizeX)
{
Vector3 newPos;
//Returns an array of all the colliding planets
Collider2D[] colliders = Physics2D.OverlapCircleAll(oldPos, sizeX);
//if the array isn't empty, choose a new Vector3 and check that position
//Else the position is valid and the planet is placed there
if (colliders.Length > 0)
{
x = Random.Range(MinX, MaxX);
y = Random.Range(MinY, MaxY);
newPos = new Vector3(x, y, 0);
newPos = CheckPlanetPosition(newPos, sizeX);
}
else
{
newPos = oldPos;
}
return newPos;
}
private void OnDrawGizmos()
{
//Gizmos.DrawWireSphere(Vector3.zero, 1);
foreach (GameObject planet in planets)
{
Gizmos.DrawWireSphere(planet.transform.position, planet.transform.localScale.x);
}
}
}
This is the main chunk of code we're dealing with. The flow is:
At start run CreatePlanets()
CreateRanges() is called, which sets the planet spawn points (position) and planet size (sizeX,SizeY,size).
CheckPlanetPosition is called, which takes the position we just generated, and size of the x component of the transform * 2 (more on this later)
In CheckPlanetPosition() we pass the position as oldPos and the adjusted size as sizeX.
We give our oldPos (center point) and sizeX (radius) and check to see if CircleOverlapAll() finds any colliders in the drawn circle. If no, oldPos is fine (move to else and set position). If there are colliders found, we give it a new x and y position, assign it newPos and then recursively call CheckPlanetPosition again with the returned newPos value.
Note that the Gizmos.DrawWireSphere is set to draw the same bounds we expect to see visually on screen that should be checked in CheckPlanetPosition(). Its for debugging and has no bearing on function.
This code works most of the time. But here will still be overlaps generated. We have also tried:
Using Physics2D.OverlapCircle also, testing each position individually
Using other Collider2D/Physics2D checks
Generating the list of planets with positions and sizes first, then iterating through the list (both using simple foreach and recursive method used above) and running the position check on each item in the list.
Changing quite literally every relevant value (range in scene where planets can spawn, size values, scale values, collider values, radius, etc) and testing differences in the behavior.
Yet every time, we still get results like this: 
(note again that the white lines are the drawn wire-sphere that represent the bounds of the collider -- just for visual debugging)
We believe the issue has to do with the value of the radius. You'll observe above that we set the radius to be the size of the circles transform x component multiplied by two (sizeX 2). We did this after reading some articles on how the radius is calculated and got a ton of different answers saying things like"Radius should be planet's transform.localscale.x 2*" or "Radius should be planet's scale 2DCollider.bounds.extents.x".
Mathematically, the radius of the circle we're generating should be the planet's transform.localscale.x / 2 right? The x component is the length from end to end of the x-axis, and the radius of that would be half the size. Yet none of those equations gave us accurate results. They all generate planets that overlap and we cannot figure out why.
We are stuck and would truly appreciate any help. This is a last ditch effort considering we've seen 100s of posts/tutorials/docs that cover this material and we figured not many people would want to answer. So please and thank you to anyone who can help us tackle this!
TL;DR We are trying to spawn circular game objects at start without overlapping. We have tried a ton of solutions but the results stay roughly the same. In the code:
CreatePlanets() is called to start the process
CreateRanges() generates random positions and sizes for each circle
CheckPlanetPosition() is the method used to recursively test to see if there is overlap in the area the next game object (circle) will be placed.
Why do our circles still overlap?
@rh_galaxy, Thank you so much for responding! Really appreciate it.
So yes, the prefab has a Collider2D component attached. Additionally, if you run the game and inspect the planets, you can see the bounds of the collider outlined in green lining up almost exactly with the gizmo wireframe sketch: 
As you can see above in the inspector, the component is recognizing the contacts with other objects -- it's just not doing what it should be when contact/collision occurs. Note that we have also tried CircleCollider2D, PolygonCollider2D and SphereCollider2D components -- all giving us more or less the exact same results. We also checked the layering as well as the z-index of the objects to make sure they weren't overlapping because they are on different layers.
We also tried building the planet generation bit from scratch -- just using a basic circle sprite on a prefab and instantiating the objects without overlapping (no other code, no classes, just one script to rule out anything else interfering). Once again, almost the exact same results. We're truly at a loss here.
Last note is that we can get this to work sort of if we add a buffer to the radius. For example, if we do sizeX 2 + 75 (or sizeX/2 + 75) -- adding a buffer to the radius, we get better results. However, even then planets will still eventually overlap.* We would really prefer not to hack the design in this way (by adding a buffer) so that's what brought me here to ask the forums.
I haven't checked everything here and found an error but you are using class variables and parameters with the same names (sizeX). And (x) and (y) in two functions and one is recursive, it's a receipt for disaster...
Try making all variables local to the functions with unique names. And move the code in CreateRanges() to CreatePlanets() then you can eli$$anonymous$$ate all the the private class variables (x, y, sizeX, mass ...) and make them local to the function. Not sure if there is an error though. Try stepping through the code if this doesn't work...
@rh_galaxy, Thanks again. Went ahead and tried that with no joy. We've tried similar things -- like hardcoding everything in CreatePlanets() or using a foreach loop to check position instead of the recursive function.
When we step into the code using VSdebugging, the code seems to be doing the right stuff. We can watch the code find invalid positions, give the planets a new position (this may happen one or more times), find a valid one and place it and move onto the next. Yet when the method completes, there is still overlap.
It truly doesn't make any sense at this point -- logically everything seems sound. I'm afraid we're reaching the frustration point, given how trivial the task seems to be.
Does the planetPrefab have a Collider2D component, and is the planetPrefab and it's collider the size x=1.0,y=1.0? Clearly the colliders are smaller than your gizmos or simply not there, because your code should work. If anything there would be more space between because instead of (sizeX*2) it should be (sizeX/2) for the first call to CheckPlanetPosition() (maybe it was like that at some point).
Edit: I think transform.localScale doesn't take effect on the Collider2D component directly... there has to be an Update() before you check for collisions. So either you move the planet generation from Start() to Update() or create a check for the collisions yourself (it's easy, just check distance to all existing planets, and return true if less than the radius of both planets). Edit2: I think I have found it, you should call this after changing the transform (or before you check for collisions).
Physics2D.SyncTransforms();
O$$anonymous$$G -- THAT WAS IT. I tried calling Physics2D.SyncTransforms() directly first, which didn't work. BUT, digging deeper into that, I discovered that there is a Physics2D Setting in Unity project settings that auto-syncs transforms. After checking/enabling that it works perfectly.
Note that somehow, for some reason, it still doesn't like sizeX/2 for the radius which makes absolutely no sense to me BUT it works as expected when simply given sizeX. Truly can't thank you enough for this -- I knew it was because of some Unity nonsense :)
I just like to add a few points here:
Randomly placing objects, checking for overlaps and just rolling new random coordinates can result is really bad performance. Furthermore in the worst case scenario there might be no space for the last planet anywhere and you end up in an infinite loop / infinite recursion. Even if there is a tiny area where the planet might fit it could take ages (maybe 10k iterations) to finally find a spot where it fits. So blindly running loops or recursive methods is dangerous.
I personally would recommend to just blindly place the planets randomly and then just perform relaxation steps to solve any overlaps. Since you usually don't want planets to be too close to each other, you can simply include a threshold / min distance between the planets.
To relax the planet positions you just iterate through the planets, get all their overlapping planets and just accumulate a "seperation force" for every planet. This process can simply done a couple of times until there are no overlaps anymore.
When doing the relaxation there are a couple of things important:
Don't use a too strong seperation. Smaller seperation values would require more iterations but in general are more stable and give you better results.
After each relaxation step you have to check the planets against the boundary. This could be included in the relaxation step itself. Though it's important to also have some threshold to the screen border to avoid ending up in many iterations at the end.
You should change your
List<GameObject>into aList<Transform>. In almost all cases when you store a list of gameobjects, the container type GameObject is the least useful as it contains the least information. From any component you can directly access the hosting gameobject, so if you really need the gameobject that's not an issue.
This could look something like this:
public List<Transform> planets;
public Transform planetPrefab;
public float MinY = -120;
public float MinX = -500;
public float MaxX = 600;
public float MaxY = 640;
public int maxRelaxationSteps = 50;
public float seperationThreshold = 0.5f;
Transform CreateRandomPlanet()
{
//Create randomly positioned planet
float x = Random.Range(MinX, MaxX);
float y = Random.Range(MinY, MaxY);
Vector3 position = new Vector3(x, y, 0);
Quaternion rotation = Quaternion.Euler(0, 0, Random.Range(0, 360));
Transform newPlanet = Instantiate(planetPrefab, position, rotation);
//Set random size for the new planet
float size = Random.Range(10, 70);
newPlanet.localScale = new Vector3(size, size, 1);
newPlanet.GetComponent<Rigidbody2D>().mass = Random.Range(100, 2000);
return newPlanet;
}
void RelaxPlanets()
{
Vector2[] offsets = new Vector2[planets.Count];
Collider2D[] colliders = new Collider2D[planets.Count];
for (int i = 0; i < maxRelaxationSteps; i++)
{
bool noOverlap = true;
for(int k = 0; k < planets.Count; k++)
{
offsets[k] = Vector2.zero;
float size = planets[k].localScale.x;
Vector2 pPos = planets[k].position;
int count = Physics2D.OverlapCircleNonAlloc(pPos, size + seperationThreshold, colliders);
for(int n = 0; n < count; n++)
{
var trans = colliders[n].transform;
// ignore the planet we're currently checking
if (trans == planets[k])
continue;
// we have overlaps so we need more iterations
noOverlap = false;
float size2 = trans.localScale.x;
Vector2 pPos2 = trans.position;
// calculate seperation direction and seperation amount
Vector2 dir = pPos - pPos2;
float dist = dir.magnitude;
float seperation = size + size2 + seperationThreshold - dist;
// ensure a minimum seperation distance
seperation = Mathf.Max(seperation*0.5f, seperationThreshold);
// normalize the direction vector
dir /= dist;
offsets[k] += dir * seperation;
}
}
// if we had no overlaps during this iteration, everything is fine and we stop
if (noOverlap)
break;
// apply seperation offsets and ensure planets stay inside screen
for (int k = 0; k < planets.Count; k++)
{
Vector2 newPos = (Vector2)planets[k].position + offsets[k];
newPos.x = Mathf.Clamp(newPos.x, MinX, MaxX);
newPos.y = Mathf.Clamp(newPos.y, MinY, MaxY);
planets[k].position = newPos;
}
// update the physics representation for the next iteration
Physics2D.SyncTransforms();
}
}
void CreatePlanets()
{
planets = new List<Transform>();
for(int i = 1; i <= 15; i++)
{
planets.Add(CreateRandomPlanet());
}
RelaxPlanets();
}
As you can see I've restructured the planet creation. Using class member variables to pass temporary information between different methods is bad style. Those variables are not used by the class after than. It also makes it much harder to follow where a value has been set / generated and where it may be used. Use local variables whenever possible. If you need pass intermediate information between methods, pass them as parameters.
To check for overlaps I used "OverlapCircleNonAlloc" since we probably do this alot we can minimize the memory allocated. Since we have a known size of planets we can confidently use the planet count as array size since we can't get back more objects than we have planets.
The seperation distance is simply "half of the overlap". So if two planets happen to be located at almost the same position the overlap is the sum of their radii plus our threshold. Since all planets will check for overlaps with their neighbors. Two planets will move each half of the overlap in the opposite direction. So each iteration each pair of overlapping planets will essentially solve their overlap. However since other planets could be involved as well, after the seperation the planets could overlap with different planets. That's why we need additional iterations. We clamped the seperation amount so if two planets overlap only a tiny bit we will at least apply a seperation of "seperationThreshold" to avoid micro adjustments which just results in many iterations.
The great thing about this approach is that when the there is a way to position the fiven planets on the screen (so there are not too many and too large planets) it should always find a solution. Though it's always a good idea to limit the iterations in case you have too many planets or got very unlucky with the planet sizes. If it's absolutely necessary to get a result without overlapping planets, you may just destroy all planets and start from scratch if the overlaps couldn't be solved after the max iteration count.
