In Stage 1, the bots will space themselves out so that each bot is in a separate column. During this stage, each bot will move to the right (whenever it can on its turn) if it sees another bot immediately on its left or if it sees a bot anywhere below it in its column. This should only take about $N^2$ rounds at worst, but to be on the safe side let's allot assign a total of $10^N$ rounds for it, during most of which most bots will simply sit idle during their turn, just counting down until the stage is over. In Stage 1a, each bot will move to the right (whenever it can on its turn) until it's $N$ spaces from the next bot (if any) to its left. In Stage 1b, each bot will move Edit made 1/24/12 in response to the right if it sees a bot directly below it.comment of Pace Nielsen.)
|3||added 41 characters in body|
|2||added 3763 characters in body|
Added 1/21/12: Here's an alternative approach, inspired by the answers of John Ramsden and John Wiltshire-Gordon.
The process begins with a predetermined number of rounds in which the bots get themselves spread out, so that each one will have room to do a little "waggle dance" without bumping into anyone.
When the spreading-out stage is complete, each bot will make a mental list of the x and y coordinates (in binary) of all the bots whose current position it knows, using its current position as the origin. At first this list will consist only of those bots it can see (plus perhaps a few it may have noticed while the bots were spreading themselves out). The point is, these lists are going to grow as the bots observe each other's waggle dances, until each bot has a complete list of all the other bots' coordinates.
The waggle dance takes the following form:
"I know where a bot is..." -- one step up from its initial position.
"Its x coordinate (of its initial position, relative to my initial position) is..." -- another step up.
"1" -- a step to the right followed by a step back to the left
"0" -- a step to the left followed by a step back to the right
[It repeats these 0's and 1's until it's communicated the entire binary sequence. The reason each bit uses two steps is so that the bot doesn't wind up wandering away from its initial position.]
"Its y coordinate (relative to my position) is..." -- another step up, followed by the right/left's and left/right's of the y coordinates 1's and 0's.
"And that's where that bot is!" -- three steps down, back to the initial position.
While each bot does its own dances, it's watching the dances of the bots it can see, and every time it sees a completed dance, it converts the transmitted information to its own coordinate system. If that results in actual new information, it adds it to its mental list and schedules it for a dance of its own. The point is, eventually every bot will know the initial position of every other bot, even for the ones it can't see, because each bot is in the line of sight of a bot that's in the line of sight of a bot that's in the lines of sight, etc.
The waggle dance might also transmit information that identifies the "number" of each bot. I'm not sure that's necessary, but it probably wouldn't hurt.
Once a bot knows where all the other bots' initial positions are, it can compute the "center of mass" of all the bots, rounded to the nearest lattice point (with appropriate tie-breaking conventions). It can then transform all its knowledge to a coordinate system with the center of mass as the origin, determine based on its own number where it belongs in a square whose lower left hand corner, say, is at the origin, and start heading toward its destination. One potential glitch in this is that bots might get in each other's way -- you might, for example, have all the perimeter bots arrive first, blocking the interior bots from getting inside -- so it might make sense for bot $k$ to wait until bots 1 through $k-1$ have had time to get into position: Once a bot knows the initial positions of all the other bots, it can compute what those bots currently know, when they'll have complete information, and what they'll do with it. In particular, each bot can linger in its initial position until it knows all the other bots have complete information. If the bots notice that some of their brethren are occupying positions within the target square, they can run a predetermined algorithm to move them out of the way and then start taking turns assembling the square.
All this, of course, is highly inefficient. I'm just trying to outline approaches that will clearly and (I hope) correctly work.
Here's a three-stage Q2 procedure at the end of which all the bots are lined up in a single horizontal row, with each bot assigned a number according to its position in the row, say from left to right. From there it's straightforward to create a square: The first $n$ bots stay where they are, the next $n$ move up 1 and over $n$ (taking as many rounds as needed), the next $n$ up 2 and over $2n$, etc.
In Stage 1, the bots will space themselves out so that each bot is in a separate column. This should only take about $N^2$ rounds at worst, but to be on the safe side let's allot $10^N$ rounds for it, during most of which most bots will simply sit idle during their turn, just counting down until the stage is over. In Stage 1a, each bot will move to the right (whenever it can on its turn) until it's $N$ spaces from the next bot (if any) to its left. In Stage 1b, each bot will move to the right if it sees a bot directly below it.
Stage 2 will last exactly $N$ rounds. Each time it's bot b's turn during this stage, bot b will move one space down if it thinks it might be in the bottommost row, otherwise it will stay put. Note that during each round, at least one bot will move down and, more important, at least one bot will stay put. (If the bots don't all start on a single row, there is certainly at least one bot that can see there are bots below it; if they do all start on a single row, then the first bot to move down serves as a signal for at least one bot to its left or right that it's no longer on the bottom row.) As in Stage 1, most of the bots wind up doing nothing during Stage 2 but counting down until the stage is over. At the end of this stage, all the bots know there is exactly one bot in the bottommost row, and they know it will regard itself as bot #1. Or should we say the "alpha" bot?
Stage 3 will take as long as it takes, but the bots will all know when it's over. During this stage, each "beta" bot will do nothing until it's been "tickled from below" by a string of bots moving from left to right on the row just below it. It counts these bots as they pass by and then drops down to join them, knowing it's own number in the left-to-right string. Once it's in the string, it will basically follow the bot ahead of it. The string, of course, is headed by the alpha bot. The alpha bot begins this stage by taking a couple of steps down (so as not to tickle anyone until it's ready) and then doing an ever-expanding back-and-forth search until it's seen all the other bots, which Stage 1 had so kindly put in separate columns. Once the alpha bot knows where all the other bots are, it heads for the rightmost bot on the bottommost row above it and begins creating the string. Each time it reaches the leftmost bot in a row, it swings down and loops back around to the right, to get started on the next row, with the ever-growing string trailing behind. And so forth.
Note that during the initial phase of Stage 3, while the alpha bot is doing it's widening search, the beta bots will be able to spot it as well (when it passes directly beneath them, at the very least). So alternatively one could do the roundup by letting each beta bot begin dropping toward the alpha bot's row as soon as it sees it, stopping say two rows above the alpha bot's pacing. The alpha will know when everyone's in place. It can then come up from below and "teach" each beta bot its number, say by touching it and then moving $k$ spaces down before going to the next bot. Once each bot knows its number they can crowd together in a single string.