Bagaimana saya bisa mempertahankan formasi persegi panjang ketika unit ditambahkan atau dihapus?

Saya punya bot dalam formasi persegi panjang dengan baris dan kolom. Masalah muncul ketika bot ditambahkan atau dihapus dari formasi. Ketika ini terjadi, bot harus mengatur ulang diri mereka sendiri sehingga formasi segi empat masih kira-kira sama dengan aspek rasio, dan selebar mungkin. Bagaimana cara melakukannya?

Beberapa ide:

• Ketika bot ditambahkan atau dihapus, gunakan jumlah bot baru dan rasio aspek konstan yang diinginkan untuk menghitung lebar dan tinggi formasi baru yang paling cocok dengan rasio aspek tersebut. Lalu, entah bagaimana atur ulang bot agar sesuai dengan dimensi baru.

• Ketika bot dihapus, pindahkan bot yang berada di belakangnya ke tempatnya, dan lanjutkan sampai Anda mencapai akhir formasi. Kemudian meratakan peringkat belakang sebanyak mungkin dengan mengacak-acak bot di peringkat belakang.

• Gagasan lain yang sama sekali berbeda adalah meniru cara struktur molekul tetap bersama. Buat setiap bot ingin dikelilingi oleh empat bot lain dengan menarik empat bot terdekat, dan tolak sisanya. Tolak semua bot (termasuk empat) yang terlalu dekat untuk memastikan pemisahan menggunakan hukum kuadrat terbalik. Anda juga membutuhkan kekuatan tambahan untuk membentuk seluruh struktur. Tapi, ini terdengar sangat mahal secara komputasi.

UPDATE : Jadi melihat ke jawaban sarahm, saya datang dengan fungsi umum yang bagus yang memberikan dimensi yang baik.

Pertama saya memecahkan persamaan simultan di bawah ini untuk lebar dan tinggi, dan kemudian membulatkan jawaban.

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

Ini memberi Anda persegi bilangan bulat terdekat dengan rasio aspek untuk jumlah bot Anda. Kotak terdekat akan separuh waktu menjadi terlalu besar, dan separuh waktu menjadi terlalu kecil (tentu saja kadang-kadang akan tepat tetapi siapa yang peduli tentang itu). Dalam kasus di mana persegi panjang agak terlalu besar, tidak ada yang perlu dilakukan. Peringkat belakang hanya akan berakhir menjadi hampir penuh, yang ideal. Dalam kasus di mana persegi panjang agak terlalu kecil, Anda punya masalah karena luapan kecil mungil harus pergi ke peringkat sendiri menciptakan peringkat dengan hanya beberapa bot di atasnya, yang tidak terlihat cantik. Ada juga kasus di mana perbedaannya besar(lebih besar dari setengah lebar), dalam hal ini menambah atau mengurangi satu peringkat untuk membuat perbedaan kecil. Kemudian, ketika persegi panjang terlalu kecil, tambahkan satu kolom untuk membuatnya sedikit lebih besar. Setelah melakukan itu sepertinya peringkat belakang akan selalu memiliki setidaknya setengah bot sebanyak peringkat lainnya.

MEMPERBARUI

Setelah Anda mendapatkan dimensi, bandingkan dengan dimensi saat ini. Jika bagian depan dimensi baru lebih besar, untuk setiap peringkat, letakan bot dari peringkat di bawah, dan dorong mereka ke peringkat saat ini hingga jumlah bot di peringkat itu sama dengan bagian depan. Lanjutkan algoritma itu sampai Anda mencapai peringkat belakang. Dengan menggunakan algoritma ini, bot akan bergerak agar sesuai dengan dimensi baru secara efisien. Setelah itu, saya hanya mendorong yang lama ke peringkat belakang. Algoritma ini sedikit berbeda untuk kasus-kasus di mana bagian depan yang baru lebih kecil, tetapi Anda dapat mengetahuinya!

Ada dua masalah lagi selanjutnya. Penghapusan, dan metode penambahan yang lebih fleksibel di mana bot baru tidak harus ditetapkan ke peringkat belakang tetapi posisi mana pun yang paling dekat dengan mereka saat mereka ditambahkan.

Teknik lain adalah meniru yang digunakan oleh batalyon Napoleon (dan mungkin sejauh phalanx Yunani jika tidak lebih jauh).

Frontage umumnya dipertahankan konstan, dan ketika seorang pria jatuh (dalam peringkat apa pun kecuali bagian belakang) ia digantikan oleh pria yang berada tepat di belakangnya, melangkah maju. Pangkat belakang diacak oleh NCO untuk memastikan beberapa orang berada pada posisi paling ekstrem di setiap sisi, dan sebaliknya mengisi secara merata.

Bagian depan hanya berkurang ketika peringkat belakang turun di bawah kepadatan yang ditentukan sebelumnya. Demikian juga, ketika peringkat belakang terlalu penuh maka ekstra pertama mulai mengisi peringkat tambahan dari kedua sisi, dan kemudian bagian depan meningkat.

Saat mengganti bagian depan, saya sarankan agar bot Anda keluar dari peringkat belakang ke kedua sisi ketika meningkatkan bagian depan, dan mengajukan dari kedua sisi ke peringkat belakang saat mengurangi bagian depan.

Jika saya benar dalam menyimpulkan bahwa Anda mencari kesan "militer", dan membuat organisasi bot Anda terlihat seperti phalanx, saya yakin pengaturan ulang yang dipesan ini adalah cara yang lebih baik untuk mencapai tujuan itu.

Pembaruan :
Salah satu cara sederhana untuk mengelola baris belakang adalah dengan membagi unit baris belakang menjadi tiga regu: satu di setiap sisi dan satu di tengah. Bergantung pada apakah bagian depan ganjil atau genap, dan apakah jumlah unit baris belakang sesuai dengan 0,1, atau 2 mod 3, ada tepat enam kasus untuk dikelola.

Sebagai tambahan untuk yang di atas, pertimbangkan untuk menempatkan unit terakhir dari masing-masing regu baris belakang setelah isi turun di bawah ambang batas, seperti ini:
xxx.x .... x.xxx.x .... x. xxx
atau ini:
xx.xx..x.xxx.x ... xxxx
Sedikit lebih banyak pekerjaan, untuk penampilan yang lebih baik.

Pembaruan # 2 :
Pikiran tambahan tentang kedalaman formasi. Dampak tembakan voli, dikombinasikan dengan bayonet modern, membuat kedalaman 3 atau 4 memadai di akhir abad ke-18 dan awal abad ke-19. (Inggris jarang bertempur dalam 2 peringkat, bertentangan dengan kepercayaan populer, sampai akhir pertempuran; untuk satu, itu membuat garis mereka terlalu lama untuk membentuk persegi dengan cepat.) Sebelum itu umum untuk memiliki kedalaman yang lebih besar, mungkin hingga 8 atau 10 untuk phalanx Yunani yang dilengkapi dengan Sarissa. Pilih kedalaman yang menciptakan kesan yang Anda inginkan.

Tentara dalam kehidupan nyata mencoba mempertahankan frontage unit selama mungkin, dengan mengorbankan peningkatan kerapuhan unit, karena hal ini membuat meletakkan medan perang menjadi lebih sederhana. Caesar di Pharsalus dengan sengaja mengurangi kedalaman unitnya untuk meningkatkan bagian depan agar sesuai dengan pasukan Pompey. Seperti kutipan: "Kami menang atau mati hari ini; pasukan Pompeye punya pilihan lain." (yang telah dipastikan dengan cerdik dan hati-hati, tentu saja).

Dengan asumsi unit adalah struktur data linear (mis. Daftar ) bot.

Pertama, Anda harus menambah / menghapus bot ke / dari struktur data dan menentukan jumlah bot baru di unit.

Kemudian, Anda harus menentukan jumlah baris dan kolom baru menggunakan https://en.wikipedia.org/wiki/Integer_factorization .

Tentu saja, ini tidak selalu mungkin karena bilangan prima . Ketika ukuran unit baru adalah bilangan prima, Anda perlu menggunakan ukuran unit lebih besar berikutnya yang tidak.

Kemudian, ulangi saja datastructure, tetapkan bot untuk baris dan kolom.

Untuk menempatkan bot, cukup beralih di atas struktur data, tetapkan setiap bot posisi yang diimbangi dari posisi unit dengan jumlah yang ditentukan oleh baris dan kolom bot berada di (atau, tetapkan titik itu sebagai target untuk pergerakan bot).

Untuk membuat unit dengan pusat di satu sudut , posisi bot diberikan oleh

unitPosition + heading * columnNumber * botSeparationDistance + rightVector * rowNumber * botSeparationDistance

Untuk membuat unit dengan pusat di tengah , posisi bot diberikan oleh

unitPosisi + heading * (kolomJumlah * unitSeparationDistance - 0,5 * (numberOfColumns * botSeparationDistance) + rightVector * rowNumber * botSeparationDistance - 0,5 * (numberOfRows * botSeparationDistance)

di mana heading adalah vektor yang menunjuk ke arah unit menghadap dan rightVector adalah vektor orthogonal menuju heading .

botSeparationDistance dapat di-tweak untuk membuat bot berdiri lebih jauh atau berdekatan.

Jika Anda sedang merasa mewah, Anda dapat mengimbangi baris terakhir dari bots oleh rightVector * 0,5 * (numberOfColumns - actualNumberOfBotsInRow) ke pusat mereka di formasi .

Saya akan menyimpan posisi yang mungkin dalam grafik dengan nilai yang lebih besar menjadi persegi panjang yang lebih kecil.

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

Setiap kali robot dihilangkan, cari semua robot lainnya dan temukan satu dalam satu simpul dengan nilai terkecil. Gunakan algoritma A * atau BST untuk menemukannya jalur dari nilai terkecil ke ruang kosong. Jika tidak ada robot dengan nilai lebih kecil dari yang dihilangkan tidak melakukan apa-apa.

Anda juga harus dapat mengontrol bagaimana persegi panjang meluruh melakukan ini. Sebagai contoh dalam grafik di bawah ini ketika robot meninggalkan bagian bawah dari samping akan mengisi tempatnya.

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

Di sini yang di 3,8 dihapus sehingga yang di 2,5 datang dan mengisi tempatnya.

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

Contoh lain. Di sini 2.8 dihapus sehingga simpul terkecil 2.2 datang dan mengisi tempatnya.

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

Anda mungkin ingin cincin node dengan nilai 0 yang Anda tidak pernah mengisi di luar untuk algoritma pathfinding Anda untuk menemukan lubang.

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

Tutorial yang bagus tentang A * dapat ditemukan di sini .