Tauon Barcadero

La formica di Langton

leave a comment »


Un’altro automa cellulare

Come Life di Conway, anche la formica di Langton è un automa cellulare a stati finiti, ovvero possiamo immaginarlo come un “essere vivente” che segue alcune regole preimpostate e in base a queste si evolve. In questo caso particolare, la formica si trova su di una griglia bidimensionale(una matrice) in cui ogni casella(elemento della matrice) può assumere i valori “1” o bianco e “0” o nero. Essa può girarsi di 90 gradi per volta a sinistra o a destra e può avanzare di una casella per iterazione.

Immagine della formica di langton

Formica di Langton

Le regole che l’automa segue a seconda del colore della casella su cui si trova, sono:

Casella Nera:

  1. Gira a destra
  2. Inverti il colore della casella
  3. Avanza di uno nella direzione puntata

Casella Bianca:

  1. Gira a sinistra
  2. Inverti il colore della casella
  3. Avanza di uno nella direzione puntata

L’implementazione

Tutto il codice del programma può essere scaricato qui.

Per scrivere il programma che simula il compormento della formica ho  usato il C++ appoggiandomi alle librerie SDL e SDL_gfx per la grafica, ho “riclicato” alcune delle funzioni che avevo già scritto per Il gioco della vita di Conway, inoltre anche la struttura principale del programma è molto simile, per cui non riscrivo qui il funzionamento del namespace anonimo all’inizio del file ne delle seguenti funzioni: MainLoop(), initSDL(), fillCell( int x, int y ).

enum AntDir {
  ANT_UP = 0,
  ANT_DOWN = 1,
  ANT_RIGHT = 2,
  ANT_LEFT = 3
 };

 //verso in cui è girata la formica
 AntDir antDir = ANT_UP;

 //posizione della formica sulla griglia
 int AntX = cellsPerRow/2 - 1;
 int AntY = cellsPerColumn/2 - 1;

L’enumerazione AntDir è utilizzata per capire verso quale direzione è girata la formica, la variabile di tipo enumerativo che ne conserva il valore è antDir,  nelle variabili AntX e AntY viene memorizzata la posizione attuale della formica nella griglia, inizialmente si trova al centro di essa.

Queste sono le funzioni che compongono il programma:


//funzioni
bool MainLoop();
void calculateNextStage();
void rotateAndMoveAnt( int left );

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

La funzione rotateAndMoveAnt( int left ) come si può intuire si occupa di ruotare la formica a sinistra o destra a seconda che left sia “1” o “0”, inoltre si occupa di invertire il valore della cella, ovvero una cella bianca diventa nera e viceversa, e di far avanzare la formica di una casella nella direzione specificata da antDir.

La funzione calculateNextStage(), già presente nell’articolo sul gioco della vita di Conway, è stata modificata in modo che si occupi di ruotare, invertire il colore della casella e far avanzare la formica utilizzando la funzione rotateAndMoveAnt( int left ) e di colorare le caselle in bianco o nero secondo quanto riportato dalla matrice cellGrid[cellsPerRow][cellsPerColumn].

Per scaricare tutto il codice clicca qui.

Per scarica un binario precompilato per linux clicca qui.

La Simulazione

La situazione di partenza è una griglia completamente bianca e la formica parte esattamente al centro di essa.

Essendo una macchina a stati finiti che segue delle regole ben precise, il comportamento della formica è completamento determinato in questa situazione di partenza, quello che stupisce è però la complessità del “disegno” che viene fuori lasciandola “camminare” per qualche migliaio di iterazioni, infatti il comportamento all’inizio appare casuale se non confuso:

Formica dopo alcune centinaia di iterazioni

Traccia lasciata all'inizio

Formica dopo una decina di migliaia di iterazioni

Formica dopo una decina di migliaia di iterazioni

Questa situazione si protrae per all’incirca 10000 iterazioni quando la formica esce dall’apparente caos in cui stava è inizia a disegnare uno schema ripetitivo di forma longilinea, questo schema come si può ben intuire si ripeterebbe all’infinito, ma per evidenti limiti di memoria( per memorizzare la griglia ) è necessità di mantenere il programma semplice essa non andrà oltre i limiti della finestra.

Il disegno finale che si andrà a formare sarà questo:

Stadio finale della formica

stadio finale della formica

Written by barcadero

15 marzo 2011 a 6:32 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: