Как найти пустое место на воде в 2d?

Question

[Аркадий Баганин]

Доброго времени суток!
Мне нужно сделать спавнер кораблей и птичек. Я не придумал ничего лучше, чем создать переменную "Dir", где хранится направление пути каждого монстра(у кораблей y = 0, у птиц = 3)... Когда 0, то мы высчитываем верхнюю точку воды и перемещаем туда объект... Но у меня другая проблема, как сделать, чтобы мобы друг над другом не спавнились, я прикреплю код ниже, функция, которая отвечает за x позицию кораблей называется poolObj()

Говнокод

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

public class EnemyController : MonoBehaviour
{
    private Rigidbody2D _rb;
    private GameCamera _gc;
    private EnemyData _data;

    private GameObject _water;

    private int _minX;
    private int _maxX;

    public EnemyData Data
    {
        get
        {
            return _data;
        }

        set
        {
            _data = value;
        }
    }

    public void Start()
    {
        _rb = GetComponent<Rigidbody2D>();
        _gc = Camera.main.GetComponent<GameCamera>();

        _water = GameObject.FindGameObjectWithTag("Water");
        _minX = (int)Mathf.RoundToInt(1 - _gc.OffsetCamX) - 5;
        _maxX = (int)Mathf.RoundToInt(Camera.main.ScreenToWorldPoint(_water.transform.position).x + Camera.main.ScreenToWorldPoint(_water.GetComponent<BoxCollider2D>().size * _water.transform.localScale).x);
        _maxX = (int)Mathf.RoundToInt((1 - (_maxX + Camera.main.ScreenToWorldPoint(this.GetComponent<BoxCollider2D>().size * this.transform.localScale).x)) * 2) + 10;

        float _waterY = Camera.main.ScreenToWorldPoint(_water.transform.position).y - (Camera.main.ScreenToWorldPoint(_water.GetComponent<BoxCollider2D>().size * _water.transform.localScale).y / 2);
        float _yPos = _data.Dir.y > 0 ? _data.Dir.y : _waterY;
        transform.position = new Vector3(transform.position.x, _data.Dir.y, transform.position.z);

        GetComponent<Animator>().runtimeAnimatorController = _data.AnimController;
        GetComponent<AudioSource>().clip = _data.WalkSound;
        GetComponent<AudioSource>().loop = true;

        GetComponent<SpriteRenderer>().sprite = _data.Skin;

        transform.localScale = _data.ScaleEnemy;

        if (_data.IsBird)
        {
            GetComponent<Rigidbody2D>().constraints = RigidbodyConstraints2D.FreezePositionY;
            transform.Rotate(0, 180, 0);
        }

        _poolObj();
    }

    private void FixedUpdate()
    {
        _rb.velocity += _data.Dir * _data.SpeedEnemy * Time.fixedDeltaTime;

        if (transform.position.x < _minX)
        {
            _poolObj();
        }
    }

    private void _poolObj()
    {
        int x = Random.Range(1 - _minX, _maxX);
        List<int> _usedCoordX = new List<int>();
        GameObject[] enemies = GameObject.FindGameObjectsWithTag("Enemy");

        foreach (GameObject enemy in enemies)
        {
            int _cx = (int)Mathf.RoundToInt(enemy.transform.position.x);

            if (_cx != (int)Mathf.RoundToInt(transform.position.x))
            {
                _usedCoordX.Add(_cx);
                _usedCoordX.Add(_cx - (int)Mathf.RoundToInt(Camera.main.ScreenToWorldPoint(enemy.GetComponent<BoxCollider2D>().size * enemy.transform.localScale).x));
                _usedCoordX.Add(_cx + (int)Mathf.RoundToInt(Camera.main.ScreenToWorldPoint(enemy.GetComponent<BoxCollider2D>().size * enemy.transform.localScale).x));
            }
        }

        int _checkX = (int)Mathf.RoundToInt(Camera.main.ScreenToWorldPoint(GetComponent<BoxCollider2D>().size * transform.localScale).x);

        if (_usedCoordX.Equals(x) || _usedCoordX.Equals(x + _checkX) || _usedCoordX.Equals(x - _checkX))
        {
            x = Random.Range(1 - _minX, _maxX);
        } else
        {
   <b></b>         transform.position = new Vector3(x, transform.position.y, transform.position.z);
        }
    }
}

Скриншот игры

Как исправить баг, чтобы они друг над другом не спавнились, т.е как найти пустое пространство? И как можно красивее оформить код?

Answer 1

[AlexHell]

простое решение - цикл перебора рандомных варинтов X

// ВНЕ цикла подбора рандомного X для оптимизации
  foreach (GameObject enemy in enemies)
  {
    // заполнить _usedCoordX
  }
// цикл подбора рандомного X
while (true)
{
  int x = Random.Range(1 - _minX, _maxX);
  if (!_usedCoordX.Contains(x)) break;
}

(НЕ эффективное по перфомансу, можно оптимизить - структурами Spatial или заполненными областями - не буду приводить реализации)

___
UPDATE:

там где _usedCoordX заполняется
хорошо бы бить поле на GRID равномерный, аналог хеша
______
|__|__|
|__|__|

например
если позиция object.X >= 10 && object.X < 20 то newX=1
если позиция object.X >= 20 && object.X < 30 то newX=2
и т.п с шагом 10
тогда при уже существующем объекте с X = 15, не сгенерится объект с X = 16 или 17 и т.п т.к они в одной ячейке сетки

и Random конечно по той же размерности кидать (_maxX должен быть не полного пиксельного\объектого размера, а размера сетки)

UPD2: по теме https://gamedev.stackexchange.com/questions/69310/...
и там же есть картинка

UPD3: вместо равномерного GRID - можно юзать истинный Collision Detection, т.е после генерации Random X - проверять всех врагов вокруг, и если есть - генерить заного, так наверное лучше будет

.. но опять же можно проверять по GRID-у всех в этой же ячейке (т.е если X равен 15, то проверим всех врагов - есть ли они в X от 10 до 19, и если нет - выход из цикла
.. плюс проверять в соседних ячейках (иначе будут прям вплотную генериться