Tauon Barcadero

Programmare il gioco della vita di Conway

with 2 comments


L’automa cellulare di Conway

Il gioco della vita è un famosissimo automa cellulare elaborato dal matematico John Conway negli anni sessanta;  si tratta sostanzialmente di una griglia costituita da celle e ognuna di esse può essere o viva o morta(piena o vuota). Data una situazione iniziale della griglia, le successive iterazioni dell’algoritmo seguono delle regole semplicissime per decidere quali celle si devono accendere( nascere o continuare a vivere ) e quali spegnere( morire ), a seconda del numero di “vicini” che si trovano nel quadrato 3×3 con centro nella cella considerata.

  • Una cella vuota diventa piena( nasce ) se  ha 3 vicini
  • Una cella piena sopravvive se ha 2 o 3 vicini, altrimenti muore per solitudine o sovrappopolazione.

Glider Cannon image

(Un cannone di “glider” di Gosper)

L’implementazione

L’implementazione è scritta in C++ e per la parte grafica, che comprende la creazione della finestra, il disegno della griglia e delle celle, è stata usata la libreria SDL.

Per tracciare le linee della griglia è stata usata SDL_gfx, un’estensione di SDL che permette il disegno di primitive 2D ben più complesse delle semplici linee.

Il codice sorgente può essere scaricato QUI. Un binario per linux compilato con CodeBlocks può essere scaricato QUI.

L’implementazione crea una griglia di cellsPerRow x cellsPerColumns dimensioni, le due variabili sono definite come cellsPerRow = SCREEN_W / CELL_W e cellsPerColumn = SCREEN_H / CELL_H, quindi per esempio se la finestra e 640×480 px, e le celle sono 10x10px ci saranno 3072 celle, la griglia è salvata nell’array cellGrid.

All’avvio del programma all’utente viene chiesto di immettere la configurazione iniziale della griglia usando i tasti freccia per spostare il cursore e la barra spaziatrice per accendere/spegnere una cella, poi quando si preme Invio parte la simulazione. Di questo si occupa la funzione getInitGridConfig() che viene chiamata subito dopo SDL_Init() che si occupa di inizializzare la libreria e creare la finestra.

Per non dover scrivere funzioni con troppi argomenti è stato creato un namespace anonimo che contiene le variabili che devono essere visibili in tutto il file, evitando così i problemi delle variabili globali.

namespace {
 //puntatore alla finestra
 SDL_Surface *screen = NULL;

 //la griglia
 SDL_Surface *grid = NULL;

 //dimesioni finestra
 const int SCREEN_W = 800;
 const int SCREEN_H = 600;

 //dimensione singola cella(px)
 const int CELL_W = 10;
 const int CELL_H = 10;

 const int cellsPerRow = SCREEN_W / CELL_W;
 const int cellsPerColumn = SCREEN_H / CELL_H;

 /*
 matrice di interi cellsPerRowxcellsPerColumn
 cellMap[j][k] = 0 se cella vuota
 ""            = 1 se cella piena
 parte da [0][0] a [cellsPerRow-1][cellsPerColumn-1]
 */
 int cellMap[cellsPerRow][cellsPerColumn];
}

La funzione main():

int main ( int argc, char** argv )
{
 //azzera cellMap
 for( int j = 0; j < cellsPerRow; j++ )
 for( int k = 0; k < cellsPerColumn; k++ )
 cellMap[j][k] = 0;

 //inizializza SDL
 if( !initSDL() ) {
 printf("Error while initializing SDL!\n");
 return 1;
 }

 //input utente
 getInitGridConfig();

 //ciclo principale
 if( MainLoop() ) {
 // all is well 😉
 printf("Exited cleanly\n");
 }

 return 0;
}

I cicli for azzerano la griglia, dopo di inizializza la libreria SDL, si chiede all’utente di inserire la configurazione iniziale della griglia e poi si chiama la funzione MainLoop(), essa esegue le seguenti operazioni:

  1. lettura degli eventi SDL: gestisce la pressione di qualsiasi tasto, tra cui +/- che servono a incrementare/decrementare la velocità della simulazione e la chiusura della finestra col tasto ‘ESC’.
  2. Cancella tutto quello che c’è già nella finestra e vi disegna sopra la griglia
  3. calcola l’iterazione successiva della griglia chiamando calculateNextStage()
  4. disegna su schermo il tutto.

