Alieni, piccioni e palline da golf (parte 2)
Autore: Raffox - Pubblicato il 24-08-2017.(© https://ready64.org - Versione Stampabile. Riproduzione Vietata.)
Antonio Savona prosegue la sua interessantissima panoramica esplicativa su altri aspetti tecnici, di non facile risoluzione per altro, che ha affrontato durante lo sviluppo di Planet Golf.
Nella seconda parte di questo mini-diario dello sviluppo di Planet Golf vorrei parlare dei vantaggi di cui godono i retrocoder oggi rispetto ai pionieri che ci hanno fatto sognare negli anni '80 e '90, lavorando con strumenti infinitamente più rozzi di quelli di cui disponiamo ora. Non mi soffermerò sui tool di sviluppo veri e propri, quali cross-compiler, strumenti grafici/audio eccetera, i cui benefici sono ovvi e sui quali sono già disponibili ampie panoramiche altrove, ma spenderò qualche parola sulla facilità con cui ora possiamo coniugare tecniche di programmazione e strumenti moderni per vincere le limitazioni del nostro adorato ma obsoleto hardware e creare con relativa semplicità cose che non avremmo potuto realizzare (almeno non senza sforzi notevoli) molti anni fa.
Nel farlo, analizzerò due componenti di Planet Golf non propriamente specifiche del gioco in sé: la schermata di selezione dei pianeti e il codec video utilizzato nell'introduzione.
Menu di selezione dei pianeti
Questa sezione di Planet Golf è stata di gran lunga la parte che ha richiesto il maggior sforzo implementativo di tipo "tradizionale", tipo lavorare di fino con IRQ e NMI (Interruption Request Line e Non Maskable Interrupt, ndr) e sincronizzazioni varie. Per quanto possano apparire fluide e immediate, ci sono parecchie altre cose che succedono "dietro le quinte" quando il giocatore si muove tra i menu, oltre a quelle più evidenti come le animazioni, la musica ecc. Andiamo a esaminarle.
Durante la rotazione tutte le risorse di calcolo del C64 sono impegnate al massimo. L'IRQ gestisce il multiplexer per visualizzare i pianeti, ciascuno dei quali è composto da ben 8 sprite hires per un totale di 40 sprite. L'IRQ inoltre riproduce la musica e si occupa delle animazioni su schermo, come le orbite e i menu lampeggianti. L'NMI si occupa della voce digitalizzata, facendosi carico anche della sua decompressione in tempo reale. Infine il "thread" principale si occupa della decompressione dei dati relativi alla descrizione del pianeta. Infatti tale descrizione nel pannello in basso a destra è una singola immagine bitmap che viene via via copiata nell'apposito riquadro con un offset differente, creando l'illusione dello scrolling.
Nel gioco sono disponibili 5 pianeti in cui giocare, ciascuno con la propria descrizione in forma di immagine bitmap. Ovviamente tutte queste informazioni grafiche non potrebbero risiedere contemporaneamente in memoria senza sottrarre parecchio spazio al resto dei dati e del codice. Si tratta però di immagini fortemente comprimibili, quindi Planet Golf tiene queste strutture in memoria in forma compressa. Quando il nostro sistema planetario immaginario ruota, il gioco decomprime la bitmap che userà nella configurazione di destinazione. Quindi, per esempio, se ci si sposta verso Marte dalla Terra, durante la rotazione il gioco cancellerà la bitmap con le informazioni relative al pianeta terra e decomprimerà al suo posto la bitmap con la descrizione di Marte. La rotazione dei pianeti è stata "rallentata" ad arte per far sì che questo processo potesse compiersi esattamente durante il tempo di rotazione stesso e ha richiesto ottimizzazioni notevoli, paragonabili a quelle che abbiamo visto per la fisica nell'articolo precedente.
Con un sistema di processi concorrenti così complesso da gestire, il multiplexer per la moltiplicazione degli sprite ha richiesto un approccio diverso dal solito. Tipicamente, quando si hanno sprite liberi di muoversi verticalmente sullo schermo, come in questo caso, si ricorre a multiplexer generici come quelli utilizzati nei giochi della Ocean a partire dalla fine degli anni '80. Questi multiplexer consentono al programmatore di avere a disposizione un numero di sprite "virtuali" che possono essere posizionati a piacimento nello schermo. Il Commodore 64 si occupa del calcolo dei raster-split in tempo reale per poter riutilizzare più volte gli 8 sprite reali. Questi calcoli tuttavia richiedono parecchio tempo macchina (in gergo tecnico "cicli macchina") e, come detto, nel menu di Planet Golf non ne rimane molto: un approccio del genere non avrebbe certamente funzionato. Veniamo quindi al primo esempio di come strumenti di calcolo moderno possano essere utilizzati per semplificarci la vita.
Per temporizzare i raster-split, prima ancora di programmare il menu di selezione del pianeta sul C64 l'ho creato in una sandbox scritta in Python su un PC. Ovviamente in un ambiente di sviluppo del genere le limitazioni del Commodore 64 non esistono e sono sufficienti pochi minuti per programmare il menu (sigh!). In questa preview ho pensato di riprodurre lo schermo del C64 in ogni sua caratteristica: dalla risoluzione, ai bordi, passando per il refresh del video. Vi avevo già raccontato di un approccio simile in occasione dello sviluppo di P0 Snake, allo scopo di ricercare la manovrabilità ottimale del serpente. In questo caso la simulazione su PC mi è servita per precalcolare i raster-split ottimali.
In questo modo mi è stato possibile disporre i pianeti ciascuno all'interno della propria orbita in maniera tale che non vi fossero sovrapposizioni verticali e che, per usare un gergo calcistico, ci fosse sempre un minimo di "luce" tra gli sprite in modo da poter sfruttare quel tempo-raster per l'effettivo multiplexing. Il programma parte da una configurazione in cui i pianeti sono disposti a una distanza angolare costante (360/5°), e poi applica piccolissime correzioni in modo da massimizzare la distanza verticale minima tra due pianeti consecutivi per ciascuno dei fotogrammi della rotazione. Il risultato è quello visibile nella figura, che mostra la simulazione opportunamente rallentata e il il menu vero e proprio.
Come si può notare, c'è sempre qualche pixel di distanza tra i pianeti, come evidenziato dalla linea rossa, e questo spazio serve al multiplexer per prendere gli sprite HW precedenti alla riga e posizionarli dopo la riga. Pur con questa disposizione ottimale, a causa del timing compromesso dalla riproduzione della voce campionata, questo spazio non sarebbe comunque sufficiente a fare un buon lavoro se applicassimo un multiplexer generico. È per questo che il prototipo genera automaticamente, per ogni fotogramma, la lista precalcolata degli split ottimali, la quale viene salvata in una tabella a tre dimensioni. Tale tabella viene poi data in pasto direttamente al sorgente di Planet Golf, in questo modo al multiplexer non è richiesto di svolgere gli onerosi calcoli di ordinamento degli sprite, in quanto questi sono già disponibili in questa tabella, che va semplicemente acceduta! In conclusione tutto il lavoro di multiplexing è fortemente semplificato (al costo di qualche KB di tabella precalcolata) e diventa quindi possibile svolgerlo nonostante gli altri calcoli onerosi che avvengono in parallelo.
Codec Video
Il secondo argomento che voglio portare alla vostra attenzione è quello del codec video. Tra gli extra di Planet Golf c'è un'introduzione che racconta l'evoluzione della tecnologia dalle missioni Apollo, che hanno portato l'uomo sulla Luna, al primo torneo interplanetario di Golf che si svolge nel 38911 (la data non è certo stata scelta a caso, ndr), anno in cui è ambientato Planet Golf. Questa parte riproduce audio e video digitalizzati. Spiegare nei dettagli la tecnica di compressione (e in particolare come sia stato possibile far girare il video, l'audio e i caricamenti da floppy allo stesso tempo), renderebbe questo articolo troppo lungo e noioso, mi limiterò quindi a descrivere brevemente alcune componenti della sola compressione video, che è forse la parte più interessante e per la quale ho dovuto scrivere un vero e proprio encoder, benché molto rudimentale e limitato.
Di seguito potete vedere una delle sequenze video (opportunamente ridotta in colori e risoluzione allo scopo di essere visualizzata dal Commodore 64), pronta per l'encoding.
Si tratta di circa 100 fotogrammi a schermo intero. Si potrebbe pensare di memorizzarli come singole immagini bitmap. Tuttavia il Commodore 64 richiede circa 8Kb per una bitmap, e quindi ci troveremmo a dover tenere su disco 800Kb solo per questa sequenza, cosa impossibile visto che un floppy disk può contenere solo 170Kb. Questo approccio non fa decisamente al caso nostro. Un sistema più realistico consiste nell'utilizzare la modalità a set di caratteri hires. Come noto, il Commodore 64 consente la ridefinizione dei set di caratteri, a patto che questi siano un massimo di 256. In questo modo ogni carattere viene indirizzato con un byte e uno "schermo", che è composto da una matrice di 40x25 caratteri, occupa esattamente 1000 byte. Supponiamo di poter utilizzare un set di caratteri unico per riprodurre questa sequenza, potremmo pensare di memorizzare questi 100 fotogrammi da 1000 caratteri basandoci su quel charset, per un totale di 100.000 caratteri, e riprodurre il filmato semplicemente scrivendo tali caratteri a schermo. In questo modo la sequenza occuperebbe 100.000 byte, cioè di 100kb. Ancora troppi, visto che il gioco ha diverse sequenze animate, ma sarebbe già un inizio! Quanti sono i caratteri unici di questa sequenza? Se non avete la pazienza e l'occhio fine per contarli, posso dirvi che sono circa 8500, cioè ben più dei 256 che possiamo utilizzare. Questo renderebbe l'approccio di cui sopra impraticabile. È a questo punto che un programmatore avrebbe dovuto alzare bandiera bianca negli anni '80.
Invece l'approccio che ho potuto utilizzare, grazie agli strumenti di calcolo moderni, è una derivazione di una pratica piuttosto comune nella compressione del video digitale: il concetto di Vector Quantization.
Ciò nasce dall'osservazione che, per quanto diversi, molti di questi 8500 caratteri saranno almeno simili tra di loro. Se due caratteri differiscono, per esempio, di un solo pixel adiacente, ha senso rappresentarli entrambi? Probabilmente no. L'idea è che si possono tollerare errori e imperfezioni grafiche, a maggior ragione visto che i caratteri compaiono sullo schermo solo per una frazione di secondo prima di cedere il posto al fotogramma successivo, rendendo quindi veramente difficile scorgere eventuali approssimazioni! Il nostro obiettivo diventa quindi quello di individuare un set di 256 caratteri che sia il più possibile "rappresentativo" degli 8500 caratteri che compongono questa animazione. In Data Science gli algoritmi che effettuano tali riduzioni appartengono alla famiglia degli algoritmi di Clustering. Uno dei più popolari, e decisamente il più adatto per questo caso, si chiama K-means. Partendo da queste osservazioni, non mi è restato altro da fare che implementare una funzione di comparazione tra caratteri e successivamente applicare l'algoritmo K-means per ottenere il set di 256 caratteri ideale a riprodurre questa sequenza. Se siete curiosi di osservarne l'aspetto... eccolo qui:
È molto difficile che questo set di caratteri ridefiniti appaia comprensibile all'osservatore, però con questi 256 tasselli è possibile comporre in maniera abbastanza fedele ciascuno dei fotogrammi dell'animazione in questione.
Il passaggio dai 100Kb necessari alla codifica dei 100 fotogrammi utilizzando questo set di caratteri, ai circa 8kb che occupa la medesima sequenza nel gioco è stato possibile grazie ad un'altra tecnica abbastanza comune nel campo della compressione video, chiamata inter-frame coding.
Dietro questo nome altisonante si nasconde un concetto molto semplice: invece di memorizzare tutti i caratteri di un fotogramma, è possibile memorizzare solo quelli che effettivamente differiscono dal fotogramma precedente. Anche questo calcolo viene svolto dal mio semplice encoder Python. Ci sono poi altre tecniche che ho dovuto applicare al fine di ridurre ulteriormente l'occupazione di memoria, ma le due appena descritte danno l'apporto di compressione maggiore. Ed ecco a voi il risultato finale, così come appare nel gioco:
Come vedete la differenza con l'input è praticamente impercettibile, tuttavia questa sequenza video nel gioco occupa circa 8Kb, per una media di soli 80 byte a fotogramma, contro i circa 800kb che avrebbe occupato se avessimo utilizzato delle immagini bitmap... o se non avessimo avuto a disposizione conoscenze e strumenti di calcolo moderni.
Continua...