AmoebotSim 2.0 Web Demo

Basic Usage

The simulator starts in Initialization Mode. In the "System Initialization" panel on the right side, you can select an algorithm from the "Algorithm" dropdown menu. Under "Parameters", you can edit the algorithm-specific generation parameters. Pressing the "Generate" button will create a new amoebot structure using the current parameters.
Press the "Start" button to run the algorithm and switch to Simulation Mode. Then, use the bottom toolbar to play and pause the simulation, adjust the simulation speed, and scrub through the already simulated rounds while paused. Press the button in the top left corner to return to Initialization Mode.

You can right-click and drag in the central area to pan the view, and use the scroll wheel (or two fingers on the touch pad) to zoom in and out. If you lose the amoebot structure from view, press the camera button at the top right. All buttons in the UI will display tooltips when hovering over them.
Clicking on an amoebot will open a panel on the left side in which you can inspect the amoebot's initialization parameters (Init Mode) or state variables (Simulation Mode) and run additional info methods if the algorithm provides them. The middle buttons in the top toolbar provide additional tools (left side) and visualization options (right side).

Further Information

To learn more about using the simulator, please refer to the User Guide in the main documentation. There are two pages specifically explaining the usage of Initialization Mode and Simulation Mode in detail.

Note that the web demo does not support all features of the simulation environment. To develop your own algorithms, you will need to setup the project locally and run it in the Unity Editor. You can find detailed installation instructions in the documentation.

A boundary is a set of amoebots that are adjacent to the same empty region, i.e., the same connected set of unoccupied nodes in the grid graph. If the amoebot structure is finite, there is always one infinite outer empty region. There can also be inner empty regions in the form of (finite) holes in the structure. Boundaries are called inner or outer boundaries depending on what kind of empty region they are adjacent to.

An amoebot can belong to up to 3 distinct boundaries. Initially, it does not know the types of the boundaries it belongs to. The boundary test algorithm allows all amoebots to determine the types of their boundaries. We only give a high-level description here. Please refer to this paper for details:

The structural power of reconfigurable circuits in the amoebot model
A. Padalkin, C. Scheideler, D. Warner, Natural Computing (2024).

Using only their local views, the amoebots are able to establish circuits on all boundaries by connecting the pins closest to the empty regions. In the first phase, they use these circuits to randomly elect a leader on each boundary (see leader election algorithm below). They synchronize the election procedures on all boundaries using a global circuit (spanning the whole structure).

In the second phase, each boundary computes the sum of the turn angles occurring when the boundary is traversed such that the adjacent empty region is on the right-hand side. For the unique outer boundary, the sum of these angles will be 360°, while for all inner boundaries, the sum will be -360°. Since the amoebots only have constant memory, they do not compute the sums directly. Instead, they use the number of 60° turns (only turns by multiples of 60° are possible in the triangular grid) and compute the sum modulo 5. The result for the outer boundary will be 1, while the result for the inner boundaries will be 4. To compute these sums, the amoebots run a parallel addition scheme similar to an adder tree on each boundary using circuits. In each step, half of the partial sums are added to the other half. In the simulator, the amoebots holding partial sums are highlighted in yellow. Note that an amoebot that belongs to multiple boundaries may hold multiple partial sums at the same time.

When the algorithm has terminated, the amoebot colors indicate the type of their boundaries:

• Black amoebots belong to no boundary
• Green amoebots belong to the outer boundary (and maybe some inner boundary too)
• Orange amoebots belong to one or more inner boundaries but not the outer boundary
• The green/red (more saturated) amoebots are the leader of at least one (inner/outer) boundary.

Boundary Test Subroutine

This is an alternative implementation of the boundary test algorithm as a subroutine. Subroutines are algorithms that can be used by other algorithms, allowing code to be more easily reusable. This version also includes some small optimizations to reduce the number of required rounds (not asymptotically however).

In general, the amoebot model allows amoebots to have different senses of direction and rotation. Relative to the global coordinate system, each amoebot has a compass identifying the global direction it believes to be the East direction. The amoebot does not know the global coordinates. In addition, the chirality of an amoebot determines which rotation direction it perceives as positive (i.e., counter-clockwise). Some algorithms rely on a common compass and/or chirality to function. The chirality & compass alignment algorithm establishes these from an arbitrary initial condition within $\mathrm{O}(\log n)$ rounds with high probability (i.e., probability at least $1-1/n^c$, where $n$ is the number of amoebots and the constant $c$ can be made arbitrarily large). For details, please refer to the following paper:

Coordinating Amoebots via Reconfigurable Circuits
M. Feldmann, A. Padalkin, C. Scheideler, S. Dolev, J. Comput. Biol. 29 (2022), 317-343.

The basic idea is the following: Consider two neighboring amoebots connected by two pins. If each amoebot sends a signal on the pin it believes to be the right-hand pin to its neighbor, both pins will send signals if and only if the amoebots have the same chirality. Similarly, if each amoebot transmits the compass direction in which it perceives its neighbor (this only requires common chirality), both amoebots learn whether they have the same compass orientation and if not, what the offset between the compasses is.

Using these checks, the amoebots can establish regions of the same chirality and later regions of the same compass orientation. The regions are indicated by the amoebot colors in the simulator. Then, the amoebots run a "competition", where random coin tosses are used to determine which of two adjacent regions adapts the chirality or compass of the other region. To generate a coin toss for a region, a leader election (see below) is run simultaneously within each region. The elected leaders (or the small number of leader candidates), indicated by brighter colors, determine the coin toss for their region.

As long as there are two regions with different chirality or compass, some amoebots beep on a global circuit to keep the competition running until all amoebots are in the same region. Note that the chirality and compass direction the amoebots have agreed upon may not match the global counter-clockwise and East direction.

This is a test and demonstration of different kinds of joint movements. It consists of multiple sub-algorithms called modes. Each mode performs one kind of movement. You can select which sub-algorithm is executed by changing the mode parameter to a value between 0 and 17 (especially modes 0, 1, and 15-17 are interesting to watch!) and pressing the Generate button.
Some of the sub-algorithms perform movements in random directions. You can pause the algorithm, move back to the first round using the slider, delete the simulation history (the button left of the slider), and then run the algorithm again to get different behavior.
Hint: Hide the circuit overlay by pressing the button Toggle circuit visibility in the middle of the top toolbar.

Amoebots move by expansions and contractions. When a contracted amoebot (occupies only one node of the grid graph) expands, it moves a part of itself called its Head onto an unoccupied adjacent node. The node it occupied before the movement is still occupied by the amoebot's Tail. An expanded amoebot may contract onto either its Head or its Tail, after which it occupies only one node again. By repeated expansions and contractions, amoebots can move through the grid, as long as the structure remains connected.

Joint movements are based on so-called bonds. Bonds are connections between neighboring amoebots, indicated by the thick red edges in the simulator. When an amoebot expands, it can select some of its incident bonds to move together with the amoebot's Head, keeping their orientation. This moves the (Head or Tail of the) neighboring amoebot connected to the bond in the direction in which the amoebot expands, "pushing" the neighbor along with the expansion. Similarly, a contracting amoebot can select some of the bonds incident to its contracting part to move in the same direction as the contraction, pulling the adjacent amoebots with them. Any amoebot incident to a bond can also release that bond so that it does not connect any movements. All possible bonds are restored at the beginning of the next round. Bonds also define the connectivity of the structure. If the subgraph defined by the amoebots and the bonds is not connected, an error will occur.

If the bonds are not managed carefully, conflicts can occur. For example, if there is a cycle in the graph defined by the bonds, where the sum of the movement offsets caused by expansions and contractions is not zero, the resulting movement is not well-defined. Additionally, collisions can occur when two amoebots end up on the same grid node or two bonds pass through each other during their (linear) motion. Such conflicts and collisions must be avoided by the algorithm. In the simulator, conflicts and collisions on target nodes cause exceptions and prevent the simulation from progressing further. Collisions that only occur during movements but lead to valid configurations are detected by a collision checker.

To obtain a unique position for each amoebot after a joint movement, one amoebot of the structure is marked as the anchor in the simulator. The movements of the anchor amoebot are always tied to its global grid position, as if the amoebot was the only one on the grid. All joint movements are calculated relative to the anchor. When selecting an amoebot, the left panel shows a button next to the "Particle" text. Pressing this button turns the selected amoebot into the anchor. You can try changing the anchor during the simulation to see its effect. For example, in mode 15, try turning an amoebot from the left half or the right half into the anchor, then turn one of the green amoebots into the anchor.
To learn more about joint movements, please refer to the following paper:

Reconfiguration and Locomotion with Joint Movements in the Amoebot Model
A. Padalkin, M. Kumar, C. Scheideler, in: A. Casteigts, F. Kuhn (Eds.), 3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, June 5-7, Patras, Greece, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 18:1-18:20.

The leader election problem is a standard problem for distributed systems, where the agents are tasked with agreeing on a single agent to be their "leader". Due to symmetry, this problem can be impossible to solve deterministically: Imagine a structure with just two amoebots that have opposite compass directions, then each amoebot has the exact same local information and no tie break is possible. This algorithm uses randomization and circuits to solve the leader election problem efficiently with high probability. It is described in this paper:

Coordinating Amoebots via Reconfigurable Circuits
M. Feldmann, A. Padalkin, C. Scheideler, S. Dolev, J. Comput. Biol. 29 (2022), 317-343.

The amoebots first establish a global circuit (each amoebot connects all of its pins with each other, so the circuit spans the whole structure) which they will use for the entire procedure. Then, they run a "competition" in which they randomly eliminate leader candidates. Initially, all amoebots are candidates, indicated by the green color in the simulator. In each iteration of the competition, all candidates perform a coin toss. The candidates with coin toss result Heads send a beep on the global circuit in the first round of the iteration. In the second round, the candidates with result Tails send a beep. Thereby, all amoebots know which results have occurred at least once. If both Heads and Tails have occurred, all candidates with result Tails withdraw their candidacy (retired candidates are colored black in the simulator). It is safe to do so because at least one candidate with result Heads will remain active. If only one result occurred, the competition ends.

After this competition, there is a chance that more than one candidate is still active. To reduce the probability of getting more than one leader, the amoebots continue the competition for $\mathrm{\Theta }(\log n)$ additional rounds. To reach this number of rounds with high probability, they run a separate competition that starts with all amoebots as candidates again (indicated by the blue color). Since the number of rounds until only one coin toss result occurs is $\mathrm{\Theta }(\log n)$ with high probability, this secondary competition runs for the desired number of rounds. It is repeated a constant number of times to boost the success probability further. When the last of these repetitions is finished, the remaining candidate declares itself as the leader (shown by the purple color).

In the line formation algorithm, one amoebot is initially marked as the leader (colored green in the simulator) and chooses a direction. The other amoebots then move to construct a line that extends from the leader into the chosen direction. This algorithm does not use joint movements and is not improved by circuits, but it showcases the movement animations and some UI features of the simulator. It was presented in the following paper:

Leader Election and Shape Formation with Self-organizing Programmable Matter
Z. Derakhshandeh, R. Gmyr, T. F. Strothmann, R. A. Bazzi, A. W. Richa, C. Scheideler, in: DNA Computing and Molecular Programming - 21st International Conference, DNA 21, Boston and Cambridge, MA, USA, August 17-21, 2015. Proceedings, 2015, pp. 117-132.

The amoebots can be categorized into four classes:

• Amoebots that have already reached their position on the line (yellow),
• amoebots that are adjacent to the line and therefore know where to move (red),
• amoebots that are not adjacent to the line but already know where to move (blue),
• and amoebots that do not know where to move yet (black).

Since no amoebot ever moves along the line towards the leader, the completed part of the line is recognized by amoebots without any neighbors outside of the line. These amoebots construct a circuit that connects the completed part of the line. When the last amoebot realizes that it is part of the completed line, it beeps on the circuit to inform all amoebots about the completion.

In some situations, multiple amoebots may want to move to the same location. For example, red amoebots on two sides of the line may want to expand onto the next open line position, or two amoebots with the same parent may want to follow the parent's movement. To prevent collisions in such cases, the current end of the line or the parent amoebot, respectively, sends a beep towards the neighbor that is allowed to move first.

In the single-source shortest path problem, a single amoebot is marked as a source (in red) and some other amoebots are marked as destinations (in blue). The amoebots must compute shortest paths connecting the source to all destinations. To accomplish this, they use axis-aligned portals to build spanning trees and run circuits along Euler tours of these trees. This algorithm only works for amoebot structures without holes. It was presented in the following paper, which also covers the shortest path forest problem for multiple sources:

Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter
A. Padalkin, C. Scheideler, in: Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, ACM, 2024.

An x-portal is a maximal connected set of amoebots on the same line parallel to the x- (horizontal) axis. Portals for the y- and z-axes are defined similarly. The amoebots can easily establish these portals and identify the "leftmost" edge between two adjacent portals as the unique edge connecting the portals. Because the amoebot structure has no holes, the resulting graph with portals as nodes is a tree. The portal tree can be visualized on top of the amoebot structure in the simulator by clicking the Show Portal Graph button in the left side panel after selecting an amoebot (check the checkbox next to the button to update the portals automatically). The red portal (orange amoebots) contains the source, blue portals (light blue amoebots) contain destinations, and a purple portal contains both the source and destinations. If we mark the portal containing the source amoebot as the root, every portal has a unique parent portal, and every amoebot in turn has at most two neighbors belonging to the parent of its own portal.

It can be shown that for any amoebot $u$, a neighbor $v$ lies on a shortest path from $u$ to the source if and only if $v$ belongs to the parent portal of $u$ for the portal trees of two axes. Therefore, the algorithm constructs the portal trees for all three axes, allowing each amoebot to identify its parent portals. This is done by constructing circuits along an in-order traversal of the portal tree (an Euler tour) and counting the number of destinations encountered along this traversal. The traversal visits every edge in the portal tree twice, once moving away from the root and once moving back toward the root. If the subtree of an edge contains a destination, the number of destinations counted before the first visit is lower than the number of destinations encountered before the second visit. By comparing these numbers, the amoebots determine the directions of all edges in the portal tree.

Each amoebot counts how many times each neighbor occurred as a portal parent. If any neighbor occurred twice, the amoebot chooses such a neighbor as its parent in the shortest path tree. These edges can be visualized by pressing the Show SP Tree button in the left panel. For some amoebots, such a neighbor does not exist. These amoebots can immediately prune themselves from the tree. After this step, there can still be subtrees that do not contain any destinations and some parts of the amoebot structure may not be connected to the shortest path tree by parent edges. To prune these superfluous amoebots, a traversal of the current shortest path tree is used to construct circuits and count occurrences of destinations like before. Disconnected parts will not receive any beeps at all and subtrees without destinations will have equal destination counts on all edges. After pruning these amoebots, only shortest paths from the destinations to the source remain. The amoebots additionally hide bonds that are not edges of the shortest path tree.

This algorithm demonstrates joint movements by rhombical/hexagonal meta-modules, as introduced in the following paper:

Reconfiguration and Locomotion with Joint Movements in the Amoebot Model
A. Padalkin, M. Kumar, C. Scheideler, in: A. Casteigts, F. Kuhn (Eds.), 3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, June 5-7, Patras, Greece, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 18:1-18:20.

A rhombical meta-module of size $k$ is a structure of $k\times 2k$ expanded amoebots forming a rhombus of side length $2k-1$. Such a meta-module can perform a joint contraction that reduces one side length of the rhombus to $k-1$. Three rhombical meta-modules of size $k$ can be arranged to form a hexagon with alternating side lengths $2k-1$ and $2k$. There are two possible arrangements to obtain this structure. In such an arrangement, the individual rhombical meta-modules can still perform their contractions while staying connected. If two hexagonal meta-modules with different internal arrangements are placed such that they line up on one side, all rhombical meta-modules can contract simultaneously, allowing the hexagonal meta-modules to "merge" partially and occupy a smaller area. Such a movement can be reversed by expanding the rhombical meta-modules again.

The Smart Material algorithm showcases such movements. The scale parameter specifies $k$ and the parameters rows and cols specify how many hexagonal meta-modules should be placed. If the hexagonShape checkbox is checked, a hexagonal arrangement is generated instead, with the number of "layers" being controlled by the rows parameter.

In the simulation, rhombical meta-modules are colored to show their different orientations and arrangements in hexagonal meta-modules. The algorithm simply makes the meta-modules contract and expand. If the simulation is not smooth for large numbers of amoebots, try disabling the collision check by pressing the rightmost button in the middle group of the top toolbar. You can change the animation speed with the slider on the left of the play button to see the movements more clearly.