Jak mogę zachować prostokątną formację, gdy jednostki są dodawane lub usuwane?

Mam boty w prostokątnej formacji z rzędami i kolumnami. Problem pojawia się, gdy bot jest dodawany lub usuwany z formacji. Kiedy tak się dzieje, boty muszą się tak przestawić, aby formacja prostokątna była w przybliżeniu tym samym współczynnikiem kształtu i była możliwie jak najbardziej prostokątna. Jak to zrobić?

Jakieś pomysły:

• Po dodaniu lub usunięciu bota użyj nowej całkowitej liczby botów i pożądanego stałego współczynnika kształtu, aby obliczyć nową szerokość i wysokość formacji, która najbardziej pasuje do tego współczynnika kształtu. Następnie w jakiś sposób przetasuj boty, aby dopasować je do nowych wymiarów.

• Po usunięciu bota przenieś bota, który był za nim, na swoje miejsce i kontynuuj, aż dojdziesz do końca formacji. Następnie wyrównaj tylną rangę tak bardzo, jak to możliwe, w jakiś sposób tasując boty z tylnej rangi.

• Innym pomysłem, który jest zupełnie inny, jest naśladowanie sposobu, w jaki struktury molekularne pozostają razem. Spraw, aby każdy bot chciał być otoczony czterema innymi botami, przyciągając cztery najbliższe boty i odpychając resztę. Odeprzyj wszystkie boty (w tym cztery), które są zbyt blisko, aby zapewnić separację, stosując odwrotne prawo kwadratowe. Potrzebujesz także dodatkowej siły, aby ukształtować całą konstrukcję. Ale to brzmi bardzo kosztownie obliczeniowo.

AKTUALIZACJA : Więc patrząc na odpowiedź Sarahm, wymyśliłem dobrą ogólną funkcję, która daje dobre wymiary.

Najpierw rozwiązałem poniższe równanie szerokości i wysokości, a następnie zaokrągliłem odpowiedzi.

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

To daje ci najbliższy prostokąt całkowity do tego współczynnika kształtu dla twojej liczby botów. Najbliższy prostokąt będzie w połowie przypadków zbyt duży, a w połowie będzie zbyt mały (oczywiście czasami będzie to w sam raz, ale kogo to obchodzi). W przypadkach, gdy prostokąt jest trochę za duży, nie trzeba nic robić. Tylna pozycja skończy się prawie pełna, co jest idealne. W przypadkach, gdy prostokąt jest trochę za mały, masz problemy, ponieważ ten malutki przepełnienie będzie musiał przejść do własnej rangi, utworzył rangę z tylko kilkoma botami, co nie wygląda ładnie. Istnieją również przypadki, w których różnica jest duża(większa niż połowa szerokości), w takim przypadku dodaj lub odejmij jedną pozycję, aby różnica była niewielka. Następnie, gdy prostokąt jest zbyt mały, dodaj jedną kolumnę, aby była nieco większa. Po zrobieniu tego wygląda na to, że tylna ranga zawsze będzie miała co najmniej o połowę mniej botów niż pozostałe szeregi.

AKTUALIZACJA

Po uzyskaniu wymiarów porównaj je z bieżącymi wymiarami. Jeśli pierzeja nowego wymiaru jest większa, dla każdej rangy strzelaj botami z poniższej rangi i pchaj je na bieżącą rangę, aż liczba botów na tej randze będzie równa pierzei. Kontynuuj ten algorytm, aż dojdziesz do tylnej rangi. Korzystając z tego algorytmu, boty będą się skutecznie dopasowywać do nowego wymiaru. Potem po prostu przesuwam nowy stary na tylną pozycję. Algorytm jest nieco inny dla przypadków, w których nowy fronton jest mniejszy, ale możesz to rozgryźć!

Następne dwa problemy. Usuwanie i bardziej elastyczna metoda dodawania, w której nowe boty niekoniecznie są przypisywane do tylnej rangi, ale w zależności od tego, która pozycja jest im najbliższa w momencie ich dodawania.

Inną techniką jest naśladowanie tej używanej przez bataliony napoleońskie (i prawdopodobnie tak daleko jak greckie falangi, jeśli nie dalej).

Pierzeja jest na ogół utrzymywana na stałym poziomie, a gdy mężczyzna upada (w dowolnej randze poza plecami), zostaje zastąpiony przez mężczyznę bezpośrednio za nim, który robi krok do przodu. Tylna ranga jest tasowana przez podoficerów, aby zapewnić kilku ludzi na skraju każdej flanki, a poza tym równomiernie wypełnić.

Pierzeja jest zmniejszana tylko wtedy, gdy tylna ranga spada poniżej z góry określonych gęstości. Podobnie, gdy tylna ranga jest przepełniona, statystycy najpierw zaczynają wypełniać dodatkową rangę z obu flanek, a następnie zwiększają się fronty.

Przy zmianie frontu sugeruję, aby twoje boty wyszły z tylnej rangi do obu flanek podczas zwiększania frontu, i przechowywanie z obu flank do tylnej rangi podczas zmniejszania frontu.

Jeśli mam rację, wnioskując, że szukasz wrażenia „militarnego”, a twoje organizacje botów wyglądają jak falangi, uważam, że ta uporządkowana reorganizacja jest lepszym sposobem na osiągnięcie tego celu.

Aktualizacja :
Jednym prostym sposobem zarządzania tylnym rzędem jest podzielenie jednostek tylnego rzędu na trzy oddziały: jeden na każdej flance i jeden na środku. W zależności od tego, czy front jest nieparzysty, czy parzysty oraz od tego, czy liczba jednostek w tylnym rzędzie jest zgodna z 0,1, czy 2 modem 3, jest dokładnie sześć przypadków do zarządzania.

Jako uzupełnienie powyższego rozważ rozważ rozmieszczenie ostatnich jednostek każdej drużyny w tylnym rzędzie, gdy wypełnienie spadnie poniżej progu, na przykład:
xxx.x .... x.xxx.x .... x. xxx
lub to:
xx.xx..x.xxx.x ... xxxx
Trochę więcej pracy, dla jeszcze lepszego wyglądu.

Aktualizacja nr 2 :
Dodatkowa refleksja na temat głębokości formacji. Oddziaływanie ognia salwy w połączeniu z nowoczesnym bagnetem sprawiło, że głębokości 3 lub 4 były wystarczające na przełomie XVIII i XIX wieku. (Brytyjczycy rzadko walczyli w 2 szeregach, wbrew powszechnemu przekonaniu, aż do późnej bitwy; po pierwsze, ich linie były zbyt długie, aby szybko uformować kwadrat). Wcześniej powszechne było posiadanie większych głębokości, być może nawet do 8 lub 10 dla greckiej falangi wyposażonej w Sarissę. Wybierz głębię, która tworzy pożądane wrażenie.

Armie w prawdziwym życiu starają się utrzymać jak najdłuższy front jednostki, kosztem zwiększonej kruchości jednostek, ponieważ ułatwia to układanie pola bitwy. Cezar w Farsalu celowo zmniejszył głębokość swojej jednostki, aby zwiększyć fronton, tak aby pasował do sił Pompejusza. Cytat brzmi: „Dzisiaj wygramy lub umrzemy; ludzie Pompejusza mają inne możliwości”. (co Cezar sprytnie i starannie zapewnił oczywiście).

Zakładając, że urządzenie jest datastructure liniowa (na przykład listy ) z robotów.

Najpierw musisz dodać / usunąć bota do / ze struktury danych i określić nową liczbę botów w urządzeniu.

Następnie musisz określić nową liczbę wierszy i kolumn za pomocą https://en.wikipedia.org/wiki/Integer_factorization .

Oczywiście nie zawsze jest to możliwe ze względu na liczby pierwsze . Gdy nowy rozmiar jednostki jest liczbą pierwszą, musisz użyć następnego większego rozmiaru jednostki, który nie jest.

Następnie po prostu iteruj po strukturze danych, przypisując boty w kolejności do wierszy i kolumn.

Aby umieścić boty, po prostu iteruj nad strukturą danych, przypisując każdemu botowi pozycję przesuniętą od pozycji jednostek o wartość określoną przez rząd i kolumnę, w której znajduje się bot (lub ustaw ten punkt jako cel ruchu botów).

Aby stworzyć jednostkę ze środkiem w jednym rogu , pozycję bota podaje

unitPosition + nagłówek * columnNumber * botSeparationDistance + rightVector * rowNumber * botSeparationDistance

Aby stworzyć jednostkę ze środkiem na środku , pozycję bota określa

unitPosition + nagłówek * (columnNumber * unitSeparationDistance - 0,5 * (numberOfColumns * botSeparationDistance) + rightVector * rowNumber * botSeparationDistance - 0,5 * (numberOfRows * botSeparationDistance)

gdzie kurs jest wektorem wskazującym kierunek, w którym jednostka jest skierowana, a prawy wektor jest wektorem prostopadłym do kierunku .

botSeparationDistance można modyfikować, aby boty stały dalej lub bliżej siebie.

Jeśli masz ochotę, możesz przesunąć ostatni rząd botów za pomocą rightVector * 0,5 * (numberOfColumns - actualNumberOfBotsInRow), aby wyśrodkować je na formacji .

Zapisałbym możliwe pozycje na wykresie, przy czym większe wartości to mniejsze prostokąty.

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

Za każdym razem, gdy robot jest usuwany, przeszukaj wszystkie pozostałe roboty i znajdź go w węźle o najmniejszej wartości. Użyj algorytmu A * lub BST, aby znaleźć ścieżkę od najmniejszej wartości do wolnego miejsca. Jeśli nie ma robota o mniejszej wartości niż usunięty, nie rób nic.

Powinieneś być także w stanie kontrolować, w jaki sposób prostokąt rozpada się, robiąc to. Na przykład na poniższym wykresie, gdy robot opuszcza dolny, z boku przyjdzie jego miejsce.

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

Tutaj ten o 3,8 jest usuwany, więc ten o 2,5 pojawia się i zajmuje swoje miejsce.

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

Inny przykład. Tutaj 2.8 jest usuwane, więc najmniejszy węzeł 2.2 zajmuje miejsce.

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

Prawdopodobnie potrzebujesz pierścienia węzłów o wartości 0, którego nigdy nie wypełniasz na zewnątrz, aby algorytm znajdujący ścieżkę znalazł dziurę.

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

Dobry samouczek na temat A * można znaleźć tutaj .