Algoritmo para espalhar etiquetas de maneira visualmente atraente e intuitiva

24

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:

Dois veículos com seus rótulos

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
...
Mac
fonte
11
Quantos aviões podem se sobrepor ao mesmo tempo?
Wangburger
11
@angburger - Nunca pensei que isso fosse relevante (estaria interessado em saber mais sobre sua linha de pensamento), mas a resposta é: depende da estratégia de jogo do jogador. Tecnicamente, o mundo poderia ter 24 veículos sobrepostos, mas uma figura realista na maioria das condições de jogo é 3-4.
mac
3
Não é mais confuso ter etiquetas em movimento em relação ao plano do que etiquetas sobrepostas, mas estáticas, por um período de tempo razoável?
Maik Semder
3
Você pode estar interessado em en.wikipedia.org/wiki/… - esse não é um problema simples de resolver. Não espere encontrar uma solução perfeita.
Blecki 01/08/19
2
O GraphViz é um conjunto de ferramentas para exibir gráficos de maneira visualmente agradável, com tendência a evitar sobreposições nas etiquetas. Embora possa não ser utilizável diretamente, você poderá coletar algumas informações da documentação ou do código-fonte sobre o tipo de algoritmo usado para o layout de seus gráficos. Eles parecem ter modelos baseados em energia e modelos baseados em mola, por exemplo.
Lars Viklund

Respostas:

14

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:

insira a descrição da imagem aqui

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.

insira a descrição da imagem aqui

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.

MichaelHouse
fonte
11
Na verdade, meu exemplo nem levou em consideração os aviões que estão diretamente um em cima do outro, pois suas coordenadas x e z correspondem exatamente (mas se você estiver usando flutuadores, isso provavelmente não acontecerá). Os exemplos que dei são de aviões próximos um do outro. Além disso, como eu disse, você pode pensar nos pontos pretos na imagem acima como outros rótulos.
MichaelHouse
11
Ah, parece que você removeu seu comentário?
MichaelHouse
11
O que eu quis dizer com meu comentário anterior [mal formulado e, portanto, agora removido], era que você poderia ter um cenário em que um rótulo fosse "preso / cercado" por outros sprites não móveis (ou seja, veículos). Nesse caso, o rótulo talvez deva "pular" fora do círculo fechado, mas não está exatamente claro para mim como isso deve acontecer. BTW: Originalmente eu pensei que o ponto verde da sua foto era de vários aviões empilhados um em cima do outro, mas depois do seu comentário eu percebi que estava errado ... desculpe!).
mac
11
Ah entendo. Então, você trataria os pontos pretos como planos e rótulos. Se a posição encontrada pela primeira iteração não for boa, duplique o raio e verifique novamente. Ou você já tem um vetor que aponta para longe da maioria da multidão, você pode segui-lo até encontrar um lugar que funcione. No entanto, acho que o primeiro método teria melhores resultados.
MichaelHouse
9

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:

insira a descrição da imagem aqui

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.

Mac
fonte
Bem feito, é realmente muito compacto. Obrigado pelo elogio. Também obrigado por postar sobre o que você acabou fazendo, sempre útil para pessoas que procuram respostas mais tarde. A partir da captura de tela, parece que está funcionando muito bem! Aceite sua resposta, pois foi com isso que você acabou indo.
Michaelhouse
@ Byte56 - Obrigado pelo "elogio retro";) Estou aguardando selecionar a resposta como aceita, porque ainda gostaria de codificar sua solução e comparar o resultado. Por um lado, suspeito que sua solução possa resultar em código mais longo, mas também mais rápido , de execução. Além disso, gostaria de ver como os dois se comparam em espaços aéreos muito abarrotados ... para que ainda haja uma chance de eu liberar o código com seu algoritmo. Assista esse espaço! ;)
mac
@ Byte56 - eu tentei implementar seu algoritmo. Ele funcionou bem e rápido em baixas densidades, mas, assim que o espaço ficou abarrotado, tive problemas em encontrar uma implementação direta que gerenciasse situações específicas nas quais um rótulo deveria "pular" um bloco de outros rótulos ou ficar preso por não- sprites móveis (por exemplo, ícone de avião). Estou marcando esta resposta como selecionada então, mas novamente: muito obrigado pelo tempo e pela contribuição! :)
mac