python e automi cellulari – griffeath circular cellular automata

Vediamo qui un esempio diverso di automa cellulare: L’automa circolare di Griffeath.

Il sitema è analogo a quello di life trattato qui e qui. Abbiamo una tabella costituita da punti di una mappa ognuno con un suo stato, un tempo di evoluzione costituito da istanti discreti e delle regole che determinano lo stato successivo di ogni punto sulla base degli stati dei vicini.

Il sistema rimane quindi definito da:

  • una matrice di punti ad ognuno dei quali deve essere associato uno stato individuato da un intero. Utilizzaremo una lista di liste il cui valore corrisponde allo stato. 10 stati possibili  è un volore ragionevole per questo sistema e lo utilizzerò nell’esempio. Il programma sarà comunque facilmente modificabile per gestire un numero di stati differenti
  • una regola di evoluzione: un punto mangia tutti i vicini nello stato immediatamente inferiore. Se avessi 4 stati il 3 mangia il 2, il 2 mangia l’1, l’1 mangia lo 0 e lo 0 mangia il 3. Se una casella viene mangiata nell’istante successivo assumerà lo stato della casella da cui è stata mangiata.
    Ogni elemento può mangiare ed essere mangiato nello stesso step
    In questo sistema per vicini si intendono le sole 4 caselle che condividono un lato.

Questo sistema, più ricco di quello del gioco life ha un comportamento molto diverso: passa sempre attraverso tre fasi:

  • una prima fase con una distribuzione casuale di punti
  • una fase in cui si formano delle grandi macchie
  • la comparsa di spirali che crescono fino a riempire completamente il sistema.

Per realizzare questo automa cellulare ho ripreso la classe del precedente adattando i metodi al nuovo sistema. Il codice completo è disponibile a questo indirizzo.

Come per il sistema life, non ho fatto un gramde sforzo per ottimizzare il metodo che calcola l’evoluzione del sistema dato che il grosso del tempo viene speso per rappresentarlo graficamente. Vorrei comunque in futuro almeno sfruttare i thread per suddividere il calcolo tra più CPU e magari trovare un metodo migliore per rappresentare il risultato.

L’automa cellulare è basata su una classe che mostra tre metodi: il cosrtruttore, una funzione per farlo evolvere e una funzione per rappresentarlo graficamente.

Il costruttore fa proprio quello che ci si aspetterebbe da un costruttore: definisce le strutture dati che costituiscono l’oggetto e gli assegna dei valori iniziali:

class CellularAutoma:
   def __init__(self, lenght=500, scale=1, levels=10):
      """genera la tabella iniziale quadrata e di dimensione iniziale lenght""
      self.board = [[]]
      self.pantone = []
      self.scale = scale
      self.levels = levels
      self.time = 0
      line = []
      random.seed()

      for a in range( lenght ):
         line = []
         for b in range( lenght ):
             line.append( random.randint( 0, self.levels-1 ))
         self.board.append( line )

      self.board.remove([])

      #inizializzo ambiente grafico 
      self.master = Tk()
      self.master.title('Griffeath circular cellular automata')
      self.w = Canvas(self.master, width=lenght*self.scale, height=lenght*self.scale)
      self.w.pack()

      #generate pantone
      for a in range( self.levels ):
         self.pantone.append( "#"+str(random.randint( 100000,999999 )))

self.board è una lista di liste che conterrà lo stato corrente del sistema
self.pantone conterrà una tavolozza di colori necessaria per la rappresentazione grafica del sistema
scales e levels sono rispettivamente la dimensione del punto nella rappresentazione grafica e il numero di stati che può assumere un elemento del sistema.

Per scales, e per altri valori ho cambiato i valori di default rispetto all’esempio precedente per ottenere un effetto grafico più adatto a questo sistema.

self.time è un contatore che conta il numero di step di evoluzione che ha subito l’oggetto. Verrà mostrato su consolle al completamento di ogni step di evoluzione: questo rende evidente che il grosso del tempo viene speso a generare la rappresentazione grafica per inciso.

Segue un blocco di codice che assegna ad ogni elemento del sistema un valore iniziale casuale

      line = []
      random.seed()

      for a in range( lenght ):
         line = []
         for b in range( lenght ):
             line.append( random.randint( 0, self.levels-1 ))
         self.board.append( line )

      self.board.remove([])

è abbastanza semplice e non mi dilunog a spiegarlo.

Inizializzo poi l’ambiente tkinter

      self.master = Tk()
      self.master.title('Griffeath circular cellular automata')
      self.w = Canvas(self.master, width=lenght*self.scale, height=lenght*self.scale)
      self.w.pack()

come si vede creo una finestra con dentro un widget canvas su cui andrò poi a disegnare la rappresentazione grafica del sistema

Il metodo si conclude con la generazione della tavolozza di colori:

      #generate pantone
      for a in range( self.levels ):
         self.pantone.append( "#"+str(random.randint( 100000,999999 )))

Ho optato per una selezione casuale dei colori che mi ha permesso di mantenere il numero di stati un semplice parametro numerico. C’è ovviamente il rischio che due stati vengano rappresentati con lo stesso colore ma direi che è abbastanza remoto.

Il secondo metodo della classe è evolve()

   def evolve( self ):
      """esegue lo step di evoluzione del gioco life su una tabella sferica"""
      rows = len(self.board)
      columns = len(self.board[0])
      board2 = [[0 for j in range(rows)] for i in range(columns)]


      for i in range( 0, rows ):
         for j in range( 0, columns ):
            if (self.board[(i-1)%(rows)][j%(columns)]-1)%self.levels  == self.board[i][j]:
               board2[i][j] = (self.board[i][j]+1)%self.levels
            elif (self.board[i%(rows)][(j-1)%(columns)]-1)%self.levels  == self.board[i][j]:
               board2[i][j] = (self.board[i][j]+1)%self.levels
            elif (self.board[i%(rows)][(j+1)%(columns)]-1)%self.levels  == self.board[i][j]:
               board2[i][j] = (self.board[i][j]+1)%self.levels
            elif (self.board[(i+1)%(rows)][j%(columns)]-1)%self.levels  == self.board[i][j]:
               board2[i][j] = (self.board[i][j]+1)%self.levels
            else:
               board2[i][j] = self.board[i][j]

      self.board = board2
      print("time: %d" %self.time )
      self.time = self.time+1

dopo alcune definizioni iniziali di variabili che verranno sfruttate nel metodo si inizia l’esame di tutti i punti del sistema. Ogni punto viene confrontato con i vicini e se il suo stato è quello immediatamente inferiore a quello di uno dei 4 vicini viene salvato nel punto corrispondente della tabella temporanea il suo valore incrementato di uno. Altrimenti viene salvato il suo valore.
L’operatore modulo viene sfruttato qui per gestire la circolarità del sistema, sia geometrica sia sugli stati.

A esame concluso lo stato attuale viene scambiato con quello calcolato, viene stampato in consolle il numero dello step e incrementato il tempo di uno.

L’ultimo metodo su cui è stato necessario intervenire è il metodo show().

Quì era necessario un sistema più generale che permettesse di rappresentare un numero arbitrario di stati. Ne è risultata, come a volte accade, una funzione anche più semplice di quella usata negli articoli precedenti:

   def show( self ):
      """Gives a graphical representation of the data"""
      self.w.delete(ALL)
      for i,v in enumerate(self.board):
         for j,w in enumerate( self.board[i] ):
               self.w.create_rectangle(i*self.scale, j*self.scale, i*self.scale+self.scale, j*self.scale+self.scale, fill=self.pantone[self.board[i][j]], outline=self.pantone[self.board[i][j]] )

Dato che questo sistema è più gradevole alla vista se costituito da tabelle grandi e punti piccoli, ho sfruttato il parametro outline per evitare il bordino nero del rettangolo che rappresenta il punto che in questo caso era di dimensioni confrontabili con il punto stesso e, quindi, piuttosto fastidioso.

One thought on “python e automi cellulari – griffeath circular cellular automata

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *