How to randomly instantiate cubes that don't overlap?

I'm trying to randomly instantiate cubes on the x and y axis but they keep overlapping. Can someone point me in the right direction to prevent them from overlapping when instantiated?

 

You could have an array of positions where you've previously instantiated cubes, and check the random position for a new cube doesn't conflict with previous positions in the array - you could define a minimum gap between cubes.

 

I had been thinking about this lately because I am going to need it in an upcoming project. What I am going to attempt to do is have 2 prefabs. First one is my cube and the second one is an empty gameobject with a script that uses SphereCast to see if there are any objects its touching. So from there I would randomly figure out my Vector3, Call the SphereCast prefab. If it finds something then destroy the SphereCast object and randomize the location again. Else if it didn't find an object then destroy the sphereCast object and spawn a cube in its place.

 

Perhaps you can just cast a ray from the new position up and test it.

 

One way to do this without sphere checks or ray casts it to create a random spatial partition tree then spawn a cube randomly within each leaf node.

Rough algorithm outline is:
* Start with a min/max bounding box in 2D.
* Split somewhere randomly on the x axis so you get two bounding boxes.
* Split each of these new bounding boxes randomly on the y axis so you now have four bounding boxes.
* Continue the process of splitting the boxes along each axis until you have enough boxes.
* Spawn a single cube prefab randomly within each box

The tricky part of this is selecting a good point to perform the splitting of a bounding box.
You need to make sure that each new bounding box you create is large enough to hold however many leaf boxes it will eventually contain.
This means that for each level of the tree you need to know an inset from the min and max bound where it is safe to split and chose a random point between the two inset bounds.

 

I'm still testing things out, but for now, I haven't figured it out. Having cubes of varying width and height make it hard to check for overlap. As of now, I can only manage to prevent cubes from spawning partially outside of a grid.

 

Ok well maybe the same method that I posted above will work but we will changing it a little. Rather than using Shpere cast spawn the object in a random space but turn off the rederer. If its collider hits then move it to another random space until if finds one it fits in.

 

Gibbonator, that sounds incredibly complicated and possibly outside of my skill level. I'm thinking of trying to place various spawn points and create different sized grids, taking the sizes into account and instantiating 1 cube in each spawn point's grid.

 

I think the better method is to use Spherecast as ardizzle sayd. But you can use it without instantiating any gameObject: just call the Physics.SphereCast on the position to test for and with the size you want (varying it as needed).

 

I'm trying to do the same thing in the game I'm working on right now, and I'm having the same problem. I'm not sure what RayDawg is using in the code, but I'm using Random.Range to spawn the objects within the play area, but they keep overlapping. I'm new to scripting and Unity3D, so some of these answers are foreign to me, such as the stuff involving SphereCast. Could anyone give an example of a code for this because I'm sure that would help us a lot! Thanks.

-- Chris

 

Hello, this script just came to my mind as I was reading your posts. I just tested it and it runs just fine

Code (csharp):

1. public static class PhysicsEx
2. {
3.     public static bool CheckBounds(Vector3 position, Vector3 boundsSize, int layerMask)
4.     {
5.         Bounds boxBounds = new Bounds(position, boundsSize);
6.  
7.         float sqrHalfBoxSize = boxBounds.extents.sqrMagnitude;
8.         float overlapingSphereRadius = Mathf.Sqrt(sqrHalfBoxSize + sqrHalfBoxSize);
9.  
10.         /* Hoping I have the previous calculation right, move on to finding the nearby colliders */
11.         Collider[] hitColliders = Physics.OverlapSphere(position, overlapingSphereRadius, layerMask);
12.         foreach (Collider otherCollider in hitColliders)
13.         {
14.             //now we ask each of thoose gentle colliders if they sens something is within their bounds
15.             if (otherCollider.bounds.Intersects(boxBounds))
16.                 return (false);
17.         }
18.         return (true);
19.     }
20.  
21.     public static bool CheckBounds2D(Vector2 position, Vector2 boundsSize, int layerMask)
22.     {
23.         Bounds boxBounds = new Bounds(position, boundsSize);
24.  
25.         float sqrHalfBoxSize = boxBounds.extents.sqrMagnitude;
26.         float overlapingCircleRadius = Mathf.Sqrt(sqrHalfBoxSize + sqrHalfBoxSize);
27.  
28.         /* Hoping I have the previous calculation right, move on to finding the nearby colliders */
29.         Collider2D[] hitColliders = Physics2D.OverlapCircleAll(position, overlapingCircleRadius, layerMask);
30.         foreach (Collider2D otherCollider in hitColliders)
31.         {
32.             //now we ask each of thoose gentle colliders if they sens something is within their bounds
33.             if (otherCollider.bounds.Intersects(boxBounds))
34.                 return (false);
35.         }
36.         return (true);
37.     }
38. }
39.  

edit: added a nice static wrapper arround it, too bad static extensions aren't possible or it could have actually extended the Physics class !
edit2: Changed the parameters to better suit the use of this, also added a 2D version (untested)

 

Thank you for the example, but would SphereCast work with 2D, or would I have to use something like a circle? My game is 2D, so I don't need any Vector3s or spheres. Also, would Bounds work with 2D?

-- Chris

 

You're welcome and no problem for 2D, just replace the 3D stuff with 2D one and you'll be fine.

Physics2D.OverlapCircle instead of Physics.OverlapSphere, and yes bounds work in 2D as well. Simply check out the Collider2D documentation and you'll see the bounds property is still available and using the same class.

 

Thanks! I'll give it a try!

-- Chris

 

Sorry to ask this of you, but could you write the code in UnityScript because I know very little about C#. I tried to translate this code over, but it's rather difficult since I'm still in the process of learning UnityScript. Half of my script is in UnityScript, so I can't have the other half be C#. If you don't know much about UnityScript, maybe you could translate my half of the code into C#? I'd really appreciate this!!

-- Chris

 

hm I'll try but usually it makes me sick...

Code (JavaScript):

1. function CheckBox(var position : Vector2, var boxSize : float, var layerMask : int)
2.     {
3.         /* First some middle grade trigonometry to get the radius of the overlapping sphere */
4.         var halfBoxSize : float = boxSize / 2;
5.         var sqrHalfBoxSize : float = halfBoxSize * halfBoxSize;
6.         var overlapingCircleRadius : float= Mathf.Sqrt(sqrHalfBoxSize + sqrHalfBoxSize);
7.  
8.         var boxBounds : Bounds = Bounds(position, Vector3(boxSize, boxSize, 0));
9.  
10.         /* Hoping I have the previous calculation right, move on to finding the nearby colliders */
11.         var hitColliders : Collider[] = Physics2D.OverlapCircle(position, overlapingCircleRadius, layerMask);
12.         for(var otherCollider : Collider in hitColliders)
13.         {
14.             //now we ask each of thoose gentle colliders if they sens something is within their bounds
15.             if (otherCollider.bounds.Intersects(boxBounds))
16.                 return (false);
17.         }
18.         return (true);
19.     }

I'm really not sure it'll work out of the box but it should help you get started at least, and I really don't want to create a JS file in my unity project, he's still a virgin so I hope you understand...

Now if you excuse me, I have to p*ke.

 

How about this: http://docs.unity3d.com/ScriptReference/Physics.CheckSphere.html ?

 

It's pretty much the same idea except it doesn't take the objects shapes into account.

It may be totally fine, depends on what they want to acheive...


ps: I even named the method "CheckBox" to give the feeling of equivalence with this very method your pointing out.

 

I don't mean to dis your method of doing this, _met44, but I found my own very simple way of doing it! Here's the code:

Code (JavaScript):

1. function Start ()
2. {
3.     // Randomly spawn the object within the specified range.
4.     var newPositionX : float = Random.Range (-5.5, 75.5)
5.     transform.position.x = newPositionX;
6.     var newPositionY : float = Random.Range (-2.5, 4.5);
7.     transform.position.y = newPositionY;
8. }
9.  
10. function OnCollisionEnter2D (col : Collision2D)
11. {
12.     Debug.Log ("Ouch!");
13.    
14.     // If collision with objects tagged "Obstacle," repeat Start function.
15.     if (col.gameObject.CompareTag ("Obstacle"))
16.     {
17.         Start ();
18.     }
19. }

This was NOT easy for me to accomplish, so I'm very proud of it! The problem I had with your code, _met44, was that I'm new to scripting, so it looked foreign to me! Plus, my version is shorter. Obviously, the Debug.Log statement could be replaced with a print statement or removed entirely. I only added that in there to tell me how many times the object collided, which tells me how many times the Start function was repeated because I don't want it to repeat too many times. I hope this helps everyone! Again, thanks for the help, everyone!

-- Chris

 

yes obviously you can do that, someone pointed it out before I believe. I thought you asked for a way to do it before instanciating the cube...

It's great if this fits your needs, what you need most when starting is fun results that motivate you to keep going forward !

I wish you best luck

 

RayDawg wanted instantiation. I apologize for not specifying that I wasn't instantiating, but you did actually help me help myself! I went to the scripting reference and read about Bounds and from there I went to collisions, which led me to the OnCollision events, which finally brought me to OnCollisionEnter2D, which is what I didn't know I needed! And yeah, I am happy about solving this problem that I've been fiddling with for a week now! And I need all the luck I can get because my game is almost done!

 

Hehe nice, that's how you learn I guess. Practice, practice, pratice

 

Met, I'm trying to test this out but some things have me confused:

1. Why a static method?
2. What does a layermask have to do with it?
3. What if the box size isn't uniform, what if I have various 2x2 cubes (the z scale is uniform), 2x3, 4x1, etc; should I pass a second float as "boxSize2?"
4. Do I attach this to the objects being spawned as a script on its own?

 

1 static means you don't need to instanciate the class, for example unity's Physics class uses statics methods, you don't have to to Physics p = new Physics(); and then p.OverlapSphere(), instead you directly call Physics.OverlapSphere() because you don't need a physics object, this is what the static is for.

2 The layerMask allows you to filter the layers you want to poll against, so for example is you have objects that you don't mind overlaping you could exclude them with the mask

3 Easy to modify, instead of of "float boxSize" in the parameters, write Vector2 boxSize, and use this directly in the OverlapSphere/Circle instead of creating a vector with the same size on the 3 axis.
4 Since this is static, you can acces it from your scripts like you would with unity's API

Also, the name should be CheckBounds instead of box, been bothered by this since I wrote the code. I'm going to update my previous post with thoose changes since it makes sens.


ps: also with non square-ish bounds I would suggest to edit the script to do a capsule cast instead of sphere cast so there are less object to check the bounds against in the loop. Maybe I'll do that later if I find the time.

 

Ugh... I'm back... I just realized that I do need to instantiate my object. So what I need to do is this:

1. Start the level with the object named "Hook" randomly within a given x and y distance. This step is done using Random.Range. One down, 3 to go...
   
2. Instantiate the Hook and spawn the clone in a different random x and y position until there are a total of 10 Hooks (including the original).
3. Before the Hook clones are placed, check if there is enough space between any other Hooks to spawn this Hook. If there is not enough space, then randomly select another position and repeat this process until you can spawn the Hook.
4. When the player collides with any instance of the Hook, restart the scene, repeating steps 1-3. This step is done in a different script, which is attached to my player object. 2 down, 2 to go..........

This is so frustrating! I thought I had it worked out, but then I realized that I need to instantiate the Hooks!! I don't like instantiation... It seems like no matter how I try to instantiate, Unity crashes. I actually have the Windows Task Manager constantly open whenever I deal with instantiation because I expect Unity to crash! My mind is fried...

-- Chris

 

Just a quick update, I'm still trying to get this problem solved. No progress so far, but I'm sure I'll get there--eventually. The problem I'm running into is that I keep getting a message stating that I can't convert bool to UnityEngine.collider[]

Code (CSharp):

1. public static bool CheckOverlap(GameObject TreasureItem)
2.     {
3.         // Get the object's position
4.         Vector3 Position = TreasureItem.transform.position;
5.         // Create a new capsule top and bottom at the object's top and bottom positions
6.         Vector3 CapsuleTop = new Vector3(TreasureItem.transform.position.x, TreasureItem.transform.position.y + TreasureItem.GetComponent<Treasure>().offsetY, TreasureItem.transform.position.z);
7.         Vector3 CapsuleBottom = new Vector3(TreasureItem.transform.position.x, TreasureItem.transform.position.y - TreasureItem.GetComponent<Treasure>().offsetY, TreasureItem.transform.position.z);
8.      
9.      
10.         float Radius = TreasureItem.GetComponent<Treasure>().sphereRadius;
11.  
12.         // Use the object's collider as the boundry
13.         Bounds TreasureBounds = TreasureItem.collider.bounds;
14.  
15.         // ------------ The problem line as stated by unity and visual studio -------------------------------
16.         Collider[] HitColliders = Physics.CheckCapsule(CapsuleBottom, CapsuleTop, Radius);
17.  
18.         foreach(Collider OtherCollider in HitColliders)
19.         {
20.             if (OtherCollider.bounds.Intersects(TreasureBounds))
21.             {
22.                 return (false);
23.             }
24.         }
25.  
26.         return (true);
27.     }

Edit: I forgot to add some code.

 

CheckCapsule just return true if hit something so return that and get rid of the other code below that.

 

I'm not that fluent in C#, I'm more of a Javascript person, myself, but I'd say that what Fraconte said sounds right. Looking at the script reference for CheckCapsule, it is a bool, so try to find something that does something like CheckCapsule that is not a bool. Could you try using OverlapSphere? OverlapShpere is a collider, so the three variables you have for CheckCapsule should work in there. Correct if I'm wrong. It's always good to learn from your mistakes!

-- Chris

 

Sure you can use OverlapSphere with that code above. I think the choice depends on the level of control you want: if you have to do something with the colliders use OverlapSphere, if you just need to know if anything is hit use the other bool type functions.

 

At this point, I've been stuck on this problem for about 4 weeks in a row. This doesn't include the time putting this little project of mine aside for several weeks total. I don't really care anymore about how it's solved, I just want to get this problem solved so I can move on.

 

I know what you mean! I'm suffering through a very similar problem, too. However, mine is in 2D, which is different from yours. I've gotten to where I can spawn the objects randomly within a given minimum and maximum value, but the only thing I can't do is instantiate them within that minimum and maximum value. I don't know what it is. Every time I try to do anything with instantiation, I end up crashing Unity every single time! Could someone give me an example of how to instantiate a game object, preferably without crashing Unity in the process? I'd really appreciate that. If I can figure instantiation out, I might be able to do the rest and it will solve RayDawg's problem, too.

-- Chris

 

I know you are having troubles with instantiation, but this topic is about solving a problem involving randomly instantiating 3D cubes while preventing them from overlapping. While they sound similar, this topic focuses on preventing overlap, not random crashes caused by instantiation. I would recommend making a separate thread in the scripting forums asking about instantiation because talking about two different things in one thread can at best, be very confusing for some and at worst, seem like thread hijacking (going off topic from the original post to focus on another topic).

 

My original problem is that the objects spawn on top of one another (overlapping), which is not what I want. Instantiating is another problem I'm having which isn't what I'm mainly talking about in this thread. I want the objects to instantiate randomly without overlapping or touching each other. I apologize for going a little off topic with that last post; I just got a little carried away!

-- Chris

 

@RayDawg you must use CapsuleCastAll, it will return a RaycastHit[] but you'll be able to work with same in the same fashion since they contain a reference to the collider.

Even if not the most optimized, have you tried the code I gave with the Vector3 as the size ? It does work so if you've been stuck with the issue for a while, grab the working thing, move on, add meaningful features and at some point you'll feel like optimizing that script.

 

Yes I have, but I didn't bother passing in the vector 3 because it was already stored in the game object. As a result, I decided to pass the game object itself as the argument as opposed to three separate arguments.

Edit: I tried just using the code you provided as-is: overlaps still persist.

 

This works:

Code (CSharp):

