Wie kann ich eine rechteckige Formation beibehalten, wenn Einheiten hinzugefügt oder entfernt werden?

Ich habe Bots in einer rechteckigen Formation mit Zeilen und Spalten. Ein Problem tritt auf, wenn ein Bot der Formation hinzugefügt oder daraus entfernt wird. In diesem Fall müssen sich die Bots neu anordnen, sodass die rechteckige Formation immer noch in etwa dasselbe Seitenverhältnis aufweist und so rechteckig wie möglich ist. Wie macht man das?

Einige Ideen:

• Wenn ein Bot hinzugefügt oder entfernt wird, verwenden Sie die neue Gesamtzahl der Bots und ein gewünschtes konstantes Seitenverhältnis, um die neue Breite und Höhe der Formation zu berechnen, die diesem Seitenverhältnis am ehesten entspricht. Dann werden die Bots irgendwie neu gemischt, um sie an die neuen Dimensionen anzupassen.

• Wenn ein Bot entfernt wird, bewegen Sie den dahinter befindlichen Bot an seinen Platz und fahren Sie fort, bis Sie das Ende der Formation erreicht haben. Dann gleichen Sie den hinteren Rang so weit wie möglich aus, indem Sie die Bots im hinteren Rang irgendwie mischen.

• Eine andere Idee, die völlig anders ist, ist die Nachahmung der Art und Weise, wie Molekülstrukturen zusammenhalten. Machen Sie, dass jeder Bot von vier anderen Bots umgeben sein möchte, indem Sie die vier nächsten Bots anziehen und den Rest abwehren. Vertreibe alle Bots (einschließlich der vier), die zu nahe beieinander liegen, um eine Trennung mit dem inversen Quadratgesetz zu gewährleisten. Sie würden auch eine zusätzliche Kraft benötigen, um die gesamte Struktur zu formen. Das klingt aber sehr rechenintensiv.

UPDATE : Als ich mich also mit der Antwort von sarahm befasste, fand ich eine gute allgemeine Funktion, die gute Dimensionen ergibt.

Zuerst löste ich die unten stehende simultane Gleichung für Breite und Höhe und rundete dann die Antworten.

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

Dies gibt Ihnen das nächste ganzzahlige Rechteck zu diesem Seitenverhältnis für Ihre Anzahl von Bots. Das nächste Rechteck ist zur Hälfte zu groß und zur Hälfte zu klein (natürlich ist es manchmal genau richtig, aber wen interessiert das schon). In den Fällen, in denen das Rechteck etwas zu groß ist, muss nichts unternommen werden. Der hintere Rang wird fast voll sein, was ideal ist. In den Fällen, in denen das Rechteck ein wenig zu klein ist, haben Sie Probleme, weil dieser winzige Überlauf zu seinem eigenen Rang gehen muss, der einen Rang mit nur wenigen Bots erstellt hat, der nicht hübsch aussieht. Es gibt auch Fälle, in denen der Unterschied groß ist(größer als die Hälfte der Breite). In diesem Fall addieren oder subtrahieren Sie einen Rang, um den Unterschied zu verringern. Wenn das Rechteck zu klein ist, fügen Sie eine Spalte hinzu, um es nur ein bisschen größer zu machen. Danach sieht es so aus, als hätte der hintere Rang immer mindestens halb so viele Bots wie die anderen Ränge.

AKTUALISIEREN

Wenn Sie die Abmessungen erhalten haben, vergleichen Sie sie mit den aktuellen Abmessungen. Wenn die Front der neuen Dimension für jeden Rang größer ist, platzieren Sie Bots aus dem darunter liegenden Rang und verschieben Sie sie in den aktuellen Rang, bis die Anzahl der Bots in diesem Rang der Front entspricht. Setzen Sie diesen Algorithmus fort, bis Sie zum hinteren Rang gelangen. Mit diesem Algorithmus werden Bots so verschoben, dass sie effizient in die neue Dimension passen. Danach schiebe ich einfach das neue alte auf den hinteren Rang. Der Algorithmus unterscheidet sich geringfügig für die Fälle, in denen die neue Front kleiner ist, aber Sie können es herausfinden!

