Algoritmo para difundir etiquetas de una manera visualmente atractiva e intuitiva

24

Version corta

¿Existe un patrón de diseño para distribuir las etiquetas de los vehículos de manera que no se superpongan, colocándolos lo más cerca posible del vehículo al que se refieren? Si no, ¿es viable alguno de los métodos que sugiero? ¿Cómo implementaría esto usted mismo?

Versión extendida

En el juego que estoy escribiendo tengo una visión panorámica de mis vehículos en el aire. También tengo al lado de cada uno de los vehículos una pequeña etiqueta con datos clave sobre el vehículo. Esta es una captura de pantalla real:

Dos vehículos con sus etiquetas.

Ahora, dado que los vehículos podrían estar volando a diferentes altitudes, sus íconos podrían superponerse. Sin embargo, me gustaría que sus etiquetas no se superpongan (o que una etiqueta del vehículo 'A' se superponga con el icono del vehículo 'B').

Actualmente, puedo detectar colisiones entre sprites y simplemente elimino la etiqueta ofensiva en una dirección opuesta al sprite superpuesto . Esto funciona en la mayoría de las situaciones, pero cuando el espacio aéreo se llena, la etiqueta puede ser empujada muy lejos de su vehículo, incluso si hubiera una alternativa alternativa "más inteligente". Por ejemplo me sale:

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

donde sería mejor (= etiqueta más cerca del vehículo) obtener:

          B - label
label - A
          C - label

EDITAR: También debe tenerse en cuenta que, además del caso de los vehículos superpuestos, podría haber otras configuraciones en las que se podrían superponer las etiquetas de los vehículos (los ejemplos de arte ASCII muestran, por ejemplo, tres vehículos muy cercanos en los que la etiqueta de Ase superpondría al icono de By C)

Tengo dos ideas sobre cómo mejorar la situación actual, pero antes de dedicar tiempo a implementarlas, pensé en pedir consejo a la comunidad (después de todo, parece un "problema bastante común" que podría existir un patrón de diseño).

Para lo que vale, estas son las dos ideas que estaba pensando:

Slot-isation del espacio de etiqueta

En este escenario, dividiría toda la pantalla en "ranuras" para las etiquetas. Luego, cada vehículo siempre tendrá su etiqueta colocada en el vacío más cercano (vacío = no hay otros sprites en esa ubicación.

Búsqueda en espiral

Desde la ubicación del vehículo en la pantalla, trataría de colocar la etiqueta en ángulos crecientes y luego en radios crecientes, hasta que se encuentre una ubicación no superpuesta. Algo en la línea de:

try 0°, 10px
try 10°, 10px
try 20°, 10px
...
try 350°, 10px
try 0°, 20px
try 10°, 20px
...
Mac
fuente
1
¿Cuántos aviones pueden superponerse a la vez?
wangburger
1
@wangburger: nunca pensé que esto sería relevante (estaría interesado en saber más sobre tu línea de pensamiento), pero la respuesta es: depende de la estrategia de juego del jugador. Técnicamente, el mundo podría tener 24 vehículos superpuestos, pero una cifra realista en la mayoría de las condiciones del juego es 3-4.
mac
3
¿No es más confuso tener etiquetas móviles en relación con el plano que superpuestas pero estáticas durante un período de tiempo razonable?
Maik Semder
3
Puede que le interese es.wikipedia.org/wiki/… : este no es un problema simple de resolver. No esperes encontrar una solución perfecta.
Blecki
2
GraphViz es un conjunto de herramientas para diseñar gráficos de una manera visualmente agradable, con una tendencia a evitar solapamientos en las etiquetas. Si bien es posible que no se pueda usar directamente, es posible que pueda obtener cierta información de su documentación o código fuente sobre qué tipo de algoritmos usan para diseñar sus gráficos. Parecen tener modelos basados ​​en energía y modelos basados ​​en resortes, por ejemplo.
Lars Viklund

Respuestas:

14

Esencialmente, este problema es similar a un problema para evitar colisiones. Sí, los aviones pueden volar a diferentes altitudes, pero sus etiquetas están a la misma "altitud".

Hay algoritmos como Evitar colisiones sin alinear , que sería un paso en la dirección correcta para usted. Por supuesto, para su situación, las etiquetas están "atadas" a sus planos, por lo que tienen un rango de movimiento limitado.

Si observa el comportamiento de flocado , desea implementar la primera "regla" de flocado: repulsión de corto alcance. Sin embargo, en lugar de "dirigirse" en la dirección que está lejos de los vecinos más cercanos, utilizará el vector "lejos" como ubicación de ubicación para su etiqueta.

Por ejemplo:

ingrese la descripción de la imagen aquí

El círculo negro grande representa su área de influencia, el círculo verde representa las ubicaciones válidas para la etiqueta, el punto verde central es el plano que está considerando actualmente, el punto verde pequeño es el punto en el círculo elegido para la colocación de la etiqueta.

Ahora los puntos negros podrían representar otras etiquetas u otros planos. No estoy seguro de cuál funcionaría mejor, puede obtener una mejor evitación si fueran otras etiquetas, pero no estoy seguro. Obviamente, las flechas de "fuerza" son los vectores de dirección entre su plano actual y los "objetos de influencia". Finalmente, el cuadro es la etiqueta.

Entonces, usando su ejemplo anterior, creo que esto produciría algo como:

            - label
           / 
          B 
label - A
          C 
           \
            - label

Con este método, hay algunas situaciones para las que tendrá que hacer casos especiales, como tres planos alineados verticalmente:

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

Las tres etiquetas pueden voltearse de derecha a izquierda, dependiendo de cómo haya definido las esquinas de su etiqueta. Básicamente, solo tendrás que estar atento a los ángulos alrededor del círculo donde tus etiquetas pueden cambiar de qué esquina están dibujadas: 0, 90, 180, 270.

ingrese la descripción de la imagen aquí

Creo que al final, esto se vería ordenado, ver cómo las etiquetas se evitan entre sí. Si te distrae demasiado, quizás puedas redondear a los 10 grados más cercanos para un movimiento menos frecuente.

Perdón por los detalles extraños, pensé en la mayoría de estas cosas cuando estaba haciendo un menú radial para mi juego, pero creo que en esta forma "dinámica" funcionaría bastante bien.

MichaelHouse
fuente
1
En realidad, mi ejemplo ni siquiera tuvo en cuenta los planos que están directamente uno encima del otro, ya que en sus coordenadas x y z coinciden exactamente (pero si está usando flotadores, esto probablemente no sucederá). Los ejemplos que di son de planos cerca uno del otro. Además, podría, como dije, pensar en los puntos negros en la imagen de arriba como otras etiquetas.
MichaelHouse
1
Oh, parece que eliminaste tu comentario?
MichaelHouse
1
Lo que quise decir con mi comentario anterior [mal formulado y ahora eliminado], fue que podría tener un escenario en el que una etiqueta está "atrapada / rodeada" por otros sprites no movibles (es decir, vehículos). En este caso, la etiqueta tal vez debería "saltar" fuera del círculo de cierre, pero no está exactamente claro para mí cómo debería suceder esto. Por cierto: originalmente pensé que el punto verde de tu foto eran varios aviones apilados uno encima del otro, pero después de tu comentario me di cuenta de que estaba equivocado ... ¡lo siento!).
mac
1
Ah, ya veo. Entonces tratarías los puntos negros como planos Y etiquetas. Si la posición encontrada por la primera iteración no es buena, duplique el radio y verifique nuevamente. O ya tiene un vector que apunta lejos de la mayoría de la multitud, podría seguirlo hasta encontrar un lugar que funcione. Sin embargo, creo que el primer método tendría mejores resultados.
MichaelHouse
9

Después de pensarlo, finalmente decidí implementar el método de búsqueda en espiral que describí brevemente en la pregunta original.

La razón es que el método Byte56 necesita un tratamiento especial para ciertas condiciones, mientras que la búsqueda en espiral no lo hace, y codifica de una manera realmente compacta . Además, la búsqueda de spriralling enfatiza encontrar el lugar más cercano al vehículo para colocar la etiqueta, lo cual es el factor principal para que el mapa sea legible.

Sin embargo, continúe votando su respuesta, ya que no solo es útil, ¡también está muy bien escrita!

Aquí hay una captura de pantalla del resultado logrado con el código en espiral:

ingrese la descripción de la imagen aquí

Y aquí está el código que, aunque no es autónomo, da una idea de cuán simple es la implementación:

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

Nota 1 : tag.place()devuelve True si la etiqueta está completamente en el área visible de la pantalla / radar. Entonces esa línea dice "sigue en bucle si la etiqueta está fuera del radar o se superpone a otra cosa ..."

Nota 2 : tag.connector.updatees el método que dibuja la línea que conecta el icono del avión con la etiqueta / etiqueta con la información del texto.

Mac
fuente
Bien hecho, eso es muy compacto. Gracias por los elogios. También gracias por publicar sobre lo que terminaste haciendo, eso siempre es útil para las personas que buscan respuestas más tarde. ¡De la captura de pantalla parece que funciona muy bien! Asegúrese de aceptar su respuesta, ya que es con lo que terminó yendo.
MichaelHouse
@ Byte56 - Gracias por el "elogio retro";) Estoy esperando seleccionar la respuesta como aceptada porque todavía me gustaría codificar su solución también y comparar el resultado. Por un lado, sospecho que su solución podría resultar en un código más largo pero también más rápido de ejecutar. Además, me gustaría ver cómo se comparan los dos en espacios aéreos muy abarrotados ... por lo que todavía existe la posibilidad de que pueda liberar el código con su algoritmo. ¡Mira este espacio! ;)
mac
@ Byte56: tuve la oportunidad de implementar su algoritmo. Funcionó bien y rápido en bajas densidades, pero tan pronto como el espacio se abarrotó, tuve problemas para encontrar una implementación sencilla que manejara situaciones específicas en las que una etiqueta debería "saltar" un bloque de otras etiquetas o quedar atrapada por sprites movibles (es decir, icono de avión). Estoy marcando esta respuesta como seleccionada entonces, pero de nuevo: ¡muchas gracias por el tiempo y la contribución! :)
mac