1.  
2. using UnityEngine;
3.  
4. public class RandomSpawn : MonoBehaviour
5. {
6.     public GameObject clone;
7.     public int maxClones = 100;
8.     public float interval = 1;
9.     public int areaSize = 10;
10.  
11.     float elapsed, radius;
12.     int clones;
13.  
14.     void Start ()
15.     {
16.         Bounds maxBounds = RecursiveMeshBB (clone);
17.         radius = maxBounds.size.magnitude;
18.         print (radius);
19.     }
20.  
21.     void Update()
22.     {
23.         if(Time.time - elapsed > interval)
24.         {
25.             Vector3 randomPosition = clone.transform.position + new Vector3 (Random.Range (-areaSize, areaSize),radius , Random.Range (-areaSize, areaSize));
26.            
27.             if (!Physics.CheckSphere (randomPosition, radius) && clones < maxClones)
28.             {
29.                 if (clone == gameObject) // you don't want a clone storm... :)
30.                     GameObject.CreatePrimitive(PrimitiveType.Cube).transform.position = randomPosition;
31.                 else
32.                     Instantiate (clone, randomPosition, Quaternion.identity);
33.                
34.                 elapsed = Time.time;
35.                 clones++;
36.             }
37.         }
38.     }
39.  
40.     static public Bounds RecursiveMeshBB(GameObject go)
41.     {
42.         MeshFilter[] mfs = go.GetComponentsInChildren<MeshFilter>();
43.        
44.         if (mfs.Length>0)
45.         {
46.             Bounds b = mfs[0].mesh.bounds;
47.             for (int i=1; i<mfs.Length; i++)
48.             {
49.                 b.Encapsulate(mfs[i].mesh.bounds);
50.             }
51.             return b;
52.         }
53.         else
54.             return new Bounds();
55.     }
56.  
57. }
58.  
59.  

Edit: changed GameObject in Collider
Edit: rechanged Collider in GameObject and added a function I found in the forum to calculate the global bounds of the object.

 

Fraconte, it does work for same sized cubes, at the moment, I'm going to see if I can adapt that to account for/include different sized cubes.

 

It automatically adapt to different meshes. I tryed it from a cube to an aeroplane.

 

Wait, so you randomly spawned cubes and aeroplanes stored in an array and they didn't overlap??? This has me curious because I'm using 9 cubes each with different sizes and I'm looking at overlap each time I test it out.

 

I only tested same types... For different types you have to recalculate radius in Update. I'll try it too later.

Edit: Indeed you can just calculate and save different radius in Start...

 

@RayDawg Just for the reccord, may I asked how you tested it ?

I'm curious because it works fine on my end, have a look at this:

It clearly shows that the bounds are properly checked doesn't it ?

Here is my script for the cube I was moving :

Code (CSharp):

1. using UnityEngine;
2. using System.Collections;
3.  
4. public class BoxTest : MonoBehaviour
5. {
6.     void Update()
7.     {
8.         if (PhysicsEx.CheckBounds(this.transform.position, this.renderer.bounds.size, Physics.AllLayers))
9.             this.renderer.material.color = Color.green;
10.         else
11.             this.renderer.material.color = Color.red;
12.     }
13. }

I don't understand how you could not use that to check the location at which you want to spawn your cubes, unless objects from the scene don't have colliders of course ...

Cheers



ps: forgot to mention, the use with a script like Fractone's would be as simple as replacing :

Code (csharp):

1. if(!Physics.CheckSphere(randomPosition, radius)&& clones < maxClones)

by :

Code (csharp):

1. if(!PhysicsEx.CheckBounds(randomPosition, this.clone.renderer.bounds.size, this.clone.layer) && clones < maxClones)

Instead of the approximative sphere detection you would get the accurate cube one. And to use it for cubes of any size you just put whichever size you need instead of the "clone" bounds like I did...

 

This is with List of different objects:

Code (CSharp):

1. using UnityEngine;
2. using System.Collections.Generic;
3.  
4. public class RandomSpawn : MonoBehaviour
5. {
6.     public List<GameObject>  clones;
7.     public int maxClones = 100;
8.     public float interval = 1;
9.     public int areaSize = 10;
10.  
11.     float elapsed;
12.     List<float> radius = new List<float>();
13.     int cloneCount;
14.  
15.     void Start ()
16.     {
17.         foreach (GameObject clone in clones)
18.         {
19.             Bounds maxBounds = RecursiveMeshBB (clone);
20.             radius.Add (maxBounds.size.magnitude);
21.         }
22.     }
23.  
24.     void Update()
25.     {
26.         if(Time.time - elapsed > interval)
27.         {
28.             int clone = Random.Range (0, clones.Count-1);
29.             Vector3 randomPosition = clones[clone].transform.position + new Vector3 (Random.Range (-areaSize, areaSize), radius[clone], Random.Range (-areaSize, areaSize));
30.          
31.             if (!Physics.CheckSphere (randomPosition, radius[clone]) && cloneCount < maxClones)
32.             {
33.                 if (clones[clone] == gameObject) // you don't want a clone storm... :)
34.                     GameObject.CreatePrimitive(PrimitiveType.Cube).transform.position = randomPosition;
35.                 else
36.                     Instantiate (clones[clone], randomPosition, Quaternion.identity);
37.              
38.                 elapsed = Time.time;
39.                 cloneCount++;
40.             }
41.         }
42.     }
43.  
44.     static public Bounds RecursiveMeshBB(GameObject go)
45.     {
46.         MeshFilter[] mfs = go.GetComponentsInChildren<MeshFilter>();
47.      
48.         if (mfs.Length>0)
49.         {
50.             Bounds b = mfs[0].mesh.bounds;
51.             for (int i=1; i<mfs.Length; i++)
52.             {
53.                 b.Encapsulate(mfs[i].mesh.bounds);
54.             }
55.             return b;
56.         }
57.         else
58.             return new Bounds();
59.     }
60.  
61. }
62.  

 

I think his problems are more because of different sizes, (shapes?) than because of the method used to check collisions.

I personally chosed CheckSphere for simplicity and because I dont see the need for greater precision: it really depends on what minimum distance you want to keep between objects. Anyway I am sure your method works and could be more accurate.

 

Yes I totally get that, I was just answering where he said "I tried just using the code you provided as-is: overlaps still persist", I don't like when my scripts "don't work", especially when I know they do !

And I agree the sphere detection is the way to go if he wants the fastest and doesn't care for accuracy which is most likely.

Anyways, your code seems to fit his need, perhaps a capsule version would allow less sparse long/thin objects but without further details it's hard to tell the actual needs.

 

I copy+pasted the code into my code, then called it shortly after instantiating the cubes. When I hit play, the cubes would spawn, but there would still be some cubes overlapping with each other.

Even with Fraconte's code supplied, I still get overlapping cubes.

 

The intend of the code I gave you was to be used before instanciating the cubes, this way you were able to check the availability of a position before putting the cube in there and you avoided the ugly cleaning up of stuff that shouldn't have been instanciated in the first place.

Have you checked the radius of the sphere you're testing ? And do you have a collider on your cubes ? Other than that I don't understand why the physics test would fail.

 

Since your code returns a bool, I tried adding it to an if statement where if it returns true, then the cube will be instantiated, if false, then I recursively call the method that instantiates the cubes and restart. It wasn't a good idea since it caused a stack overflow.

 

Do you call that CheckOverlap() function you posted above, for every object you want to spawn? It seems you have just spawned it when you call that function. So you just move it around until you find a free place? We can't tell how do you get that sphereRadius so are you sure it's right for all the object you spawn?

 

Well that explains it.

If there is even one chance in a million that you can fill the stack you can be sure it'll happen at some point, and if the odds are even worse you have a winner. If you're in this situation then it's not a good design.

You should either iterate on a certain amount of attempts to do in one frame or if you're in no hurry it's even simpler to just try once per frame, this way no stack overflow... And a bonus, a steady framerate

If you have a very specific need that require everything to be randomly instanciated from the start then it should be fully scripted, no calls to the physics API, no room for approximation. Use a sort of quad/octree, fill with bigger cubes first then go down in size. It'll be a bit harder to create for you but it'll be done instanciating everything very quickly.

Other than this case you'll be fine without recursion.

 

I called it prior to instantiation. As for the sphere radius, it's a public variable set in the "Treasure" script and yes, I've checked the scripts and prefabs dozens of times to make sure they are correct.

To clarify some things, here's a basic outline of what I can (and want to) do right now:

1. Store a set of x and y points in a grid-like manner.
2. Randomly select a cube object (prefabbed) that has different x and y scale values from one of three different lists.
3. Pass the selected object as an argument to the method that instantiates the cubes.
4. In the instantiating method, randomly select an x and y position (from step 1), check to see if the object will spawn partially off camera and compensate for the possible offset (because unity sets the pivot point to be the exact center of the object and not a corner).
5. (Want to do) In the instantiating method, after all the possible adjustments to x and y positions are done, call a method to check to see if there are any overlap, if there is any overlap, then select another location and call a method to check again.
6. Once there are no possible overlaps detected, instantiate the object at the location.