Es gibt zwei weitere Probleme. Löschen und flexiblere Hinzufügungsmethode, bei der neue Bots nicht unbedingt dem hinteren Rang zugewiesen werden, sondern an der Position, die ihnen zum Zeitpunkt des Hinzufügens am nächsten liegt.

Eine andere Technik ist es, die der napoleonischen Bataillone nachzuahmen (und wahrscheinlich bis zu den griechischen Phalanxen, wenn nicht sogar noch weiter).

Die Front wird im Allgemeinen konstant gehalten, und wenn ein Mann fällt (in einem beliebigen Rang außer dem Rücken), wird er durch den Mann direkt hinter ihm ersetzt, der nach vorne tritt. Der hintere Rang wird von den Unteroffizieren gemischt, um sicherzustellen, dass sich am äußersten Ende jeder Flanke ein paar Männer befinden, und um sich ansonsten gleichmäßig zu füllen.

Die Front wird nur reduziert, wenn der hintere Rang unter die vorgegebenen Dichten fällt. Wenn der hintere Rang überfüllt ist, füllen die Statisten zunächst einen zusätzlichen Rang von beiden Flanken aus und erhöhen dann die Front.

Wenn Sie die Front ändern, empfehle ich, dass Ihre Bots vom hinteren Rang zu beiden Flanken verschoben werden, wenn Sie die Front vergrößern, und von beiden Flanken zum hinteren Rang verschoben werden, wenn Sie die Front verkleinern.

Wenn ich richtig schließe, dass Sie nach einem "militärischen" Eindruck suchen und Ihre Bot-Organisationen wie Phalanxe aussehen, ist diese geordnete Neuanordnung meiner Meinung nach ein besserer Weg, um dieses Ziel zu erreichen.

Update :
Eine einfache Möglichkeit, die hintere Reihe zu verwalten, besteht darin, die Einheiten der hinteren Reihe in drei Gruppen zu unterteilen: eine an jeder Flanke und eine in der Mitte. Abhängig davon, ob die Front ungerade oder gerade ist und ob die Anzahl der Einheiten in der hinteren Reihe mit 0,1 oder 2 mod 3 übereinstimmt, sind genau sechs Fälle zu verwalten.

Als eine Verbesserung des Vorstehenden sollten Sie in Betracht ziehen, die letzten Einheiten jedes Trupps in der hinteren Reihe zu
beabstanden, sobald die Besetzung unter einen Schwellenwert fällt, wie folgt : xxx.x .... x.xxx.x .... x. xxx
oder so:
xx.xx..x.xxx.x ... xxxx
Ein bisschen mehr Arbeit für ein noch besseres Aussehen.

Update Nr. 2 :
Ein zusätzlicher Gedanke zur Formationstiefe. Der Aufprall von Salvenfeuer in Kombination mit dem modernen Bajonett machte Tiefen von 3 oder 4 im späten 18. und frühen 19. Jahrhundert angemessen. (Die Briten kämpften entgegen der landläufigen Meinung selten in zwei Rängen, bis spät in einer Schlacht. Zum einen waren ihre Linien zu lang, um schnell ein Quadrat zu bilden.) Vorher war es üblich, größere Tiefen zu haben, vielleicht bis zu 8 oder 10 für eine griechische Phalanx mit Sarissa. Wählen Sie eine Tiefe, die den gewünschten Eindruck vermittelt.

Armeen im wirklichen Leben versuchen, die Front der Einheiten so lange wie möglich aufrechtzuerhalten, was zu einer erhöhten Sprödigkeit der Einheiten führt, da dies das Aufstellen eines Schlachtfelds vereinfacht. Caesar bei Pharsalus reduzierte absichtlich seine Einheitentiefe, um die Front zu vergrößern, die der von Pompey's Streitkräften entspricht. Wie das Zitat lautet: "Wir gewinnen oder sterben heute; Pompeys Männer haben andere Möglichkeiten." (was Caesar natürlich geschickt und sorgfältig sichergestellt hatte).

Angenommen, eine Einheit ist eine lineare Datenstruktur (z. B. eine Liste ) von Bots.

Zuerst müssen Sie den Bot zur Datenstruktur hinzufügen / daraus entfernen und die neue Anzahl der Bots in der Einheit bestimmen.

Anschließend müssen Sie die neue Anzahl der Zeilen und Spalten mithilfe von https://en.wikipedia.org/wiki/Integer_factorization ermitteln .

Natürlich ist dies aufgrund von Primzahlen nicht immer möglich . Wenn die neue Einheitsgröße eine Primzahl ist, müssen Sie die nächstgrößere Einheitsgröße verwenden, die es nicht ist.

Dann iterieren Sie einfach über die Datenstruktur und weisen den Zeilen und Spalten Bots zu.

Um die Bots zu platzieren, iterieren Sie einfach über die Datenstruktur und weisen jedem Bot eine Position zu, die von der Einheitsposition um einen Betrag versetzt ist, der durch die Zeile und Spalte bestimmt wird, in der sich der Bot befindet (oder legen Sie diesen Punkt als Ziel für die Bots-Bewegung fest).

Um eine Einheit mit der Mitte an einer Ecke zu erstellen , wird die Position eines Bots durch angegeben

unitPosition + Überschrift * columnNumber * botSeparationDistance + rightVector * rowNumber * botSeparationDistance

Um eine Einheit mit der Mitte in der Mitte zu bilden , wird die Position eines Bots durch gegeben

unitPosition + Überschrift * (columnNumber * unitSeparationDistance - 0.5 * (numberOfColumns * botSeparationDistance) + rightVector * rowNumber * botSeparationDistance - 0.5 * (numberOfRows * botSeparationDistance)

Dabei ist Heading ein Vektor, der in die Richtung zeigt, in die die Einheit zeigt, und RightVector ist ein Vektor, der orthogonal zum Heading ist .

botSeparationDistance kann so angepasst werden, dass Bots weiter voneinander entfernt oder näher beieinander stehen.

Wenn Sie das Gefühl Phantasie, können Sie den Offset letzte Reihe von Bots durch rightVector * 0.5 * (NumberOfColumns - actualNumberOfBotsInRow) zu zentrieren sie auf die Bildung .

Ich würde die möglichen Positionen in einem Diagramm speichern, wobei größere Werte kleinere Rechtecke sind.

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

Jedes Mal, wenn ein Roboter entfernt wird, durchsuchen Sie alle anderen Roboter und finden Sie denjenigen in einem Knoten mit dem kleinsten Wert. Verwenden Sie einen A * - oder einen BST-Algorithmus, um einen Pfad vom kleinsten Wert zum freien Platz zu finden. Wenn es keinen Roboter mit einem kleineren Wert als dem entfernten gibt, nichts tun.

Sie sollten auch steuern können, wie das Rechteck dabei zerfällt. Zum Beispiel würde in der folgenden Grafik ein Roboter, wenn er den unteren von der Seite verlässt, seinen Platz einnehmen.

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

Hier wird der bei 3.8 entfernt, so dass der bei 2.5 kommt und seinen Platz einnimmt.

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

Ein anderes Beispiel. Hier wird 2.8 entfernt, damit der kleinste Knoten 2.2 seinen Platz einnimmt.

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

Sie möchten wahrscheinlich einen Ring von Knoten mit dem Wert 0, den Sie niemals außen herum auffüllen, damit Ihr Pfadfindungsalgorithmus die Lücke findet.

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

Ein gutes Tutorial zu A * finden Sie hier .