Como posso manter uma formação retangular quando unidades são adicionadas ou removidas?

18

Eu tenho bots em uma formação retangular com linhas e colunas. Um problema surge quando um bot é adicionado ou removido da formação. Quando isso acontece, os robôs precisam se reorganizar para que a formação retangular ainda tenha aproximadamente a mesma proporção e seja o mais retangular possível. Como fazer isso?

Algumas ideias:

  • Quando um bot é adicionado ou removido, use o novo número total de bots e a proporção desejada desejada para calcular a nova largura e altura da formação que melhor se encaixa nessa proporção. De alguma forma, reorganize os robôs para se ajustarem às novas dimensões.

  • Quando um bot é removido, mova o bot que estava atrás dele para o seu lugar e continue até chegar ao final da formação. Então, mesmo fora da classificação traseira, tanto quanto possível, de alguma forma embaralhando os bots na classificação traseira.

  • Outra idéia que é completamente diferente é imitar a maneira como as estruturas das moléculas permanecem juntas. Faça com que cada bot queira estar cercado por outros quatro bots, atraindo os quatro bots mais próximos e repelindo o resto. Repelir todos os bots (incluindo os quatro) que estão muito próximos para garantir a separação usando a lei do quadrado inverso. Você também precisaria de uma força adicional para moldar toda a estrutura. Mas isso parece muito caro computacionalmente.

ATUALIZAÇÃO : Então, analisando a resposta de sarahm, criei uma boa função geral que fornece boas dimensões.

Primeiro resolvi a equação simultânea abaixo para largura e altura e depois arredondei as respostas.

width/height=aspect ratio of your choice
width*height=number of bots

Isso fornece o retângulo inteiro mais próximo dessa proporção para o seu número de bots. O retângulo mais próximo será na metade do tempo muito grande e na metade do tempo será muito pequeno (é claro que às vezes será correto, mas quem se importa com isso). Nos casos em que o retângulo é um pouco grande demais, nada precisa ser feito. O ranking traseiro acaba ficando quase cheio, o que é ideal. Nos casos em que o retângulo é um pouco pequeno demais, você tem problemas, porque esse pequeno excesso de excesso terá que ir para sua própria classificação, criando uma classificação com apenas alguns bots, o que não parece bonito. Há também casos em que a diferença é grande(maior que a metade da largura); nesse caso, adicione ou subtraia uma classificação para diminuir a diferença. Em seguida, quando o retângulo for muito pequeno, adicione uma coluna para torná-lo um pouco maior. Depois de fazer isso, parece que o back rank sempre terá pelo menos metade do número de bots que os outros.

ATUALIZAR

Depois de obter as dimensões, compare-as com as dimensões atuais. Se a fachada da nova dimensão for maior, para cada classificação, solte bots da classificação abaixo e empurre-os para a classificação atual até que o número de bots nessa classificação seja igual à fachada. Continue esse algoritmo até chegar à classificação de trás. Usando esse algoritmo, os bots se moverão para caber na nova dimensão com eficiência. Depois disso, eu simplesmente empurro o novo velho para a fila de trás. O algoritmo é um pouco diferente para os casos em que a nova fachada é menor, mas você pode descobrir!

Há mais dois problemas a seguir. Exclusão e um método de adição mais flexível, em que novos bots não são necessariamente atribuídos ao back rank, mas a posição mais próxima deles no momento em que são adicionados.

Tiby312
fonte
Qual é o número máximo de bots em uma unidade? Se for relativamente pequeno, você pode codificar quantas linhas e colunas uma formação possui para um determinado número de bots.
Exilyth 23/07
3
Você pode postar uma imagem de formações válidas ou inválidas? Estou com problemas para entender o que você procura. Linhas / colunas incompletas são permitidas?
MichaelHouse
3
Você percebe que isso não funcionará para números primos? por exemplo, com 7 bots, você teria que fazer uma unidade 3x2 com um único bot na parte de trás.
Exilyth 23/07
11
Bem, isso é constrangedor. Esqueci completamente os números primos. Talvez a próxima melhor opção seja permitir apenas linhas e colunas que são QUASE preenchidas. Um Bot em uma linha não parece certo, mas menos um Bot em uma linha não ficaria ruim.
Tiby312 23/07
3
Os números primos não são os únicos que causam problemas - escolher o tamanho da formação por fatoração pode dar a você formações excessivamente longas e finas. Por exemplo, se você tiver 14 bots, a única formação retangular perfeita é 7x2, enquanto pode parecer melhor ter uma formação 3x4 com uma linha extra de 2 bots.
Nathan Reed

Respostas:

16

Outra técnica é imitar a usada pelos batalhões napoleônicos (e provavelmente já nas falanges gregas, se não mais).

A fachada geralmente é mantida constante e, quando um homem cai (em qualquer posição, exceto na parte de trás), ele é substituído pelo homem diretamente atrás dele, dando um passo à frente. Os suboficiais são embaralhados pelos suboficiais para garantir que alguns homens se encontrem no extremo de cada flanco e, caso contrário, preencham uniformemente.

A fachada é reduzida apenas quando a fila de trás cai abaixo das densidades pré-especificadas. Da mesma forma, quando a fila de trás está cheia, os extras começam a preencher uma fila adicional de ambos os flancos, e então a fachada é aumentada.

Ao mudar de fachada, sugiro que seus bots saiam da fila de trás para os dois flancos ao aumentar a fachada e entrem nos dois flancos para a fila de trás ao reduzir a fachada.

Se estou certo ao deduzir que você está procurando uma impressão "militar" e fazer com que as organizações de bot pareçam falanges, acredito que esse reorganização ordenada é a melhor maneira de atingir esse objetivo.

Atualização :
Uma maneira simples de gerenciar a fila de trás é dividir as unidades da fila de trás em três esquadrões: um em cada flanco e outro no centro. Dependendo se a fachada é ímpar ou par, e se o número de unidades da fila de trás é congruente a 0,1 ou 2 mod 3, há exatamente seis casos para gerenciar.

Como um aprimoramento ao acima, considere espaçar a (s) última (s) unidade (s) de cada esquadrão da linha de trás quando o preenchimento cair abaixo de um limite, assim:
xxx.x .... x.xxx.x .... x. xxx
ou este:
xx.xx..x.xxx.x ... xxxx
Um pouco mais de trabalho, para uma aparência ainda melhor.

Atualização # 2 :
Uma reflexão adicional sobre a profundidade da formação. O impacto do tiro de vôlei, combinado com a baioneta moderna, tornou profundidades de 3 ou 4 adequadas no final do século XVIII e início do século XIX. (Os britânicos raramente brigavam em duas fileiras, ao contrário da crença popular, até o final de uma batalha; por um lado, faziam suas filas muito longas para formarem um quadrado rapidamente.) Antes disso, era comum ter profundidades maiores, talvez até 8 ou 10 para uma falange grega equipada com Sarissa. Escolha uma profundidade que crie a impressão que você deseja.

Os exércitos na vida real tentam manter a fachada da unidade o maior tempo possível, às custas do aumento da fragilidade da unidade, pois isso simplifica a disposição de um campo de batalha. César em Fársalo reduziu deliberadamente a profundidade de sua unidade para aumentar a fachada para corresponder à das forças de Pompeu. Como diz a citação: "Vencemos ou morremos hoje; os homens de Pompeu têm outras opções". (que César havia inteligente e cuidadosamente assegurado, é claro).

Pieter Geerkens
fonte
Isso soa como uma solução muito mais elegante. Não há necessidade de se preocupar com números primos ou proporções, e ainda assim evita qualquer linha que tenha um número incomumente baixo de bots, e a única condição que precisa ser verificada é quão cheia está a reorganização!
22813 Tiby312
Mas espere. Digamos que a fila de trás tenha apenas 3 bots e esteja nas colunas 1, 2 e 3. E removo alguém da 5ª coluna alguém perto da frente. Eu terminaria com um lugar livre na penúltima linha da 5ª coluna sem nenhum bot atrás dele para substituí-lo. Quem deve preencher este local?
22613 Tiby312
Presumivelmente, o bot mais próximo na fila de trás (ou seja, o da coluna 3) deve ser executado para preenchê-lo. Ou você pode economizar um pouco de tempo, colocando os robôs nas colunas 3 e 4 da penúltima classificação, cada etapa uma coluna acima, movendo a lacuna para a coluna 3 e, em seguida, faça o bot da coluna 3 avançar para preencher isto. (IMO, a estratégia procura mais "natural" seria provavelmente uma combinação heurística dos dois, possivelmente com alguma aleatoriedade jogados dentro.)
Ilmari Karonen
11
Se o ranking traseiro tiver muito poucos membros (digamos, menos de 50% das outras fileiras), e você aumentar a fachada, isso garante a correção do problema ou é possível que o ranking secundário ainda tenha poucos membros após aumentar a fachada exigindo que seja repetida ou algo assim?
22613 Tiby312
11
@ Tiby312: Eu acredito que você está pensando demais. Experimente, sabendo que você sempre pode ajustá-lo depois #
Pieter Geerkens
7

Supondo que uma unidade é uma estrutura de dados linear (por exemplo, uma lista ) de bots.

Primeiro, você deve adicionar / remover o bot de / para a estrutura de dados e determinar o novo número de bots na unidade.

Em seguida, você deve determinar a nova quantidade de linhas e colunas usando https://en.wikipedia.org/wiki/Integer_factorization .

Obviamente, isso nem sempre é possível devido aos números primos . Quando o novo tamanho da unidade é um número primo, você precisa usar o próximo tamanho de unidade maior que não é.

Em seguida, apenas itere sobre a estrutura de dados, atribuindo bots em ordem às linhas e colunas.

Para colocar os bots, apenas itere sobre a estrutura de dados, atribuindo a cada bot uma posição deslocada da posição das unidades por uma quantidade determinada pela linha e coluna em que o bot está (ou defina esse ponto como um alvo para o movimento dos bots).

Para fazer uma unidade com o centro em um canto , a posição de um bot é dada por

unitPosition + cabeçalho * columnNumber * botSeparationDistance + rightVector * rowNumber * botSeparationDistance

Para fazer uma unidade com o centro no meio , a posição de um bot é dada por

