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

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:

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
...

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:

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.

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.

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:

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.