In 2014, Harvard's Kilobot project got 1,024 real robots to arrange themselves into shapes with no central control. I recreated the algorithm with 150 simulated bots.
Each bot gets a map of the shape and can measure how far away its neighbours are. From that, a few rules:
- Seeds: four bots sit where the shape starts and know their positions. Everyone else starts out not knowing where they are.
- A gradient: every bot takes one more than the smallest number it hears from the bots touching it, so each one knows roughly how many hops it is from the seeds.
- Working out where it is: from the distances to neighbours that already know their positions, a bot can calculate its own (trilateration).
- Edge-following: bots on the outside of the group travel round its edge, one at a time.
- Stopping: a bot stops when its next step would take it out of the shape, or when it touches a bot that has already joined and is no closer to the seeds than it is.
Wall, star and the letter K all assemble. It's slow, because only the bots on the edge move, but it works for any shape you can draw, which is exactly the property I want to keep as the bots get more complicated.