Party Planner – LudoProgrammazione su 6502/6510 (#05)

(Articolo di Emanuele Bonin)

PartyPlanner_Sorgente (file .asm)

Party Planner

Sinceramente non ho idea se l’immagine che vedete in testa di questo articolo vi susciti qualche emozione, ma a me ha sempre fatto un effetto misto di sorpresa e ammirazione essendo associata ad un articolo che non ho mai scordato. L’articolo in questione si trovava nel numero di novembre del 1987 di “Le Scienze” (traduzione italiana di Scientific American), l’articolo è stato scritto dal grande A.K.Dewdney, il quale non ha bisogno di presentazioni. Nell’articolo Dewdney ha descritto come creare un programma in grado di simulare le interazioni umane ad una festa. Questa cosa mi ha affascinato sin da quando, “giovine”, imberbe ed aspirante nerd, lo lessi la prima volta e riuscii a riprodurlo in un C64,
programmando con l’amato Basic. Col passare del tempo lo riscrissi anche in altri linguaggi e su computer più veloci, se non altro per dare un po’ di sprint al party, ora sono tornato all’adorato biscottone color crema (emulato sigh), ma stavolta utilizzando l’assembly.

Let’s party

Un momento della festa virtuale

“Recentemente ho dato un ricevimento a cui non ho potuto partecipare di persona.”, così iniziava Dewdney sul suo bellissimo articolo, e fu dopo aver letto quelle parole che decisi di dare anch’io il mio primo ricevimento, ora, con altri mezzi, ho dato un altro ricevimento, ma, al contrario di Dewdney, ho trovato il modo per essere presente in esso. Ho quindi organizzato una festa ed ho invitato tutta la redazione di 8BRPI. Il fine ultimo di “Party Planner” (o PP, così chiamerò il programma) è quello di dare un’idea di come potrebbe svolgersi la festa. Le simpatie e le antipatie tra le persone sono cosa normale e squisitamente umana, e saranno proprio questi sentimenti che guideranno i movimenti della festa, le persone tenderanno ad avvicinarsi tra di loro se si conoscono o provano attrazione, oppure si allontaneranno in casi totalmente opposti o ancora si rincorreranno se sussistesse una sorta di antipatia/simpatia asimmetrica.
Come codificare tutto questo con una sequenza di fredde istruzioni all’interno di PP ? Possiamo iniziare con il decidere di assegnare una distanza “ideale” a cui un’ospite vuole stare rispetto ad un altro ospite presente al party e quindi quantificare di “disagio” che il primo ospite proverà nel caso in cui la distanza con l’altro ospite si discosti da quella ideale. Quindi in base al disagio il nostro ospite potrà decidere di allontanarsi o avvicinarsi rispetto all’altro ospite. Naturalmente questo ragionamento va fatto per ogni componente della festa.
La festa si terrà all’interno di una stanza virtuale, disegnata sullo schermo in bassa risoluzione, ogni ospite occuperà lo spazio di un carattere e potrà muoversi liberamente, facendo un passo, su una delle otto caselle a disposizione che fanno da contorno alla sua posizione, oppure potrebbe decidere di rimanere fermo.

Calcolare il “disagio”

Per calcolare il disagio che una persona, ad esempio Fabrizio, prova rispetto ad un’altra persona, basterà innanzitutto calcolare la distanza effettiva tra le due persone e semplicemente sottrarla alla distanza ideale che Fabrizio vorrebbe mantenere con l’altro, non tenendo conto del segno. Fabrizio deve fare i conti anche con gli altri ospiti, per i quali ha altre distanze che vorrebbe mantenere, quindi il disagio totale di Fabrizio sarà la somma dei singoli disagi rispetto ad ogni altro ospite. Con i calcoli siffatti vien da sé che il disagio non potrà mai essere negativo, al massimo sarà 0 (nel caso in cui tutte le distanze ideali siano state rispettate). Ora Fabrizio dovrà decidere dove e se spostarsi (ammettendo un certo disagio nell’attuale posizione), per sciogliere questo nodo, Fabrizio, non dovrà fare altro che ripetere il calcolo sopra descritto come se immaginasse di essere di volta in volta in ognuna delle otto posizioni adiacenti, per poi scegliere alla fine quella che gli procurerà il disagio minore e se il disagio fosse minore anche del disagio attuale, Fabrizio compirà un passo verso quella nuova posizione.

Vi sono da aggiungere un paio di elementi al calcolo del disagio, il primo è il tavolo, ogni festa che si rispetti ha un tavolo con le cibarie e le bevande, ed ogni ospite dovrà fare i conti anche con il tavolo, il quale è composto da una serie di caratteri adiacenti che formano un rettangolo, quindi anche con questo elemento ci sarà da considerare una distanza ideale.

Inoltre potrebbero esserci alcuni ospiti che sentono indifferenza rispetto a qualche altro ospite, in questo caso si potrà tranquillamente evitare il calcolo del disagio rispetto all’altro ospite.

Gestione delle distanze

La distanza tra due punti in un piano cartesiano è data da dove (x1,y1) e (x2,y2) rappresentano la coppia di coordinate dei due punti considerati, nel nostro caso sono le coordinate dello schermo che ci dicono dove si trova un’ospite. La prima cosa chiara appena si prende in mano questa formula è che si avrà a che fare con numeri con la virgola, per i fini di PP possiamo evitare l’uso della radice quadrata (e quindi non doverci impegolare con l’algoritmo di Bombelli per esempio) e considerare i quadrati delle distanze. Questo naturalmente farà lievitare i numeri interi con cui si avrà a che fare, quindi per esprimere una distanza (o meglio il suo quadrato) non ci basterà un byte ma dovremo utilizzare una word, poco male, l’altra prospettiva era meno alettante.

Tabella delle distanze ideali su tre ospiti, la diagonale maggiore indica le distanze ideali del tavolo

Dovendo codificare le distanze ideali di ogni ospite rispetto ad a ogni altro ospite ed al tavolo, a rigor di logica, dovremmo valorizzarle (prima che il programma parta) in una tabellina con un certo numero di righe intestate ognuna ad un ospite e una serie di colonne anch’esse intestate una ad ogni ospite più una colonna aggiuntiva  intestata al tavolo. In una tabella rettangolare così concepita avremmo che le caselle identificate da intestazione riga/colonna uguali(la diagonale) saranno sempre vuote in quanto una persona (a parte casi di mai svelata ubiquità) non avrà scelta nella distanza ideale da mantenere con se stessa, quindi per ottimizzare le cose, useremo una tabellina quadrata in cui la diagonale maggiore conterrà la distanza da mantenere con tavolo.

La gestione di una tabella come quella descritta implica che venga riservata da qualche parte un blocco di memoria contiguo sufficientemente ampio. Nel nostro caso abbiamo 12 (potenziali) ospiti per un totale di 144 words quindi 288 bytes.

Inizializzazione di Party Planner

Alla partenza del nostro programma organizzatore di eventi, dovremo iniziare con il costruire la stanza, tavolo compreso e quindi inserirvi all’interno gli ospiti. Per la visualizzazione della stanza e del tavolo ci serviremo di alcune routine già belle e pronte presenti all’interno del nostro C64, le routine del KERNAL (non è un errore di scrittura, il nome è l’acronimo di Keyboard Entry Read, Network, And Link ), una sorta di moderne API di sistema ante litteram, d’altronde è inutile reinventare la ruota avendola già a disposizione.
All’interno di Party Planner viene fatto uso di alcune di queste routine, codificate con dei nomi comunemente riconosciuti, ad ognuno di questi nomi corrisponde un indirizzo, che costituisce il punto di ingresso della routine, richiamabile con il comando jsr:

CLEAR   = $E544 ; pulizia dello schermo
CHROUT  = $FFD2 ; visualizza un carattere sullo schermo
STROUT  = $AB1E ; visualizza una stringa sullo schermo
PLOT    = $E50A ; Posiziona/legge la posizione del cursore

CLEAR, come descritto nello spezzone di codice, sgombrerà lo schermo, mentre CHROUT, STROUT visualizzeranno, in ordine un carattere e una stringa a partire dalla posizione corrente del cursore, posizione che possiamo modificare tramite PLOT.
In questa limitata selezione di routine solo CLEAR non ha bisogno di impostazioni particolari, per le altre bisognerà impostare alcuni registri prima della chiamata. All’interno di PP sono state costruite delle routine che “wrappano” le routine del KERNAL  per combinarne l’utilizzo:

; visualizza il carattere presente in A
        ; alle coordinate x,y (dei registri Y,X)
PrintSingleCharXY   
        jsr SetCursorPosition
        jsr PrintSingleChar
        rts

        ; posiziona il cursore nella posizione x, y
        ; impostata rispettivamente nei registri Y,X
        ; non è un errore, i nomi dei registri NON rispecchiano 
        ; i nomi delle coordinate
SetCursorPosition
        pha                 ; salvo l'accumulatore
        clc                 ; pulizia del carry per impostare la posizione
        jsr PLOT
        pla                 ; riprendo il vecchio valore dell'accumulatore
        rts

BckA    byte $00            ; Byte di comodo per salvare il valore dell'accumulatore'
        
        ; visualizza il carattere presente in A
PrintSingleChar
        sta BckA            ; mi salvo l'accumulatore in un byte di comodo
        txa                 ; per poter poi salvare
        pha                 ; nello stack il registro X
        lda BckA            ; ripristino il valore di A
        ldx #$00            ; azzero il registro X, è necessario
        jsr CHROUT          ; per poter chiamare la funzione del kernal CHROUT
        pla                 ; riprendo il valore originario 
        tax                 ; passando dall'accumulatore  
        lda BckA            ; mi riprendo il valore originario di A

La chiamata a STROUT viene fatta all’inizio del programma per la visualizzazione del titolo:

Title   text "party planner (a.k. dewdnay)", $00

        ldy #LUX
        ldx #$00
        jsr SetCursorPosition
        lda #<Title
        ldy #>Title
        jsr STROUT

Per la sua utilizzazione dovremo posizionare il cursore opportunamente, dopodiché impostare i registri X e A rispettivamente con LSB e MSB dell’indirizzo di memoria da cui parte la stringa che si vuole visualizzare, la quale dovrà terminare con il carattere marcatore di fine stringa, \$00.

Una volta creata la stanza ed il tavolo, le loro coordinate sono state codificate con delle costanti all’inizio del listato, dobbiamo disporre gli ospiti all’interno della stanza. Per fare questo ho optato per una iniziale disposizione Random.

Tipica forma d’onda del rumore bianco

Come saprete, di norma i numeri generati “random” da un computer, in realtà si basano su calcoli in cui entrano in gioco logaritmi e numeri iniziali detti “semi”, quindi alla fin fine il termine “casuale”, almeno per me, non è proprio aderente alla realtà. Il nostro C64 ci mette a disposizione una reale (o perlomeno più credibile) fonte di numeri casuali, un generatore di rumore bianco. Per generare il rumore bianco sfrutteremo la voce 3 del SID (il chip dedicato al suono), senza renderlo udibile, per fare questo bastano queste poche righe di codice:

InitRandom
        lda #$ff            ; Imposta la frequenza d'onda al massimo
        sta $d40e           ; LSB Frequenza Voce 3
        sta $d40f           ; MSB Frequenza Voce 3
        lda #$80            ; Forma d'onda del rumore
        sta $d412           ; nel registro di controllo della Voce 3 
        rts

Una volta richiamata la routine InitRandom, e fintantoché non verrà interrotta la generazione dell’onda di rumore, per avere un numero casuale basterà leggere il valore all’indirizzo \$BDCD (label NBROUT del listato), che continuerà a variare casualmente nell’intervallo \$00 – \$FF. Per limitare i valori casuali, facendoli rientrare entro i limiti delle dimensioni della stanza, possiamo dividere il numero casuale ottenuto per l’ampiezza del range a cui si vuole limitare il numero, prendendo come risultato il resto intero della divisione. Per esempio se ottenessimo il numero 42 come valore casuale e volessimo limitarlo in un range di valori che possono andare da 0 a 29,  basterà eseguire la divisione intera 42/30 = 1 con il resto di 12, quest’ultimo sarà il nostro valore casuale “limitato”. Questa limitazione verrà fatta dalla routine GetLimitedRandom, la quale richiama la routine DivInt (meritevole di un approfondimento) che eseguirà la divisione tra due interi in maniera efficiente.

L’efficienza nella divisione (Routine DivInt)

Diagramma di flusso per la divisione intera fatta sfruttando le potenze di due

Per eseguire una divisione tra due numeri sarebbe sufficiente un loop controllato che conta quante volte possiamo sottrarre al dividendo il divisore fintantoché il dividendo rimane maggiore del divisore. In questa maniera se ci trovassimo a fare la divisione 420/9 il nostro loop verrà eseguito 46 volte.
Vi è un modo più “economico” di affrontare il problema, infatti in assembly possiamo sfruttare le istruzione ASL (Arithmetic) e LSR (Logical Shist Right) le quali eseguono lo spostamento a sinistra e a destra di un bit all’interno dell’argomento passato, questo equivale a moltiplicare o dividere per due. Bene, ma se devo dividere per 9 come posso fare ?
L’algoritmo si basa sul fatto che potendo sfruttare agevolmente le potenze di 2, invece di sottrarre sempre il divisore nudo e crudo, possiamo sottrarre il divisore opportunamente moltiplicato per una potenza di 2 fintantoché questo sarà possibile. Raggiunta la potenza di 2 massima da sfruttare per la sottrazione, calcoliamo il resto e riprendiamo il ciclo di sottrazioni fino ad ottenere un resto inferiore al divisore, il quale resto, sarà proprio il resto intero della divisione. Il quoziente intero invece si otterrà sommando potenze utilizzate.
Sembra tutto molto complicato ma il diagramma di flusso potrà chiarire le idee. Utilizzando questo algoritmo riusciamo  a diminuire il numero di sottrazioni necessarie per arrivare al risultato. Naturalmente questo risparmio ha un piccolo costo in termini di complessità (ma questo certo non ci spaventa) e di lunghezza del codice. La routine sarà tanto più efficace, rispetto ad un algoritmo standard, quanto più avremo a che fare con grandi numeri.

Routine Principale

Riassumendo i concetti fin’ora espressi possiamo scrivere, in un pseudo linguaggio, il corpo principale del programma:

Per ogni OSPITE del gruppo {
  Poni DISAGIO_MINIMO = (numero enorme)
  Poni NUOVA_POSIZIONE= (nessuna)
  Per ogni POSIZIONE in cui OSPITE potrà spostarsi {
    Calcola DISAGIO rispetto agli altri ospiti
    Se DISAGIO < DISAGIO_MINIMO {
      NUOVA_POSIZIONE   = POSIZIONE
      DISAGIO_MINIMO    = DISAGIO
    }
  }
  Sposta OSPITE su NUOVA_POSIZIONE
}

Il calcolo del disagio di un ospite, come già accennato, non è altro che un numero ottenuto confrontando le distanze (o meglio i loro quadrati) reali e quelle ideali, presenti in una tabella a doppia entrata. Per poter accedere a questa tabella abbiamo a disposizione un numero di riga (Ospite da analizzare) ed un numero di colonna (Ospite dal quale prendere le “misure”). Il compito è quello di ottenere il valore della cella all’incrocio dei due valori sopra indicati, per fare questo dobbiamo “spianare” la tabella e considerarla come realmente è, e cioè una successione di indirizzi di memoria. Sapendo che la tabella come è stata strutturata contiene 12 colonne (da 0 a 11) basterà un elementare calcolo per ottenere la posizione “spianata” (Offset) rispetto al primo valore della casella in alto a sinistra:

Offset = Riga*12 + Colonna

Naturalmente per ottenere l’indirizzo di memoria corretto dovremo sommare all’offset l’indirizzo di memoria della prima casella in alto a sinistra e cioè la label DistOpt del nostro listato.
Avendo a che fare con l’operazione di moltiplicazione, che per di più verrà usata molte volte a causa della natura del programma (o perlomeno così come l’ho scritto io), verranno agevolati i calcoli moltiplicativi usando un algoritmo ottimizzato per la moltiplicazione, che sfrutta anch’esso l’utilizzo delle istruzioni ASL e LSR. Similmente a come è stato fatto per la divisione intera, diminuiremo il numero di somme necessarie scomponendo idealmente uno dei due fattori in somme di potenze di due.
Per esempio se dovessimo eseguire la moltiplicazione di 420*420, con un algoritmo tradizionale ci ritroveremmo a fare 420 somme consecutive, se invece scomponessimo uno dei due fattori ad esempio 420 (non avevo tanta scelta) possiamo vedere che 420 = 2^8+2^7+2^5+2^2, quindi con un ciclo di calcolo in cui eseguire gli opportune ASL e somme progressive ci ritroveremmo a concludere il lavoro con più efficienza. Vi lascio il compito si costruirvi il diagramma di flusso per compiere queste operazioni. In PP il codice di moltiplicazione si trova nella routine Multiply.

Conclusioni

Nonostante la semplicità dell’algoritmo per movimentare gli ospiti della festa, Party Planner, userà molti cicli di clock per ogni ospite, e tali cicli aumenteranno all’aumentare degli ospiti. Per farvi un’idea, potete giocare con il valore della costante GuestNum, la quale indica quanti ospiti parteciperanno alla festa, diminuendo il suo valore, i movimenti dei nostri ospiti saranno più veloci. Il codice può essere, come sempre, ottimizzato in molte parti, ad esempio non viene memorizzato il disagio “attuale”, costringendo Party Planner a ricalcolarselo ogni volta, questo farebbe risparmiare un giro di calcolo di disagio per ogni ospite presente alla festa.

Per rendere PP più accattivante ho ridefinito i caratteri degli ospiti, la ridefinizione dei caratteri è stata indicata dagli omologhi in carne ed ossa, così come le distanze ideali presenti nella tabella DistOpt.

Oltre a DistOpt, nel listato ho inserito (remmandole) alcune configurazioni “estreme” delle distanze ideali, giusto per vedere i balletti che avrebbero fatto gli ospiti durante la festa in casi di interazioni sociali molto particolari.

Nella speranza che Party Planner vi sia piaciuto ma soprattutto nella speranza che vi sia stata utile questa lettura, vi saluto.

Have your say