Up-Down passes solver

[blakeelias]

The bot moves to the center of any grounded subspace of the current layer. The bot fills in the grounded subspace of the current layer. Bot moves to next higher layer. After completing top layer, bot moves down one layer. Bot fills in any new grounded subspace of the current layer that could not be added before. After completing bottom layer, bot moves up one layer. Continue making upward and downward passes until model is complete.

Pseudocode: http://collabedit.com/tv499

[kirelagin]

I’ll first try to implement a single bottom-up pass, which should work pretty well for non-umbrella models. Then, if I have time, I’ll add a single top-down pass, which will make it work for an umbrella, but not for more complex vertical spirals.

There is plenty of space for optimisation:

1. How to split a layer into zones for individual bots.
   • Good idea: find bounding rectangle, create a singleton list with it. Take the first rectangle from the list, split it into four quadrants, take the second, etc. Eliminate empty quadrants. Repeat. Stop when the number of rectangles equals the max number of bots.
   • What I’m going to implement: split the layer into MAX_BOTS stripes and assign each stripe to a bot. The trick is this makes bot allocation and recollection easy, they are guaranteed not to collide.
2. How to fill each individual zone.
   • See a naive approach proposed in the pseudo-code document. It is a good idea to take into account the distance from the current position to each cell.

Tricky subprograms:

• [] Fork a line of bots efficiently
• [] Unfork bots standing in a line

[kirelagin]

It’s done, I’ll provide a more detailed write up a little later. Long story short: a lot of things can be optimised; making a down-pass will be fantastic.