Choosing an empty spawning position efficiently

Hello,

I am looking for a more efficient way to select an empty spawning place.
I don't have a fixed Vector3 array with possible spawn points.
I have a rectangular area and i'm selecting random points inside it, and then using Physics.OverlapSphere to find out if there are any other colliders that would touch my object.
I'm using a while loop to recheck until Physics.OverlapSphere returns no colliders, and then i'm continuing with trying to spawn my next object.

But the playing area is not big and I can easily get 50 - 100 iterations per object before finding an empty spot.

Is there a better way of doing this?

Thanks

 

I use a grid and a bool array for it. Once I place a piece, I set the bool to true for that grid space. If you can't do a grid, I can't think of another way. Even with the grid, I ended up putting walls on odd positions and items and people on even positions, otherwise it took too long. Very small grid too, but there was a noticeable lag when the scene loaded.
Maybe think in 2d if the terrain is flat. Might be faster than a sphere check. Then do a check like this:
bool collision = (A.position - B-position).magnitude <= A.Radius + B.Radius;
Also, you can divide the area into quadrants or something, and only check if somethings radius is in the same quadrant. Not sure if that would be faster or not, but it might be something to try. The physics engine is probably pretty fast and has those things cataloged already. I think you are kind of stuck actually, unless you can think of a different way to eliminate possible checks. You could find the minimum radius of something, and then cut down the possible positions by using a smaller random number and then multiplying by some number so they are spaced out evenly on the area without touching.

 

A grid is a nice idea but my objects are in different sizes.. so I would need to keep each cell the size of my largest object. that would create a lot of unusable space and would cause my scene to look "less random".
So I don't think that will work for me.

Maybe there's a mathematical solution to this?
If each time I instantiate an object, I save it's position to an array, maybe I can loop once on that array per new object and compare the distance between the random coordinates to all of the array's coordinates and somehow make an alteration that puts them at a minimal distance from all the others?
Maybe by sorting the array somehow. I only need an X and a Z. The Y is always 0 since i'm spawning the objects on the ground

Mmm. I need to think about that..

 

Picture the cells as being imaginary. Say you had something with the diameter of 3, something with 2, something with one. If you were on a 10x10 area, you could use( random 10/3) * 3 for x and z to evenly space those. If it was 2, you would use (random 10/2) * 2 to evenly space those, if it was 1, random 10. It wouldn't eliminate everything, but would cut down on possible collisions compared to using random 10 for everything. Of course, you would want a small distance between each member so they didn't collide if they were beside each other. To take it further, the larger member would eliminate a larger amount of grid cells on a one by one grid, but it would be known. So, instead of one grid space being true, maybe 4 would be true or whatever.

 

The thing is that I'm spawning objects randomly from a pool.
I don't know ahead of time how many 'large' objects and how many 'small' objects I will have.

I'll try to 'create' each cell after choosing each object from the pool and place that cell at a random free point on the grid that could contain that cell size.
And make each cell a bit larger than it's object and randomize a position within that cell so that objects won't align with each other.

A bit tricky but it can be done.
Thanks!

 

Welcome. Good luck.

 

I do something similar for a space game, Random.insideUnitSphere\onUnitSphere * distance to get a position.
Keep a list of all positions, each time you pick a new position loop through all positions to see if its too close, if it is pick a new one if its not add it to the list and spawn the object.
Make the list only in the method, you don't need to keep it, and use sqr mag to optimize