Amorphous Growth


Cell Model

Here, a "cell" refers to a computing element that represents a biological cell. In this model, cells are immobile and non-overlapping. They have no notion of global position or direction, but can store a small amount of local state and communicate with neighbors using local interactions. They have the following major capabilities:

i. Replication - Cells can replicate, or produce new cells that differ only in terms of local state. When a cell replicates, it places a daughter cell in a random location within a fixed radius of its own center.
ii. Messaging - Cells communicate by exuding and reacting to chemical-like signals, referred to as gradients. Messages originate from a sender-cell with a certain strength that decays as it travels through the medium; its relative concentration therefore encodes the distance between the sending- and receiving-cells. A cell's behavior upon executing its internal cell program is highly dependent on the gradients it receives.

In each "clock cycle", the environment simulator program directs a random subset of all existing cells to execute their cell programs in a random order. To impart greater realism to the system, cells are subject to random death.


Center & Reference Cells

Throughout the growing process, cells may designate themselves as either center cells or reference cells.

Center Cells - Center cells initiate the growth of circles. A center cell essentially exudes a gradient with a strength proportional to the radius of the desired circle, and begins to replicate. Replication halts when cells can no longer hear the message from the center.
Reference Cells - Cells, lacking knowledge of global position or direction, must accomplish the growth of overlapping circles in fairly precise relative locations. To achieve this, the cells define a coordinate system for the emerging shape at the circle level; that is, as a circle is being formed via replication, certain cells will designate themselves as "reference cells" which define the north, east, south, and west poles of the circle (see diagram). Once these cells are in place, any position in the circle (e.g. positions of new center and reference cells) can be specified as a ratio of distances from the reference points.


A circle grown from "cells". The non-yellow cells are reference points.


Competition

Special (center and reference) cells are selected by means of a competition mechanism, in which the victorious cell earns the respective designation. As mentioned earlier, the ideal position of a special cell can be given in terms of distances (gradients) from currently-existing reference points. Therefore, the cell whose incoming gradient messages match the ideal gradient values should become the new special point.

Competition is necessary because cells in the environment exist only at random locations; that is, a cell might not exist at the exact position specified by gradients for the location of a new special cell. Therefore, the cell whose gradient values most closely match the ideal gradient values should become the new special cell. Proximity to the ideal gradient values is indicated by high values of a certain goodness function computed by the cell.

One quality of this competition mechanism is that it nicely handles the event of random cell death; if a special cell were to die, competition would ensure that the next-closest living cell would replace it.

<--back
next--->