Magazine Tecnologia

Sulla Generazione Procedurale, ovvero: algoritmo, lavora tu al posto mio

Creato il 26 dicembre 2017 da Lightman

Sfidare i limiti dell'hardware elaborando nuovi modi per modellare strutture e poterle implementare con algoritmi giusti al momento giusto: è questo uno degli obiettivi che gli sviluppatori videoludici devono conquistare per lasciare il segno nella storia del medium.
Chi ha letto un libro come Master of Doom sa che il successo di pezzi pregiati come Return to Castle Wolfenstein e Doom deve moltissimo alle abilità del loro programmatore principale, John Carmack, che qualche anno prima era riuscito a perfezionare la tecnica dell' adaptive tile refresh per prodotti pionieristici come Commander Keen.

La nascita di un roguelike e la bellezza di un dungeon sempre diverso

La generazione procedurale ( Procedural Generation, PG) è nata da una sfida lanciata alle vecchie memorie fisiche. Nel 1978 Beneath Apple Manor, nel quale bisogna dare la caccia ad una mela nascosta in un maniero infestato di nemici, apre le porte alla PG. Due anni dopo è il momento di Rogue, ossia il primo roguelike della storia dei videogiochi.
Nel titolo, basato sull'estetica dell'ascii, impersoneremo un esploratore di dungeon alla ricerca per l'amuleto di Yendor: l'avventura è costellata di pericoli, tra goblin e trappole, magie e trabocchetti vari, tutti realizzati con la generazione procedurale. Grandi passi in avanti sono stati poi compiuti da Elite nel 1984, sviluppato da Ian Bell e David Braben sul Commodore 64: si trattava di un gioco in grado di mettere a disposizione otto galassie, ciascuna abitata da 256 pianeti differenti, dotati di nomi, situazione politica e caratteristiche differenti. Per non parlare della possibilità di svolgere attività commerciali nello spazio e sfidare altre astronavi, accompagnati dal sottofondo midi del Sul bel Danubio Blu di Strauss.
Perché un gioco del 1984, pesante qualche centinaio di kilobyte, è in grado di essere così espanso?

La risposta stessa è nella logica della generazione procedurale che crea strutture e oggetti solo nel momento in cui questi devono essere utilizzati, implicando così un importante risparmio della memoria. Nel caso di Elite c'è un algoritmo che prende un seed (dei valori randomici) e li usa per generare i pianeti e le loro coordinate nel mondo, così come il resto dell'universo che il pilota deve affrontare. Il " goat soup" era un seed di informazioni che permetteva la descrizione fantasiosa di ogni pianeta. E così via.
Negli anni novanta è Diablo a farsi carico dell'eredità di Rogue. L'esperienza procedurale mette a dura prova le skills di un giocatore in quanto la combinazione randomica degli ostacoli non si concede mai un semplice pattern di apprendimento mentale.
La PG può essere "adattiva", capace di adattarsi alle esigenze del videogiocatore ma anche di rendergli la vita molto difficile: da una parte possiamo creare una mappa semplice, libera da barbari e difficoltà geofisiche in un Civilization, mentre dall'altra la discesa nei livelli di un labirinto di Crypt of the Necrodancer potrebbe, di contro, rendere il gioco sempre più insidioso.

Il videogioco è un artigianato

Certo è, che come in tutte le discipline dove la tecnica dell'artigiano è importante, le attività fatte a mano sono sempre più curate e pregevoli. Dare il totale controllo della creazione a un algoritmo vuol dire privarsi di una "mano umana" che, in certi casi fortunati, è pura arte. Un buonissima soluzione, ci insegna Spelunky, è fare un compromesso tra il procedurale e l'hand-made.
La generazione procedurale implica risparmiare con la memoria, ma non si può dire lo stesso con i tempi di lavoro di un team. Un conto è creare un gioco à la The Binding of Isaac o Dungeon of Endless, un altro è realizzare un'esperienza breve e ristretta, ma curata nei minimi dettagli.

La generazione procedurale si fa maggiormente problematica quando gli obiettivi diventano più sofisticati, perché l'algoritmo si complica in modo direttamente proporzionale alla complessità del gioco da sviluppare. Occorre, inoltre, sapere bene cosa si sta programmando: scrivere un generatore di labirinti funzionerà solamente se il programmatore è un abile ideatore di labirinti, al di là di ogni automatizzata generazione.
Il 2008 è un anno di svolta per la generazione procedurale, grazie all'uscita di due giochi molto diversi tra loro. Ve lo ricordate Will Wright? Il padre di SimCity è stato anche la mente dietro Spore, nel quale gestiamo la nascita della vita e l'evoluzione di una specie, con tanto di guerre e conquista nello spazio.
Nel Creature Creator l'algoritmo forma le abilità fisiche, mentali e sociali di una specie a seconda di come l'utente decida di modellare fisicamente la bestiaccia. Ammirabile anche quello che è stato fatto da un punto di vista musicale, con la soundtrack che muta in real-time a seconda di cosa stiamo creando: impiantare sulla creatura un carattere socievole fa cambiare i toni della musica, che virano verso sonorità allegre e piacevoli, mentre iniziano ad incalzare alcuni ritmi tribali quando plasmiamo un animale feroce. Un lavoro di indubbia qualità, grazie anche e soprattutto alla collaborazione con un certo Brian Eno (che, tra le varie cose, è stato anche il compositore dell'intro di Windows 95).

Dello stesso anno di Spore è il già citato Spelunky, un ottimo esempio di come un solo programmatore, se dotato di capacità e idee giuste, può tirare fuori dal cilindro un piccolo capolavoro in perfetta autonomia. In Spelunky ogni livello è sempre godibile e mai scadente: il gioco possiede infatti due anime, una randomica e l'altra disegnata a mano. Ciascuno stage è generato da uno script che divide una stanza da 16 box con una struttura 4x4. L'algoritmo prende una delle quattro stanze della prima fila e la sceglie come entrata; in seguito si crea un punto di uscita dal quadro, e si collegano i box in modo tale che siano sempre percorribili senza dover usare abilità o armi, ma solo passeggiando e saltando. Ogni box è generato con pezzi di texture, e l'algoritmo lancia un dado per piazzare tesori, mostri e altri elementi. Derek Yu lascia che a svolgere gran parte del lavoro sia un algoritmo ben guidato, su di un sentiero sicuro che lo sviluppatore ha fatto in modo fosse impossibile abbandonare. È il giocatore stesso che in Spelunky decide come affrontare la propria avventura, se salvare gli npc in difficoltà, derubare il venditore di oggetti o spendere tutte le proprie monete. Il mondo è sempre randomico ma al tempo stesso, se giocato più volte, inizia a divenire familiare.

La scienza della generazione procedurale

Descrivere in generale la PG non è difficile, ma è complesso entrarne nello specifico: diciamo che la generazione dei contenuti può essere di due differenti tipi. Una, basata sul random seeds, sfrutta una serie di numeri generati casualmente; se invece il vettore che contiene i valori si basa su parametri sui quali attenersi si definisce di tipo parameter vector.
La quantità di informazione che viene prodotta dalla PG può essere suddivisa in cinque sottogruppi: Game Bits (gli elementi decorativi o d'ambiente), Game System , Game Space (in pratica le mappe), Game Scenarios (elementi legati allo storytelling) e Game Design.

Negli anni si è giustamente data sempre più importanza alla qualità del materiale prodotto, motivo per il quale esiste il cosiddetto reinforcement learning: si crea cioè un agente di calcolo, ovvero un'entità artificiale che prova numerose volte il livello generato in modo da testarne la completa giocabilità.
Si può sviluppare senza impazzire un gioco che implementa algoritmi di generazione procedurale? La risposta è positiva, a patto di moderare le ambizioni. Spesso nei corsi di programmazione all'Università può capitare di ricevere come progetto d'esame proprio lo sviluppo di un semplice gioco basato sulla PG. È il caso, ad esempio, di un piccolissimo roguelike, Knossos, e qui potete leggerne il codice. Nel gioco c'è un dado virtuale che stabilisce la sorte del giocatore quando apre una porta appena scoperta, o si mette alla ricerca di oggetti nella stanza. La PG del gioco è data dal " random seeds" e dal lancio di un dado.
Questo è il modo più semplice per generare.
Le idee più complesse necessitano di due metodi: uno che si definisce search-based, dove si generano varie istanze dei contenuti e si scelgono le migliori, ed uno " costruttivo", dove la generazione non passa per nessuna fase di analisi. Nel primo caso i tempi di calcolo, per quanto molto lunghi, possono dare risultati interessanti e non ipotizzati dal designer, nel secondo, invece, si procede a colpo sicuro, richiedendo di giocare ogni possibile generazione di entità.

Sono inoltre molte le tecniche possibili per creare contenuti, come la generazione per frattali o la cellular-automata. La tecnica Automa cellulare è sicuramente una delle più affascinanti, soprattutto per le sue origini matematiche e le sue derivazioni filosofiche. Immaginiamo una matrice di celle in uno spazio dato a n-dimensioni, e le celle della matrice evolvono seguendo un tempo gestito da un orologio all'interno della stessa. Simile metodo è usato nei videogiochi, ad esempio, per far crescere flora o fauna.
Questo modello è la simulazione di come cresce una foresta nella tecnica cellular-automata.
Esiste poi una tecnica definita Perlin Noise, sfruttata all'interno di Minecraft: si genera quindi una Noise Map, una mappa fatta di punti di ombre differenti, come se fosse una mappa topografica, dopodiché la Noise Map viene livellata, affinata, e dall'essere un ammasso di roccia si riempie di laghi, flora e oggetti. È come se vari strati venissero, insomma, appoggiati uno sopra l'altro.

Il futuro è nello spazio

I giochi dedicati all'esplorazione spaziale stanno sempre più sfruttando le potenzialità della generazione procedurale. È del 2017 Astroneer, titolo indie che sfrutta la generazione procedurale dei pianeti.
Con il passare dei mesi (anzi, anni) un gioco come Star Citizen, inoltre, sta diventando sempre meno un mito e sempre più realtà. Quella che potrebbe rivelarsi una delle opere videoludiche più importanti di sempre ha un impianto procedurale davvero complesso. Da quanto ne sappiamo, vengono costruiti con algoritmi di PG intere città e interi pianeti, dotati di una complessità che, almeno in teoria, No Man's Sky può solo sognarsi. Per non far esplodere la memoria si utilizza un escamotage non da poco: si genera la superficie del pianeta tenendo conto della qualità del livello di dettaglio a seconda della posizione della view-camera. Altre tecniche dovrebbero evitare la perdita di precisione e regalarci in real-time lo stesso spettacolo mostrato nei video della pre-alpha.

Un paio di anni fa la stampa di settore (e non) ha prodotto una gran quantità di articoli a causa del forte hype che i ragazzi di Hello Games e la Sony avevano suscitato con No Man's Sky.
Il videogioco deve tutta la sua (ai tempi millantata) unicità alla prepotenza degli algoritmi di generazione procedurale. Fra i vari articoli usciti per accompagnare il periodo di lancio di No Man's Sky troviamo uno distribuito sul magazine Slate nel quale si analizza un particolare paradosso di un GDR caratterizzato dalla generazione procedurale. Hal Bouma, uno dei programmatori di Daggerfall (1996, storico capitolo della saga di The Elder Scrolls) racconta di come l'allora lead designer Julian Lafray trovasse interessante, da un punto di vista cognitivo, il senso di ripetitività che può dare un mondo fatto di paesaggi, villaggi e abitanti costruiti in un modo randomico, quindi a rischio di monotonia e alienazione. " Se viaggi per la suburbia, tutte le cittadine ti sembrano le stesse.
Ed era OK che il gioco avesse quel tipo di feeling
." In Daggerfall, come in No Man's Sky, un mondo anonimo è carta bianca per il videogiocatore, carta che l'utente colora e disegna con la propria esperienza ludica. Il paradosso della generazione procedurale, pertanto, è dato dalla coesistenza tra un mondo creato da un dio automatizzato e la possibilità di agire secondo la propria volontà, un fattore che rende ogni avventura incredibilmente personale.


Potrebbero interessarti anche :

Ritornare alla prima pagina di Logo Paperblog

Possono interessarti anche questi articoli :