Algorithme pour diffuser des étiquettes d'une manière visuellement attrayante et intuitive

24

Version courte

Existe-t-il un modèle de conception pour distribuer les étiquettes des véhicules de manière non superposée, en les plaçant le plus près possible du véhicule auquel elles se réfèrent? Sinon, l'une des méthodes que je suggère est-elle viable? Comment mettriez-vous cela en œuvre vous-même?

Version étendue

Dans le jeu que j'écris, j'ai une vision à vol d'oiseau de mes véhicules aéroportés. J'ai également à côté de chacun des véhicules une petite étiquette avec des données clés sur le véhicule. Ceci est une capture d'écran réelle:

Deux véhicules avec leurs étiquettes

Maintenant, comme les véhicules pouvaient voler à différentes altitudes, leurs icônes pouvaient se chevaucher. Cependant, je voudrais que leurs étiquettes ne se chevauchent jamais (ou qu'une étiquette du véhicule «A» chevauche l'icône du véhicule «B»).

Actuellement, je peux détecter les collisions entre les sprites et je repousse simplement le libellé incriminé dans une direction opposée au sprite autrement chevauché . Cela fonctionne dans la plupart des situations, mais lorsque l'espace aérien est encombré, l'étiquette peut être poussée très loin de son véhicule, même s'il existait une alternative "plus intelligente". Par exemple, je reçois:

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

où il serait préférable (= étiquette plus proche du véhicule) d'obtenir:

          B - label
label - A
          C - label

EDIT: Il faut également considérer qu'à côté du cas des véhicules qui se chevauchent, il pourrait y avoir d'autres configurations dans lesquelles les étiquettes des véhicules pourraient se chevaucher (les exemples de l'art ASCII montrent par exemple trois véhicules très proches dans lesquels l'étiquette de Achevaucherait l'icône de Bet C).

J'ai deux idées sur la façon d'améliorer la situation actuelle, mais avant de passer du temps à les mettre en œuvre, j'ai pensé me tourner vers la communauté pour obtenir des conseils (après tout, cela semble être un "problème assez courant" pour qu'un modèle de conception puisse exister).

Pour ce que ça vaut, voici les deux idées auxquelles je pensais:

Slot-isation de l'espace d'étiquette

Dans ce scénario, je diviserais tout l'écran en "fentes" pour les étiquettes. Ensuite, chaque véhicule aurait toujours son étiquette placée dans le vide le plus proche (vide = aucun autre sprite à cet endroit).

Recherche en spirale

À partir de l'emplacement du véhicule sur l'écran, j'essayerais de placer l'étiquette à des angles croissants puis à des rayons croissants, jusqu'à ce qu'un emplacement sans chevauchement soit trouvé. Quelque chose sur la ligne de:

try 0°, 10px
try 10°, 10px
try 20°, 10px
...
try 350°, 10px
try 0°, 20px
try 10°, 20px
...
Mac
la source
1
Combien d'avions peuvent se chevaucher à la fois?
wangburger
1
@wangburger - Je n'ai jamais pensé que cela serait pertinent (je serais intéressé à en savoir plus sur votre ligne de pensée), mais la réponse est: cela dépend de la stratégie de jeu du joueur. Techniquement, le monde pourrait avoir 24 véhicules qui se chevauchent, mais un chiffre réaliste dans la plupart des conditions de jeu est de 3-4.
mac
3
N'est-il pas plus déroutant d'avoir des étiquettes mobiles par rapport à l'avion que des étiquettes qui se chevauchent mais qui sont statiques pendant un temps raisonnable?
Maik Semder
3
Vous pourriez être intéressé par en.wikipedia.org/wiki/… - ce n'est pas un problème simple à résoudre. Ne vous attendez pas à trouver une solution parfaite.
Blecki
2
GraphViz est une suite d'outils pour disposer des graphiques de manière visuellement agréable, avec une tendance à éviter les chevauchements d'étiquettes. Bien qu'il ne soit pas directement utilisable, vous pourrez peut-être glaner des informations dans leur documentation ou leur code source sur le type d'algorithmes qu'ils utilisent pour mettre en page leurs graphiques. Ils semblent avoir à la fois des modèles basés sur l'énergie et des modèles basés sur des ressorts, par exemple.
Lars Viklund

Réponses:

14

Essentiellement, ce problème est similaire à un problème d'évitement de collision. Oui, les avions peuvent voler à différentes altitudes, mais leurs étiquettes sont toutes à la même "altitude".

Il existe des algorithmes comme l' évitement des collisions non alignées , ce serait un pas dans la bonne direction pour vous. Bien sûr, pour votre situation, les étiquettes sont «attachées» à leurs avions, donc elles ont une amplitude de mouvement limitée.

Si vous regardez le comportement de flocage , vous voulez implémenter la première "règle" du flocage: la répulsion à courte portée. Cependant, au lieu de "diriger" dans la direction éloignée des voisins les plus proches, vous utiliserez le vecteur "absent" comme emplacement de placement de votre étiquette.

Par exemple:

entrez la description de l'image ici

Le grand cercle noir représente votre zone d'influence, le cercle vert représente les emplacements valides pour l'étiquette, le point vert central est le plan que vous envisagez actuellement, le petit point vert est le point du cercle choisi pour le placement de l'étiquette.

Maintenant, les points noirs pourraient représenter soit d'autres étiquettes, soit d'autres plans. Je ne sais pas lequel fonctionnerait le mieux, vous pourriez être mieux évité s'il s'agissait d'autres étiquettes, mais je ne suis pas sûr. Évidemment les flèches "force" sont les vecteurs de direction entre votre plan actuel et les "objets d'influence". Enfin, la boîte est l'étiquette.

Donc, en utilisant votre exemple ci-dessus, je pense que cela produirait quelque chose comme:

            - label
           / 
          B 
label - A
          C 
           \
            - label

En utilisant cette méthode, vous devrez créer des cas spéciaux pour certaines situations, comme trois plans alignés verticalement:

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

Les trois étiquettes peuvent basculer de droite à gauche, selon la façon dont vos coins d'étiquette sont définis. Fondamentalement, vous n'aurez qu'à faire attention aux angles autour du cercle où vos étiquettes peuvent changer de quel coin elles sont tirées: 0, 90, 180, 270.

entrez la description de l'image ici

Je pense qu'en fin de compte, cela aurait l'air plutôt bien, en regardant les étiquettes s'éviter. Si cela devient trop distrayant, vous pouvez peut-être arrondir aux 10 degrés les plus proches pour des mouvements moins fréquents.

Désolé pour les détails étranges, la plupart de ces trucs auxquels j'ai pensé quand je faisais un menu radial pour mon jeu, mais je pense que sous cette forme "dynamique" cela fonctionnerait plutôt bien.

MichaelHouse
la source
1
En fait, mon exemple n'a même pas pris en compte les plans qui sont directement les uns sur les autres, car leurs coordonnées x et z correspondent exactement (mais si vous utilisez des flotteurs, cela ne se produira probablement pas). Les exemples que j'ai donnés sont des avions proches les uns des autres. De plus, vous pouvez, comme je l'ai dit, considérer les points noirs de l'image ci-dessus comme d'autres étiquettes.
MichaelHouse
1
Oh, il semble que vous ayez supprimé votre commentaire?
MichaelHouse
1
Ce que je voulais dire avec mon commentaire précédent [mal formulé et donc maintenant supprimé], c'est que vous pourriez avoir un scénario dans lequel une étiquette est "piégée / entourée" par d'autres sprites non mobiles (c'est-à-dire des véhicules). Dans ce cas, l'étiquette devrait peut-être "sauter" en dehors du cercle qui l'entoure, mais je ne sais pas exactement comment cela doit se produire. BTW: Au départ, je pensais que le point vert de votre photo était plusieurs avions empilés les uns sur les autres, mais après votre commentaire, j'ai réalisé que j'avais tort ... désolé!).
mac
1
Ah, je vois. Vous traitez donc les points noirs comme des plans ET des étiquettes. Si la position trouvée par la première itération n'est pas bonne, doublez le rayon et vérifiez à nouveau. Ou vous avez déjà un vecteur qui pointe loin de la majorité de la foule, vous pouvez le suivre jusqu'à ce que vous trouviez un endroit qui fonctionne. Cependant, je pense que la première méthode aurait de meilleurs résultats.
MichaelHouse
9

Après réflexion, j'ai finalement décidé de mettre en œuvre la méthode de recherche en spirale que j'ai brièvement décrite dans la question d'origine.

La raison en est que la méthode du Byte56 nécessite un traitement spécial pour certaines conditions, alors que la recherche en spirale ne le fait pas, et elle code de manière vraiment compacte . En outre, la recherche de virage met l'accent sur la recherche de l'endroit le plus proche du véhicule pour placer l'étiquette, ce qui est le principal facteur qui rend l'OMI lisible.

Cependant, veuillez continuer à voter pour sa réponse, car elle n'est pas seulement utile, elle est également très bien écrite!

Voici une capture d'écran du résultat obtenu avec le code en spirale:

entrez la description de l'image ici

Et voici le code qui - bien que non autonome - il donne une idée de la simplicité de la mise en œuvre:

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

Remarque 1 - tag.place()renvoie True si la balise se trouve entièrement sur la zone visible de l'écran / radar. Donc, cette ligne se lit comme "continuez à boucler si la balise est en dehors du radar ou si elle chevauche autre chose ..."

Note 2 - tag.connector.updateest la méthode qui trace la ligne reliant l'icône de l'avion à l'étiquette / étiquette avec les informations textuelles.

Mac
la source
Bravo, c'est vraiment très compact. Merci pour les éloges. Merci également d'avoir posté ce que vous avez fini par faire, c'est toujours utile pour les personnes qui recherchent des réponses plus tard. De la capture d'écran, il semble que cela fonctionne très bien! Assurez-vous d'accepter votre réponse, car c'est ce que vous avez fini par faire.
MichaelHouse
@ Byte56 - Merci pour le "rétro-éloge";) J'attends de sélectionner la réponse comme acceptée car je voudrais toujours coder votre solution aussi et comparer le résultat. D'une part, je soupçonne que votre solution pourrait entraîner un code plus long mais aussi plus rapide à exécuter. De plus, j'aimerais voir comment les deux se comparent dans des espaces aériens très saturés ... donc il y a encore une chance que je puisse publier le code avec votre algorithme. Surveillez cet endroit! ;)
mac
@ Byte56 - J'ai essayé d'implémenter votre algorithme. Cela fonctionnait bien et rapidement à faible densité, mais dès que l'espace était saturé, j'ai eu des problèmes pour trouver une implémentation simple qui gérerait des situations spécifiques dans lesquelles une étiquette devrait "sauter" un bloc d'autres étiquettes ou être piégée par des non sprites mobiles (c.-à-d. icône d'avion). Je marque cette réponse comme sélectionnée alors, mais encore une fois: merci beaucoup pour le temps et la contribution! :)
mac