Как найти ближайшее свободное место для размещения объекта?
Добавлено:
21 апр 2018, 08:31
novavision
Привет.
Не могу найти подходящий и простой алгоритм для определения ближайшего места для размещения круглого спарайта на доске с другими спрайтами. Пример в скриншоте
http://take.ms/mygD6Пример - пользователь перетаскивает красный кружок, и отпускает мышь на границе. Нужно понять, куда можно разместить этот новый объект. На картинке довольно простой случай, но будут такие, когда на сцене уже много других размещенных объектов с разными радиусами (но тем не менее все круглые)
Подскажите пожалуйста, с чего начать?
Re: Как найти ближайшее свободное место для размещения объекта?
Добавлено:
21 апр 2018, 08:52
1max1
Тащи на сцену пустышку с коллайдером, определяй есть ли коллизия с другими, если нету значит можно установить объект.
Re: Как найти ближайшее свободное место для размещения объекта?
Добавлено:
21 апр 2018, 10:44
novavision
1max1 писал(а):Тащи на сцену пустышку с коллайдером, определяй есть ли коллизия с другими, если нету значит можно установить объект.
Не особо представляю как это сделать все в одном кадре, но вообще это делаю и без пустышки сейчас, через Physics2D.OverlapCircle, но сложность то в том, что там может быть огромное количество вариантов размещения, ведь поиск места не идет по какой то определенной траектории
Re: Как найти ближайшее свободное место для размещения объекта?
Добавлено:
21 апр 2018, 11:08
1max1
А в чем проблема? Если твой коллайдер на том объекте который ты хочешь разместить не соприкасается ни с какими другими коллайдерами других объектов, то можно разместить это объект.
У тебя размещение вручную или методом тыка?
Re: Как найти ближайшее свободное место для размещения объекта?
Добавлено:
21 апр 2018, 11:41
novavision
Как раз это я и пытался объяснить в теме и скриншоте - попробую по другому
Второй скриншот
http://take.ms/uYEOiНадо ПРОГРАМНО найти возможные места 1 и 2, без каких либо манипуляций со стороны пользователя
Re: Как найти ближайшее свободное место для размещения объекта?
Добавлено:
21 апр 2018, 14:13
1max1
Это уже алгоритмы поиска пути, тут я не помогу с грамотной реализацией.
Если быдло кодом, то можно циклом пробежаться по всему полю с рейкастом и брать ближайшее свободное место к позиции мышки:)
Re: Как найти ближайшее свободное место для размещения объекта?
Добавлено:
28 апр 2018, 13:07
formurik
Эээ... может я чего-то не понимаю, но по моему, вот это
https://docs.unity3d.com/ScriptReference/Physics2D.CircleCast.html, то самое, что вам нужно.
Re: Как найти ближайшее свободное место для размещения объекта?
Добавлено:
28 апр 2018, 15:15
formurik
Re: Как найти ближайшее свободное место для размещения объекта?
Добавлено:
26 июн 2018, 08:31
novavision
Спасибо за ответ. Я рассматривал такой подход, но он довольно тяжелый в рассчетах. Тем не менее имеет право быть
Re: Как найти ближайшее свободное место для размещения объекта?
Добавлено:
28 июн 2018, 08:03
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), а затем проверить каждую из них на нахождение вне каждого круга.