How can I maintain a rectangular formation when units are added or removed?

Question

I've got bots in a rectangular formation with rows and columns. A problem arises when a bot is added or removed from the formation. When this happens, the bots have to rearrange themselves so that the rectangular formation is still roughly the same aspect ratio, and is as rectangular as possible. How to do this?

Some ideas:

• When a bot is added or removed, use the new total number of bots and a desired constant aspect ratio to calculate the new width and height of the formation that most closely fits that aspect ratio. Then somehow reshuffle the bots to fit the new dimensions.

• When a bot is removed, move the bot that was behind it into it's place, and continue until you reach the end of the formation. Then even out the back rank as much as possible by somehow shuffling the bots in the back rank.

• Another idea that's completely different is to mimic the way molecule structures stay together. Make every bot want to be surrounded by four other bots by attracting the four closest bots, and repelling the rest. Repel all bots (including the four) that are too close to ensure separation using inverse square law. You'd also need an additional force to shape of the entire structure. But, this sounds very computationally expensive.

UPDATE: So looking into sarahm's answer, I came up with a good general function that gives good dimensions.

First I solved the below simultaneous equation for width and height, and then rounded the answers.

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

This gives you the closest integer rectangle to that aspect ratio for your number of bots. The closest rectangle will half the time be a too large, and half the time be a too small (of course sometimes it will be just right but who cares about those). In the cases where the rectangle is a little too large, nothing needs to be done. The back rank will just end up being almost full, which is ideal. In the cases where the rectangle is a little too small, you got problems because that teeny tiny overflow will have to go to its own rank created a rank with only a few bots on it, which doesn't look pretty. There are also cases where the difference is large (larger than half the width), in which case add or subtract one rank to make the difference small. Then, when the rectangle is too small, add one column to make it just a little bit larger. After doing that it looks like the back rank will always have at least half as many bots as the other ranks.

UPDATE

Once you got the dimensions, compare them to the current dimensions. If the frontage of the new dimension is bigger, for every rank, pop bots from the rank below, and push them onto the current rank until that the number of bots on that rank is equal to the frontage. Continue that algorithm until you get to the back rank. Using this algorithm, bots will move to fit into the new dimension efficiently. After that, I simply push the new old onto the back rank. The algorithm is slightly different for the cases where the new frontage is smaller, but you can figure it out!

There's two more problems next. Deletion, and a more flexible addition method where new bots are not necessarily assigned to the back rank but whichever position is closest to them at the moment they are added.

Answer 1

Another technique is to mimic that used by Napoleonic battalions (and probably as far back as Greek phalanxes if not further).

Frontage is generally maintained constant, and as a man falls (in any rank except the back) he is replaced by the man directly behind him stepping forward. The back rank is shuffled by the NCO's to ensure a few men at the extreme of each flank, and otherwise to fill in evenly.

The frontage is only reduced when the back rank falls below pre-specified densities. Likewise, when the back rank is overfull the extras first start filling in an additional rank from both flanks in, and then the frontage is increased.

When changing frontage, I suggest having your bots file out from the back rank to both flanks when increasing frontage, and filing in from both flanks to the back rank when reducing frontage.

If I am correct in inferring that you are looking for a "military" impression, and having your bot organizations look like phalanxes, I believe this ordered re-arrangement is a better way to achieve that end.

Update:
One simple way to manage the back row is to divide the back-row units into three squads: one on each flank and one in the centre. Depending on whether the frontage is odd or even, and whether the number of back-row units is congruent to 0,1,or 2 mod 3, there are exactly six cases to manage.

As an enhancement to the above, consider spacing the last unit(s) of each back-row squad once the fill drops below a threshold, like this:
xxx.x....x.xxx.x....x.xxx
or this:
xx.x.x...x.xxx.x...x.x.xx
A bit more work, for an even better appearance.

Update #2:
An additional thought on formation depth. The impact of volley fire, combined with the modern bayonet, made depths of 3 or 4 adequate in the late 18th and early 19th century. (The British rarely fought in 2 ranks, contrary to popular belief, until late in a battle; for one, it made their lines too long to form square quickly.) Prior to that it was common to have greater depths, perhaps up to 8 or 10 for a Greek phalanx equipped with Sarissa. Choose a depth that creates the impression you desire.

Armies in real life try to maintain unit frontage as long as possible, at the expense of increased unit brittleness, as this makes laying out a battlefield simpler. Caesar at Pharsalus deliberately reduced his unit depth to increase frontage to match that of Pompey's forces. As the quote goes: "We win or die today; Pompey's men have other choices." (which Caesar had cleverly and carefully ensured, of course).

Answer 2

Assuming a unit is a linear datastructure (e.g. a list) of bots.

First, you have to add/remove the bot to/from the datastructure and determine the new number of bots in the unit.

Then, you have to determine the new amount of rows and columns using https://en.wikipedia.org/wiki/Integer_factorization.

Of course, this is not always possible due to prime numbers. When the new unit size is a prime number, you need to use the next larger unit size which isn't.

Then, just iterate over the datastructure, assigning bots in order to the rows and columns.

For placing the bots, just iterate over the datastructure, assigning each bot a position offset from the units position by an amount determined by the row and column the bot is in (or, set that point as a target for the bots movement).

To make a unit with the center at one corner, the position of a bot is given by

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

To make a unit with the center in the middle, the position of a bot is given by

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

where heading is a vector pointing in the direction the unit is facing and rightVector is a vector orthogonal to heading.

botSeparationDistance can be tweaked to make bots stand further apart or closer together.

If you're feeling fancy, you can offset the last row of bots by rightVector * 0.5 * (numberOfColumns - actualNumberOfBotsInRow) to center them on the formation.

Answer 3

I would store the possible positions in a graph with larger values being smaller rectangles.

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

Every time a robot is removed search though all the other robots and find the one in a node with the smallest value. Use A* or a BST algorithim to find it a path from the that smallest value to the vacant space. If there is no robot with a smaller value than the removed one do nothing.

You should also be able to control how the rectangle decays doing this. For example in the below graph when a robot leaves the bottom one from the side would come fill its 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]

Here the one at 3.8 is removed so the one at 2.5 comes and fills its place.

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

Another example. Here 2.8 is removed so the smallest node 2.2 comes an fills its place.

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

You probably want a ring of nodes with value 0 that you never populate around the outside for your pathfinding algorithim to find the hole with.

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

A good tutorial on A* can be found here.