Wolfram

L’insieme cellulare di Wolfram è servito: un programma educativo alla scoperta degli automi cellulari unidimensionali

Dopo i recenti articoli pubblicati Rendering grafico in GDI e WPF e Calcolo parallelo applicato agli automi cellulari ecco un video dimostrativo sul mondo cellulare di Wolfram.

Scritto in C# WPF (.NET Framework 4) e compilato con Visual Studio 2010, il codice sorgente e l’eseguibile sono scaricabili dalla pagina cellular-automata-world ospitata su google code.

Annunci

Come implementare automi cellulari unidimensionali in C#

Dopo il primo post sugli automi cellulari vediamo come implementare il tipo più semplice di automa: l’unidimensionale di Wolfram.

Iniziamo col definire la nostra struttura dati per descrivere l’ambiente dell’automa. Nel caso di automi di Wolfram avremmo bisogno di una matrice a due dimensioni (benchè l’automa venga definito come unidimesnionale abbiamo bisogno della seconda dimensione per descriverne l’evoluzione nel tempo).

public class Environment2D {
  public byte[] Buffer { get; private set; }
  public int Width { get; private set; }
  public int Height { get; private set; }
  public Environment2D(int w, int h) {
    Width = w;
    Height = h;
    Buffer = new byte[w * h];
  }
  public byte GetValue(int x, int y) {
    int i = x + Width * y;
    return Buffer[i];
  }
  public void SetValue(int x, int y, byte value) {
    int i = x + Width * y;
    Buffer[i] = value;
  }
}

Definiamo ora la struttura del nostro automa tramite una classe astratta. E’ una definizione generica che sarà valida anche per automi bidimensionali (come per esempio il famoso gioco della vita di Conway).

public abstract class Automata {
  public Environment2D Env { get; protected set; }
  protected Environment2D Env0 { get; set; }

  public Automata() { Env = new Environment2D(0, 0); Env0 = null; }		
  public int Width { get { return Env.Width; } }
  public int Height { get { return Env.Height; } }
  public abstract bool IsFinite();
  public abstract bool Next();
  public abstract void RandomInit();
  public abstract void StandardInit();
  public virtual void SetSize(int w, int h) { Env = new Environment2D(w, h); }

  protected abstract byte ComputeRule(int x, int y);
}

public enum AutomataInitialCondition {
  Random, Standard
}

L’automa va inizializzato di dimensioni tramite il metodo SetSize(int w, int h), vanno impostate le condizioni iniziali, che possono essere generate casualmente (RandomInit()) oppure attivando solo la cella centrale dell’automa (StandardInit()). Next() calcola e attualizza la nuova generazione, applicando la regola definita in ComputeRule(int x, int y).

Vediamo ora come implementare il caso specifico dell’automa unidimensionale di Wolfram.
Mi preme introdurre la definizione di notazione di Wolfram, che potete dolcemente leggervela su Wikipedia.

public class Automata1DWolfram : Automata {
  private int x = 0;
  private int y = 0;
  private byte rule;
  private byte[, ,] tt = new byte[2, 2, 2];
  public Automata1DWolfram(byte rule) {
    this.rule = rule;
    tt[0, 0, 0] = (byte)((rule & 1) > 0 ? 1 : 0);
    tt[0, 0, 1] = (byte)((rule & 2) > 0 ? 1 : 0);
    tt[0, 1, 0] = (byte)((rule & 4) > 0 ? 1 : 0);
    tt[0, 1, 1] = (byte)((rule & 8) > 0 ? 1 : 0);
    tt[1, 0, 0] = (byte)((rule & 16) > 0 ? 1 : 0);
    tt[1, 0, 1] = (byte)((rule & 32) > 0 ? 1 : 0);
    tt[1, 1, 0] = (byte)((rule & 64) > 0 ? 1 : 0);
    tt[1, 1, 1] = (byte)((rule & 128) > 0 ? 1 : 0);
  }
  public override bool IsFinite() {	return true; }
  public override void SetSize(int w, int h) { Env = new Environment2D(w, h);	}
  public override void RandomInit() {
    Random rand = new Random(Environment.TickCount);
    for (x = 0, y = 0; x < Env.Width; x++)
      Env.SetValue(x, y, (byte)rand.Next(0, 2));
    x = 0;
    y = 1;
  }
  public override void StandardInit() {
    Env.SetValue(Env.Width / 2, 0, 1);
    x = 0;
    y = 1;
  }
  public override bool Next() {
    for (int i = 0; i < Env.Width; i++) {
      if (y >= Env.Height)
        return false;

      Env.SetValue(x, y, (byte)(ComputeRule(x, y)));
      if (x == Env.Width - 1) {
        x = 0;
        y++;
      } else
        x++;
    }

    return true;
  }		
  protected override byte ComputeRule(int x, int y) {
    byte l = Env.GetValue(x == 0 ? 0 : x - 1, y - 1);
    byte c = Env.GetValue(x, y - 1);
    byte r = Env.GetValue(x == Env.Width - 1 ? x : x + 1, y - 1);
    return tt[l, c, r];
  }
  public override string ToString() {
    return string.Format("Wolfram Rule {0}", rule);
  }
}

L’automa è ben che implementato in tutta la sua gustosità, il parametro rule passato nel costruttore Automata1DWolfram(byte rule) definisce la regola che identifica univocamente l’automa cellulare di Wolfram. Un po’ come una legge universale che decide la vita e la morte degli esemplari di una popolazione, un po’ come un Dio che determina le sorti di un mondo immaginario ma ben regolato da leggi fisiche e strutturato da fondamenti matematici. Per ognuna delle otto possibili configurazioni dell’intorno viene deciso (la regola!) se la cella dovrà vivere o morire.

Wolfram Regola 30

L'immagine visualizza la regola 30 di Wolfram (30 = 00011110 in decimale).

In WPF, utilizzando una UniformGrid, è semplice quanto banale creare una vista d’insieme degli 256 possibili automi cellulari di Wolfram, vi allungo qualche immagine direttamente dal mio schermo.

Wolfram Rules 1 Cell Initial Condition

Le 256 regole di Wolfram, con una cella attiva come condizione iniziale.

Wolfram Rules with Random Initial Condition

Le 256 regole di Wolfram, con condizione iniziale casuale.



Ho caricato l’eseguibile e i sorgenti del progetto in questa pagina: cellular-automata-world. Se qualcuno volesse contribuire, si faccia avanti! ;=)

Libri e appunti sugli automi cellulari

appunti sugli automi cellulari

Alcuni esempi di automi cellulari unidimensionali

Raccolgo qui delle risorse sugli automi cellulari, come base per iniziare a conoscerli e comprenderli. Non è una cosa facile percepirne la loro potenzialità e il loro significato intrinseco. Con automa cellulare si intende un modello matematico discreto in grado di descrivere perfettamente un sistema biologico complesso, come ad esempio la crescita di una foglia di palma, le fantasiose colorazioni di una conchiglia, la proliferazione nello spazio di una certa specie biologica.
 

Come l'automa cellulare descrive pattern biologici

Come l'automa cellulare descrive pattern biologici


Immagine da Cellular Automata.
 

Ho creato una pagina su facebook sugli automi cellulari, unico luogo di ritrovo italiano dove poter scambiare informazioni e conoscenze!

Qui un elenco di articoli e pubblicazioni interessanti trovati in rete:

 

Vi consiglio A New Kind of Science, il libro bibbia sugli automi cellulari. E’ stato scritto dal fisico matematico Stephen Wolfram, che negli anni ottanta sperimentò per primo automi cellulari computazionali.

Altri libri di interesse: