Nota: questo post fa parte di un articolo suddiviso in 4 sezioni:
Algoritmo
Iniziamo ora a pensare come calcolare le due informazioni che ci servono per calcolare se la cellula sarà viva o morta nella prossima generazione:
- stato della cellula nella generazione corrente
- somma S delle cellule vive intorno ad essa
Stato della cellula corrente
Riprendendo la notazione introdotta nel post precedente, supponiamo di avere il byte R che ospita la riga di cellule.
Se stiamo considerando il bit con indice N, un'operazione di AND bit a bit tra il byte R e 2N restituirà due possibili valori:
- 0 (se il bit con indice N è 0 su R)
- 2N (se il bit con indice N è 1 su R)
Nell'esempio in figura N=3, calcoliamo 23 e facciamo l'operazione (R&8): in base al valore del bit X, otterremo 8 oppure 0.
Se vogliamo un risultato che sia 1 per cellula viva e 0 per cellula morta, l'operazione completa sarà:
bitN = (R&2N)/2N
Questa informazione mi è utile anche al fine di stampare a video lo stato della cella, continuando nel ciclo fino alla fine del byte, quando dovrò andare a capo prima di iniziare il byte successivo.
Nota implementativa: in BASIC, l'operazione di divisione può essere sostituita con un'operazione di confronto: l'espressione (R&2N)=2N restituisce 1 se i due membri dell'uguaglianza sono uguali, 0 altrimenti.
Somma delle cellule vive
Passiamo ora al calcolo delle cellule vive intorno al bit corrente.
Iniziamo con la premessa che ora dovremo gestire non il solo byte R ma anche il precedente ed il successivo sulla griglia; compreso questo, il discorso non si discosta molto da quanto visto prima.
Dovremo considerare non solo il bit in posizione N, ma anche il precedente ed il successivo.
Usiamo le variabili di tipo byte offerte dal dispositivo per i nostri "moltiplicatori" e battezziamo:
O=2N+1 P=2N Q=2N-1
Dovremo però gestire due casi limite: quando N=0, Q dovrà essere 128 (perché la griglia è illimitata lateralmente)
Nel caso opposto, quanto N=7, O dovrà essere 1.
La somma delle cellule vive intorno al bit corrente comprende i contributi dati dai 3 byte:
per V= byte superiore, avremo un contributo pari a:
(V&O)/O+(V&P)/P+(V&Q)/Q
per il byte R avremo un contributo:
(R&O)/O+(R&Q)/Q
infine per V= byte inferiore (nuovamente) un contributo:
(V&O)/O+(V&P)/P+(V&Q)/Q
La somma dei tre contributi sarà il risultato del calcolo voluto.
Mettiamo insieme i pezzi
Con queste informazioni, vado a strutturare il programma BASIC come segue:
10 M020000000000082818000000 'inizializzazione griglia 8+8x8+8
20 CLR 'svuoto schermo
30 FOR A=$0200 TO A+7 'inizio ciclo sui bytes in memoria
40 P=0 'inizializzo moltiplicatore bit centrale
50 T=0 'inizializzo byte prossima generazione
60 FOR N=0 TO 7 'inizio ciclo sui bit (0->7)
70 GOSUB 1000 'subroutine di calcolo moltiplicatori
80 V=PEEK A 'carico il byte superiore dalla RAM
90 S=(V&O)/O+(V&P)/P+(V&Q)/Q 'contributo del byte superiore
100 V=PEEK A+1 'carico il byte centrale dalla RAM
110 R=V 'copio il byte centrale su R
120 S=S+(R&O)/O+(R&Q)/Q 'contributo del byte centrale
130 V=PEEK A+2 'carico il byte inferiore dalla RAM
140 S=S+(V&O)/O+(V&P)/P+(V&Q)/Q 'contributo del byte inferiore
150 U=(R&P)=P 'U=1 se attuale cella piena, 0 se vuota
160 PRINT U; 'stampo 1 o 0
170 T=T+P*(S=3) 'aggiungo al byte T l'informazione se nella
180 T=T+P*(S=2)*U 'prossima generazione il bit N sarà 1 o 0
190 NEXT N
200 PRINT "" 'vado a capo
210 C=A+10
220 ......
500 GOTO 20 'torno all'inizio
1000 O=128*(N=0) 'subroutine aggiornamento moltiplicatori
1010 O=O+P 'O = moltiplicatore bit a sx
1020 P=1<<N 'P = moltiplicatore bit centrale 1030 Q=(N=7) 'Q = moltiplicatore bit a dx1040 Q=P*2+Q
1050 RETURN 'fine subroutine
Il programma richiede alcune osservazioni:
- Alla riga 10 c'è una istruzione, specifica del STM8 BASIC, che carica all'indirizzo $0200 i valori esadecimali che seguono, raggruppati per byte (due cifre esadecimali ogni byte). L'istruzione inizializza la matrice con un glider, come mostrato in una figura nel secondo post.
- Alla riga 1020 c'è l'operatore "<<" che rappresenta lo shift a sinistra dei bit dell'operando di sinistra, di tante posizioni quanto vale il secondo operando
- Ho ritenuto opportuno calcolare, per ogni N, i moltiplicatori O,P e Q una sola volta ed utilizzarli per i tre byte. Il calcolo dei moltiplicatori viene fatto nella subroutine evidenziata in giallo alla riga 1000.
- La stampa dello stato della cella corrente, poiché viene fatto da sinistra verso destra, farà apparire sullo schermo una griglia "allo specchio", dove il bit meno significativo viene stampato più a sinistra e quello più significativo a destra.
- alle righe 170 e 180 si trova una moltiplicazione in cui un operando è un'operazione di confronto. Il significato di questa notazione è che se l'uguaglianza è verificata, l'operando vale 1; se non è verificata, vale 0. In particolare la riga 180 significa: al valore T viene sommato P se S è uguale a 2 e se U è uguale ad 1. Ricordiamo che U è lo stato della cellula corrente (1=viva, 0=morta) - si veda la riga 150.
- Il programma non può essere inserito così sul dispositivo stm8: occorre eliminare completamente i commenti e riassegnare i numeri di riga in modo da ridurre al massimo i byte utilizzati.
Bonus content
Esempio di esecuzione
Codice sorgente
1 M020000000000082818000000
2 CLR
3 FOR A=$0200 TO A+7
4 P=0
5 T=0
6 FOR N=0 TO 7
7 GOSUB 90
8 V=PEEK A
9 S=(V&O)/O+(V&P)/P+(V&Q)/Q
10 V=PEEK A+1
11 R=V
12 S=S+(V&O)/O+(V&Q)/Q
13 V=PEEK A+2
14 S=S+(V&O)/O+(V&P)/P+(V&Q)/Q
15 U=(R&P)=P
16 PRINT U;
17 T=T+P*(S=3)
18 T=T+P*(S=2)*U
19 NEXT N
20 PRINT ""
21 C=A+10
22 POKE C,T
23 NEXT A
24 FOR B=$0201 TO B+7
25 P=PEEK B+9
26 POKE B,P
27 NEXT B
28 P=PEEK $020A
29 POKE $0209,P
30 P=PEEK $0211
31 POKE $0200,P
32 SLEEP 1
33 GOTO 2
90 O=128*(N=0)
91 O=O+P
92 P=1<<N
93 Q=(N=7)
94 Q=P*2+Q
95 RETURN
Oscillatore
provate ad inizializzare la griglia con questa configurazione:
1 M0200000000007E0000000000
Doppio glider
provate ad inizializzare la griglia con questa configurazione:
1 M02000020A06000020A060020
Nessun commento:
Posta un commento