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

18

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.

Tiby312
quelle
Was ist die maximale Anzahl von Bots in einer Einheit? Wenn es relativ klein ist, können Sie fest codieren, wie viele Zeilen und Spalten eine Formation für eine bestimmte Anzahl von Bots hat.
Exilyth
3
Können Sie vielleicht ein Bild von Formationen posten, die gültig oder ungültig sind? Ich habe ein wenig Probleme zu verstehen, wonach Sie suchen. Sind unvollständige Zeilen / Spalten erlaubt?
MichaelHouse
3
Sie wissen, dass dies für Primzahlen nicht funktioniert? zB mit 7 Bots müssten Sie eine 3x2-Einheit mit einem einzelnen Bot im Rücken herstellen.
Exilyth
1
Nun, das ist peinlich. Ich habe die Primzahlen komplett vergessen. Dann wäre es vielleicht das nächstbeste, nur Zeilen und Spalten zuzulassen, die FAST gefüllt sind. Ein Bot in einer Reihe sieht nicht richtig aus, aber ein Bot weniger in einer Reihe würde nicht schlecht aussehen.
Tiby312
3
Primzahlen sind nicht die einzigen, die Probleme bereiten. Die Auswahl der Formationsgröße durch Faktorisierung kann zu unangemessen langen und dünnen Formationen führen. Wenn Sie beispielsweise 14 Bots haben, ist die einzige perfekte rechteckige Formation 7x2, während es besser aussehen könnte , eine 3x4-Formation mit einer zusätzlichen Reihe von 2 Bots zu haben.
Nathan Reed

Antworten:

16

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).

Pieter Geerkens
quelle
Das klingt nach einer viel eleganteren Lösung. Es besteht kein Grund, sich um Primzahlen oder Seitenverhältnisse zu kümmern, und dennoch werden Zeilen mit einer ungewöhnlich geringen Anzahl von Bots vermieden. Die einzige Bedingung, die überprüft werden muss, ist, wie voll der Hintergrund ist!
Tiby312
Aber warte. Angenommen, der hintere Rang enthält nur 3 Bots und befindet sich in den Spalten 1, 2 und 3. Und ich entferne jemanden aus der fünften Spalte, der sich in der Nähe des vorderen Ranges befindet. Am Ende hätte ich einen freien Platz in der vorletzten Reihe in der fünften Spalte, ohne dass ein Bot dahinter stünde, um seinen Platz einzunehmen. Wer soll diese Stelle besetzen?
Tiby312
Vermutlich sollte der nächste Bot im hinteren Rang (dh der in Spalte 3) ausgeführt werden, um ihn zu füllen. Sie können auch ein wenig Zeit sparen, indem Sie die Bots in den Spalten 3 und 4 des vorletzten Ranges jeweils eine Spalte nach oben verschieben, die Lücke zu Spalte 3 verschieben und dann den Bot in Spalte 3 zum Füllen nach vorne bewegen es. (IMO, die "natürlichste" Strategie wäre wahrscheinlich eine heuristische Kombination der beiden, möglicherweise mit etwas Zufälligkeit.)
Ilmari Karonen
1
Wenn der hintere Rang zu wenig Mitglieder hat (sagen wir weniger als 50% der anderen Ränge) und Sie die Front erhöhen, wird dies garantiert das Problem beheben, oder ist es möglich, dass der hintere Rang nach der Erhöhung noch zu wenig Mitglieder hat die Front, die es erfordert, wiederholt zu werden, oder etwas?
Tiby312
1
@ Tiby312: Ich glaube du überdenkst es. Probieren Sie es aus und wissen Sie, dass Sie es später immer noch tun können
Pieter Geerkens
7

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 .

Exilyth
quelle
Das ist sehr nah an dem, wonach ich suche! Meine einzige Einschränkung ist, dass beim Zuweisen neuer Positionen ein Bot ganz rechts in einer Reihe ganz links in der nächsten Reihe im neuen Rechteck zugewiesen werden kann, was dazu führt, dass der Bot eine lange Strecke zurücklegt und die Prozesse ausführt Sich anderen Bots in den Weg stellen, die versuchen, ihre eigene neue zugewiesene Position zu erreichen. Ich mache mir Sorgen, dass, wenn ein Bot hinzugefügt oder entfernt wird, die gesamte Formation ein Durcheinander sein könnte, wenn Bots geschäftig an ihr weit entferntes Ziel gelangen.
Tiby312
2
Sie können jederzeit die neuen Positionen berechnen und dann den nächsten Bot an diese Position verschieben, anstatt eine lineare Iteration durchzuführen.
Exilyth
Wie kann man dies tun, ohne eine Quadratberechnung zu erhalten? Wenn ich das richtig verstehe, müsste ich für jeden Bot die nächstgelegene Position im 2d-Array von ihrer aktuellen Position im 2d-Array finden.
Tiby312
In jeder Iteration würde eine Einheit zugewiesen (und muss daher bei weiteren Iterationen nicht berücksichtigt werden), daher wäre die Laufzeit O (n!). Was immer noch nicht sehr gut ist. Andererseits ist es auch nicht schnell, eine [Optimierungsstruktur der Wahl] zu erstellen und n Bereichsabfragen durchzuführen. Ich kann mir im Moment nur vorstellen, die letzten Bots in einer Reihe nach hinten zu verschieben oder die letzten Stellen in einer Reihe mit Bots von hinten zu füllen.
Exilyth
Wie wäre es damit. Angenommen, die neue Formation hat eine kleinere Zeilengröße. Dann hast du in jeder Reihe einen zusätzlichen Bot. Sie weisen diesen Bot einen nach unten und einen nach links zu. Dann haben Sie in der nächsten Reihe unten zwei Bots ohne Platz. Sie weisen diese beiden einen nach unten und einen nach links. Dann hast du 3 Bots ohne Platz. Fahren Sie fort, bis Sie unten eine zusätzliche Zeile haben. Ich spucke nur Ball hier. Ich habe es nicht durchgedacht, aber es hört sich so an, als würde es funktionieren und es ist schnell.
Tiby312
2

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 .

ClassicThunder
quelle
Dies ist eine süße Idee, aber wenn ich das richtig verstehe, lassen Sie Formationen zu, die keine perfekten Rechtecke sind. Die Zeilen und Spalten an den Rändern sind möglicherweise nicht voll. Ich dachte, ich könnte es so gestalten, dass es immer einen rechteckigen Rand hat, und stattdessen das Seitenverhältnis ein wenig ändern, um diese Anforderung zu erfüllen, indem die Anzahl der Zeilen und Spalten geändert wird. Ich kann bereits die neue Breite und Höhe berechnen, die dies bewirken würde, aber dann gibt es eine komplizierte Möglichkeit, die Bots wieder dem nächsten Punkt zuzuweisen. Ich denke.
Tiby312
@ Tiby312 Wie hast du vor, mit etwa 7 Robotern ein perfektes Rechteck zu machen?
ClassicThunder
NIEMALS habe ich Primzahlen vergessen. Es tut uns leid. Aber ich denke immer noch, dass das Anpassen der Anzahl der Zeilen und Spalten verhindern könnte, dass eine Zeile oder Spalte ungewöhnlich wenige Bots enthält.
Tiby312
@ Tiby312 Ich denke, du bist besser dran, ein konsistentes Seitenverhältnis anzustreben (dh immer 4: 3 oder 8: 5), als immer zu versuchen, es zu einem perfekten Rechteck zu machen.
Corsika