¿Cómo puedo mantener una formación rectangular cuando se agregan o eliminan unidades?

Tengo bots en una formación rectangular con filas y columnas. Un problema surge cuando se agrega o elimina un bot de la formación. Cuando esto sucede, los bots tienen que reorganizarse para que la formación rectangular tenga aproximadamente la misma relación de aspecto y sea lo más rectangular posible. ¿Como hacer esto?

Algunas ideas:

• Cuando se agrega o elimina un bot, use el nuevo número total de bots y una relación de aspecto constante deseada para calcular el nuevo ancho y alto de la formación que mejor se ajuste a esa relación de aspecto. Luego, de alguna manera, reorganice los bots para que se ajusten a las nuevas dimensiones.

• Cuando se retira un bot, mueve el bot que estaba detrás de él en su lugar y continúa hasta llegar al final de la formación. Luego, incluso fuera del rango trasero tanto como sea posible barajando de alguna manera a los bots en el rango trasero.

• Otra idea que es completamente diferente es imitar la forma en que las estructuras de las moléculas se mantienen juntas. Haz que cada bot quiera estar rodeado de otros cuatro bots atrayendo a los cuatro bots más cercanos y repeliendo al resto. Repele todos los bots (incluidos los cuatro) que estén demasiado cerca para garantizar la separación utilizando la ley del cuadrado inverso. También necesitaría una fuerza adicional para dar forma a toda la estructura. Pero, esto suena muy computacionalmente costoso.

ACTUALIZACIÓN : Entonces, mirando la respuesta de sarahm, se me ocurrió una buena función general que da buenas dimensiones.

Primero resolví la siguiente ecuación simultánea para ancho y alto, y luego redondeé las respuestas.

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

Esto le da el rectángulo entero más cercano a esa relación de aspecto para su número de bots. El rectángulo más cercano la mitad del tiempo será demasiado grande y la mitad del tiempo será demasiado pequeño (por supuesto, a veces será correcto, pero a quién le importan). En los casos en que el rectángulo es un poco demasiado grande, no necesita nada por hacer. El rango de vuelta terminará siendo casi completo, lo cual es ideal. En los casos en que el rectángulo es un poco demasiado pequeño, tienes problemas porque ese pequeño desbordamiento tendrá que ir a su propio rango creado un rango con solo unos pocos bots en él, lo que no se ve bonito. También hay casos donde la diferencia es grande(mayor que la mitad del ancho), en cuyo caso sumar o restar un rango para que la diferencia sea pequeña. Luego, cuando el rectángulo sea demasiado pequeño, agregue una columna para hacerlo un poco más grande. Después de hacer eso, parece que el rango trasero siempre tendrá al menos la mitad de los bots que los otros rangos.

ACTUALIZAR

Una vez que tenga las dimensiones, compárelas con las dimensiones actuales. Si el frente de la nueva dimensión es más grande, para cada rango, saca los bots del rango inferior y empújalos al rango actual hasta que la cantidad de bots en ese rango sea igual al frente. Continúa ese algoritmo hasta llegar al rango de atrás. Usando este algoritmo, los bots se moverán para adaptarse a la nueva dimensión de manera eficiente. Después de eso, simplemente empujo el nuevo viejo al rango de atrás. El algoritmo es ligeramente diferente para los casos en los que el nuevo frente es más pequeño, ¡pero puede resolverlo!

Hay dos problemas más a continuación. Eliminación, y un método de adición más flexible en el que los nuevos bots no se asignan necesariamente al rango de reverso sino a la posición más cercana a ellos en el momento en que se agregan.

Otra técnica es imitar la utilizada por los batallones napoleónicos (y probablemente desde las falanges griegas, si no más).

La fachada generalmente se mantiene constante, y cuando un hombre cae (en cualquier rango, excepto en la espalda), es reemplazado por el hombre directamente detrás de él que se adelanta. Los suboficiales barajan el rango de atrás para garantizar unos pocos hombres en el extremo de cada flanco y, de lo contrario, completarlo de manera uniforme.

La fachada solo se reduce cuando el rango inferior cae por debajo de las densidades especificadas previamente. Del mismo modo, cuando el rango de atrás está lleno, los extras primero comienzan a llenar un rango adicional desde ambos flancos, y luego se incrementa el frente.

Al cambiar el frente, sugiero que los bots se archiven desde el rango de atrás a ambos flancos al aumentar el frente, y archivar desde ambos flancos al rango de atrás al reducir el frente.

Si estoy en lo cierto al inferir que está buscando una impresión "militar", y que sus organizaciones bot parezcan falanges, creo que esta reordenación ordenada es una mejor manera de lograr ese fin.

Actualización :
Una forma sencilla de administrar la fila de atrás es dividir las unidades de la fila de atrás en tres escuadrones: uno en cada flanco y uno en el centro. Dependiendo de si el frente es impar o par, y si el número de unidades de la fila de atrás es congruente con 0,1, o 2 mod 3, hay exactamente seis casos para administrar.

Como una mejora a lo anterior, considere espaciar la (s) última (s) unidad (es) de cada escuadrón de la fila de atrás una vez que el relleno caiga por debajo de un umbral, así:
xxx.x .... x.xxx.x .... x. xxx
o esto:
xx.xx..x.xxx.x ... xxxx
Un poco más de trabajo, para una apariencia aún mejor.

Actualización n. ° 2 :
un pensamiento adicional sobre la profundidad de la formación. El impacto del fuego de volea, combinado con la bayoneta moderna, hizo adecuadas profundidades de 3 o 4 a fines del siglo XVIII y principios del XIX. (Los británicos rara vez lucharon en 2 filas, contrariamente a la creencia popular, hasta el final de una batalla; por un lado, hicieron que sus líneas fueran demasiado largas para formar un cuadrado rápidamente.) Antes de eso, era común tener mayores profundidades, tal vez hasta 8 o 10 para una falange griega equipada con Sarissa. Elija una profundidad que cree la impresión que desea.

Los ejércitos en la vida real intentan mantener el frente de la unidad el mayor tiempo posible, a expensas de una mayor fragilidad de la unidad, ya que esto simplifica el diseño de un campo de batalla. César en Farsalo redujo deliberadamente la profundidad de su unidad para aumentar el frente para que coincida con el de las fuerzas de Pompeyo. Como dice la cita: "Hoy ganamos o morimos; los hombres de Pompeyo tienen otras opciones". (que César se había asegurado inteligente y cuidadosamente, por supuesto).

Suponiendo que una unidad es una estructura de datos lineal (por ejemplo, una lista ) de bots.

Primero, debe agregar / eliminar el bot a / de la estructura de datos y determinar el nuevo número de bots en la unidad.

Luego, debe determinar la nueva cantidad de filas y columnas usando https://en.wikipedia.org/wiki/Integer_factorization .

Por supuesto, esto no siempre es posible debido a los números primos . Cuando el nuevo tamaño de la unidad es un número primo, debe usar el siguiente tamaño de unidad más grande que no lo es.

Luego, solo itera sobre la estructura de datos, asignando bots en orden a las filas y columnas.

Para colocar los bots, simplemente itera sobre la estructura de datos, asignando a cada bot una posición desplazada de la posición de las unidades en una cantidad determinada por la fila y columna en la que se encuentra el bot (o establece ese punto como objetivo para el movimiento de los bots).

Para hacer una unidad con el centro en una esquina , la posición de un bot viene dada por

unitPosition + encabezado * * ColumnNumber botSeparationDistance + rightVector * * rowNumber botSeparationDistance

Para hacer una unidad con el centro en el medio , la posición de un bot viene dada por

unitPosition + partida * (ColumnNumber * unitSeparationDistance - 0,5 * (NumberOfColumns * botSeparationDistance) + rightVector * rowNumber * botSeparationDistance - 0,5 * (numberOfRows * botSeparationDistance)

donde el encabezado es un vector que apunta en la dirección a la que se enfrenta la unidad y rightVector es un vector ortogonal al encabezado .

botSeparationDistance se puede ajustar para que los bots se mantengan más separados o más juntos.

Si se siente de lujo, se puede compensar la última fila de los robots por rightVector * 0,5 * (NumberOfColumns - actualNumberOfBotsInRow) para centrar ellos en la formación .

Almacenaría las posibles posiciones en un gráfico con valores más grandes que son rectángulos más pequeños.

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

Cada vez que se elimina un robot, busque en todos los demás robots y encuentre el que está en un nodo con el valor más pequeño. Use A * o un algoritmo BST para encontrar una ruta desde el valor más pequeño hasta el espacio vacante. Si no hay un robot con un valor menor que el eliminado, no haga nada.

También deberías poder controlar cómo se descompone el rectángulo haciendo esto. Por ejemplo, en el gráfico a continuación, cuando un robot abandona la parte inferior desde un lado, ocuparía su 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]

Aquí se quita el de 3.8 para que llegue el de 2.5 y ocupa su lugar.

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

Otro ejemplo. Aquí se elimina 2.8, por lo que el nodo más pequeño 2.2 viene y ocupa su lugar.

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

Probablemente desee un anillo de nodos con valor 0 que nunca llene alrededor del exterior para que su algoritmo de búsqueda de ruta encuentre el agujero.

[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]

Un buen tutorial sobre A * se puede encontrar aquí .