Tauon Barcadero

Automi cellulari unidimensionali

with 3 comments


Automi di Wolfram

Gli automi cellulari unidimensionali sono uno degli esempi più ecclatanti di quanto delle regole di base molto semplici possano portare alla costruzione di pattern anche molto complicati, in special modo qui si parlerà degli automi studiati da Stephen Wolfram intorno agli inizi degli anni 80.

Regola 129

Gli automi sono distribuiti su una riga, da cui la classificazione di automi monodimensionali, e ognuno di essi può assumere due stati differenti rappresentabili con 1 e 0(bianco e nero). Data una configurazione di partenza della riga, la generazione successiva viene calcolata in modo dipendente dalla riga precedente attraverso le regole mostrate nell’immagine:

spiegazione regole generazione successivaQuella presenta nell’immagine è la regola che definisce come creare una nuova riga a partire dalla quella precedente, infatti oltre alla casella immediatamente “sopra”, si considerano anche quelle a sinistra e a destra di essa, poichè consideriamo 3 caselle, ognuna della quali può assumere 2 stati( 1 = nero, 0 = bianco ), si hanno 2^3=8 possibili configurazioni precedenti, la cella della riga da creare avrà 2 possibili stati, 2^8 = 256, quindi vi sono 256 combinazioni possibili. Per descrivere la regola di usa il numero binario che si viene a formare, in questo caso 10111110 che equivale a 190 in decimale, da cui il nome della regola secondo la notazione di Wolfram: regola 190.

Perciò l’intera evoluzione dell’automa si effettua prendendo una casella dalla vecchia riga e applicandovi la regola per decidere se la corrispondente casella(cellula) della nuova riga assume come stato ‘1’ o ‘0’. E’ incredibile come variando la regola di base si ottengano comportamenti assolutamenti differenti tra loro, avvolte semplici righe, più spesso triangoli disordinati e figure astratte ma con una certa regolarità geometrica. L’unico automa di questo tipo Turing-compatibile, ciò capace di eseguire un qualsiasi algoritmo per computer, è quello definito dalla regola 110, ma vi sono molti altri pattern interessanti.

regola 110 2xregola 110 4x

Implementazione

Il codice per simulare gli automi è stato scritto in Processing, un linguaggio semplice e potente creato specificatamente per applicazioni grafiche dalla sintassi simile al Java. Un programma in processing è costituito da due funzioni principali: setup() che serve a definire le impostazione iniziali, preparare le variabili ecc… e  draw() che è invece una funzione chiamata ciclicamente e che contiene la parte del disegno e il corpo del programma stesso.

L’intero codice sorgente può essere scaricato qui.

Definizioni della griglia:


int screen_w = 640;  //risoluzione schermo
int screen_h = 480;
int cell_w = 2;    //larghezza, altezza di una cella della griglia
int cell_h = 2;    //che siano multipli di 2
int cell_num_x = 0;  //numero di celle su assi x, y
int cell_num_y = 0;  //il numero viene calcolato in setup()
int griglia[][];  //matrice contenente gli automi
int cur_y = 0;  //linea attuale in cui sto disegnando

Definizione della regola applicata sotto forma di array di interi:


int rule[] = { 0, 1, 1, 0, 1, 1, 1, 0 };  //regola 110 - turing compatibile

La funzione setup() si occupa di creare la finestra, impostare il frameRate, calcolare il numero di celle della grigli sull’asse x facendo screen_x / cell_w, poi crea in memoria l’array e inizializza tutte le celle a 0 tranne una, quella al centro della prima riga che sarà la cella di partenza.


void setup() {
size( 640, 480, P2D );
frameRate(200);

//calcola il numero di celle
cell_num_x = screen_w / cell_w;
cell_num_y = screen_h / cell_h;

//crea la griglia in memoria
griglia = new int[cell_num_x][cell_num_y];

//azzera la griglia
for( int i = 0; i < cell_num_y; i++ ) {
for( int j = 0; j < cell_num_x; j++ ) {
griglia[j][i] = 0;
}
}

//primo punto al centro della riga 0
griglia[(cell_num_x/2)][0] = 1;

//parte dalla prima riga
cur_y = 0;
}

Definisco le funzioni int leftCellValue( int x ) e int rightCellValue( int x ) che ricevono la posizione di una cella sulla riga e restituiscono lo stato( ‘1’ o ‘0’ ) rispettivamente della cella a sinistra e a destra di x.

Definisco inoltre:


//imposta il valore passato nella nuova cella, passata la vecchia (x;y)
void setNewCellValue( int x, int value ) {
//(x;y) è la cella vecchia!
if( x < 0 || x > cell_num_x ) return;
if( value != 0 && value != 1 ) return;

if( cur_y < (cell_num_y-1) )  {
griglia[x][cur_y+1] = value;
}
else return;
}

La funzione setNewCellValue( int x, int value ) copia nella cella corrispondente a x della nuova riga il valore di value.

Mentre la funzione getValueFromRule( int x ) restituisce il valore dell’elemento della nuova riga a partire da x elemento della vecchia riga, il suo vicino sinistro e quello destro( ricavati usando leftCellValue(x) e rightCellValue(x) ).


int getValueFromRule( int x ) {
int l = leftCellValue( x );
int c = griglia[x][cur_y];
int r = rightCellValue( x );

//applica la regola salvata in rule
if( l==1 && c==1 && r==1 ) return rule[0];
else if( l==1 && c==1 && !(r==1) ) return rule[1];
else if( l==1 && r==1 && !(c==1) ) return rule[2];
else if( l==1 && !(c==1) && !(r==1) ) return rule[3];
else if( !(l==1) && c==1 && r==1 ) return rule[4];
else if( c==1 && !(l==1) && !(r==1) ) return rule[5];
else if( r==1 && !(l==1) && !(c==1) ) return rule[6];
else if( !(r==1) && !(l==1) && !(c==1) ) return rule[7];
else return 0;

}

La funzione draw_cell( int x, int y ) si occupa di colorare di bianco una cella in posizione (x;y) della griglia.

Il ciclo principale del programma è la funzione loop():

void draw() {
background( 0 );

//creazione nuova riga
if( cur_y < cell_num_y ) {

for( int j = 0; j < cell_num_x; j++ ) {
setNewCellValue( j, getValueFromRule( j ) );
}

cur_y++;
}

//disegno
for( int i = 0; i < cell_num_y; i++ ) {
for( int j = 0; j < cell_num_x; j++ ) {

if( griglia[j][i] == 1 )
draw_cell( j, i );

}
}

//input utente per la prox. iterazione
if( keyPressed ) {
delay( 50 );  //se l'utente tiene premuto il tasto
//viene contato come premuto ogni 50ms

if( key == '+' ) {
cell_w++;
cell_h++;
setup();
}
else if( key == '-' ) {
if( cell_w - 1 > 0 ) cell_w--;
if( cell_h - 1 > 0 ) cell_h--;
setup();
}

} //keyPressed

}

In draw() si cancella lo schermo col nero usando background(0), poi si passa alla generazione della nuova riga che viene salvata nella matrice griglia[][] dalla funzione setNewCellValue( x, getValueFromRule( x )) la quale viene chiamata per ogni cella x della vecchia riga. Poi si passa al disegno su schermo delle celle della griglia a ‘1’, mentre quelle a ‘0’ restano nere, per far questo si usa la funzione draw_cell( x, y ). La gestione dei tasti finale è stata introdotta per permettere all’utente di cambiare la dimensione in pixel delle celle durante il programma, questo richiede che vengano calcolati nuovamente cell_num_x e cell_num_y e che la schermata sia ridisegnata da capo, perciò è necessaria una chiamata alla funzione setup() dopo aver ingrandito la dimensione delle celle. Questa funzione funge da zoom ed è molto utile per vedere il pattern nella sua interezza( per quanta limitata dalla risoluzione dello schermo ) o nei suoi particolari.

Bisogna far notare che tutto il codice non ha richiesto più di mezz’ora per essere scritta da zero, a dimostrare la versatilità e utilità del linguaggio Processing quando si ha a che far con un programma che deve gestire della grafica.

Per quanto riguarda gli automi si possono sperimentare diverse regole  cambiando il valore dell’array rule[] nel codice, ve ne sono alcuni già inseriti e commentati, basterà togliere il commento per renderlo attivo. A ogni pattern nuovo ci si sorprende di come poche regole possano formare un disegno così complesso e intricato.

Si può scaricare l’intero codice sorgente qui.

Per approfondire il tema degli automi cellulari si rimanda al sito di Stephen Wolfram qui.

regola 4

regola 250regola 190

Written by barcadero

8 agosto 2011 a 2:56 pm

3 Risposte

Subscribe to comments with RSS.

  1. Bellissimo articolo, spiegato in modo chiaro e completo! 😉

    b3nd3rbunny

    15 febbraio 2012 at 10:03 am

  2. […] Automi cellulari unidimensionali […]


Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: