Come Pharaoh viveva in 16 megabyte di memoria

Il codice che disegnava unità e tile negli strategici di fine anni Novanta veniva eseguito centinaia di volte per frame: il blitting hardware era già abbastanza economico, ma non lo era ancora abbastanza in termini di memoria, e quel codice toccava quasi ogni pixel che il giocatore vedeva sullo schermo. Forse non era così importante se la risoluzione poteva essere 640×480 (almeno, è su un monitor del genere che ho giocato le prime volte a Pharaoh), e per un codice del genere contava già più la disposizione dei dati in memoria che l’eleganza dell’architettura, anche se, a pensarci bene, chi meglio di quei pionieri poteva parlare di bellezza dell’architettura in 16 megabyte tutti contati.

I giochi sono sempre stati prima di tutto immagine, checché ne dicano i marketer, e una bella immagine in uno strategico ambientato nell’antico Egitto significa migliaia di sprite: case, abitanti, animazioni in otto direzioni, templi, dodici eserciti nemici e monumenti. I monumenti, poi, venivano disegnati con una passata a parte, perché erano grandi e non entravano in tutti gli schermi.

In Pharaoh, sul disco ci sono circa 302 megabyte di sola grafica, e se fate il parsing del file ini del gioco ci troverete il parametro RAM, impostato di default a 15, più o meno quanto ne aveva una macchina media dell’epoca. E c’era anche una modalità «poca memoria» per le macchine sotto i 16 megabyte, se avevate dei modesti 14 megabyte di RAM (come me), in cui il gioco passava forzatamente a 640×480 e semplificava il ciclo di simulazione della città.

Gli strumenti standard dell’epoca si prestavano poco a un compito in cui bisognava tenere in memoria anche tutto ciò che al momento non serviva, così Impressions già ai tempi di Caesar lo risolse con un proprio formato di compressione grafica, che si può descrivere nel modo più semplice come «hack, trucchi e magia nera che fanno risparmiare RAM».

In questo articolo analizzerò questi trucchi, con i numeri dei file reali del gioco e il codice di Tutankhamun, la mia reimplementazione di Pharaoh in C. Il progetto è iniziato circa tre anni fa e finalmente è arrivato al traguardo, cioè a sorgenti comprensibili, e se leggete i miei articoli da tempo vi ricorderete forse che il primo parlava del reverse engineering del motore di Caesar, e quindi... è ora di saccheggiare anche le tombe dei faraoni.

Anche i formati di dati sono strumenti

Blitting: calco dal nome della funzione ddraw che copia istantaneamente una texture precaricata nella scheda video nel punto giusto del back buffer, cioè il buffer dello schermo per il frame successivo. Tecn.: operazione di trasferimento di un’immagine raster da un dispositivo di memorizzazione alla finestra di output sullo schermo. Thanks to 8 street.

Oggi i formati di dati sono verità incrollabili scolpite nel codice, calate dall’alto insieme all’SDK del vendor o della console, e se volete che il vostro modellino si carichi in fretta con il decoder hardware, siate così gentili da limare le parti sporgenti del vostro motore... ma questo è oggi, mentre un tempo i formati di dati erano un ulteriore livello di strumenti, e la gente si inventava il formato adatto a compiti specifici. Nessuno si metterebbe a stringere un dado esagonale con una chiave pentagonale, ma se non sapete che si può fare diversamente, continuerete a cercare di infilare la grafica del gioco in BMP solo perché BMP/PNG si apre nell’editor.

Quali opzioni aveva uno sviluppatore nel 1999 per memorizzare la grafica, e quale prezzo comportava ciascuna? Si poteva prendere una bitmap grezza, l’opzione più ovvia, e allora ogni immagine sarebbe stata un normale rettangolo di pixel, larghezza per altezza per due byte, o quattro. La si può leggere, disegnare con un solo memcpy, e dentro, ahimè, non c’è alcuna magia... in molti facevano così, e lo fanno tuttora.

Ma uno strategico cittadino in isometria (soprattutto quelli vecchi, in 2.5D) è fatto quasi interamente di texture che non sono rettangoli, come la casella di terreno a rombo che nel suo rettangolo 58×30 occupa meno di metà dell’area, mentre tutto il resto sono angoli trasparenti che vanno onestamente memorizzati, visto che la nostra texture è rettangolare.

E poi bisognerà onestamente leggerla dal disco e onestamente saltare tutto il trasparente in fase di disegno, e attorno alla figurina di un abitante che cammina per strada lo sfondo trasparente è ancora di più; se si sommano tutte le immagini che Pharaoh tiene in memoria dopo l’avvio, sotto forma di semplici bitmap, si arriva a circa 62,6 megabyte. Cioè non ci sta proprio, e servirebbe un supercomputer con 64 MB di RAM, che non avevano certo tutti.

Una palette a 256 colori

Si può fare un hack sul colore stesso, in modo che invece dei colori normali un solo byte faccia riferimento a una palette di 256 colori, il che permette di dimezzare subito la memoria, e il vecchio Caesar II viveva proprio così, come del resto molti giochi dell’epoca.

Ma verso la fine degli anni Novanta le schede video lavoravano già tranquillamente a 16 bit, e gli artisti volevano sfumature morbide di sabbia e acqua, mentre 256 colori per tutto lo schermo significavano che deserto, Nilo, verde dei campi, pelle degli abitanti e oro dei templi avrebbero dovuto spartirsi un’unica palette. E palette multiple, come sullo SNES, su PC nessuno sano di mente le avrebbe fatte a mano, perché costose, brutte e comunque poco efficaci, così Impressions passò ai 16 bit, e risparmiare bisognò altrove. Lo vedete il gopher? No? Eppure c’è...

Le superfici DirectDraw

Il nuovissimo DirectDraw proponeva di memorizzare le immagini in «superfici», idealmente direttamente nella memoria video, e di disegnarle con il blitter hardware, il che sulla carta suonava come prestazioni gratis. Ma in pratica una tipica scheda video del 1999 aveva sì e no 4 megabyte di memoria, di cui una parte già occupata dallo schermo e dal back buffer, le superfici potevano «perdersi» al cambio di finestra e andavano ripristinate, e il blitter hardware sapeva gestire il color key, ma non l’RLE, né i rombi, né la colorazione del font nel colore desiderato. Alla fine Pharaoh usa DirectDraw solo come mezzo per mostrare il frame finito, e tutte le immagini le disegna da sé, con la CPU, ed è per questo che i PC dell’epoca con processori deboli reggevano il gioco solo a 640×480 a 20 frame.

Archivi e compressione

Si poteva comprimere tutto con qualche LZ e decomprimere al caricamento, risparmiando così spazio su disco (relativamente: il gioco occupava comunque meno di metà CD), ma la memoria non la si risparmia in questo modo, e uno sprite decompresso occuperà quanto uno non compresso. Per questo comprimere ha senso solo se l’immagine si può disegnare direttamente dalla forma compressa, senza decomprimerla.

E l’ultima opzione si affida al funzionamento di Windows: allocare quanto serve, e poi ci pensi lo swap. Ma se al gioco mancava memoria fisica, le pagine finivano fisicamente su disco e tornavano indietro quando servivano... il che era, diciamo così, percepibile a occhio nudo, e non appena la scena chiede più di quanto c’è, il frame si trasforma in un fruscio di hard disk, e il giocatore scopre che aspetto hanno tre frame al secondo.

Anticipo subito che anche Pharaoh si appoggia a questo meccanismo, solo che cerca di fare in modo che i dati freddi siano davvero freddi.

Come è fatto in Pharaoh

Tutta la grafica del gioco sta nella cartella Data in coppie di file: .sg3 è l’indice e .555 sono i pixel, e di coppie così nella build se ne contano circa duecento, in tutto 395 file e 302 MB, di cui 177 megabyte sono i pixel veri e propri e altri 125 megabyte gli indici, ma gli indici sono per lo più vuoti

Ogni .sg3 inizia con un header, una tabella da 300 gruppi, i nomi dei file BMP sorgente da cui gli artisti assemblavano il texture pack, e un array di record da 64 byte per immagine. I record nel file sono sempre 10 000 oppure 13 000, indipendentemente da quante immagini ci siano davvero, per cui 158 file hanno una dimensione di 695 080 byte, e altri 17 file con gli sprite di abitanti e nemici ne hanno 887 080. Sospetto che dipendesse dalla pipeline di build o dalla build farm, anche se quando ho parlato con Simon Bradbury (lead del team di sviluppo di Caesar e in parte di Pharaoh, e anche di Stronghold), di build farm non ha fatto alcuna menzione: la build la faceva semplicemente su richiesta uno dei programmatori sul proprio PC e la metteva sul disco condiviso.

typedef struct {
    int32_t data;                  // offset dei pixel nel .555
    int32_t data_length;
    int32_t isometric_top_offset;  // dove inizia la parte alta dell’edificio
    int32_t file_slot;
    int32_t mirror_source_offset;  // da dove prendere l’immagine, se è specchiata
    int16_t width, height;
    // ... animazione, offset dello sprite ...
    uint8_t draw_type;             // piatta, isometrica, font monocolore ...
    uint8_t is_compressed;
    uint8_t is_external;           // pixel non in memoria, ma su disco
    uint8_t has_isometric_top;
    // ...
    uint8_t is_mirrored;
} image_header;                    // 64 byte, static_assert nel nostro codice

Quindi un centinaio abbondante di megabyte su disco saranno in gran parte zeri, che non arrivano mai in memoria: il gioco legge il .sg3 in un buffer temporaneo, lo analizza e lo libera subito. Nel 2000 i dischi erano già grandi, ma la possibilità di mettere in memoria tutto il texture pack non c’era, e a dire il vero non c’è nemmeno oggi, il che è buffo: con 8 GB di memoria video, i livelli adesso pesano 20–30 GB.

E poi ogni texture pack, oltre agli sprite veri e propri, inizia con le stesse duecento immagini di system.bmp (cornici, pulsanti, frecce), tutta un’eredità di Caesar 2, che lì quei dati li conservava davvero. A quanto pare era più comodo mantenere la continuità del formato. Il loader del gioco lo sa, e per tutti i pacchetti successivi al primo salta questi duecento record e inizia a leggere il .555 dall’offset 39 214 byte. Una sciocchezza, circa un megabyte di risparmio su tutti i pacchetti insieme, ma nel 2000 un megabyte era ancora un megabyte, e si combatteva per i kilobyte.

Un RLE da cui si può disegnare

Torniamo ai pixel trasparenti (abitanti, animali, alberi, fumo) che stanno nel nostro sprite. Il gioco codifica questi byte con RLE e mette come marcatore di inizio di un tratto trasparente 0xFF, seguito da un numero N, che significa «salta N pixel trasparenti», mentre qualsiasi altro byte N significa «seguono N normali pixel a 16 bit».

while (row_left > 0) {
    uint8_t n = *src++;
    if (n == 0xFF) {        // tratto trasparente
        n = *src++;
        dst += n;
    } else {                // tratto opaco
        memcpy(dst, src, n * 2);
        src += n * 2;
        dst += n;
    }
    row_left -= n;
}

La cosa principale qui non è nemmeno il rapporto di compressione, ma il fatto che un formato del genere non va decompresso e il blitter può disegnare direttamente da lì (ricordate che disegniamo con la CPU, pixel per pixel): i pixel trasparenti si possono non toccare affatto, spostando semplicemente il puntatore. Così, delle 13 366 immagini compresse che il gioco tiene dopo l’avvio, risultano 19,85 megabyte di pixel reali da disegnare invece dei 34 MB delle bitmap grezze, cioè meno 40%.

Come si sa, tutto si paga, e se lo sprite è tagliato in alto dal bordo dello schermo, il blitter scorre diligentemente tutte le righe invisibili per trovare la prima visibile e iniziare a disegnare, e poi il bello deve ancora venire...

Rombi senza angoli

Una casella di terreno in isometria appare al giocatore come un rombo di 58×30 pixel, ma memorizzarlo come rettangolo significa memorizzare 1740 pixel, di cui se ne vede meno della metà. Per questo gli autori del gioco iniziarono a memorizzare solo il rombo stesso (righe lunghe 2, 6, 10 … 58, 58 … 6, 2 pixel, una dopo l’altra), senza byte vuoti, ottenendo 900 pixel e una dimensione ridotta del 50%, e considerando che tutte le nostre caselle della mappa sono rombi, ci ritroviamo con un’altra metà di memoria libera.

Da qui deriva anche la suddivisione degli edifici grandi N×N, le cui caselle sono memorizzate come N² rombi di questo tipo e disegnate diagonale dopo diagonale. Questo semplifica anche il disegno, perché al blitter dei rombi non serve né il color key né il controllo della trasparenza: conosce semplicemente la lunghezza di ogni riga, anzi non sa proprio cosa ci sia da disegnare, tutto il rendering isometrico dell’edificio si basa sulla matematica degli offset. Chi è che parlava di trasparenza?

La parte alta dell’edificio a parte

Ma questo modo di disegnare va bene solo per i tile «piatti», e un edificio come si deve non è solo la base. Il tempio ha le colonne, la casa ha il tetto, la bottega avrà una tettoia, e tutto questo sporge sopra i rombi, quindi questa parte va memorizzata separatamente, subito dopo i rombi, compressa con lo stesso RLE, e nell’header dell’immagine c’è isometric_top_offset, che indica dove inizia.

Un edificio di 6×6 caselle, di 358×223 pixel, ora occupa 36 rombi da 1800 byte più 28 726 byte di parte alta, in totale 93 526 byte invece di 159 668. E in più questo risolve il problema delle sovrapposizioni senza usare lo z-buffer (che non è economico nemmeno oggi, e negli anni Duemila era un vero problema per i giochi isometrici). Ora il gioco disegna prima tutte le basi sullo schermo, poi in una seconda passata, fila dopo fila, le parti alte degli edifici, gli abitanti e le animazioni, e alla fine la fila più vicina viene semplicemente disegnata dopo quella più lontana, e così tutto finisce al suo posto.

Cinque direzioni invece di otto

Passiamo agli abitanti della nostra città virtuale: in Pharaoh camminano in otto direzioni, e ogni frame di animazione richiede otto texture distinte, ma dato che gli schermi erano piccoli, gli autori del gioco ricorsero a un hack e memorizzarono solo le animazioni di cinque direzioni, mentre le direzioni 5, 6 e 7 erano marcate con il flag is_mirrored e rimandavano ai record vicini con offset −2, −4 e −6. Cioè il blitter le disegnava specchiate, il che permise di risparmiare altri 2,3 megabyte circa di RAM: a pensarci bene, andare a destra costa la metà che andare a sinistra.

Un font che si colora mentre viene disegnato

Restano ancora le lettere... lettere normalissime, che pure vanno disegnate sullo schermo e pure occupano memoria. Le lettere sono normali immagini nel pacchetto Pharaoh_Fonts, ce ne sono 1340 per 488 kilobyte, e una parte di esse è di tipo «monocolore»: una maschera RLE a sé, senza colori propri, che il blitter riempie con il colore che gli viene passato. Un unico set di glifi funziona per il testo bianco, rosso e verde, e l’ombra sotto la scritta sarà la stessa lettera, disegnata un’altra volta in nero e spostata di un pixel.

Immagini che non stanno in memoria

Ma il guadagno più grande nel gioco lo dà il meccanismo che nel codice si chiama «disegno sul posto»: tutte queste texture sono state spostate dai texture pack in uno solo. È un file quasi vuoto, che contiene duecento immagini di sistema per 39 kilobyte e 482 texture i cui pixel stanno in .555 separati e non vengono mai caricati in memoria. Sono texture grandi, che occupano quasi 44 MB (sfondi a tutto schermo dei menu, immagini dei briefing, ritratti dei consiglieri, illustrazioni del tutorial, cornici dei pannelli).

E quando il gioco deve disegnare un’immagine del genere, apre il file, legge quel pezzo in un buffer di lavoro separato grande quanto lo schermo, poi converte il colore e lo disegna sopra lo schermo principale.

seek(fd, offset_of_first_visible_row);
for (row = 0; row < visible_height; row++) {
    read(fd, buffer, visible_width * 2);
    seek(fd, row_skip, SEEK_CUR);   // 1024 * 2 - visible_width * 2
    buffer += visible_width * 2;
}

Slot e segnaposto

Manca ancora poco: tutta la grafica in memoria è distribuita su trenta slot, che possono indirizzare singoli texture pack con un intervallo fisso di numeri di immagine, cioè fisicamente Pharaoh non poteva tenere in memoria più di 16k texture. I numeri delle immagini erano cablati nel codice e nei salvataggi, quindi il contenuto di uno slot si poteva cambiare, ma spostare i numeri no.

Anche questa è un’eredità di Caesar 2, abbandonata solo in Zeus, per cui bisognava creare un sistema di caricamento in cui una parte degli slot era fissa (sprite principali, grafica comune, terreno, font, mappa dell’impero), mentre gli altri cambiavano a seconda della situazione:

per esempio lo slot del nemico: c’era solo uno dei dodici eserciti, dagli Hyksos ai Persiani, circa 1,2 megabyte ciascuno, scelto in base allo scenario della missione;
oppure lo slot del complesso templare, uno dei cinque dèi, quando il giocatore lo costruisce, il che limitava la possibilità di costruire complessi diversi sulla stessa mappa.
oppure gli slot dei monumenti (piramide, mastaba, tombe della Valle dei Re, Abu Simbel, biblioteca e faro di Alessandria, a seconda dell’epoca della missione).
Per la sfinge, il faro, la biblioteca e il mausoleo, ogni fase di costruzione è un texture pack a sé, che viene caricato man mano che il cantiere avanza e sostituisce il precedente

Per questo il vero Abu Simbel pesa 9.4 megabyte, ma se ne carica solo la parte da 1.2 che viene effettivamente usata nella missione.

int32_t image_collection_load_file(const char *name, int32_t slot)
{
    if (strcmp(slots[slot].name, name) == 0) {
        return 1;                      // già caricato, non facciamo nulla
    }
    free(slots[slot].pixels);          // liberiamo il vecchio pacchetto
    load_sg3_and_555(name, slot);      // i numeri delle immagini dello slot non cambiano
    return 1;
}

Come si facevano i giochi una volta

Esattamente come oggi: trucchi, hack e convenzioni, sono cambiate solo le dimensioni. In Pharaoh, dopo l’avvio, in memoria ci sono circa 39 megabyte di pixel in trenta slot, più 3,2 megabyte per la tabella degli header, più i buffer dello schermo. È più di 16 megabyte, e più di 32, ma molto meno dei 300 megabyte iniziali: il gioco si appoggiava onestamente allo swap di Windows, e tutto il meccanismo descritto sopra serviva a far sì che il working set di un singolo frame (terreno, sprite degli abitanti, nemico corrente, fase giusta del monumento) entrasse nella memoria fisica, mentre tutto il resto se ne stava tranquillo su disco, senza frusciare e senza scricchiolare.

Senza tutti questi trucchi, le stesse immagini avrebbero occupato circa 92,6 megabyte più altri 8,3 per le direzioni specchiate, senza contare i 43,8 megabyte di sfondi a tutto schermo, che non vengono proprio caricati, e i monumenti, che si caricano solo nelle rispettive missioni: ecco, nel 2000 la differenza tra «ci sta con lo swap» e «non ci sta per niente» era più o meno questa.

Invece di una conclusione

Mi piace scavare nei vecchi giochi, perché mostrano come si può lavorare dentro dei vincoli. Nessuno dei trucchi descritti era una svolta di per sé: lo stesso RLE è noto dagli anni Settanta, e la matematica dei rombi isometrici addirittura dagli anni Cinquanta o anche prima. Anche gli sprite specchiati c’erano già sul NES, e il caricamento dei dati su richiesta è semplicemente buon senso da sviluppatore.

Ma tutti insieme hanno trasformato 300 megabyte di grafica in un working set che entrava nella memoria di un computer del 2000, e lo hanno fatto senza una sola riga di assembly, semplicemente cambiando il formato dei dati. Il problema, come al solito, non era disegnare più in fretta: bastava che al momento giusto in memoria ci fossero le immagini giuste nella forma giusta.

P.S. Così si chiude la storia di quasi tre anni di ricostruzione dei sorgenti del Pharaoh originale, potete dare un’occhiata a cosa ne è venuto fuori. Compatibile a livello binario e spirituale con il gioco del 2000. Benvenuti agli scavi IT https://github.com/dalerank/tutankhamun

P.P.S. Il progetto ha subito l’intervento di Claude, solo nelle ultime fasi (più o meno gli ultimi due mesi), quando c’era da scrivere la documentazione, a cui sono fortemente allergico: cioè smontare il codice non è un problema per me, ma poi scrivere cosa succede lì dentro e renderlo leggibile... ecco, lì sono messo male... ma è sempre stato il mio punto debole. Per il resto si è rivelato un ottimo aiutante nelle faccende archeologiche, sorprendentemente....

Tutti gli articoli