Algorithm Development: Implementation Walkthrough

On this page, we will demonstrate how to implement a simple algorithm from scratch. The focus of this demo is showing how conceptual ideas for an algorithm are translated into code for the simulation environment. If you have set up the simulator according to the Installation Guide, you can follow the walkthrough and experiment by changing the code along the way.

A Simple Demo Algorithm

Before we can start writing code, we need a clear idea of what the algorithm should do. This includes the behavior of the amoebots as well as the system setup: What is the initial configuration? Do the amoebots have a common chirality and/or compass orientation? Do they communicate using circuits and how many pins do they need? These questions should be answered before we start with the implementation.

!Demo Algorithm

For this example, we want the amoebots to communicate using circuits and to perform basic joint movements. To keep it simple, we will assume common chirality and compass alignment. The initial configuration of the structure will be a line of amoebots parallel to the West-East axis. The idea for the algorithm is the following: The structure starts with a single, arbitrary amoebot that is marked as the leader. In each round, the leader randomly decides whether a movement should be performed or not. If it decides to perform a movement, it will send a beep on the global circuit (which has to be established first). All amoebots receiving a beep will perform a movement: If they are contracted, they will expand in the East direction and if they are expanded, they will contract into their tail. If some of these terms seem unfamiliar, you can refer to the Model Reference pages for more information.

From this description of the algorithm, we can already deduce that we will need a custom initialization method to place the amoebots and determine a leader, and that a single pin will be sufficient for this simple communication. Due to the common compass orientation, all amoebots know where the East direction is, which simplifies the movements (although it is possible to lift that assumption and still achieve a very similar behavior!).

Creating the Algorithm File

To start implementing the algorithm, we first need to create a new algorithm file. Since this has already been explained on the Algorithm Creation page, we will only go through it briefly:

Algorithm Generator

We create a new algorithm class called DemoParticle, call the algorithm "Demo Algorithm" and give it only a single pin. The new file is created in the Assets/Code/Algorithms folder and contains a blank algorithm template. The algorithm has a default generation method and can already be run in the simulator, but since we have not added any behavioral code yet, the amoebots will stay idle.

There are two components that need to be implemented next: The amoebot behavior and the system initialization. Because we cannot test the behavior without a proper initialization, we will start with the custom initialization method and then implement the behavior.

Implementing the System Initialization

Because custom system initialization is optional, the relevant code is commented out in the algorithm template. As a result, our algorithm has a default initialization method which will place a number of amoebots randomly in such a way that they are still connected.

Default generation method

The method has parameters to control how many amoebots are placed and how likely it is for positions to be unoccupied, as well as settings for the chirality and compass orientation of the amoebots. Our new initialization method does not need parameters, but we will make the number of amoebots adjustable to demonstrate how this works.

Enabling Custom Initialization

To start with, we uncomment the DemoInitializer class at the bottom of the template file as well as the GenerationMethod property of the DemoParticle class and enter the name of the initializer class:

public class DemoParticle : ParticleAlgorithm
{
    ...
    // If the algorithm has a special generation method, specify its full name here
    public static new string GenerationMethod => typeof(DemoInitializer).FullName;
    ...
}

public class DemoInitializer : InitializationMethod
{
    public DemoInitializer(AS2.Sim.ParticleSystem system) : base(system) { }

    // This method implements the system generation
    // Its parameters will be shown in the UI and they must have default values
    public void Generate(/* Parameters with default values */)
    {
        // The parameters of the Init() method can be set as particle attributes here
    }
}

If we save the file and run the simulator now, the Initialization Panel will not display any parameters and no amoebots will be placed when our Demo Algorithm is selected: Init Mode after uncommenting the initialization method

Placing the Amoebots

Next, we will add an initialization parameter for the number of amoebots and actually place the amoebots. The parameter can simply be added as a parameter of the Generate method. It only needs to have a default value so that the system can already be initialized when the algorithm is selected. Thus, we simply add the parameter int numParticles = 10.

To place the amoebots, we could use the AddParticle method, which is available inside the initializer class and allows us to place single amoebots at arbitrary positions. However, we also have access to the PlaceParallelogram method, which simplifies our task: A line of \(n\) amoebots is a parallelogram of length \(n\) and height \(1\). This method requires the global start position, the lengthwise direction and the length of the parallelogram as parameters. As start position, we choose the origin, which has the coordinates \((0, 0)\) and is represented as a Vector2Int, Unity's data type for two-dimensional integer vectors. The zero vector even has a shorthand, accessed by Vector2Int.zero. The lengthwise direction of the parallelogram must be the direction in which we want to place our line, which is the East direction, represented by Direction.E. Finally, the length of the parallelogram should be the length of the line, i.e., the number of amoebots we just added as a parameter. All other parameters can be left at their default values because the default height is \(1\) and the chirality and compass orientation are aligned with the global chirality and compass by default.

The Generate method now looks as follows:

public void Generate(int numParticles = 10)
{
    PlaceParallelogram(Vector2Int.zero, Direction.E, numParticles);
}

With these changes, the Initialization Panel now displays the numParticles parameter and we can control how many amoebots are placed: Init Mode with new parameter

Electing a Leader

Currently, all amoebots placed by the generation method are identical. In order to turn one amoebot into the leader, we first need to add a state attribute telling an amoebot whether it is the leader, and then we have to initialize this attribute differently for one amoebot than for the others.

We will use a Boolean value to mark the leader. To do this, we add a new particle attribute of type bool, give it a display name and initialize it to false:

public class DemoParticle : ParticleAlgorithm
{
    ...
    public ParticleAttribute<bool> isLeader;
    ...
    public DemoParticle(Particle p) : base(p)
    {
        isLeader = CreateAttributeBool("Is Leader", false);

        SetMainColor(ColorData.Particle_Blue);
    }
    ...
}

Now, every amoebot has a bool attribute called isLeader with the initial value false. The attribute is public so that an amoebot can check whether its neighbor is the leader or not (this is not necessary for the algorithm though). It will also be displayed as "Is Leader" in the Particle Panel during the simulation, where its value can be edited and displayed for all amoebots simultaneously. To learn more about attributes, please refer to the Particle Attribute reference page. Note that we also set the color of the amoebot to ColorData.Particle_Blue. This is optional, but it makes the algorithm more interesting to look at and colors can be very useful for visualizing different states or roles of the amoebots. The ColorData class contains several standard colors for amoebots.

Next, we need to determine a leader and set its isLeader attribute to true. This is where the Init method of the particle class becomes relevant. It allows us to change attribute values based on parameters that can be passed to individual amoebots by the generation method or even manually through the UI.

First, we uncomment the Init method and add a bool parameter called leader with a default value of false. Inside the Init method, we set the isLeader attribute to true if the leader parameter is true:

public void Init(bool leader = false)
{
    if (leader)
    {
        isLeader.SetValue(true);
        SetMainColor(ColorData.Particle_Green);
    }
}

We also change the leader amoebot's color so that it can be distinguished from the other amoebots visually.

By adding the leader parameter to the Init method, we have implicitly created an attribute for the InitializationParticles placed by the generation method. In the Initialization Mode, all amoebots are placed as InitializationParticles, which can be moved, deleted and edited freely. When the "Start" button is pressed, the InitializationParticles are turned into proper amoebots and their attributes are passed as parameters to the Init method of those amoebots. Thus, we can now manually determine a leader by selecting one of the amoebots in the Init Mode, setting its leader attribute to true and pressing "Start": Selecting a leader manually Selected leader during simulation

However, we want this to be done automatically by the initialization method. For this, we first need to find a random amoebot from the line we placed in the Generate method of the initialization class. The GetParticles method returns an array containing all InitializationParticles that have been placed so far. We can use the length of this array and Unity's Random.Range(int min, int maxExclusive) method to get a random amoebot. Having selected an amoebot, we can set its leader attribute by calling its SetAttribute method:

public void Generate(int numParticles = 10)
{
    PlaceParallelogram(Vector2Int.zero, Direction.E, numParticles);

    InitializationParticle[] particles = GetParticles();
    if (particles.Length > 0)
    {
        int randIdx = Random.Range(0, particles.Length);
        particles[randIdx].SetAttribute("leader", true);
    }
}

The SetAttribute method gets the name of the Init method's parameter and its value. Note that it is not the name of the final amoebot's attribute (isLeader)!

If we save the file and run the simulator now, the generation method will automatically determine a random leader each time we generate the structure by clicking "Generate". The selected leader amoebot knows that it is the leader because its isLeader attribute is set to true.

Implementing the Algorithm Behavior

Now that the structure is initialized correctly, we can implement the amoebot activation methods to achieve the desired behavior. This is what the algorithm should do:

  • The leader should decide randomly whether to perform a movement
  • If a movement shall be performed, the leader will send a beep on the global circuit (which has to be established first)
  • Every amoebot will perform a movement if it receives a beep
    • Expansion to the East direction when contracted, contraction into the tail if expanded

We will extend the algorithm incrementally until this behavior is achieved.

Deciding Randomly When to Move

We want the leader amoebot to decide randomly whether or not the structure should move in each simulation round. For now, we will simulate a coin toss for the random decision. Unity's Random.Range(float min, float max) method returns a uniformly random value between min and max, which means that the probability of a value in the range \([0,1]\) being less than \(0.5\) will be \(0.5\). There are other ways to simulate a coin toss, but this approach allows us to change the movement probability later. Because the leader should send a beep when it decides to move, it makes sense to put this code into the beep activation method:

public override void ActivateBeep()
{
    if (isLeader)  // Only the leader should run this code
    {
        if (Random.Range(0.0f, 1.0f) < 0.5f)
        {
            // Decided to move => Send a beep on the global circuit
        }
    }
}

Setting Up the Communication

The beep has to be received by all amoebots in the structure. Before sending a beep, we need to create a circuit that connects the amoebots. Due to the line shape of this structure, we could set up a circuit that connects all amoebots along the line by putting the two pins in East and West direction into one partition set. However, it is easier to simply put all pins into one partition set, because the other pins are not used for anything else anyway. The PinConfiguration class has a SetToGlobal(int ps) method that will put all pins into the partition set with index ps. Thus, setting up the circuit is as simple as calling this method in every beep activation:

public override void ActivateBeep()
{
    PinConfiguration pc = GetNextPinConfiguration(); // Get the PinConfiguration instance defining the connections for the next round
    pc.SetToGlobal(0);                               // Collect all pins in partition set 0

    ...
}

We use the partition set with ID \(0\) to hold the pins. Note that it may not be necessary to set up a new pin configuration in each round: If no movement is performed in a round, the amoebots keep their pin configurations and can reuse them in the next round. However, there is no disadvantage in setting the pin configuration explicitly in each round. You can read more about the pin configuration system on the Pin Configuration reference page.

Now, the leader can use its partition set \(0\) to send a beep if it decides to move:

public override void ActivateBeep()
{
    PinConfiguration pc = GetNextPinConfiguration(); // Get the PinConfiguration instance for next round
    pc.SetToGlobal(0);                               // Collect all pins in partition set 0

    if (isLeader)  // Only the leader should run this code
    {
        if (Random.Range(0.0f, 1.0f) < 0.5f)
        {
            // Decided to move => Send a beep on the global circuit
            SendBeepOnPartitionSet(0);
        }
    }
}

If we run the algorithm now, the amoebots will set up the global circuit and the leader will irregularly send a beep:

The established global circuit Irregular beeps

The visual representation of the pin configurations clearly shows that all pins of each amoebot are contained in a single partition set and that all partition sets are connected in a global circuit. When the leader sends a beep, its partition set is highlighted with a white dot and all connection lines of the circuit are flashing white.

Performing the Movements

The algorithm is almost finished now, we only need to get the amoebots moving when they receive a beep. As explained in the Round Simulation reference and according to the circuit model, beeps and messages sent in the beep phase can only be received in the following movement phase (the only exception is that they can still be received in the next beep phase if the amoebot has not expanded or contracted in the move phase). Thus, we have to check for received beeps in the movement activation method:

public override void ActivateMove()
{
    if (ReceivedBeepOnPartitionSet(0))
    {
        // Received a beep => Perform movement
    }
}

We can use partition set \(0\) because we have set up this partition set to contain the pins in the previous beep phase. In the first simulation round (recall that the simulation starts with a move phase), partition set \(0\) contains only a single pin, but because no beeps have been sent at that point, no beeps can be received. Note that we do not have to distinguish between the leader and the other amoebots because the leader will receive the beep on partition set \(0\) just like any other amoebot on the circuit.

We want contracted amoebots to expand East and expanded amoebots to contract into their tail. The expansion status of an amoebot can be checked with the IsExpanded and IsContracted methods. Simple movements are performed using the Expand(Direction d) and ContractTail or ContractHead methods. Using these methods to perform our desired movements is straightforward:

public override void ActivateMove()
{
    if (ReceivedBeepOnPartitionSet(0))
    {
        // Received a beep => Perform movement
        if (IsContracted())  // Expand East if contracted
            Expand(Direction.E);
        else                 // Contract into tail if expanded
            ContractTail();
    }
}

We do not have to care about bonds because there are no bonds that could hinder our movements. In fact, releasing any of the existing bonds would break the connectivity of the structure and lead to an error. Please refer to the Bonds and Joint Movements reference for a more detailed explanation of bonds.

With the movements in place, our demo algorithm is complete! Here is the final code:

using AS2.Sim;
using UnityEngine;

namespace AS2.Algos.Demo
{

    public class DemoParticle : ParticleAlgorithm
    {
        // This is the display name of the algorithm (must be unique)
        public static new string Name => "Demo Algorithm";

        // Specify the number of pins (may be 0)
        public override int PinsPerEdge => 1;

        // If the algorithm has a special generation method, specify its full name here
        public static new string GenerationMethod => typeof(DemoInitializer).FullName;

        // Declare attributes here
        public ParticleAttribute<bool> isLeader;

        public DemoParticle(Particle p) : base(p)
        {
            isLeader = CreateAttributeBool("Is Leader", false);

            SetMainColor(ColorData.Particle_Blue);
        }

        // Implement this if the particles require special initialization
        // The parameters will be converted to particle attributes for initialization
        public void Init(bool leader = false)
        {
            if (leader)
            {
                isLeader.SetValue(true);
                SetMainColor(ColorData.Particle_Green);
            }
        }

        // The movement activation method
        public override void ActivateMove()
        {
            if (ReceivedBeepOnPartitionSet(0))
            {
                // Received a beep => Perform movement
                if (IsContracted())  // Expand East if contracted
                    Expand(Direction.E);
                else                 // Contract into tail if expanded
                    ContractTail();
            }
        }

        // The beep activation method
        public override void ActivateBeep()
        {
            PinConfiguration pc = GetNextPinConfiguration(); // Get the PinConfiguration instance for next round
            pc.SetToGlobal(0);                               // Collect all pins in partition set 0

            if (isLeader)  // Only the leader should run this code
            {
                if (Random.Range(0.0f, 1.0f) < 0.5f)
                {
                    // Decided to move => Send a beep on the global circuit
                    SendBeepOnPartitionSet(0);
                }
            }
        }
    }

    // Use this to implement a generation method for this algorithm
    // Its class name must be specified as the algorithm's GenerationMethod
    public class DemoInitializer : InitializationMethod
    {
        public DemoInitializer(AS2.Sim.ParticleSystem system) : base(system) { }

        // This method implements the system generation
        // Its parameters will be shown in the UI and they must have default values
        public void Generate(int numParticles = 10)
        {
            PlaceParallelogram(Vector2Int.zero, Direction.E, numParticles);

            InitializationParticle[] particles = GetParticles();
            if (particles.Length > 0)
            {
                int randIdx = Random.Range(0, particles.Length);
                particles[randIdx].SetAttribute("leader", true);
            }
        }
    }

} // namespace AS2.Algos.Demo

Next Steps

Congratulations! If you completed this walkthrough successfully, you are now able to start developing your own amoebot algorithms. You can use the API documentation and the reference pages to learn more about AmoebotSim 2.0 and try out your own ideas. However, there are several features of the simulation environment that have not been discussed in this guide and that might be useful, especially for more complex algorithms. The Advanced Features guide demonstrates some of these features by extending the demo algorithm we developed in this walkthrough.