Comment puis-je conserver une formation rectangulaire lorsque des unités sont ajoutées ou supprimées?

J'ai des robots dans une formation rectangulaire avec des rangées et des colonnes. Un problème survient lorsqu'un bot est ajouté ou retiré de la formation. Lorsque cela se produit, les bots doivent se réorganiser de sorte que la formation rectangulaire soit toujours à peu près le même rapport d'aspect, et soit aussi rectangulaire que possible. Comment faire ça?

Quelques idées:

Lorsqu'un bot est ajouté ou supprimé, utilisez le nouveau nombre total de bots et le rapport d'aspect constant souhaité pour calculer la nouvelle largeur et hauteur de la formation qui correspond le mieux à ce rapport d'aspect. Ensuite, remaniez en quelque sorte les robots pour les adapter aux nouvelles dimensions.
Lorsqu'un bot est retiré, déplacez le bot qui se trouvait derrière lui à sa place et continuez jusqu'à la fin de la formation. Ensuite, égalisez le rang arrière autant que possible en mélangeant en quelque sorte les robots dans le rang arrière.
Une autre idée complètement différente consiste à imiter la façon dont les structures des molécules restent ensemble. Faites en sorte que chaque robot veuille être entouré de quatre autres robots en attirant les quatre robots les plus proches et en repoussant les autres. Repoussez tous les robots (y compris les quatre) qui sont trop proches pour assurer la séparation en utilisant la loi du carré inverse. Vous auriez également besoin d'une force supplémentaire pour façonner la structure entière. Mais cela semble très coûteux en calcul.

MISE À JOUR : Donc, en regardant la réponse de sarahm, j'ai trouvé une bonne fonction générale qui donne de bonnes dimensions.

J'ai d'abord résolu l'équation simultanée ci-dessous pour la largeur et la hauteur, puis arrondi les réponses.

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

Cela vous donne le rectangle entier le plus proche de ce rapport d'aspect pour votre nombre de bots. Le rectangle le plus proche sera la moitié du temps trop grand, et la moitié du temps trop petit (bien sûr, parfois, ce sera juste, mais qui s'en soucie). Dans les cas où le rectangle est un peu trop grand, rien ne doit être fait. Le dernier rang finira par être presque plein, ce qui est idéal. Dans les cas où le rectangle est un peu trop petit, vous avez eu des problèmes parce que ce minuscule débordement devra aller à son propre rang, ce qui a créé un rang avec seulement quelques bots dessus, ce qui n'est pas joli. Il y a aussi des cas où la différence est grande(plus de la moitié de la largeur), auquel cas ajoutez ou soustrayez un rang pour réduire la différence. Ensuite, lorsque le rectangle est trop petit, ajoutez une colonne pour l'agrandir un peu. Après cela, il semble que le dernier rang aura toujours au moins la moitié du nombre de robots que les autres rangs.

MISE À JOUR

Une fois que vous avez obtenu les dimensions, comparez-les aux dimensions actuelles. Si la façade de la nouvelle dimension est plus grande, pour chaque rang, sortez les bots du rang inférieur et poussez-les sur le rang actuel jusqu'à ce que le nombre de bots de ce rang soit égal à la façade. Continuez cet algorithme jusqu'à ce que vous arriviez au dernier rang. En utilisant cet algorithme, les robots se déplaceront pour s'adapter efficacement à la nouvelle dimension. Après cela, je pousse simplement le nouvel ancien au dernier rang. L'algorithme est légèrement différent pour les cas où la nouvelle façade est plus petite, mais vous pouvez le comprendre!

Il y a deux autres problèmes ensuite. Suppression, et une méthode d'addition plus flexible où les nouveaux robots ne sont pas nécessairement affectés au rang arrière, mais quelle que soit la position qui leur est la plus proche au moment où ils sont ajoutés.

mathematics algorithm ai software-engineering Tiby312
la source

Quel est le nombre maximum de bots dans une unité? S'il est relativement petit, vous pouvez coder en dur le nombre de lignes et de colonnes d'une formation pour un certain nombre de bots.

Exilyth

Pouvez-vous peut-être publier une image de formations valides vs invalides? J'ai un peu de mal à comprendre ce que tu cherches. Les lignes / colonnes incomplètes sont-elles autorisées?

MichaelHouse

Vous vous rendez compte que cela ne fonctionnera pas pour les nombres premiers? Par exemple, avec 7 bots, vous devrez faire une unité 3x2 avec un seul bot à l'arrière.

Exilyth

Hum, ceci est embarrassant. J'ai complètement oublié les nombres premiers. Alors peut-être que la meilleure chose à faire serait de n'autoriser que les lignes et les colonnes qui sont PRESQUE remplies. Un Bot sur une rangée ne semble pas bien, mais un Bot de moins sur une rangée ne serait pas mauvais.

Tiby312

Les nombres premiers ne sont pas les seuls à causer des problèmes - le choix de la taille de la formation en factorisant pourrait vous donner des formations déraisonnablement longues et maigres. Par exemple, si vous avez 14 bots, la seule formation rectangulaire parfaite est 7x2, alors qu'il pourrait être préférable d'avoir une formation 3x4 avec une rangée supplémentaire de 2 bots.

Nathan Reed

Réponses:

Une autre technique consiste à imiter celle utilisée par les bataillons napoléoniens (et probablement aussi loin que les phalanges grecques sinon plus loin).

La façade est généralement maintenue constante, et lorsqu'un homme tombe (dans n'importe quel rang sauf le dos), il est remplacé par l'homme directement derrière lui qui s'avance. Le rang arrière est mélangé par les sous-officiers pour assurer quelques hommes à l'extrême de chaque flanc, et sinon pour remplir également.

La façade n'est réduite que lorsque le rang arrière tombe en dessous des densités prédéfinies. De même, lorsque le rang arrière est saturé, les figurants commencent d'abord à remplir un rang supplémentaire à partir des deux flancs, puis la façade est augmentée.

Lorsque vous changez de façade, je suggère que vos bots se déplacent du rang arrière vers les deux flancs lors de l'augmentation de la façade et qu'ils soient limités des deux flancs au rang arrière lors de la réduction de la façade.

Si j'ai raison de déduire que vous recherchez une impression "militaire" et que vos organisations de robots ressemblent à des phalanges, je pense que ce réarrangement ordonné est un meilleur moyen d'atteindre cet objectif.

Mise à jour :
Une façon simple de gérer la rangée arrière est de diviser les unités de la rangée arrière en trois escouades: une sur chaque flanc et une au centre. Selon que la façade est impaire ou paire et que le nombre d'unités de rang arrière est congru à 0,1 ou 2 mod 3, il y a exactement six cas à gérer.

Pour améliorer ce qui précède, envisagez d'espacer la ou les dernières unités de chaque escouade de rang arrière une fois que le remplissage tombe en dessous d'un seuil, comme ceci:
xxx.x .... x.xxx.x .... x. xxx
ou ceci:
xx.xx..x.xxx.x ... xxxx
Un peu plus de travail, pour une apparence encore meilleure.

Mise à jour # 2 :
Une réflexion supplémentaire sur la profondeur de la formation. L'impact du feu de volée, combiné avec la baïonnette moderne, a rendu les profondeurs de 3 ou 4 adéquates à la fin du 18e et au début du 19e siècle. (Les Britanniques ont rarement combattu dans 2 rangs, contrairement à la croyance populaire, jusqu'à la fin d'une bataille; d'une part, cela a rendu leurs lignes trop longues pour former rapidement des carrés.) Avant cela, il était courant d'avoir des profondeurs plus grandes, peut-être jusqu'à 8 ou 10 pour une phalange grecque équipée de Sarissa. Choisissez une profondeur qui crée l'impression que vous désirez.

Dans la vraie vie, les armées essaient de maintenir la façade des unités aussi longtemps que possible, au détriment de la fragilité accrue des unités, car cela simplifie la configuration d'un champ de bataille. César à Pharsale a délibérément réduit la profondeur de son unité pour augmenter la façade pour correspondre à celle des forces de Pompée. Comme le dit la citation: "Nous gagnons ou mourons aujourd'hui; les hommes de Pompey ont d'autres choix." (ce que César avait astucieusement et soigneusement assuré, bien sûr).

