Algoritmo para espalhar etiquetas de maneira visualmente atraente e intuitiva

Versão curta

Existe um padrão de design para distribuir etiquetas de veículos de maneira não sobreposta, colocando-as o mais próximo possível do veículo a que se referem? Caso contrário, algum dos métodos sugeridos é viável? Como você implementaria isso sozinho?

Versão extendida

No jogo que estou escrevendo, tenho uma visão aérea dos meus veículos aéreos. Também tenho ao lado de cada um dos veículos uma pequena etiqueta com dados importantes sobre o veículo. Esta é uma captura de tela real:

Agora, como os veículos podiam voar em diferentes altitudes, seus ícones podiam se sobrepor. No entanto, eu gostaria de nunca ter suas etiquetas sobrepostas (ou uma etiqueta do veículo 'A' se sobreponha ao ícone do veículo 'B').

Atualmente, posso detectar colisões entre sprites e simplesmente afasto o rótulo incorreto em uma direção oposta ao sprite sobreposto . Isso funciona na maioria das situações, mas quando o espaço aéreo fica lotado, a etiqueta pode ser empurrada para muito longe do veículo, mesmo se houvesse uma alternativa "mais inteligente" alternativa. Por exemplo, eu recebo:

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

onde seria melhor (= rotular mais perto do veículo) obter:

          B - label
label - A
          C - label

EDIT: Também deve-se considerar que, além do caso de veículos sobrepostos, pode haver outras configurações nas quais os rótulos dos veículos possam se sobrepor (os exemplos da arte ASCII mostram, por exemplo, três veículos muito próximos nos quais o rótulo de Asobreporia o ícone de Be C)

Tenho duas idéias sobre como melhorar a situação atual, mas antes de dedicar algum tempo para implementá-las, pensei em pedir conselhos à comunidade (afinal, parece um "problema bastante comum" que um padrão de design possa existir).

Pelo que vale, aqui estão as duas idéias que eu estava pensando:

Slot-isation do espaço da etiqueta

Nesse cenário, eu dividiria toda a tela em "slots" para os rótulos. Então, cada veículo sempre teria seu rótulo colocado no mais próximo vazio (vazio = nenhum outro sprite naquele local.

Pesquisa em espiral

A partir da localização do veículo na tela, eu tentaria colocar a etiqueta em ângulos crescentes e depois em raios crescentes, até encontrar um local não sobreposto. Algo abaixo da linha de:

try 0°, 10px
try 10°, 10px
try 20°, 10px
...
try 350°, 10px
try 0°, 20px
try 10°, 20px
...

Essencialmente, esse problema é semelhante a um problema de prevenção de colisões. Sim, os aviões podem voar em diferentes altitudes, mas seus rótulos estão todos na mesma "altitude".

Existem algoritmos como o Desalinhamento de Colisão Desalinhado , que seriam um passo na direção certa para você. Obviamente, para a sua situação, os rótulos são "amarrados" aos seus planos, de modo que eles têm uma amplitude de movimento limitada.

Se você observar o comportamento de flocagem , deseja implementar a primeira "regra" de flocagem: repulsão de curto alcance. No entanto, em vez de "direcionar" na direção que está longe dos vizinhos mais próximos, você usará o vetor "ausente" como o local do canal para sua etiqueta.

Por exemplo:

O círculo preto grande representa sua área de influência, o círculo verde representa os canais válidos para o rótulo, o ponto verde central é o plano que você está considerando atualmente, o pequeno ponto verde é o ponto no círculo escolhido para o posicionamento do rótulo.

Agora, os pontos pretos podem representar outros rótulos ou outros planos. Não sei ao certo qual funcionaria melhor; é possível evitar melhor se fossem outros rótulos, mas não tenho certeza. Obviamente, as setas de "força" são os vetores de direção entre o seu plano atual e os "objetos de influência". Finalmente, a caixa é o rótulo.

Então, usando o seu exemplo acima, acho que isso produziria algo como:

            - label
           / 
          B 
label - A
          C 
           \
            - label

Usando esse método, há algumas situações para as quais você precisará criar casos especiais, como três planos alinhados verticalmente:

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

Todos os três rótulos podem mudar da direita para a esquerda, dependendo de como os cantos dos rótulos estão definidos. Basicamente, você só precisa observar os ângulos ao redor do círculo, onde seus rótulos podem mudar de que canto são desenhados: 0, 90, 180, 270.

Eu acho que, no final, isso pareceria legal, vendo os rótulos se evitarem. Se ficar muito perturbador, talvez você possa arredondar para os 10 graus mais próximos para movimentos menos frequentes.

Desculpem os detalhes estranhos, na maioria das coisas em que pensei quando estava criando um menu radial para o meu jogo, mas acho que nessa forma "dinâmica" funcionaria muito bem.

Depois de pensar um pouco, finalmente decidi implementar o método de pesquisa em espiral que descrevi brevemente na pergunta original.

A lógica é que o método Byte56 precisa de tratamento especial para certas condições, enquanto a pesquisa em espiral não, e codifica de uma maneira realmente compacta . Além disso, a busca abrangente enfatiza a localização do local mais próximo ao veículo para colocar a etiqueta, que IMO é o principal fator para tornar o mapa legível.

No entanto, continue votando a resposta dele, pois não só é útil, como também está muito bem escrita!

Aqui está uma captura de tela do resultado alcançado com o código em espiral:

E aqui está o código que - embora não seja independente - fornece uma idéia de quão simples é a implementação:

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()retorna True se a tag estiver totalmente na área visível da tela / radar. Portanto, essa linha diz "continue em loop se a tag estiver fora do radar ou se sobrepuser a outra coisa ..."

Nota 2 - tag.connector.updateé o método que desenha a linha que conecta o ícone do avião ao rótulo / etiqueta com as informações de texto.