Instantiating objects randomly on a sphere with set distances

Unity Engine
,
1

Hello Everyone.

I am working on a game where the player is able to run around a sphere. (a tiny planet if you will), this is working quite well and I am now looking into randomly generating these planets so there can be some variety.

        void GenerateObjects()
        {
            currentPrefab = treePrefab;
 
            string holderName = "Generated Objects";
 
            if (transform.Find(holderName))
            {
                DestroyImmediate(transform.Find(holderName).gameObject);
            }
 
            Transform holder = new GameObject(holderName).transform;
            holder.parent = transform;
 
 
            objectCount = 0f;
            while (objectCount < maxObjects)
            {
                Vector3 randomPoint = Random.onUnitSphere * planetSize / 10;
 
                Transform obj = Instantiate(treePrefab, randomPoint, Quaternion.identity).transform;
                obj.name = "Tree " + objectCount;
                obj.parent = holder;
 
                Vector3 gravityUp = (obj.position - transform.position).normalized;
                Vector3 localUp = obj.transform.up;
 
                obj.rotation = Quaternion.FromToRotation(localUp, gravityUp) * obj.rotation;
 
                objectCount++;
            }
        }

In the code above I generate random points, Instantiate the prefabs and rotate them so that they are faced the right way up on the sphere. the only downside here is that the objects tend to overlap. I’ve tried many ‘solutions’ to this so far but to no avail. Very often it ends up in my unity crashing due to it running into an infinite loop when it comes to generating random points.

Imgur: The magic of the Internet (just a minor example, there are also cases where its fully inside a previously instantiated object.

I hope someone can help me with this!
Thanks!

2

One easy and fast way to deconflict objects spatially is to produce a key from a quantized version of their Vector3 position and use that to index a HashSet that tracks all used “boxes.”

Given your randomPoint position above, one quick way to make a key is to use .ToString() on it.

string key = randomPoint.ToString();

This will end up with something like “(0.1,0.4,-0.2)”, which we consider a unique identifier for this point in space.

At the start you create your HashSet:

HashSet<string> UsedBoxes = new HashSet<string>();

Whenever you go to place an object, you make a key from its randomPoint and then check if the HashSet already contains that value. If it does, pick another spot. If it does not, use that spot up by adding it to the HashSet:

if (!UsedBoxes.Contains( key))
{
   // it's open, we can use it!
   UsedBoxes.Add( key);
}

Of course this leaves still the possibility of two objects been right next to each other juuuuuuust across the boundary of a “box,” such as 0.1999 and 0.2001, or however the rounding math works out.

Therefore instead of adding one key above, you would test only ONE key, but when you find the box open, you would add several keys, each key generated from slightly-adjacent position. You would select how big this adjacent space is based on the size of your objects, which defines how close they can be placed to each other.

Keep in mind if ALL the possible spots are taken, you must have a retry count so you will eventually give up. Otherwise your code could deadlock once all the tree spots are taken up.

2 Likes
3

I was actually curious how a cartesian coordinate spatial deconflict would look on a sphere so I put together a quick demo project, attached to this message. It actually works pretty well for tall tree-like things.

You could blob out large swaths of area in advance if you wanted to mark areas of “no trees.”

Of course you could also knock giant gaps into the trees AFTER creating them, to create clearings like a Daisy Cutter bomb.

5953931–638057–DeconflictSpatially.unitypackage (3.59 KB)

1 Like
4

It’s a good solution and fixed the problem somewhat. The only problem that arises for me now is that it doesnt always generate all the objects I told it to (so lets say I tell it to generate 50 trees, sometimes it does so, sometimes it only generates 7 or any other random number it seems like?)

    void GenerateObjects()
    {
        currentPrefab = treePrefab;

        string holderName = "Generated Objects";

        if (transform.Find(holderName))
        {
            DestroyImmediate(transform.Find(holderName).gameObject);
        }

        Transform holder = new GameObject(holderName).transform;
        holder.parent = transform;


        objectCount = 0f;

        while (objectCount < maxObjects)
        {
            Vector3 point = Random.onUnitSphere * planetSize / 10;

            string key = MakeVector3IntoKey(point);

            if (hs.Contains(key))
            {
                failCounter++;

                if (failCounter > failsInARowBeforeGivingUp)
                {
                    break;
                }
            }
            else
            {
                Transform obj = Instantiate(currentPrefab, point, Quaternion.identity).transform;
                obj.name = "Tree " + (objectCount + 1);
                obj.parent = holder;

                Vector3 gravityUp = (obj.position - transform.position).normalized;
                Vector3 localUp = obj.transform.up;
                obj.rotation = Quaternion.FromToRotation(localUp, gravityUp) * obj.rotation;

                // mark a small collection of boxes around us in 3D space;
                for (int k = -1; k <= 1; k++)
                {
                    for (int j = -1; j <= 1; j++)
                    {
                        for (int i = -1; i <= 1; i++)
                        {
                            var point2 = point + new Vector3(i, j, k) * radius;

                            key = MakeVector3IntoKey(point2);

                            hs.Add(key);        // might be dupes, who cares
                        }
                    }
                }

                objectCount++;
            }
        }

        if (objectCount < maxObjects)
        {
            Debug.LogError("RECURSION");
            GenerateObjects();
        }
    }

I adapted your snippet in this way (the last recursion bit was just an attempt in making it generate all the things I ask it to but even that doesnt work.