Как найти ближайшее свободное место для размещения объекта?

[novavision]

Привет.

Не могу найти подходящий и простой алгоритм для определения ближайшего места для размещения круглого спарайта на доске с другими спрайтами. Пример в скриншоте
http://take.ms/mygD6

Пример - пользователь перетаскивает красный кружок, и отпускает мышь на границе. Нужно понять, куда можно разместить этот новый объект. На картинке довольно простой случай, но будут такие, когда на сцене уже много других размещенных объектов с разными радиусами (но тем не менее все круглые)

Подскажите пожалуйста, с чего начать?

[1max1]

Тащи на сцену пустышку с коллайдером, определяй есть ли коллизия с другими, если нету значит можно установить объект.

[novavision]

Тащи на сцену пустышку с коллайдером, определяй есть ли коллизия с другими, если нету значит можно установить объект.

Не особо представляю как это сделать все в одном кадре, но вообще это делаю и без пустышки сейчас, через Physics2D.OverlapCircle, но сложность то в том, что там может быть огромное количество вариантов размещения, ведь поиск места не идет по какой то определенной траектории

[1max1]

А в чем проблема? Если твой коллайдер на том объекте который ты хочешь разместить не соприкасается ни с какими другими коллайдерами других объектов, то можно разместить это объект.

У тебя размещение вручную или методом тыка?

[novavision]

Как раз это я и пытался объяснить в теме и скриншоте - попробую по другому
Второй скриншот
http://take.ms/uYEOi

Надо ПРОГРАМНО найти возможные места 1 и 2, без каких либо манипуляций со стороны пользователя

[1max1]

Это уже алгоритмы поиска пути, тут я не помогу с грамотной реализацией.
Если быдло кодом, то можно циклом пробежаться по всему полю с рейкастом и брать ближайшее свободное место к позиции мышки:)

[formurik]

Эээ... может я чего-то не понимаю, но по моему, вот это https://docs.unity3d.com/ScriptReference/Physics2D.CircleCast.html, то самое, что вам нужно.

[formurik]

Чет стало интересно, чуток повозился. Вот что получилось http://take.ms/luWdD Архив проекта https://drive.google.com/file/d/1R9sJSnkqpdrxf-I35uB8YABOTXy87J6r/view?usp=sharing

[novavision]

Чет стало интересно, чуток повозился. Вот что получилось http://take.ms/luWdD Архив проекта https://drive.google.com/file/d/1R9sJSnkqpdrxf-I35uB8YABOTXy87J6r/view?usp=sharing

Спасибо за ответ. Я рассматривал такой подход, но он довольно тяжелый в рассчетах. Тем не менее имеет право быть

[jetyb]

Задача: пусть дано n кругов на доске с радиусами r_1, ... , r_n , надо найти на доске место куда можно вписать круг с радиусом r.
Она равносильна задаче: пусть дано n кругов с радиусами r_1 + r, ... , r_n + r , надо найти на доске место куда можно поставить точку.
Наблюдение: самое компактное место для этой точки находится на границе одного из кругов r_i + r.

Алгоритм:
- для каждого существующего круга r_i проверяем его на пересечение с остальными кругами
- если он пересекается с кругом r_j, то находим точки пересечения r_i с r_j, если какая-то из них лежит вне остальных кругов (кроме r_i и r_j) и на доске, то эта точка - искомая.
- если круг r_i не пересекается ни с каим из кругов, то берем любую точку на границе r_i, лежащую на доске.
- если же на всех кругах не удалось таким действиями найти искомой точки, то точку поставить нельзя.

Сложность алгоритма O(n^3) , n - число кругов, на практике скорее O(n^2).
Можно решить и за O(n^2), если найти все точки попарного пересечения всех кругов (r_i, r_j), а затем проверить каждую из них на нахождение вне каждого круга.