Prevent objects from overlapping when spawning in random locations (Unity 2D)

Question

I’m struggling to stop prefab objects from overlapping when they spawn. I’ve Googled a lot of similar questions and realized that this issue is common in game development, but I’m having trouble solving it myself.

I have a prefab with a Box Collider 2D and a Sprite Renderer components. They are bound to the screen boundary and spawn randomly anywhere within this boundary. Every 8 seconds the number of prefabs increases by 1 until it reaches 8 objects. The problem is that as the number of objects increases, the available space for spawning decreases, and the prefab tries to find any free space. If it can't find any, it spawns in any location resulting in overlapping with other prefabs (see GIF).

How can I ensure that prefabs don't overlap each other when spawning a large number of objects? The GIF shows that there is still plenty of free space for spawning prefabs, but for some reason it doesn't detect these spaces and overlaps with other objects. I tried a few things, but it didn't work (look at GetUniqueSpawnPosition).

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class SpikeController : MonoBehaviour
{
    public int initialSpikeCount = 3;          // Initial number of spikes
    public int maxSpikes = 8;                  // Maximum number of spikes
    public int spikesIncreaseInterval = 8;     // Interval for increasing spikes
    public float spikeSpawnInterval = 1.5f;    // Spikes disappear time
    public GameObject spikePrefab;             // Spike prefab

    public Transform LeftBoundary;            

    private int currentSpikeCount;
    private List<GameObject> spikes = new List<GameObject>();

    // Spike size
    public Vector3 spikeSize = new Vector3(2.84f, 2.84f, 2.84f);

    void Start()
    {
        currentSpikeCount = initialSpikeCount;
        SpawnSpikes();
        StartCoroutine(SpikeIncreaseRoutine());
    }

    void Update()
    {
        if (spikes.Count < currentSpikeCount)
        {
            SpawnSpikes();
        }
    }

    private IEnumerator SpikeIncreaseRoutine()
    {
        while (currentSpikeCount < maxSpikes)
        {
            yield return new WaitForSeconds(spikesIncreaseInterval);
            IncreaseSpikeCount();
        }
    }

    private void SpawnSpikes()
    {
        ClearSpikes();  // Remove previous spikes if any

        for (int i = 0; i < currentSpikeCount; i++)
        {
            Vector3 spawnPosition = GetUniqueSpawnPosition();
            GameObject spike = Instantiate(spikePrefab, spawnPosition, Quaternion.Euler(0, 0, 90f)); // Spawning only on the left
            
            // Set the size of the prefab
            spike.transform.localScale = spikeSize;
            
            spikes.Add(spike);
            StartCoroutine(RemoveSpikeAfterDelay(spike, spikeSpawnInterval));
        }
    }

    private Vector3 GetUniqueSpawnPosition()
    {
        BoxCollider2D boundaryCollider = LeftBoundary.GetComponent<BoxCollider2D>();
        float boundaryYMin = LeftBoundary.position.y - boundaryCollider.size.y / 2;
        float boundaryYMax = LeftBoundary.position.y + boundaryCollider.size.y / 2;

        float x = -2.24f; // Fixed position on the left
        float y = 0;

        float spikeHeight = spikeSize.y;  // Spike height

        // Adjust y range to avoid spawning outside the boundary
        float boundaryMin = boundaryYMin + spikeHeight / 2;
        float boundaryMax = boundaryYMax - spikeHeight / 2;

        // Try to find a unique spawn position
        for (int attempt = 0; attempt < 100; attempt++)
        {
            y = Random.Range(boundaryMin, boundaryMax); // Adjusted for the height of the spike

            Vector3 potentialPosition = new Vector3(x, y, 0);

            if (!IsOverlappingWithExistingSpikes(potentialPosition, spikeSize.x, spikeSize.y))
            {
                return potentialPosition;
            }
        }

        Debug.LogWarning("Cannot find unique positions");
        return new Vector3(x, Random.Range(boundaryMin, boundaryMax), 0);
    }

    private bool IsOverlappingWithExistingSpikes(Vector3 position, float width, float height)
    {
        // Check for overlap with existing colliders
        foreach (var spike in spikes)
        {
            if (Vector2.Distance(position, spike.transform.position) < (width / 2 + spikeSize.x / 2))
            {
                return true;
            }
        }

        return false;
    }

    public void IncreaseSpikeCount() 
    {
        if (currentSpikeCount < maxSpikes)
        {
            currentSpikeCount++;
            SpawnSpikes();  // Create new spikes after increasing the count
        }
    }

    private void ClearSpikes()
    {
        foreach (var spike in spikes)
        {
            Destroy(spike);
        }
        spikes.Clear();
    }

    private IEnumerator RemoveSpikeAfterDelay(GameObject spike, float delay)
    {
        yield return new WaitForSeconds(delay);
        spikes.Remove(spike);
        Destroy(spike);
    }
}

I tried to find a position for spawning a prefab by making up to 100 attempts. I limited the number of attempts to find a unique position to 100 because I am unsure how a larger number of attempts might affect overall performance, and it seems like increasing the attempts doesn't make any difference.

I expected it to find a unique position for each prefab so that they don't overlap. However, it didn't work as expected. When prefabs can't find a unique position, they start looking for any available space to spawn which results in overlapping.

Answer 1

Jittered grid

1. Create n spikes evenly.
2. Add a random offset to the position of each spike.

Poisson disc

1. Randomly add a spike.
2. Add new spikes at random position near the previous spike each time.

Ordered list

1. Save spikes in an ordered (by position) list.
2. Randomly select a spike from the list.
3. Calculate whether the space between this spike and the prev/next spike in the list (or boundary) can hold at least one spike, and if so, add a spike at a random position in the space, if not, repeat the previous step.

Answer 2

Just create a list of positions and after creating the object in the current random position, add that position to the list and when creating the next object in the new position, compare that position with the positions in the list and check that Do not overlap. If there is an overlap with the positions in the list, select a new random position again, otherwise save the object in the random position and add that position to the list like the previous position. Sorry for my poor English.