automi cellulari

Come renderizzare automi cellulari a due dimensioni con GDI e WPF

Ok, noi abbiamo il nostro automa cellulare bidimensionale, un divertente gioco della vita interattivo implementato in C# / WPF. Vediamo come estendere il rendering grafico ad armoniose e più interessanti varianti. Definiamo prima di tutto l’interfaccia IRender:

public interface IRender {
  int CellSize { get; set; }
  void SetColorPalette(IList<System.Drawing.SolidBrush> colorsPalette);
  void SetColorPalette(IList<System.Windows.Media.Color> colorsPalette);
  System.Windows.Controls.Image Render(byte[] buf, int width, int height);
}

 
Il rendering base, basato cioè sulla corrispondenza “cella” -> “1×1 pixel su schermo” viene implementato agevolmente utilizzando BitmapImage.Create():

class RenderBase : IRender {
  public int CellSize { get { return 1; } set { } }
  private BitmapPalette Palette = BitmapPalettes.BlackAndWhite;
  public void SetColorPalette(IList<System.Drawing.SolidBrush> colorsPalette) {
    Palette = new BitmapPalette(ImageUtils.ConvertPaletteInMediaColor(colorsPalette));
  }
  public void SetColorPalette(IList<System.Windows.Media.Color> colorsPalette) {
    Palette = new BitmapPalette(colorsPalette);
  }

  public System.Windows.Controls.Image Render(byte[] buf, int width, int height) {
    const double dpi = 96;
    return new Image() {
      Source = BitmapImage.Create((int)width, (int)height, dpi, dpi,
        PixelFormats.Indexed8, Palette, buf, (int)width)
    };
  }
  public override string ToString() {
    return "1x1 Pixel (fastest)";
  }
}

 
Per ottenere diversi render più complessi, basati sulla forma della singola cella e relativamente al bordo della stessa, creiamo una classe astratta RenderGraphics che utilizza le librerie grafiche GDI+ per il disegno delle singole celle e la composizione dell’ambiente.

abstract class RenderGraphics : IRender {
  public int CellSize { get; set; }
  protected IList<System.Drawing.SolidBrush> Palette { get; private set; }

  public void SetColorPalette(IList<System.Drawing.SolidBrush> colorsPalette) {
    foreach (System.Drawing.SolidBrush brush in Palette)
      brush.Dispose();
    Palette = colorsPalette;
  }
  public void SetColorPalette(IList<System.Windows.Media.Color> colorsPalette) {
    Palette = ImageUtils.ConvertPaletteInDrawingBrush(colorsPalette);
  }

  public System.Windows.Controls.Image Render(byte[] buf, int width, int height) {
    using (Bitmap b = new Bitmap(width * CellSize, height * CellSize)) {
      using (Graphics g = Graphics.FromImage(b)) {
        g.PixelOffsetMode = System.Drawing.Drawing2D.PixelOffsetMode.None;
        g.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.None;
        g.CompositingMode = System.Drawing.Drawing2D.CompositingMode.SourceCopy;
        g.CompositingQuality = System.Drawing.Drawing2D.CompositingQuality.HighSpeed;
        for (int i = 0; i < width * height; i++) {
          int x = (int)(i % width);
          int y = (int)(i / width);
          Draw(g, Palette[buf[i]], x, y);
        }
      }

      return ImageUtils.ConvertToWpfImage(b);
    }
  }

  protected abstract void Draw(Graphics g, System.Drawing.SolidBrush brush, int x, int y);
}

 
I diversi rendering grafici si ottengono estendendo RenderGraphics e implementando il metodo Draw():

class RenderFilledRects : RenderGraphics {
  public override string ToString() { return "Filled Rects without border"; }
  protected override void Draw(Graphics g, System.Drawing.SolidBrush brush, int x, int y) {
    g.FillRectangle(brush, x + (CellSize - 1) * x, y + (CellSize - 1) * y, CellSize, CellSize);
  }
}
class RenderFilledRectsBorder : RenderGraphics {
  public override string ToString() {	return "Filled Rects with border"; }
  protected override void Draw(Graphics g, System.Drawing.SolidBrush brush, int x, int y) {
    g.FillRectangle(brush, x + (CellSize - 1) * x, y + (CellSize - 1) * y, CellSize - 1, CellSize - 1);
  }
}
class RenderFilledDots : RenderGraphics {
  public override string ToString() { return "Filled Dots without border"; }
  protected override void Draw(Graphics g, SolidBrush brush, int x, int y) {
    g.FillEllipse(brush, x + (CellSize-1) * x, y + (CellSize-1) * y, CellSize+1, CellSize+1);
  }
}
class RenderFilledDotsBorder : RenderGraphics {
  public override string ToString() { return "Filled Dots with border"; }
  protected override void Draw(Graphics g, SolidBrush brush, int x, int y) {
    g.FillEllipse(brush, x + (CellSize - 1) * x, y + (CellSize - 1) * y, CellSize-1, CellSize-1);
  }		
}
class RenderEmptyDots : RenderGraphics {
  public override string ToString() { return "Empty Dots"; }
  protected override void Draw(Graphics g, SolidBrush brush, int x, int y) {
    g.DrawEllipse(new Pen(brush, 1), x + (CellSize - 1) * x, y + (CellSize - 1) * y, CellSize - 2, CellSize - 2);
  }		
}
class RenderEmptyRects : RenderGraphics {
  public override string ToString() { return "Empty Rects"; }
  protected override void Draw(Graphics g, SolidBrush brush, int x, int y) {
    g.DrawRectangle(new Pen(brush, 1), x + (CellSize - 1) * x, y + (CellSize - 1) * y, CellSize - 2, CellSize - 2);
  }
}
game of life animated gif

Gioco della vita renderizzato a cubetti

Annunci

Calcolo parallelo applicato agli automi cellulari

Un piccolo esempio per tastare la praticità e l’eleganza delle nuove funzionalità di calcolo parallelo introdotte dal .NET Framework 4. La classe Parallel fornisce semplicemente e senza tante complicazioni metodi statici che permettono di sfruttare al meglio l’archittettura multicore in cui viene eseguita l’applicazione. Vediamo un esempio applicato agli automi cellulari, più precisamente al gioco della vita:

public override bool Next() {
  GenerationCount++;
  Environment2D etmp = new Environment2D(Env.Width, Env.Height);
  Parallel.For(0, Env.Width, x => {
    Parallel.For(0, Env.Height, y => {
      etmp.SetValue(x, y, ComputeRule(x, y));
    });
  });
  Env = etmp;
  return true;
}		

dove Next() calcola la nuova generazione dell’automa, computando per ogni cella dell’ambiente il nuovo valore, che come tutti sapranno, dipende dallo stato delle celle dell’intorno.

Vediamo ora la versione non parallela, formata semplicemente da due cicli for annidati, che spazzano in sequenza le celle dell’ambiente.

public override bool Next() {
  GenerationCount++;
  Environment2D etmp = new Environment2D(Env.Width, Env.Height);
  for (int x = 0; x < Env.Width; x++)
    for (int y = 0; y < Env.Height; y++)
      etmp.SetValue(x, y, ComputeRule(x, y));
  Env = etmp;
  return true;
}				

Simpatico e divertente, non come implementare una logica basata su thread che poi chissà cosa ti combinano questi furbi e malandrini thread 😦 bella questa classe System.Threading.Tasks.Parallel!

Per la cronaca, su un Intel Core2 Quad Q6600 (2,40Ghz) con quattro core separati e RAM da 3Gb, il mio algoritmo risulta tre volte più veloce!

Come implementare il Gioco della Vita di Conway in C#

Dopo il primo post sugli automi di Wolfram, passiamo allo studio ben più interessante e vario degli automi a due dimensioni. Un mondo artificiale, chiamato comunemente “Game of Life” gioco della vita perchè è un misto variegato di pattern e conglomerati di bytes che si raccolgono e si evolvono in fantasiose creature, o variegati accrescimenti sincronizzati, o in una morte certa ed atroce, fa sempre un po’ tristezza quando ti muore un automa cellulare, sono momenti che non vorresti mai accadessero nella tua vita. Non è giusto che un automa vive solo perchè ha delle regole favorevoli o delle condizioni iniziali tarate ad hoc da una entità superiore. Personalmente non trovo giusto ed eticamente corretto che si creino degli automi cellulari per poi farli morire, o ancora peggio per godere mentre questi muoiono nell’indifferenza più totale della società moderna. Un po’ come Pernolino il tenero buchino nero, tanto amato ma tanto temuto del mondo intero. Per questo mi impegnerò nella salvaguardia degli automi cellulari, voglio fondare una associazione, in modo tale da organizzare una forza lavoro per raccogliere risorse, dibattiti, divulgazione, volantini informativi. Tutti devono sapere che gli automi cellulari esistono e molti incontrano la morte solo dopo neanche un paio di cicli di evoluzione!

Accrescimento cellulare sincronizzato

Accrescimento cellulare sincronizzato generato dal Gioco della Vita regola S23/B246.

Accrescimento cellulare incontrollato game of life conway

Accrescimento cellulare incontrollato generato dalla regola S23/B2356

Replicatore cellulare Game of Life Conway

Replicatore cellulare generato dalla regola S1357/B1357

Espanditore cellulare Game of Life Conway

Espanditore cellulare generato dalla regola S012345678/B3

Espanditore cellulare labirintico Game of Life Conway

Espanditore cellulare labirintico generato dalla regola S1234/B3

Questi sono degli automi cellulari possenti! Sembrano non morire mai, ed infatti così è! Ma ne esistono anche di altamente insicuri e precari, i quali dipendono fortemente dalle condizioni iniziali. Ma sono anche i più interessanti, come il classico gioco della vita di Conway basato sulla regola S23/B3 (qui potete leggervi la descrizione delle regole Game of Life di Conway).

Game of Life S23B356 Conway

Regola S23B356

Vediamo il codice, dove la classe astratta Automata e la classe Environment2D sono descritte nel precedente post sugli automi unidimensionali di Wolfram.

public class Automata2DGameLife : Automata {
  protected readonly List<byte> RuleSurvival = null;
  protected readonly List<byte> RuleBirth = null;

  public Automata2DGameLife(byte[] ruleSurvival, byte[] ruleBirth, Environment2D env0 = null) {
    this.RuleSurvival = ruleSurvival.ToList();
    this.RuleBirth = ruleBirth.ToList();
    this.Env0 = env0;
  }

  public override void StandardInit() {
    if (this.Env0 != null)
      this.Env.Merge(this.Env0);
    else {
      Env.SetValue(Env.Width / 2, Env.Height / 2, 1);
      Env.SetValue(Env.Width / 2 + 1, Env.Height / 2, 1);
      Env.SetValue(Env.Width / 2 - 1, Env.Height / 2 - 1, 1);
      Env.SetValue(Env.Width / 2 - 2, Env.Height / 2 - 1, 1);
      Env.SetValue(Env.Width / 2 - 2, Env.Height / 2 - 2, 1);
      Env.SetValue(Env.Width / 2 - 3, Env.Height / 2 - 2, 1);
      Env.SetValue(Env.Width / 2 - 3, Env.Height / 2 - 3, 1);
      Env.SetValue(Env.Width / 2 - 4, Env.Height / 2 - 2, 1);
    }
  }
  
  public override bool IsFinite() { return false; }
  public override void RandomInit() {
    Env0 = new Environment2D(20, 20);
    Random rand = new Random(Environment.TickCount);
    for (int i = 0; i < (Env.Width * Env.Height); i++) {
      int x = rand.Next(0, Env.Width);
      int y = rand.Next(0, Env.Height);
      Env.SetValue(x, y, (byte)rand.Next(0, 2));
    }
  }
  public override bool Next() {
    Environment2D etmp = new Environment2D(Env.Width, Env.Height);
    for (int x = 0; x < Env.Width; x++)
      for (int y = 0; y < Env.Height; y++)
        etmp.SetValue(x, y, ComputeRule(x, y));

    Env = etmp;
    return true;
  }		
  protected override byte ComputeRule(int x, int y) {
    byte neighbours = GetNeighbours(x, y);
    byte c = Env.GetValue(x, y);
    if (c > 0) {
      return (byte)(RuleSurvival.Contains(neighbours) ? 1 : 0);
    } else {
      return (byte)(RuleBirth.Contains(neighbours) ? 1 : 0);
    }
  }
  private byte GetNeighbours(int x, int y) {
    byte neighbours = 0;
    if (x > 0) { if (Env.GetValue(x - 1, y) > 0) neighbours++; }
    if (x > 0 && y > 0) { if (Env.GetValue(x - 1, y - 1) > 0) neighbours++; }
    if (x > 0 && y < Env.Height - 1) { if (Env.GetValue(x - 1, y + 1) > 0) neighbours++; }
    if (y > 0) { if (Env.GetValue(x, y - 1) > 0) neighbours++; }
    if (y < Env.Height - 1) { if (Env.GetValue(x, y + 1) > 0) neighbours++; }
    if (x < Env.Width - 1 && y > 0) { if (Env.GetValue(x + 1, y - 1) > 0) neighbours++; }
    if (x < Env.Width - 1) { if (Env.GetValue(x + 1, y) > 0) neighbours++; }
    if (x < Env.Width - 1 && y < Env.Height - 1) { if (Env.GetValue(x + 1, y + 1) > 0) neighbours++; }
    return neighbours;
  }  
  public override string ToString() {
    return string.Format("Game of Life S{0}/B{1}",
      string.Concat(RuleSurvival.Select(b => b.ToString()).ToArray()),
      string.Concat(RuleBirth.Select(b => b.ToString()).ToArray()));
  }
}

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: