Алгоритм распространения меток визуально привлекательным и интуитивно понятным способом

24

Укороченная версия

Существует ли шаблон дизайна для распределения этикеток транспортных средств непересекающимся образом, размещая их как можно ближе к транспортному средству, к которому они относятся? Если нет, то является ли какой-либо метод, который я предлагаю, жизнеспособным? Как бы вы реализовали это сами?

Расширенная версия

В игре, которую я пишу, у меня есть вид с высоты птичьего полета моих летательных аппаратов. У меня также есть рядом с каждым из транспортных средств небольшая табличка с ключевыми данными об автомобиле. Это фактический скриншот:

Два автомобиля с их ярлыками

Теперь, когда машины могли летать на разных высотах, их значки могли перекрываться. Однако я бы не хотел, чтобы их ярлыки перекрывали друг друга (или ярлык транспортного средства «А» перекрывал значок транспортного средства «В»).

В настоящее время я могу обнаружить столкновения между спрайтами и просто оттолкнуть поврежденную метку в направлении, противоположном спрайту, перекрывающемуся в противном случае . Это работает в большинстве ситуаций, но когда воздушное пространство переполнено, этикетка может отодвинуться очень далеко от своего транспортного средства, даже если была альтернатива «умнее». Например я получаю:

  B - label
A -----------label
  C - label

где было бы лучше (= наклейка ближе к автомобилю) получить:

          B - label
label - A
          C - label

РЕДАКТИРОВАТЬ: Следует также учитывать, что помимо случая перекрытия транспортных средств, могут быть другие конфигурации, в которых метки транспортных средств могут перекрываться (примеры ASCII-искусства показывают, например, три очень близких транспортных средства, в которых метка Aбудет перекрывать значок Bи C).

У меня есть две идеи о том, как улучшить существующую ситуацию, но прежде чем тратить время на их реализацию, я подумал обратиться к сообществу за советом (в конце концов, это кажется «достаточно общей проблемой», что шаблон проектирования для него может существовать).

Для чего это стоит, вот две идеи, о которых я думал:

Слотация пространства метки

В этом сценарии я бы разделил весь экран на «слоты» для надписей. Тогда у каждого транспортного средства всегда будет метка, расположенная в ближайшем пустом (пусто = других спрайтов в этом месте нет).

Спиральный поиск

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

try 0°, 10px
try 10°, 10px
try 20°, 10px
...
try 350°, 10px
try 0°, 20px
try 10°, 20px
...
макинтош
источник
1
Сколько самолетов может перекрываться одновременно?
Вангбургер
1
@wangburger - Никогда не думал, что это будет актуально (было бы интересно узнать больше о вашем образе мыслей), но ответ таков: это зависит от стратегии игры игрока. Технически мир мог бы иметь 24 транспортных средства, перекрывающихся, но реалистичная фигура в большинстве игровых условий - 3-4.
Мак
3
Разве не сложнее иметь движущиеся метки относительно плоскости, чем перекрывающиеся, но статичные в течение разумного периода времени?
Майк Земдер
3
Вы можете быть заинтересованы в en.wikipedia.org/wiki/… - это не простая проблема, которую нужно решить. Не ждите, чтобы найти идеальное решение.
Блецки
2
GraphViz - это набор инструментов для построения графиков визуально приятным способом, с тенденцией избегать наложений на ярлыки. Хотя это может быть невозможно использовать напрямую, вы можете почерпнуть некоторую информацию из их документации или исходного кода о том, какие алгоритмы они используют для разметки своих графиков. Например, у них есть как модели на основе энергии, так и модели на основе пружины.
Ларс Виклунд

Ответы:

14

По сути, эта проблема похожа на проблему предотвращения столкновений. Да, самолеты могут летать на разных высотах, но их метки находятся на одной и той же «высоте».

Существуют такие алгоритмы, как Unaligned Collision Avoidance , которые будут шагом в правильном направлении для вас. Конечно, для вашей ситуации метки «привязаны» к своим плоскостям, поэтому они имеют ограниченный диапазон движения.

Если вы посмотрите на поведение флокирования, вы захотите реализовать первое «правило» флокирования: отталкивание на короткие расстояния. Однако вместо «поворота» в направлении, удаленном от ближайших соседей, вы будете использовать вектор «вдали» в качестве места размещения для вашей метки.

Например:

введите описание изображения здесь

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

Теперь черные точки могут представлять либо другие метки, либо другие плоскости. Я не уверен, какой из них лучше всего подойдет, вы можете лучше избежать, если бы они были другими лейблами, но я не уверен. Очевидно, что стрелки «силы» - это векторы направления между вашей текущей плоскостью и «объектами влияния». Наконец, на коробке стоит этикетка.

Итак, используя ваш пример выше, я думаю, что это приведет к чему-то вроде:

            - label
           / 
          B 
label - A
          C 
           \
            - label

