Generazione procedurale 2D in Javascript

Fuori si sta per scatenare il primo temporale del mese, con mia immensa soddisfazione, e nel frattempo me ne sto chiuso qua dentro, col ventilatore a palla e il gatto che lo guarda tra il curioso e l’impaurito. Pronto a raccontare qualcosa del nuovo passo compiuto sul cammino della generazione procedurale.

Ho già accennato qualcosa sull’argomento, che è molto vasto e complesso, e del quale vi lascio la definizione di Wikipedia: In computer graphics, procedural generation is generating content algorithmically rather than manually. In video games this means graphic content for a game can be created by the host computer, instead of prerendered artwork being included with game package.
Quindi, generazione di contenuti tramite un algoritmo e non pescandoli da un lavoro fatto in precedenza.

Cosa si genera in maniera procedurale? Qualsiasi cosa, o quasi. Abbiamo ormai sempre più spesso esempi di videogame con contenuti di questo tipo, ma ad esempio per le texture (i “motivi” che ricoprono oggetti nei giochi, dando loro un maggior realismo, spaziando dal terreno alle case, dalle foglie degli alberi a fumo e fiamme) questo è un metodo in uso già da molti anni.
In questo caso il vantaggio è ovvio, a fronte di una maggiore potenza di calcolo richiesta, non si devono memorizzare le texture che verranno visualizzate nel gioco.

Questo tipo di tecnica si può applicare a mondi interi, pensate ai corridoi sotterranei dei primi roguelike ai mondi fantastici di giochi come Elder Scroll II.

Ancora più affascinante l’utilizzo di questi algoritmi per scrivere la storia inventata del proprio mondo, come fa il già citato Dwarf Fortress e il più recente Ultima Ratio Regum. In quest’ultimo titolo la generazione procedurale è applicata a ogni aspetto del mondo, dalla geografia alla politica, dall’urbanistica alla storia.

Molto più modestamente, sono partito da un generatore di strutture simil-dungeon, il motore per ora chiamato “Caves&Creatures“, che non avete ancora visto, e da lì sono passato a studiare il pathfinding, per comprendere la gestione di entità capaci di muoversi autonomamente e con efficacia verso un dato obiettivo.

Conclusa la digressione, rieccoci agli algoritmi di generazione procedurale.
Questa volta però andiamo sul vasto, questa volta parliamo di come si possono generare i mondi, o almeno un pezzetto di essi. Obiettivo, generare in modo casuale delle mappe di altezza, height map, che rappresentino in modo sufficientemente realistico un territorio.

Ammetto di aver speso una certa quantità di tempo su metodi molto più complessi di quello che ho implementato (Perlin Noise e affini, per chi li conosce). Mi sono affezionato invece all’algoritmo Middle Point Displacement, del quale ho scritto una variante che lo porta vicino al più complesso Diamond Square (senza saperlo, il che è stato di notevole soddisfazione).

Il funzionamento è molto semplice.

a) data una griglia di punti, vuota, si parte dai vertici (x,y,z) e si va a generare una mappa delle altezze (height map) che possa rappresentare, più realisticamente possibile, un territorio

b) viene calcolato il valore di z per il punto centrale (il Middle Point), con una media dei valori sui quattro vertici e sommando una certa quantità casuale (punto fondamentale sul quale torneremo)

c) vengono calcolati quindi i valori di z per i punti intermedi ai quattro lati. Qui è dove i due algoritmi differiscono. Il MDP utilizza, per ogni lato, una media sugli estremi. Il DSQ utilizza tutti i quattro punti che formano appunto il “diamante” attorno al punto in esame. Questo porta a un calcolo più complesso ma permette di evitare alcuni artefatti visivi (che rovinano le immagini generate dal MDP introducendo simmetrie innaturali)

Le seguenti immagini descrivono i primi passi del processo, sono iterazioni successive ma non correlate tra loro, essendo state prese da valori iniziali diversi.

Middle Point Displacement - fig 1
In questo primo passaggio si vedono i quattro punti iniziali e i cinque punti calcolati
Middle Point Displacement - fig 2
Secondo ciclo, ulteriore definizione dei punti, ora la dimensione della griglia è 5 (2^2+1)
i4
Quarto ciclo, griglia di dimensione pari a 17=2^4+1 e iniziano a vedersi più dettagliate le aree del terreno
Middle Point Displacement - fig 4
Con 7 cicli la mappa è già a buon punto

d) generati i punti si hanno nuovi quadrati, in ognuno dei quali si procede come appena visto, iterando fino a esaurire i pixel disponibili (o le celle della griglia)

Aumentare il parametro di roughness, con lo stesso numero di cicli, porta a landscape meno dettagliati e più omogenei.

Otto cicli e roughness=0.9
Otto cicli e roughness=0.9

Le differenze con l’algoritmo standard (senza alcuna pretesa di “inventare” qualcosa, ci saranno fior di implmentazioni in giro) sono:

– la componente casuale può essere anche negativa, proporzionale a R=random()*2-1, quindi un float che varia nell’intervallo [-1,1)

– l’ampiezza della componente casuale è fondamentale, se essa varia troppo poco rispetto la misura del lato del quadrato in esame, il risultato sarà troppo poco omogeneo e irrealistico. Dopo varie prove sono arrivato a una variazione pari a D=D*2^(-r) dove r è il parametro di roughness sfruttato per variare la “grana” del grafico

– il calcolo dei punti mediani viene fatto prendendo in considerazione tre punti e non i canonici due, questo permette una maggior omogeneità dell’immagine generata. Si sfrutta quindi “metà diamante”. Se indichiamo i punti come di seguito (dove ogni lettera è una coppia di valori (x,y) )

A -- B -- C
|    |    |
D -- E -- F
|    |    |
G -- H -- I

con il metodo classico si avrebbe

F.z=(C.z+I.z)/2

nel mio caso

F.z=(C.z+I.z+E.z)/3

Nel corso del post avete visto i risultati, che trovo più che apprezzabili per i miei fini.

L’algoritmo è molto semplice, io ho utilizzato una funzione ricorsiva di poche righe. A breve inserirò il codice e la demo online, intanto ecco quanto scritto.

// x0,y0 - top left point coordinates
// size - grid side
// displace, roughness - random displacement function coefficients
function mdp2dIteration(x0,y0,size,displace,roughness) {
  size = size / 2;
  // middle point
  var px = x0+size;
  var py = y0+size;
  MDP2D[px][py] = assignValue( ( MDP2D[px-size][py-size] + MDP2D[px+size][py-size] + MDP2D[px+size][py+size] + MDP2D[px-size][py+size] ) / 4 + randomDisplace(displace) );
  // top point
  if (py-size == 0) // avoid recalculating left point
    MDP2D[px][py-size] = assignValue( ( MDP2D[px-size][py-size] + MDP2D[px+size][py-size] + MDP2D[px][py] ) / 3 + randomDisplace(displace) );
  // left point
  if (px-size == 0) // avoid recalculating top point
    MDP2D[px-size][py] = assignValue( ( MDP2D[px-size][py-size] + MDP2D[px-size][py+size] + MDP2D[px][py] ) / 3 + randomDisplace(displace) );
  // right point
  MDP2D[px+size][py] = assignValue( ( MDP2D[px+size][py-size] + MDP2D[px+size][py+size] + MDP2D[px][py] ) / 3 + randomDisplace(displace) );
  // bottom point
  MDP2D[px][py+size] = assignValue( ( MDP2D[px-size][py+size] + MDP2D[px+size][py+size] + MDP2D[px][py] ) / 3 + randomDisplace(displace) );
  // decrease displace according to the roughness value
  displace = displace*Math.pow(2,(-1)*roughness);
  // iterate to the next level
  mdp2dIteration(px-size,py-size,size,displace,roughness); // top left
  mdp2dIteration(px, py-size,size,displace,roughness); // bottom left
  mdp2dIteration(px-size,py, size,displace,roughness); // top right
  mdp2dIteration(px, py, size,displace,roughness); // bottom right
}

Lo step successivo è prendere la height map, una mappatura coerente dell’altezza di un certo landscape bidimensionale,  e “colorarla”.
Questo può essere fatto indipendentemente da altri fattori (climatici, ad esempio), con livelli di colore fissi (gradienti in relazione alla z del punto).

Dai primi tentativi con semplici gradienti lineari di colore, ecco cosa ho ottenuto:

javascript generated height map
La height map generata
javascript generated height map
Il risultato dopo una prima colorazione

Si può andare più a fondo, valorizzando queste zone in maniera diversa a seconda di certi parametri ambientali.
Ad esempio, riportando alcune idee viste in giro:
– utilizzare funzioni di erosion (thermal, hydric,…) per simulare l’erosione dei territori
– definire delle soglie di altezza che separino in modo più o meno continuo le fasce di temperatura
– definire le tipologie di territorio (mare, bosco, palude, savana,…)
– scrivere una matrice che per un certo insieme di set climatici (tropicale, desertico, temperato,…) definisca i relativi rapporti tra altezza e territorio

C’è tanto da imparare e da fare, terre da disegnare e da far esplorare.

E dire che sento di gente che si annoia…

 

Print Friendly, PDF & Email

Vuoi rispondere?