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

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.

-
What is the maximum number of bots in a unit? If it's relatively small, you could hardcode how many rows and columns a formation has for a certain number of bots. – sarahm Jul 23 '13 at 16:22
Can you maybe post an image of formations that are valid vs invalid? I'm having a little trouble understanding what you're after. Are incomplete rows/columns allowed? – MichaelHouse 'Byte56' Jul 23 '13 at 16:59
You do realise that this won't work for prime numbers? e.g. with 7 bots, you'd have to make a 3x2 unit with a single bot in the back. – sarahm Jul 23 '13 at 17:02
Well this is embarrassing. I completely forgot about prime numbers. Then maybe the next best thing would be to only allow rows and columns that are ALMOST filled. One Bot on a row doesn't look right, but one less Bot on a row wouldn't look bad. – Tiby312 Jul 23 '13 at 17:05
Prime numbers aren't the only ones that will cause trouble - choosing formation size by factoring could give you unreasonably long and skinny formations. E.g. if you have 14 bots, the only perfect rectangular formation is 7x2, while it might look better to have a 3x4 formation with an extra row of 2 bots. – Nathan Reed Jul 23 '13 at 18:39

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

-
This sounds like a much more elegant solution. There is no need to fuss about prime numbers or aspect ratios at all, and yet it still avoids any row that has an unusually low number of bots on it, And the only condition that needs to be checked is how full the backrank is! – Tiby312 Jul 24 '13 at 13:50
But hold on. Say the back rank only has 3 bots in it and are in columns 1, 2, and 3. And I remove someone from the 5th column someone near the front. I'd end up with a free spot on the second to last row in the 5th column without no bot behind it to take it's place. Who should fill this spot? – Tiby312 Jul 24 '13 at 13:55
Presumably, the closest bot in the back rank (i.e. the one in column 3) should run to fill it. Or you could save a bit of time by having the bots in columns 3 and 4 of the second-to-last rank each step one column up, moving the gap to column 3, and then have the bot at column 3 step forward to fill it. (IMO, the most "natural" looking strategy would probably be some heuristic combination of the two, possibly with some randomness thrown in.) – Ilmari Karonen Jul 24 '13 at 14:15
If the back rank has too few members (say less than 50% of the other ranks), and you increase the frontage, is this guaranteed to fix the problem, or is it possible that the back rank would still have too few members after increasing the frontage requiring it to be repeated or something? – Tiby312 Jul 25 '13 at 16:29
@Tiby312: I believe you are over-thinking it. Give it a try, knowing you can always tune it later – Pieter Geerkens Jul 25 '13 at 22:04

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.

-
This is very close to what I'm looking for! My only reservation is that when assigning new positions, a Bot on the very right of one row, might be assigned to the very left of the next row in the new rectangle, resulting in the Bot having the travel a long distance and in the processes getting in the way of other bots trying to reach their own new assigned position. I worry that when a bot is added or removed, the entire formation would be a jumble as Bots hustle and bustle to get to their far away destination. – Tiby312 Jul 23 '13 at 17:40
You could always calculate the new positions, then move the closest bot to that position instead of doing a linear iteration. – sarahm Jul 23 '13 at 17:43
How to do this without ending up with a n squared computation? I'd have to find the closest position in the 2d array from their current position in the 2d array, for each Bot, if I'm understanding this correctly. – Tiby312 Jul 23 '13 at 17:51
In each iteration, one unit would be assigned (and thus doesn't need to be considered on further iterations), thus the runtime would be O(n!). Which, still, isn't very good. Then again, building a [optimisation structure of choice] and doing n range queries isn't fast either. Only thing I can think of right now is moving the last bots in a row to the back or filling the last places in a row with bots from the back. – sarahm Jul 23 '13 at 18:03
How about this. Say the new formation has smaller row size. Then on each row, you've got an extra bot. You assign that bot one down, and one to the left. Then on the next row down, you've got two Bots without a place. You assign those two one down, and one to the left. Then you got 3 bots without a place. Continue untill you've got an extra row at the bottom. I'm just spit balling here. I didn't think it all the way through, but it sounds like it will work and its fast. – Tiby312 Jul 23 '13 at 18:43

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.

-
This a sweet idea, but if I'm understanding this correctly, you are allowing for formations that arn't perfect rectangles. The rows and columns on the borders may not be full. I was thinking that I could make it so that it's always got a rectangular border, and instead change the aspect ratio a bit to meet this requirement by changing the number of rows and columns. I can already calculate the new width and height that would accomplish this, but then theres some complicated way to re-assign the Bots to the nearest Spot..I think. – Tiby312 Jul 23 '13 at 16:56
@Tiby312 How are you planning to make a perfect rectangle with say... 7 robots? – ClassicThunder Jul 23 '13 at 17:07
NEVERMIND I forgot about prime numbers. Sorry. But I'm still thinking that adjusting the number of rows and columns could avoid a row or column having an unusually low number of Bots on it. – Tiby312 Jul 23 '13 at 17:07
@Tiby312 I think you're better off aiming for a consistent aspect ratio (i.e. always 4:3 or 8:5) than trying to always make it a perfect rectangle. – corsiKa Jul 23 '13 at 22:06