При использовании этого метода есть несколько ситуаций, для которых вам нужно создать особые случаи, например, три плоскости, выровненные вертикально:

          - label       label -
          |                   |
          B                   B
  label - A                   A - label
          C                   C
          |                   |
          - label       label -

Все три надписи могут переворачиваться справа налево, в зависимости от того, как определены углы надписей. По сути, вам просто нужно следить за углами вокруг круга, где ваши метки могут переключаться, из какого угла они нарисованы: 0, 90, 180, 270.

введите описание изображения здесь

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

Извините за странные детали, большинство из этих вещей, о которых я думал, когда создавал радиальное меню для своей игры, но я думаю, что в этой «динамической» форме это будет работать довольно хорошо.

MichaelHouse
источник
1
На самом деле в моем примере даже не учитывались плоскости, которые находятся прямо друг над другом, так как их координаты x и z точно совпадают (но если вы используете поплавки, этого, скорее всего, не произойдет). Я привел примеры самолетов рядом друг с другом. Кроме того, как я уже сказал, вы можете думать о черных точках на изображении выше как о других метках.
MichaelHouse
1
О, кажется, вы удалили свой комментарий?
MichaelHouse
1
Что я имел в виду в своем предыдущем [плохо сформулированном и, следовательно, теперь удаленном) комментарии, так это то, что у вас может быть сценарий, в котором метка «захвачена / окружена» другими неподвижными (то есть транспортными средствами) спрайтами. В этом случае, возможно, метка должна «выпрыгнуть» за пределы окружающего круга, но мне не совсем понятно, как это должно происходить. Кстати, я изначально думал, что зеленой точкой вашей фотографии были несколько самолетов, сложенных друг на друге, но после вашего комментария я понял, что был неправ ... извините!).
Мак
1
Ах я вижу. Таким образом, вы будете рассматривать черные точки как плоскости и метки. Если позиция, найденная на первой итерации, не подходит, удвойте радиус и проверьте снова. Или у вас уже есть вектор, который указывает на большую часть толпы, вы можете следить за этим, пока не найдете место, которое работает. Однако я думаю, что первый метод будет иметь лучшие результаты.
MichaelHouse
9

Подумав немного, я наконец решил реализовать метод спирального поиска, который я кратко описал в исходном вопросе.

Обоснование состоит в том, что метод Byte56 требует специальной обработки для определенных условий, в то время как поиск по спирали - нет, и он кодирует очень компактным способом . Кроме того, быстрый поиск подчеркивает нахождение ближайшего места к транспортному средству для размещения этикетки, что, по мнению IMO, является основным фактором, делающим карту удобочитаемой.

Однако, пожалуйста, продолжайте высказывать свое мнение, так как он не только полезен, но и очень хорошо написан!

Вот скриншот результата, достигнутого с помощью спирального кода:

введите описание изображения здесь

А вот код, который, хотя и не является автономным, дает представление о том, насколько проста реализация:

def place_tags(self):
    for tag in self.tags:
        start_angle = tag.angle
        while not tag.place() or is_colliding(tag):  #See note n.1
            tag.angle = (tag.angle + angle_step) % 360
            if tag.angle == start_angle:
                tag.radius += radius_step
        tag.connector.update()                       #See note n.2

Примечание 1 - tag.place()возвращает True, если тег полностью находится в видимой области экрана / радара. Таким образом, эта строка выглядит как «продолжать цикл, если тег находится за пределами радара или перекрывает что-то еще ...»

Примечание 2 - tag.connector.updateэто метод, который рисует линию, соединяющую значок самолета с меткой / меткой с текстовой информацией.

макинтош
источник
Хорошо сделано, это действительно очень компактно. Спасибо за похвалу. Также спасибо за сообщение о том, что вы в итоге сделали, это всегда полезно для людей, которые ищут ответы позже. На скриншоте это выглядит очень хорошо! Обязательно примите свой ответ, так как это то, что вы в итоге пошли.
MichaelHouse
@ Byte56 - Спасибо за "ретро-похвалу";) Я жду, чтобы выбрать ответ как принятый, потому что я все еще хотел бы написать и ваше решение и сравнить результат. С одной стороны, я подозреваю, что ваше решение может привести к более длинному, но и более быстрому выполнению кода. Кроме того, я хотел бы увидеть, как эти два сравниваются в очень загруженном воздушном пространстве ... так что есть еще шанс, что я смогу выпустить код с вашим алгоритмом. Смотреть это пространство! ;)
Mac
@ Byte56 - я попытался реализовать твой алгоритм. Он работал хорошо и быстро при низкой плотности, но как только пространство было забито, у меня возникли проблемы с нахождением простой реализации, которая справилась бы с конкретными ситуациями, в которых метка должна «перепрыгнуть» блок других меток или попасть в ловушку подвижные (т.е. плоские иконки) спрайты. Я отмечаю этот ответ как выбранный тогда, но снова: большое спасибо за время и вклад! :)
Mac