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.

python e automi cellulari – life

Volendo farmi un’idea del python, dopo aver letto il tutorial ho pensato di provare a fare un piccolo programma e, avendo recentemente letto un articolo sugli automi cellulari la scelta è caduta su un’implementazione del famoso gioco life.

Per chi non lo conoscesse, life è un automa cellulare, ovvero un sistema che evolve sulla base di regole di interazione tra gli elementi del sistema. Nel caso specifico di life il sistema è costituito da una tabella in cui ogni elemento è costituito da una casella che può essere in due stati: morto o vivo. Ogni casella ha 8 vicini:

  1. Se una casella è morta ed ha esattamente 3 vicini vivi, diventa viva. Altrimenti rimane morta
  2. Se una casella è viva ed ha 2 o 3 vicini vivi rimane viva altrimenti muore

nell’implementazione che ho realizzato il sistema è a topologia toroidale:

  1. l’elemento a destra di quello a più a destra è l’elemento più a sinistra della stessa riga,
  2. l’elemento a sinistra di quello più a sinistra è l’elemento più a destra della stessa riga
  3. l’analogo per le colonne

Riporto ora il programma da copiare in un file ed eseguire con python 3.
In questa implementazione ho trovato comodo dare valore 0 alle cellule more ed 1 a quelle vive.

import random

def evolve( array ):
### esegue lo step di evoluzione del gioco life su una tabella sferica
   rows = len(array)
   columns = len(array[0])
   array2 = [[0 for j in range(rows)] for i in range(columns)]

# i=0, j=0 
   totale = array[rows-1][columns-1]+array[rows-1][0]+array[rows-1][1]+array[0][columns-1]+array[0][0]+array[0][1]+array[1][columns-1]+array[1][0]+array[1][1]
   if    array[0][0] == 0:
      if totale == 3:
         array2[0][0]=1
      else:
         array2[0][0]=0
   if array[0][0] == 1:
      if totale <= 2:
         array2[0][0]=0
      elif totale <= 4:
         array2[0][0]=1
      else:
         array2[0][0]=0
# i=rows-1, j=0 
   totale = array[rows-2][columns-1]+array[rows-2][0]+array[rows-2][1]+array[rows-1][columns-1]+array[rows-1][0]+array[rows-1][1]+array[0][columns-1]+array[0][0]+array[0][1]
   if    array[rows-1][0] == 0:
      if totale == 3:
         array2[rows-1][0]=1
      else:
         array2[rows-1][0]=0
   if array[rows-1][0] == 1:
      if totale <= 2:
         array2[rows-1][0]=0
      elif totale <= 4:
         array2[rows-1][0]=1
      else:
         array2[rows-1][0]=0

# i=0, j=columns-1
   totale = array[rows-1][columns-2]+array[rows-1][columns-1]+array[rows-1][0]+array[0][columns-2]+array[0][columns-1]+array[0][0]+array[1][columns-2]+array[1][columns-1]+array[1][0]
   if    array[0][columns-1] == 0:
      if totale == 3:
         array2[0][columns-1]=1
      else:
         array2[0][columns-1]=0
   if array[0][columns-1] == 1:
      if totale <= 2:
         array2[0][columns-1]=0
      elif totale <= 4:
         array2[0][columns-1]=1
      else:
         array2[0][columns-1]=0

# i=rows-1, j=columns-1 
   totale = array[rows-2][columns-2]+array[rows-2][columns-1]+array[rows-2][0]+array[rows-1][columns-2]+array[rows-1][columns-1]+array[rows-1][0]+array[0][columns-2]+array[0][columns-1]+array[0][0]
   if    array[rows-1][columns-1] == 0:
      if totale == 3:
         array2[rows-1][columns-1]=1
      else:
         array2[rows-1][columns-1]=0
   if array[rows-1][columns-1] == 1:
      if totale <= 2:
         array2[rows-1][columns-1]=0
      elif totale <= 4:
         array2[rows-1][columns-1]=1
      else:
         array2[rows-1][columns-1]=0

# i=0
   for j in range( 1, columns-2 ):
      totale = array[rows-1][j-1]+array[rows-1][j]+array[rows-1][j+1]+array[0][j-1]+array[0][j]+array[0][j+1]+array[1][j-1]+array[1][j]+array[1][j+1]
      #print( totale )
      if    array[0][j] == 0:
         if totale == 3:
            array2[0][j]=1
         else:
            array2[0][j]=0
      if array[0][j] == 1:
         if totale <= 2:
            array2[0][j]=0
         elif totale <= 4:
            array2[0][j]=1
         else:
            array2[0][j]=0

# i=rows-1
   for j in range( 1, columns-2 ):
      totale = array[rows-2][j-1]+array[rows-2][j]+array[rows-2][j+1]+array[rows-1][j-1]+array[rows-1][j]+array[rows-1][j+1]+array[0][j-1]+array[0][j]+array[0][j+1]
      #print( totale )
      if    array[rows-1][j] == 0:
         if totale == 3:
            array2[rows-1][j]=1
         else:
            array2[rows-1][j]=0
      if array[rows-1][j] == 1:
         if totale <= 2:
            array2[rows-1][j]=0
         elif totale <= 4:
            array2[rows-1][j]=1
         else:
            array2[rows-1][j]=0

# j=0
   for i in range( 1, rows-2 ):
      totale = array[i-1][columns-1]+array[i-1][0]+array[i-1][1]+array[i][columns-1]+array[i][0]+array[i][1]+array[i+1][columns-1]+array[i+1][0]+array[i+1][1]
      #print( totale )
      if    array[i][0] == 0:
         if totale == 3:
            array2[i][0]=1
         else:
            array2[i][0]=0
      if array[i][0] == 1:
         if totale <= 2:
            array2[i][0]=0
         elif totale <= 4:
            array2[i][0]=1
         else:
            array2[i][0]=0

# j=columns-1
   for i in range( 1, rows-2 ):
      totale = array[i-1][columns-2]+array[i-1][columns-1]+array[i-1][0]+array[i][columns-2]+array[i][columns-1]+array[i][0]+array[i+1][columns-2]+array[i+1][columns-1]+array[i+1][0]
      #print( totale )
      if    array[i][columns-2] == 0:
         if totale == 3:
            array2[i][columns-2]=1
         else:
            array2[i][columns-2]=0
      if array[i][columns-2] == 1:
         if totale <= 2:
            array2[i][columns-2]=0
         elif totale <= 4:
            array2[i][columns-2]=1
         else:
            array2[i][columns-2]=0

# other cases
   for i in range( 1, rows-2 ):
      for j in range( 1, columns-2 ):
         totale = array[i-1][j-1]+array[i-1][j]+array[i-1][j+1]+array[i][j-1]+array[i][j]+array[i][j+1]+array[i+1][j-1]+array[i+1][j]+array[i+1][j+1]
         #print( totale )
         if    array[i][j] == 0:
            if totale == 3:
               array2[i][j]=1
            else:
               array2[i][j]=0
         if array[i][j] == 1:
            if totale <= 2:
               array2[i][j]=0
            elif totale <= 4:
               array2[i][j]=1
            else:
               array2[i][j]=0

   return array2

# j=0
   for i in range( 1, rows-2 ):
      totale = array[i-1][columns-1]+array[i-1][0]+array[i-1][1]+array[i][columns-1]+array[i][0]+array[i][1]+array[i+1][columns-1]+array[i+1][0]+array[i+1][1]
      #print( totale )
      if    array[i][0] == 0:
         if totale == 3:
            array2[i][0]=1
         else:
            array2[i][0]=0
      if array[i][0] == 1:
         if totale <= 2:
            array2[i][0]=0
         elif totale <= 4:
            array2[i][0]=1
         else:
            array2[i][0]=0

# j=columns-1
   for i in range( 1, rows-2 ):
      totale = array[i-1][columns-2]+array[i-1][columns-1]+array[i-1][0]+array[i][columns-2]+array[i][columns-1]+array[i][0]+array[i+1][columns-2]+array[i+1][columns-1]+array[i+1][0]
      #print( totale )
      if    array[i][columns-2] == 0:
         if totale == 3:
            array2[i][columns-2]=1
         else:
            array2[i][columns-2]=0
      if array[i][columns-2] == 1:
         if totale <= 2:
            array2[i][columns-2]=0
         elif totale <= 4:
            array2[i][columns-2]=1
         else:
            array2[i][columns-2]=0

# other cases
   for i in range( 1, rows-2 ):
      for j in range( 1, columns-2 ):
         totale = array[i-1][j-1]+array[i-1][j]+array[i-1][j+1]+array[i][j-1]+array[i][j]+array[i][j+1]+array[i+1][j-1]+array[i+1][j]+array[i+1][j+1]
         #print( totale )
         if    array[i][j] == 0:
            if totale == 3:
               array2[i][j]=1
            else:
               array2[i][j]=0
         if array[i][j] == 1:
            if totale <= 2:
               array2[i][j]=0
            elif totale <= 4:                
               array2[i][j]=1
            else:
               array2[i][j]=0
    return array2 

def start_configuration( lenght = 6 ): 
### genera la tabella iniziale quadrata e di dimensione iniziale lenght
    board = [[]]
    line = []
    random.seed()

    for a in range( lenght ):
       line = []
       for b in range( lenght ):
           tmp = random.randint( -1, 1 )
           if tmp > 0:
             line.append( 1 )
          else:
             line.append( 0 )
      board.append( line )

   board.remove([])
   return board

board = [[]]
board = start_configuration( 20 )

for i,v in enumerate(board):
   print(board[i])

print("\n")

while True:
   ok = input()
   board = evolve( board )
   for i,v in enumerate(board):
      print(board[i])

Dopo aver importato il modulo random che utilizzerò per generare la configurazione iniziale, il programma definisce due funzioni: la prima per calcolare uno step di evoluzione, la seconda per generare una configurazione iniziale. Segue poi il corpo principale.

Iniziamo ad esaminare il programma a partire dal corpo principale che è piuttosto semplice:

board = [[]]
board = start_configuration( 20 )

inizio dichiarando la tabella come lista di liste e gli assegno una configurazione con una funzione che esamineremo in seguito. Alla funzione start_configuration() passo come parametro il numero di righe e colonne: ho presupposto che fosse quadrata.

for i,v in enumerate(board):
   print(board[i])

stampo a video la configurazione iniziale con un semplice loop sugli elementi della lista. enumerate restituisce come primo valore l’indice numerico dell’elemento di una lista, indice che poi uso per stampare l’elemento.

while True:
   ok = input()
   board = evolve( board )
   for i,v in enumerate(board):
      print(board[i])

entro infine in un loop infinito per il calcolo degli stati successivi del sistema. Per avere controllo sul processo ad ogni ciclo attendo un invio da parte dell’utente e poi calcolo e stampo a video lo stato successivo.

Esaminiamo ora la prima funzione.

import random

start_configuration() genera casualmente la configurazione iniziale e per farlo ho importato il modulo random

def start_configuration( length = 6 ):
### genera la tabella iniziale quadrata e di dimensione iniziale length

segue poi la definizione della funzione nella quale ho impostato un valore di default per la variabile passata e una riga di commento.
Questa riga di commento ad inizio funzione e preceduta da tre # è in qualche modo speciale e serve a documentare il codice. Appositi tool possono essere utilizzati per esaminare il codice in python alla loro ricerca e generare automaticamente della documentazione.

   board = [[]]
   line = []

definisco le liste che mi serviranno

   random.seed()

inizializzo il generatore di numeri casuali.

   for a in range( length ):
      line = []
      for b in range( length ):
          tmp = random.randint( -1, 1 )
          if tmp > 0:
             line.append( 1 )
          else:
             line.append( 0 )
      board.append( line )

entro nel loop che genera la tabella casuale. Dato che la tabella è in realtà una lista di liste la cosa che mi è sembrata funzionare meglio è stata genereare una riga alla volta per poi aggiungerla alla tabella utilizzando la funzione append delle liste.

   board.remove([])

per come l’ho generata, la tabella conteneva una riga vuota che quindi rimuovo.

   return board

Restituisco infine la tabella generata.

La funzione evolve() sebbene molto lunga non è particolarmente complicata. La sua lunghezza deriva dalla casistica articolata necessaria per gestire cosa accade sui bordi della tabella.

def evolve( array ):
### esegue lo step di evoluzione del gioco life su una tabella sferica
   rows = len(array)
   columns = len(array[0])
   array2 = [[0 for j in range(rows)] for i in range(columns)]

[...]
# other cases
   for i in range( 1, rows-2 ):
      for j in range( 1, columns-2 ):
         totale = array[i-1][j-1]+array[i-1][j]+array[i-1][j+1]+array[i][j-1]+array[i][j]+array[i][j+1]+array[i+1][j-1]+array[i+1][j]+array[i+1][j+1]
         #print( totale )
         if    array[i][j] == 0:
            if totale == 3:
               array2[i][j]=1
            else:
               array2[i][j]=0
         if array[i][j] == 1:
            if totale <= 2:
               array2[i][j]=0
            elif totale <= 4:
               array2[i][j]=1
            else:
               array2[i][j]=0

   return array2

ho riportato quindi solo il caso generico.

Dato che lo stato nel tempo successivo dipende dal numero di vicini e dato che si è scelto di assegnare 1 per il caso cella viva e 0 per quello cella morta, tutto quello che serve è sommare i valori delle caselle coinvolte e confrontare il risultato con le regole che definiscono il gioco.

Il programma andrebbe migliorato sotto diversi aspetti. In particolare:

  • trovare un modo più elegante per gestire la variegata casistica dell’evoluzione per le caselle lungo il bordo.
  • stampare lo stato in modo più visibile
  • dare al  programma un aspetto più unix like, permettendo di eseguirlo passando dei parametri, come le dimensioni delle tabelle, un fiel con una configurazione iniziale, se si vuole che il programma aspetti l’ok dell’esecutore per passare allo stato successivo o eseguire un numero predeterminato di step, altro.
  • capire se il python ha strutture dati più adatte
  • molto altro probabilmente.

PS 1

Si può usare l’operatore modulo per scrivere in modo più compatta la funzione evolve() che diverrà

def evolve( array ):
### esegue lo step di evoluzione del gioco life su una tabella sferica
   rows = len(array)
   columns = len(array[0])
   array2 = [[0 for j in range(rows)] for i in range(columns)]

   for i in range( 0, rows ):
      for j in range( 0, columns ):
         totale = array[(i-1)%(rows)][(j-1)%(columns)]+array[(i-1)%(rows)][j%(columns)]+array[(i-1)%(rows)][(j+1)%(columns)]+array[i%(rows)][(j-1)%(columns)]+array[i%(rows)][j%(columns)]+array[i%(rows)][(j+1)%(columns)]+array[(i+1)%(rows)][(j-1)%(columns)]+array[(i+1)%(rows)][j%(columns)]+array[(i+1)%(rows)][(j+1)%(columns)]
         #print( totale )
         if array[i][j] == 0:
            if totale == 3:
               array2[i][j]=1
            else:
               array2[i][j]=0
         if array[i][j] == 1:
            if totale <= 2:
               array2[i][j]=0
            elif totale <= 4:
               array2[i][j]=1
            else:
               array2[i][j]=0

   return array2