Alberi con Scratch (usando le liste)

In questo tutorial impareremo a disegnare un albero binario. Per binario intendiamo un albero che ha due rami ogni nodo.

Premessa: non è un tutorial adatto a chi inizia con Scratch.

Iniziamo un nuovo progetto (File → Nuovo) e rimpiccioliamo il gatto. Usiamo lo strumento “Riduci lo sprite” (in alto al centro) applicandolo al gatto fino a farlo diventare circa abbastanza piccolo.

Programmiamo quindi lo sprite del gatto con un primo script, per fargli disegnare un ramo (Figura 1). Notiamo che inizialmente abbiamo posizionato il gatto in basso al centro e lo abbiamo fatto puntare verso l’alto.

Figura 1

Modifichiamo lo script precedente perché si inclini di 15 gradi a sinistra rispetto alla direzione attuale dello sprite (Figura 2), risolvendo così il problema di disegnare il ramo sinistro della biforcazione.

Figura 2

Copiamo parte del codice precedente per disegnare anche il ramo destro (Figura 3).

Ci accorgiamo però che il ramo prende l’ultima direzione e le ultime coordinate dello sprite (e infatti il gatto disegna il ramo di destra partendo dal punto in cui è terminato il disegno del ramo di sinistra).

Figura 3

Un altro aspetto che non ci piace è che abbiamo del codice duplicato. Tentiamo di rendere più modulare il nostro programma creando un blocco personalizzato (categoria “Altri blocchi”, pulsante “Crea un blocco”) che chiamiamo disegna ramo. Aggiungiamo a questa procedura un parametro, che chiamiamo inclinazione (Figura 4).

Figura 4

Modifichiamo il programma come in Figura 5. Il risultato non cambia, ma il codice è ora organizzato in maniera migliore.

Figura 5

Riflettiamo sul problema che abbiamo di fronte. Il gatto inizia a disegnare il ramo destro dal punto in cui ha terminato di disegnare quello sinistro. Mentre noi abbiamo bisogno che il gatto, prima di disegnare il ramo destro, torni alla direzione e alla posizione che aveva prima di disegnare il ramo sinistro.

Dobbiamo quindi memorizzare questi dati (direzione, posizione x, posizione y) prima che il gatto inizi il disegno del ramo sinistro.

Vogliamo poter memorizzare questi dati, leggerli e poi cancellarli quando non ci servono più. Come?

In Scratch esiste una struttura di dati chiatama “lista”. Creiamone una (categoria “Variabili e Liste”, pulsante “Crea una Lista”) chiamandola stack (Figura 6).

Modifichiamo il programma cancellando il contenuto della lista appena si clicca sulla bandierina verde.

Figura 6

Lo stack è una struttura dati molto ricorrente nel mondo della programmazione. Funziona come una pila di piatti nelle cucine di un ristorante. Il piatto che per primo viene preso dal cameriere è l’ultimo che è stato appoggiato sulla pila (perché è quello che si trova più in alto).

Ora modifichiamo il secondo script del gatto aggiungendo tre blocchi che servono a memorizzare posizione x, posizione y e direzione prima che lo script disegni il ramo (Figura 7).

Figura 7

Eseguiamo nuovamente il programma e vediamo che la situazione non è migliorata, ma almeno la memorizzazione dei dati funziona (Figura 8).

Figura 8

In effetti non basta memorizzare i dati. Bisogna anche leggeri dopo che il ramo è stato tracciato, come mostrato in Figura 9.

Notiamo che i dati vengono letti in ordine inverso rispetto a come sono stati memorizzati (come i piatti del ristorante, appunto).

Figura 9

Un nuovo test (Figura 10) ci mostra una situazione un po’ strana. La direzione del ramo di destra ora è giusta, ma non il punto in cui viene disegnato.

Figura 10

Manca qualcosa. Ci siamo limitati a leggere i dati memorizzati in precedenza, ma dopo aver letto un dato, dobbiamo toglierlo dalla pila (come fosse un piatto), altrimenti leggiamo sempre il solito dato (Figura 11).

Il programma ora disegna i due rami in maniera corretta.

Figura 11

Noi, però, vogliamo disegnare due rami per ogni nodo. Far crescere il nostro albero, insomma. Come fare?

Esiste un metodo per risolvere in maniera elegante questo problema. Possiamo utilizzare la “ricorsione”. Ovvero, possiamo fare in maniera che il blocco disegna ramo, chiami se stesso, disegnando un ramo a sinistra e uno a destra dopo che terminato il disegno del ramo precedente.

Sembra semplice, ma la modifica dello script disegna ramo, ci fa ottenere una serie di rami disegnati in cerchio (Figura 12). Perché?

Figura 12

Ciò avviene perché per ogni ramo disegnato, il blocco disegna ramo chiama se stesso e fa disegnare per primo un ramo a sinistra. Poi al termine del disegno chiama se stesso e fa disegnare per primo un ramo a sinistra e così via all’infinito…

Dobbiamo inserire una condizione di terminazione (ad esempio quanti livelli di rami vogliamo).

Modifichiamo il blocco personalizzato aggiungendo un altro parametro numerico, che chiamiamo livello (Figura 13).

Figura 13

Ora possiamo inserire una condizione. Se livello è uguale a 5 (oppure a 4 ecc.), il blocco non fa nulla. Se il valore di livello è inferiore a 5, la procedura funziona come avevamo progettato (Figura 14).

Figura 14

Funziona (Figura 15)!

Figura 15

E se vogliamo disegnare delle foglie, possiamo fare come nell’esempio di Figura 16.

Figura 16