unitPosition + posição * (* columnNumber unitSeparationDistance - 0,5 * (* numberOfColumns botSeparationDistance) + rightVector * RowNumber * botSeparationDistance - 0,5 * (* NumberOfRows botSeparationDistance)

onde cabeçalho é um vetor apontando na direção em que a unidade está voltada e rightVector é um vetor ortogonal ao cabeçalho .

O botSeparationDistance pode ser ajustado para fazer com que os bots fiquem mais afastados ou mais próximos.

Se você está se sentindo fantasia, você pode compensar a última fileira de bots por rightVector * 0.5 * (numberOfColumns - actualNumberOfBotsInRow) para centrar -los sobre a formação .

Exilyth
fonte
Isso é muito próximo do que estou procurando! Minha única reserva é que, ao atribuir novas posições, um Bot à direita de uma linha pode ser atribuído à esquerda da próxima linha no novo retângulo, resultando no Bot percorrendo uma longa distância e nos processos atrapalhando outros bots tentando alcançar sua nova posição atribuída. Eu me preocupo que quando um bot é adicionado ou removido, toda a formação seria uma confusão quando Bots se apressasse para chegar ao seu destino distante.
23413 Tiby312
2
Você sempre pode calcular as novas posições e depois mover o bot mais próximo para essa posição, em vez de fazer uma iteração linear.
Exilyth 23/07
Como fazer isso sem terminar com uma computação ao quadrado? Eu teria que encontrar a posição mais próxima no array 2D da posição atual no array 2D, para cada Bot, se eu estiver entendendo isso corretamente.
23413 Tiby312
Em cada iteração, uma unidade seria atribuída (e, portanto, não precisa ser considerada em iterações adicionais), portanto, o tempo de execução seria O (n!). O que, ainda assim, não é muito bom. Por outro lado, a construção de uma [estrutura de otimização de escolha] e a realização de n consultas de intervalo também não são rápidas. A única coisa em que consigo pensar agora é mover os últimos bots em uma linha para trás ou preencher os últimos lugares seguidos com bots por trás.
Exilyth 23/07
Que tal agora. Digamos que a nova formação tenha um tamanho de linha menor. Então, em cada linha, você tem um bot extra. Você atribui esse bot um para baixo e outro para a esquerda. Então, na próxima linha abaixo, você tem dois Bots sem lugar. Você atribui os dois um para baixo e outro para a esquerda. Então você tem 3 bots sem um lugar. Continue até que você tenha uma linha extra na parte inferior. Estou cuspindo bolas aqui. Não pensei nisso o tempo todo, mas parece que vai funcionar e é rápido.
22613 Tiby312
2

Eu armazenaria as posições possíveis em um gráfico com valores maiores sendo retângulos menores.

[4][3][2][1]
[3][3][2][1]
[2][2][2][1]
[1][1][1][1]

Toda vez que um robô é removido, pesquise todos os outros robôs e encontre aquele em um nó com o menor valor. Use um algoritmo A * ou BST para encontrar um caminho do menor valor para o espaço vago. Se não houver robô com um valor menor que o removido, não faça nada.

Você também deve poder controlar como o retângulo decai fazendo isso. Por exemplo, no gráfico abaixo, quando um robô sai do lado inferior, ele vem ocupar seu lugar.

[4.9][3.8][2.7][1.0]
[4.8][3.7][2.6][1.0]
[3.9][3.6][2.5][1.0]
[3.5][3.4][2.4][1.0]
[2.9][2.8][2.3][1.0]
[2.0][2.1][2.2][1.0]
[1.9][1.8][1.7][1.0]
[1.6][1.5][1.4][1.0]

Aqui o de 3,8 é removido, de modo que o de 2,5 chega e preenche seu lugar.

[o][x][o][ ]
[o][o][o][ ]
[o][o][r][ ]
[o][o][ ][ ]
[o][o][ ][ ]
[ ][ ][ ][ ]
[ ][ ][ ][ ]
[ ][ ][ ][ ]

Outro exemplo. Aqui 2.8 é removido para que o menor nó 2.2 chegue ao seu lugar.

[o][o][o][ ]
[o][o][o][ ]
[o][o][o][ ]
[o][o][o][ ]
[o][x][r][ ]
[ ][ ][ ][ ]
[ ][ ][ ][ ]
[ ][ ][ ][ ]

Você provavelmente deseja um anel de nós com o valor 0 que você nunca preenche do lado de fora para que seu algoritmo de busca de caminhos encontre o buraco.

[0.0][0.0][0.0][0.0][0.0][0.0]
[0.0][4.9][3.8][2.7][1.0][0.0]
[0.0][4.8][3.7][2.6][1.0][0.0]
[0.0][3.9][3.6][2.5][1.0][0.0]
[0.0][3.5][3.4][2.4][1.0][0.0]
[0.0][2.9][2.8][2.3][1.0][0.0]
[0.0][2.0][2.1][2.2][1.0][0.0]
[0.0][1.9][1.8][1.7][1.0][0.0]
[0.0][1.6][1.5][1.4][1.0][0.0]
[0.0][0.0][0.0][0.0][0.0][0.0]

Um bom tutorial sobre A * pode ser encontrado aqui .

ClassicThunder
fonte
Essa é uma boa idéia, mas se estou entendendo isso corretamente, você está permitindo formações que não são retângulos perfeitos. As linhas e colunas nas bordas podem não estar cheias. Eu estava pensando que poderia fazê-lo para que ele sempre tenha uma borda retangular e, em vez disso, altere um pouco a proporção para atender a esse requisito, alterando o número de linhas e colunas. Já posso calcular a nova largura e altura que conseguiriam isso, mas há uma maneira complicada de reatribuir os Bots ao local mais próximo ... eu acho.
23413 Tiby312
@ Tiby312 Como você planeja fazer um retângulo perfeito com digamos ... 7 robôs?
precisa
Nunca esqueci os números primos. Desculpe. Mas ainda estou pensando que ajustar o número de linhas e colunas poderia evitar uma linha ou coluna com um número incomumente baixo de Bots.
23813 Tiby312
@ Tiby312 Acho melhor você procurar uma proporção consistente (ou seja, sempre 4: 3 ou 8: 5) do que tentar sempre torná-lo um retângulo perfeito.
corsiKa