Random Instantiate with no overlap

Unity Engine
,
1

Hi guys,
I have a function that returns a random position on a mesh every time I call it.
I can use this position to instantiate say 100 GameObjects.

7987569--1026279--Screenshot 2022-03-23 at 14.03.10.png
7987569--1026279--Screenshot 2022-03-23 at 14.03.10.png1239×762 87.4 KB

What I am wondering is how to instantiate these GameObjects without overlap.
I thought to use Vector3. Distance and some range variable. But not sure how to do it in code.

I tried this, but its logic is wrong…

private void CheckRange(Vector3 position, List<GameObject> items)
    {
        if(items.Count > 0)
        {
            foreach(var item in items)
            {
                if(Vector3.Distance(position, item.transform.position) < range)
                {
                    position = GetRandomPositionOnMesh();
                }
            }
        }
    }
2

I think I need somehow to introduce the number of attempts to place an object and be able to test the proposed random position relative to all already existing GameObjects ?

3

Each item in items needs to check each item in items, except for itself, and get the distance from itself to that item and if it is closer than it needs to be then you can break and not instantiate a new item. For a small scene as yours this is okay. But for a larger set up it will be very time consuming.

to instantiate a new item and add it to the items list you are not allowed to add to the list you are currently iterating so you should attach a bool which lets you know if the spawn location was viable and then spawn the object after the for each or for loop checks have occurred.

4

Poisson Disc Sampling

3 Likes
5

Hi @AnimalMan Yes it is kinda what I want.
The problem I have is while I am iterating each item in items I am comparing it with the proposed position.
If position is two close to an item I need to try different position.
But foreach loop is not working as I will basically compare only one item with the proposed position.

If it is within range I can brake, but there is a chance other items stayed unchecked .

6

Hi @Yoreki ,
How are things? Long time no see (if it applies to forums :))

Thanks for the link. Yes, watched it last night. But I am trying to make something very basic.
I am sure Vector3.Distance is a way to go.

7

I’d go for something like “Poisson Disc Sampling” above rather than just pure random then you don’t need to do all this expensive checking. Also, you have to be careful of setting up a situation where you are forever searching so you then need to set-up a threshold. You could use physics to help you here but again, it seems like a brute-force way to go.

Here’s some example code which might help but it isn’t how I’d choose to do it:

using System.Collections.Generic;
using UnityEngine;

public class CreatorExample : MonoBehaviour
{
    public GameObject MyPrefab;
    public float minRange = 2f;
    public int AllowedSearches = 10;
    public List<GameObject> items = new List<GameObject> ();

    private void Start()
    {
        CreateItems(50);
    }

    void CreateItems(int itemQuantity)
    {
        for(var n = 0; n < itemQuantity; ++n)
        {
            var searchCount = AllowedSearches;

            // Keep searching to our limit.
            while(searchCount-- > 0)
            {
                // Choose a random position.
                var position = GetRandomPositionOnMesh();

                // Is the position is empty?
                if (IsPositionEmpty(position))
                {
                    // Yes, so add to the list.
                    items.Add(Instantiate(MyPrefab, position, Quaternion.identity));

                    break;
                }
            }
        }
    }

    bool IsPositionEmpty(Vector3 position)
    {
        // This will increase in time as we get more items.
        foreach(var item in items)
        {
            if (Vector3.Distance(position, item.transform.position) < minRange)
                return false;
        }

        return true;
    }

    // Made-up random call.
    Vector3 GetRandomPositionOnMesh() { return Random.insideUnitSphere * 100f; }
}
1 Like
8

I have a bunch of spawning and deconflicting examples in my MakeGeo package.

MakeGeo is presently hosted at these locations:

https://bitbucket.org/kurtdekker/makegeo

Probably the closest specific example can be found in the SpawningOverAnArea scene / folder / script.

1 Like
9

This is great! Thank you guys so much. I will give “Poisson Disc Sampling” a go and also will try simple brute-force.
I will share where I will end up …

2 Likes
10

To be honest this is what I was looking for. Thank you @MelvMay
I just had to split my functions in two. It is much clear now…

// Check if position is empty from existing objects
    private bool IsPositionEmpty(Vector3 position)
    {
        // This will increase in time as we get more items.
        foreach (var item in objects)
        {
            if (Vector3.Distance(position, item.transform.position) < range)
            {
                return false;
            }
        }
        return true;
    }
1 Like