Random/procedural object locations, anti-overlap method?

Hey, I’m trying to populate a square area with different objects using random (X,Y) locations. What is the best way to prevent them from overlapping each other? There will be a lot of them, so I’m trying to find a reasonably performant solution. My first idea:
Every object has a small set of Sphere Colliders that are set to overlap only with their special ‘spawnBlocker’ object type (for performance). You can place & scale them in object’s BP to approximately match any object shape:

After getting random X,Y location, objects could check if their sphere colliders overlap any other colliders from other actors (e.g. by SphereCollisionComponent.GetOverlappingComponents() → if ( InOverlappingComponents].Length > 0 ) )…
If not, they can spawn there, if yes, they they must select a different random (X,Y) location and check again.

This could work, but I have a feeling that there is a better way to achieve something like that. I would be grateful for some hints… Any ideas? :slight_smile:

UE4 newbie answer here:

The way your already doing it with actor overlaps seems the best to me.

This is just a concept, i’m not sure how it can be (or even if it can be) implemented.

The only alternative i can think of is to round the X,Y location up or down.
So, assuming that the object your generating has a radius of 5.
create a random position (x17 y74) round it to the nearest 10 (x20 y70)
Compare the results make sure none are the same. and use those x and y.

Depending on how it’s used though, this could become quite “griddy” looking.

Don’t know if that helped at all, I am a UE4 newbie so could be miles off with this. :slight_smile:

Not sure if that makes things more or less complex.

If the square size is known / fixed, pre-assign locations into an array: X, Y, Size.
Then randomly choose a slot from the array each time before object placement…
If the object fits the gap plus a space then proceed removing old slot from array.
If not try another. Just like pre-allocating / dividing up a grid on a piece of paper.

Hell no, “many objects”, “collision” and “performance” simply don’t work together. Instead of using a real collision (using collisionspheres), calculate it.
Assign every object one or more points (which would be the center of the circle/collision sphere you drew) and give all of them a certain radius.
When you want to spawn a new object, choose a random point, check the distance to every point and compare it to the radius - if it returns true, choose a new point, else you can spawn it.

@Eightshot Thanks, I’ll try to implement some test logic for this and see how it works, if it’ll become too ‘griddy’ or not :slight_smile:

@franktech That’s an interesting way to do this, I had a similar idea, but this would require some 2D array neighbor detection to handle all the different radiuses…? This stopped me, but maybe I’m missing something here…

@Fragment7 That’s the funny part, I was thinking the same thing and tested the performance footprint on a test project for both solutions. Every object has a sphere collider with realistic 2000 radius. In their event tick (to make it constantly under heavy load & test ms) they have SphereCollider → GetOverlappingComponents → if (length > 0). I have 181 test actors like this in my scene, they are placed in the way that every one overlaps with other 4 colliders. They detect each other correctly, using separate object channel and ignoring any other channel. Running this in Standalone window results in 0.60 ms blueprint time (‘stat game’ command).
Then I change the logic in the Event Tick to check distance to every other actor (ForLoop with 180 iterations) (Vector - Vector).VectorLength] → check if larger than some value. Running this results in… 35 ms blueprint time.
… And this confuses me :slight_smile: Looks like the sphere colliders are not heavy if they don’t overlap with many other colliders (and that would be the case, usually they would not overlap with anything, and occasionally with max 1-5 other colliders, so then they’d change their spawn location) - unless I miss something… I don’t know how they’re implemented internally.

Thanks for the hints!

Do you spawn them at runtime? If So, The Spawn node has an option to avoid collisions.

Yes, they would be spawned using Spawn Actor From Class, but not immediately. For performance reasons they would only ‘reserve’ a location at game start, save it to closest chunk and spawn only when player gets closer (un-cull), because I’ve heard that spawning actor is an expensive operation in UE.
That’s interesting, actually I’ve never utilized the ‘Collision Handling Override’ in the Spawn node… The ‘Try To Adjust Location, But Always Spawn’ option sounds intriguing, I’ll need to test it and see how it works. I don’t know if it tries to offset colliding actor, but if so, in my case it must be only X,Y (without Z) offset, because I need a planar object placement.

The idea was just based around pre-allocating slots at design time, like how restaurants take table bookings etc.

I was thinking you’d create an array of squares (or x,y center-points and a radius, if that’s easier to work with).
These are unique, so once pulled out of the array there wouldn’t be any need for any neighbor overlap checks.

But a possible downside is leaving more than the necessary gap, so lost space if you need objects packed tight.
It would also require accurate sizing info for each placed object obviously. Set as a Tag at design time maybe…?