Pieter Geerkens
la source

Cela ressemble à une solution beaucoup plus élégante. Il n'est pas nécessaire de s'inquiéter des nombres premiers ou des proportions, et pourtant cela évite toujours toute ligne contenant un nombre inhabituellement bas de robots, et la seule condition qui doit être vérifiée est la quantité de backrank!

Tiby312

Mais attendez. Disons que le rang arrière n'a que 3 bots et qu'il est dans les colonnes 1, 2 et 3. Et je retire quelqu'un de la 5e colonne quelqu'un près du front. Je me retrouverais avec une place libre sur l'avant-dernière ligne de la 5ème colonne sans aucun bot derrière pour prendre sa place. Qui devrait occuper ce poste?

Tiby312

Vraisemblablement, le bot le plus proche du dernier rang (c'est-à-dire celui de la colonne 3) devrait fonctionner pour le remplir. Ou vous pourriez gagner un peu de temps en ayant les bots dans les colonnes 3 et 4 de l'avant-dernier rang à chaque étape d'une colonne vers le haut, en déplaçant l'écart vers la colonne 3, puis en faisant avancer le bot de la colonne 3 pour le remplir il. (IMO, la stratégie la plus "naturelle" serait probablement une combinaison heuristique des deux, peut-être avec un peu de hasard.)

Ilmari Karonen

Si le rang arrière a trop peu de membres (disons moins de 50% des autres rangs), et que vous augmentez la façade, est-ce garanti pour résoudre le problème, ou est-il possible que le rang arrière ait encore trop peu de membres après avoir augmenté la façade exigeant qu'il soit répété ou quelque chose?

Tiby312

@ Tiby312: Je pense que vous en pensez trop. Essayez-le, sachant que vous pouvez toujours le régler plus tard

Pieter Geerkens

En supposant qu'une unité est une structure de données linéaire (par exemple une liste ) de robots.

Tout d'abord, vous devez ajouter / supprimer le bot à / de la structure de données et déterminer le nouveau nombre de bots dans l'unité.

Ensuite, vous devez déterminer la nouvelle quantité de lignes et de colonnes à l'aide de https://en.wikipedia.org/wiki/Integer_factorization .

Bien sûr, cela n'est pas toujours possible en raison des nombres premiers . Lorsque la nouvelle taille d'unité est un nombre premier, vous devez utiliser la prochaine taille d'unité plus grande qui ne l'est pas.

Ensuite, il suffit d'itérer sur la structure de données, en affectant des bots dans l'ordre aux lignes et aux colonnes.

Pour placer les bots, il suffit d'itérer sur la structure de données, en attribuant à chaque bot une position décalée par rapport à la position des unités d'une quantité déterminée par la ligne et la colonne dans lesquelles se trouve le bot (ou, définissez ce point comme cible pour le mouvement des bots).

Pour faire une unité avec le centre dans un coin , la position d'un bot est donnée par

unitPosition + cap * columnNumber * botSeparationDistance + rightVector * rowNumber * botSeparationDistance

Pour faire une unité avec le centre au milieu , la position d'un bot est donnée par

unitPosition + n * (* columnNumber unitSeparationDistance - 0,5 * (* numberOfColumns botSeparationDistance) + rightVector * * rowNumber botSeparationDistance - 0,5 * (* numberOfRows botSeparationDistance)

où cap est un vecteur pointant dans la direction à laquelle l'unité fait face et droiteVecteur est un vecteur orthogonal au cap .

botSeparationDistance peut être modifié pour éloigner ou rapprocher les robots.

Si vous êtes de fantaisie de sentiment, vous pouvez compenser la dernière rangée de bots par rightVector * 0,5 * (numberOfColumns - actualNumberOfBotsInRow) pour centrer les sur la formation .

Exilyth
la source

C'est très proche de ce que je recherche! Ma seule réserve est que lors de l'attribution de nouvelles positions, un bot à l'extrême droite d'une ligne peut être assigné à l'extrême gauche de la ligne suivante dans le nouveau rectangle, ce qui fait que le bot doit parcourir une longue distance et dans les processus gênant d'autres robots essayant d'atteindre leur propre nouvelle position assignée. Je crains que lorsqu'un bot soit ajouté ou supprimé, la formation entière soit un fouillis alors que les bots s'affairent pour se rendre à leur destination lointaine.

Tiby312

Vous pouvez toujours calculer les nouvelles positions, puis déplacer le bot le plus proche vers cette position au lieu de faire une itération linéaire.

Exilyth

Comment faire cela sans se retrouver avec un calcul au carré? Je devrais trouver la position la plus proche dans le tableau 2d de leur position actuelle dans le tableau 2d, pour chaque Bot, si je comprends bien.

Tiby312

Dans chaque itération, une unité serait affectée (et n'a donc pas besoin d'être prise en compte lors d'itérations ultérieures), ainsi le temps d'exécution serait O (n!). Ce qui n'est toujours pas très bon. Là encore, construire une [structure d'optimisation de choix] et faire des requêtes sur n plages n'est pas rapide non plus. La seule chose à laquelle je peux penser en ce moment est de déplacer les derniers bots d'affilée vers l'arrière ou de remplir les dernières places d'affilée avec des bots de l'arrière.

Exilyth

Que dis-tu de ça. Supposons que la nouvelle formation ait une taille de ligne plus petite. Ensuite, sur chaque ligne, vous avez un bot supplémentaire. Vous attribuez ce bot un en bas et un à gauche. Ensuite, au rang suivant, vous avez deux Bots sans place. Vous attribuez ces deux un vers le bas et un vers la gauche. Ensuite, vous avez 3 robots sans place. Continuez jusqu'à ce que vous ayez une rangée supplémentaire en bas. Je suis juste en train de cracher du ballon ici. Je ne l'ai pas pensé tout au long, mais il semble que cela fonctionnera et que c'est rapide.

Tiby312

Je stockerais les positions possibles dans un graphique avec des valeurs plus grandes étant des rectangles plus petits.

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

Chaque fois qu'un robot est supprimé, recherchez parmi tous les autres robots et trouvez celui dans un nœud avec la plus petite valeur. Utilisez A * ou un algorithme BST pour lui trouver un chemin de la plus petite valeur à l'espace vacant. S'il n'y a pas de robot avec une valeur inférieure à celle retirée, ne faites rien.

Vous devriez également pouvoir contrôler la façon dont le rectangle se désintègre. Par exemple, dans le graphique ci-dessous, lorsqu'un robot quitte le bas par le côté viendrait remplir sa place.

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

Ici, celui de 3,8 est supprimé afin que celui de 2,5 arrive et remplisse sa place.

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

Un autre exemple. Ici, 2.8 est supprimé pour que le plus petit nœud 2.2 vienne à sa place.

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

Vous voulez probablement un anneau de nœuds avec une valeur 0 que vous ne remplissez jamais autour de l'extérieur pour que votre algorithme de recherche de chemin trouve le trou avec.

[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 bon tutoriel sur A * peut être trouvé ici .

ClassicThunder
la source

C'est une bonne idée, mais si je comprends bien, vous autorisez des formations qui ne sont pas des rectangles parfaits. Les lignes et les colonnes sur les bordures peuvent ne pas être pleines. Je pensais que je pourrais faire en sorte qu'il ait toujours une bordure rectangulaire, et changer plutôt un peu le rapport d'aspect pour répondre à cette exigence en changeant le nombre de lignes et de colonnes. Je peux déjà calculer la nouvelle largeur et hauteur qui permettrait d'accomplir cela, mais il existe ensuite un moyen compliqué de réaffecter les Bots au Spot le plus proche ... Je pense.

Tiby312

@ Tiby312 Comment prévoyez-vous de faire un rectangle parfait avec disons ... 7 robots?

ClassicThunder

NEVERMIND J'ai oublié les nombres premiers. Pardon. Mais je pense toujours que l'ajustement du nombre de lignes et de colonnes pourrait éviter qu'une ligne ou une colonne ne contienne un nombre inhabituellement bas de robots.

Tiby312

@ Tiby312 Je pense que vous feriez mieux de viser un rapport d'aspect cohérent (c'est-à-dire toujours 4: 3 ou 8: 5) que d'essayer de toujours en faire un rectangle parfait.

corsiKa