La funzione calculateNextStage() calcola quali celle sopravvivono e/o nascono scrivendoli in un nuovo array tempCellGrid, alla fine copia tutti gli elementi di tempCellGrid in cellGrid. Essa usa per calcolare le celle che sopravvivono la funzione cellSurvives(int j, int k) e cellBecomesAlive(int j, int k), entrambe ritornano true in caso affermativo rispetto alla cella cellGrid[j][k].

//calcola le celle che sopravvivono
 for( int j = 0; j < (cellsPerRow); j++ ) {
for( int k = 0; k < (cellsPerColumn); k++ ) {

//celle già piene
if( cellMap[j][k] ) {
if( cellSurvives(j,k) ) tempCellMap[j][k] = 1;
else tempCellMap[j][k] = 0;
}
else {
//celle vuote
if( cellBecomesAlive(j,k) ) tempCellMap[j][k] = 1;
else tempCellMap[j][k] = 0;
}

}
 } //fine calcolo sopravvissuti

La conta dei “sopravvissuti” e dei “nati”

Le funzioni cellBecomesAlive( int j, int k ) e cellSurvives(int j, int k) in pratica contano il numero di celle piene presenti nel quadrato 3×3 costruito attorno alla cella considerata usando il contatore neighbours e lo incrementano a ogni cella piene, poi ritornano true o false a seconda che la cella rispetti o meno le regole dell’automa.

//true se la cella piena sopravvive
bool cellSurvives(int x, int y) {
 int neighbours = 0;

 if( x < 0 || x > (cellsPerRow-1) || y < 0 || y > (cellsPerColumn-1) ) {
 printf("Attenzione!cellSurvives() x o y vanno oltre i limiti dell'array.");
 return false;
 }

 //si assicura che la cella sia già piena
 if( !cellMap[x][y] ) {
 printf("Attenzione! cellSurvives() chiamato su una cella vuota!");
 return false;
 }

 /*
 Conta vicini
 */
 if( x > 1 ) { if( cellMap[x-1][y] ) neighbours++; }
 if( x > 1 && y > 1 ) { if( cellMap[x-1][y-1] ) neighbours++; }
 if( x > 1 && y < cellsPerColumn) { if( cellMap[x-1][y+1] ) neighbours++; }
 if( y > 1 ) { if( cellMap[x][y-1] ) neighbours++; }
 if( y < cellsPerColumn ) { if( cellMap[x][y+1] ) neighbours++; }
 if( x < cellsPerRow && y > 1 ) { if( cellMap[x+1][y-1] ) neighbours++; }
 if( x < cellsPerRow ) { if( cellMap[x+1][y] ) neighbours++; }
 if( x < cellsPerRow && y < cellsPerColumn ) { if( cellMap[x+1][y+1] ) neighbours++; }

 if( neighbours == 2 || neighbours == 3 ) return true;
 else return false;
}

Nella funzione calculateNextStage(), dopo aver copia in tempCellGrid il contenuto di cellGrid, si richiama la funzione fillCell(int x, int y) che riempe su schermo la cella corrispondente alla coordinate passate come argomenti. Ora che si ha un visione di insieme sul funzionamento del programma ecco la lista delle funzioni:

//funzioni principali
bool MainLoop();
bool cellSurvives(int x, int y);
bool cellBecomesAlive(int x, int y);
void calculateNextStage();
void getInitGridConfig();            //permette all'utente di riempire i quadratini col mouse prima di iniziare

//funzioni di supporto
bool initSDL();
bool generateGrid();
void fillCell( int x, int y );

 

Per scaricare il codice  sorgente clicca qui.

Per scarica il binaro per Linux compilato con Gcc da CodeBlocks clicca qui.


Written by barcadero

6 marzo 2011 a 10:58 pm

2 Risposte

Subscribe to comments with RSS.

  1. […] Programmare il gioco della vita di Conway […]

  2. L’ha ribloggato su Googlando Italia.

    amministratored

    28 aprile 2014 at 6:36 pm


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: