Class UniversalReconfiguration

Implements the Universal Reconfiguration algorithm (https://doi.org/10.4230/LIPIcs.SAND.2026.11). Transforms any connected amoebot structure into a straight line in three phases:

1. TO_BOUNDED: Fuses adjacent rows until each row has at least ⌈√n⌉ particles (bounded phase).
2. TO_MONTONE: Sweep the bounded structure into an y-monotone structure.
3. TO_LINE: Uses the MonotoneToLine suboracle to reconfigure the monotone structure into a line.

Inheritance

object

ParticleAlgorithm

UniversalReconfiguration

Namespace: AS2.Algos.Reconfiguration

Assembly: .dll

Syntax

public class UniversalReconfiguration : ParticleAlgorithm

Constructors

UniversalReconfiguration(Particle)

Declaration

public UniversalReconfiguration(Particle p)

Parameters

Type	Name	Description
Particle	p

Fields

boundedRole

Declaration

private ParticleAttribute<int> boundedRole

Field Value

Type	Description
ParticleAttribute<int>

boundedRow

Declaration

private ParticleAttribute<bool> boundedRow

Field Value

Type	Description
ParticleAttribute<bool>

boundedUnevenRows

Declaration

private ParticleAttribute<int> boundedUnevenRows

Field Value

Type	Description
ParticleAttribute<int>

monotoneRow

Declaration

private ParticleAttribute<int> monotoneRow

Field Value

Type	Description
ParticleAttribute<int>

monotoneToLineSuboracle

Declaration

private MonotoneToLine monotoneToLineSuboracle

Field Value

Type	Description
MonotoneToLine

phase

Declaration

private ParticleAttribute<UniversalReconfiguration.Phase> phase

Field Value

Type	Description
ParticleAttribute<UniversalReconfiguration.Phase>

round

Declaration

private ParticleAttribute<int> round

Field Value

Type	Description
ParticleAttribute<int>

showAllConflictsInFirstPhase

Declaration

private ParticleAttribute<bool> showAllConflictsInFirstPhase

Field Value

Type	Description
ParticleAttribute<bool>

Properties

GenerationMethod

Declaration

public static string GenerationMethod { get; }

Property Value

Type	Description
string

Name

Declaration

public static string Name { get; }

Property Value

Type	Description
string

PinsPerEdge

The number of pins on each edge.

This number must be the same constant for all particles.

Declaration

public override int PinsPerEdge { get; }

Property Value

Type	Description
int

Overrides

ParticleAlgorithm.PinsPerEdge

Methods

ActivateBeep()

This is the second part of the main activation logic of the particle. It is called exactly once in each round, after the movements scheduled in ActivateMove() have been executed, and should contain the algorithm code that implements the look-compute-beep cycle.

Inside of this method, particles are allowed to change their pin configuration and send beeps and messages on the updated configuration.

Note that beeps and messages sent in the current round will be readable in both the ActivateMove() and ActivateBeep() calls in the next round.

Declaration

public override void ActivateBeep()

Overrides

ParticleAlgorithm.ActivateBeep()

ActivateMove()

This is one part of the main activation logic of the particle. It is called exactly once in each round and should contain the algorithm code that implements the look-compute-move cycle. After the movements are executed, ActivateBeep() is called within the same round.

Inside of this method, particles are allowed to release bonds, define which bonds should be marked, and schedule movements. Only the last movement operation scheduled in this method will be applied.

Declaration

public override void ActivateMove()

Overrides

ParticleAlgorithm.ActivateMove()

AdvanceEnum<T>(ParticleAttribute<T>)

Declaration

private static void AdvanceEnum<T>(ParticleAttribute<T> attr) where T : struct, Enum

Parameters

Type	Name	Description
ParticleAttribute<T>	attr

Type Parameters

Name	Description
T

BorderColors(ParticleSystem, Particle)

Draws colored borders on particle edges to visualize internal states. Delegates to the active suboracle's border coloring. Borders are only drawn when the MonotoneToLine suboracle is active (TO_LINE phase).

Declaration

[StatusInfo("BorderColors", "Color the borders", false)]
public static void BorderColors(ParticleSystem system, Particle selectedParticle)

Parameters

Type	Name	Description
ParticleSystem	system	The particle system.
Particle	selectedParticle	The currently selected particle (unused).

ColumnsCounts(UniversalReconfiguration[][])

Declaration

private static int[] ColumnsCounts(UniversalReconfiguration[][] grid)

Parameters

Type	Name	Description
UniversalReconfiguration[][]	grid

Returns

Type	Description
int[]

GetBorderColor(Direction, UniversalReconfiguration)

Returns the border color for a given direction. Used for visualisation. Delegates to the MonotoneToLine suboracle while it is active; otherwise returns transparent.

Declaration

public Color GetBorderColor(Direction dir, UniversalReconfiguration mv)

Parameters

Type	Name	Description
Direction	dir	The direction for which the color is requested.
UniversalReconfiguration	mv	The algorithm instance of the particle.

Returns

Type	Description
Color	The border color (green for line bonds), or transparent.

HandleBoundedPhase(ParticleSystem, UniversalReconfiguration)

Declaration

private static bool HandleBoundedPhase(ParticleSystem system, UniversalReconfiguration data)

Parameters

Type	Name	Description
ParticleSystem	system
UniversalReconfiguration	data

Returns

Type	Description
bool

HandleLinePhase(ParticleSystem, UniversalReconfiguration)

Declaration

private static bool HandleLinePhase(ParticleSystem system, UniversalReconfiguration data)

Parameters

Type	Name	Description
ParticleSystem	system
UniversalReconfiguration	data

Returns

Type	Description
bool

HandleMonotonePhase(ParticleSystem, UniversalReconfiguration)

Handles the TO_MONTONE phase: reconfigures the bounded structure into an y-monotone structure by moving a sweep line from top to bottom. For all rows above the sweep line we remove the x- and z-bonds to create columns ("teeth") starting from the sweep line. When the sweep line moves from one row to the next a column is moved to the southwest, by expanding the bottom amoebot, if there is a gap in the next row.

Declaration

private static bool HandleMonotonePhase(ParticleSystem system, UniversalReconfiguration data)

Parameters

Type	Name	Description
ParticleSystem	system	The particle system being simulated.
UniversalReconfiguration	data	one designated amoebot for storing data

Returns

Type	Description
bool	Returns false (automatic bonds are not used in this phase).

Init(Phase, bool)

Resets the algorithm. Start from a specific phase directly.

Declaration

public void Init(UniversalReconfiguration.Phase startPhase, bool showAllConflictsInFirstPhase = false)

Parameters

Type	Name	Description
UniversalReconfiguration.Phase	startPhase	The phase to start at.
bool	showAllConflictsInFirstPhase

IsFinished()

Checks whether this particle has finished its algorithm.

Override this method to return true when a particle is done executing the algorithm. Once all particles in the system are finished, the simulation will stop automatically. When a particle's state results in this method returning true, its activation methods should not change its state any more.

Declaration

public override bool IsFinished()

Returns

Type	Description
bool	true if and only if this particle has finished its algorithm.

Overrides

ParticleAlgorithm.IsFinished()

LightColor(Color, float)

Declaration

private static Color LightColor(Color c, float multiplier)

Parameters

Type	Name	Description
Color	c
float	multiplier

Returns

Type	Description
Color

NextPhase(UniversalReconfiguration)

Declaration

private static void NextPhase(UniversalReconfiguration data)

Parameters

Type	Name	Description
UniversalReconfiguration	data

ParticleGrid(ParticleSystem)

Declaration

private static UniversalReconfiguration[][] ParticleGrid(ParticleSystem system)

Parameters

Type	Name	Description
ParticleSystem	system

Returns

Type	Description
UniversalReconfiguration[][]

ReconfigurationOracle(ParticleSystem)

The central oracle method called by the simulator each round. It reads the current phase and dispatches to the appropriate phase handler. When a phase handler returns true, automatic bonds are applied to all particles. Returns true when the algorithm has reached the FINISHED state.

Declaration

public static bool ReconfigurationOracle(ParticleSystem system)

Parameters

Type	Name	Description
ParticleSystem	system	The particle system being simulated.

Returns

Type	Description
bool	true if the reconfiguration has completed, false otherwise.

RemoveAllBonds(ParticleAlgorithm, bool)

Declaration

private static void RemoveAllBonds(ParticleAlgorithm p, bool head)

Parameters

Type	Name	Description
ParticleAlgorithm	p
bool	head

RowCounts(UniversalReconfiguration[][])

Declaration

private static int[] RowCounts(UniversalReconfiguration[][] grid)

Parameters

Type	Name	Description
UniversalReconfiguration[][]	grid

Returns

Type	Description
int[]

RowReps(ParticleSystem, UniversalReconfiguration[][])

Declaration

private static UniversalReconfiguration[] RowReps(ParticleSystem system, UniversalReconfiguration[][] grid)

Parameters

Type	Name	Description
ParticleSystem	system
UniversalReconfiguration[][]	grid

Returns

Type	Description
UniversalReconfiguration[]

SelectCurrentRow(UniversalReconfiguration[][], int)

Helper function to select particles for a given row and identify their "teeth" (particles above them in the same column). Also colors particles for visualization: green for selected, red for teeth, black for all others.

Declaration

private static (List<UniversalReconfiguration>, List<UniversalReconfiguration>) SelectCurrentRow(UniversalReconfiguration[][] grid, int row)

Parameters

Type	Name	Description
UniversalReconfiguration[][]	grid	the grid of particles
int	row	the row to select particles from

Returns

Type	Description
(List<UniversalReconfiguration>, List<UniversalReconfiguration>)	Returns a tuple containing the selected particles and their corresponding teeth.

SetBonds(List<UniversalReconfiguration>)

Helper function to release bonds for a list of particles based on their state (contracted or expanded). Releases the x- and z-bonds (E, W, NNW, SSE)

Declaration

private static void SetBonds(List<UniversalReconfiguration> particles)

Parameters

Type	Name	Description
List<UniversalReconfiguration>	particles	List of particles for which to release bonds.

SetGridAnchor(UniversalReconfiguration[][], int)

Declaration

private static void SetGridAnchor(UniversalReconfiguration[][] grid, int row)

Parameters

Type	Name	Description
UniversalReconfiguration[][]	grid
int	row