Una ricetta per farvi il vostro Dungeons 3D Procedurale

In questo tutorial, impareremo a costruire dungeon complessi a partire da parti prefabbricate, non vincolate a griglie 2D o 3D. I vostri giocatori non saranno mai più a corto di dungeon da esplorare, i vostri artisti apprezzeranno la libertà creativa, e il vostro gioco avrà una "rigiocabilità" migliore.

Per beneficiare di questo tutorial, è necessario comprendere le trasformazioni 3D di base e sentirsi a proprio agio con gli scene graphs (grafi di scena) ed i sistemi di entità- componenti.

Un pò di storia

Uno dei primi giochi ad utilizzare la generazione procedurale del mondo è stato Rogue. Realizzato nel 1980, era caratterizzato dalla generazione dinamica, 2D, di dungeon basati su griglia. Grazie a questo non esistevano mai due percorsi di gioco identici, il gioco ha generò un nuovo genere di giochi, chiamati "roguelikes". Dopo più di 30 anni questo tipo di dungeon è ancora abbastanza comune.

Nel 1996, è stato rilasciato Daggerfall. Era caratterizzato da dungeon e città 3D procedurali, che hanno permesso agli sviluppatori di creare migliaia di luoghi unici, senza doverli costruire tutti manualmente. Non è molto comune, anche se il suo approccio 3D offre molti vantaggi rispetto ai classici dungeon a griglia 2D.

Ci concentreremo sulla generazione di dungeon simili a quelli di Daggerfall.

Come costruire un Dungeon?

Al fine di costruire un dungeon, abbiamo bisogno di definire cosa è un dungeon. In questo tutorial, definiremo un dungeon come un insieme di moduli (modelli 3D) collegati tra loro secondo una serie di regole. Useremo room (stanze) collegate da corridors (corridoi) e junctions (incroci, giunzioni):

• Una stanza è una grande area che ha uno o più uscite
• Un corridoio è una zona stretta e lunga che può essere inclinata, e ha esattamente due uscite
• Una incrocio è una piccola area che ha tre o più uscite

In questo tutorial, useremo modelli semplici per i moduli, le cui mesh conterranno solo il piano. Ne useremo tre per ciascuno: stanze, corridoi e incroci. Visualizzeremo dei marcatori di uscita con degli assi, con l'asse -X/+X in rosso, l'asse Y in verde, e l'asse Z in blu.

Notare che l'orientamento delle uscite non è vincolato a incrementi di 90 gradi.

Quando andremo a collegare i moduli, verranno definite le seguenti regole:

• Le stanze possono connettersi ai corridoi
• I corridoi possono connettersi a stanze o a giunzioni
• Le giunzioni possono connettersi ai corridoi

Ogni modulo contiene un insieme di oggetti marcatore-uscita con posizione e rotazione noti. Ogni modulo è etichettato per dire che tipo è e ogni uscita ha una lista di tag cui è possibile collegarsi.

Al livello più alto, il processo di costruzione del dungeon è il seguente:

1. Instanziare un modulo di partenza (preferibilmente con un numero maggiore di uscite).
2. Instanziare e collegare moduli validi a ciascuna delle uscite non collegate del modulo.
3. Ricostruire un elenco di uscite non ancora collegate in tutto il dungeon.
4. Ripetere il processo fino a quando il dungeon è grande abbastanza.

Il processo dettagliato di collegamento di due moduli è:

1. Scegli un'uscita scollegata dal vecchio modulo.
2. Scegli un prefabbricato per un nuovo modulo i cui tag coincidono con i tag consentiti dalle uscite del vecchio modulo.
3. Instanzia il nuovo modulo.
4. Scegli un'uscita dal nuovo modulo.
5. Collega i moduli: abbinando l'uscita del nuovo modulo a quella del vecchio modulo.
6. Contrassegnare entrambe le uscite come collegate, o semplicemente cancellarle dal grafo di scena.
7. Ripetere l'operazione per il resto delle uscite non collegate del vecchio modulo.

Per collegare due moduli insieme, dobbiamo allinearli (ruotare e traslare nello spazio 3D), in modo che l'uscita dal primo modulo corrisponda un'uscita dal secondo modulo. Le uscite corrispondono quando la loro posizione è la stessa e i loro assi +Z sono di fronte, mentre i loro assi +Y sono corrispondenti.

L'algoritmo per fare questo è semplice:

1. Ruotare il nuovo modulo sull'asse +Y con la rotazione di origine alla posizione della nuova uscita, in modo che l'asse +Z della vecchia uscita sia opposto all'asse +Z della nuova uscita, ed i loro assi +Y sinoa uguali.
2. Traslare il nuovo modulo in modo che la posizione della nuova uscita sia la stessa posizione della vecchia uscita.

Realizzazione

La pseudo-codice è simil-Python, ma dovrebbe essere leggibile da chiunque. Il codice sorgente di esempio è un progetto Unity.

Supponiamo di lavorare con un sistema entità componente che contiene le entità in un grafo di scena, definendo il loro rapporto genitore-figlio. Un buon esempio di un motore di gioco con un tale sistema è Unity, con i suoi oggetti di gioco e componenti. I moduli e le uscite sono entità; le uscite sono figli dei moduli. I moduli hanno una componente che definisce la loro etichetta, e le uscite hanno una componente che definisce i tag cui sono autorizzate a connettersi.

Prima ci occuperemo dell'algoritmo di generazione del dungeon. Come vincolo di fine useremo un numero di iterazioni di passi per la generazione del dungeon.

1

2

def generate_dungeon(starting_module_prefab, module_prefabs, iterations):

3

    starting_module = instantiate(starting_module_prefab)

4

    pending_exits = list(starting_module.get_exits())

5

6

    while iterations > 0:

7

        new_exits = []

8

        for pending_exit in pending_exits:

9

            tag = random.choice(pending_exit.tags)

10

            new_module_prefab = get_random_with_tag(module_prefabs, tag)

11

            new_module_instance = instantiate(new_module_prefab)

12

            exit_to_match = random.choice(new_module_instance.exits)

13

            match_exits(pending_exit, exit_to_match)

14

            for new_exit in new_module_instance.get_exits():

15

                if new_exit != exit_to_match:

16

                    new_exits.append(new_exit)

17

        pending_exits = new_exits

18

        iterations -= 1

La funzione instantiate() crea un'istanza di un prefabbricato modulo: crea una copia del modulo, con le sue uscite e la inserisce nella scena. La funzione get_random_with_tag() itera attraverso tutti i prefabbricati dei moduli e ne prende uno a caso, contrassegnato con l'etichetta fornita. La funzione random.choice() ottiene un elemento casuale da un elenco o una matrice passato come parametro.

La funzione match_exits è dove accade tutta la magia, ed è mostrata in dettaglio qui di seguito:

1

2

def match_exits(old_exit, new_exit):

3

    new_module = new_exit.parent

4

    forward_vector_to_match = old_exit.backward_vector

5

    corrective_rotation = azimuth(forward_vector_to_match) - azimuth(new_exit.forward_vector)

6

    rotate_around_y(new_module, new_exit.position, corrective_rotation)

7

    corrective_translation = old_exit.position - new_exit.position

8

    translate_global(new_module, corrective_translation)

9

10

def azimuth(vector):

11

    # Returns the signed angle this vector is rotated relative to global +Z axis

12

    forward = [0, 0, 1]

13

    return vector_angle(forward, vector) * math.copysign(vector.x)

La proprietà backward_vector di un'uscita è il suo vettore Z. La funzione rotate_around_y() ruota, di un angolo specificato, l'oggetto attorno ad un asse +Y con il suo perno in un punto fornito. La funzione translate_global() trasla l'oggetto con i suoi figli nello spazio globale (scene), indipendentemente da qualsiasi rapporto i figli possano avere . La funzione vector_angle() restituisce un angolo tra due vettori arbitrari, e infine, la funzione math.copysign() copia il segno di un numero fornito: -1 per un numero negativo, 0 per zero e +1 per un numero positivo.

Estendere il Generatore

L'algoritmo può essere applicato ad altri tipi di generazione del mondo, non solo dungeon. Siamo in grado di estendere la definizione di un modulo per coprire non solo le parti di un dungeon, come stanze, corridoi e incroci, ma anche mobili, scrigni del tesoro, decorazioni della stanza, etc. Inserendo i marcatori di uscita nel bel mezzo di una stanza, o sul muro di una stanza, e codificandoli come loot (bottino), decoration (decorazione), o addirittura monster (mostro), siamo in grado di portare il dungeon alla vita, con gli oggetti da rubare, ammirare o uccidere.

Deve essere fatto un solocambiamento, in modo che l'algoritmo funzioni correttamente: uno dei marcatori presenti in un elemento posizionabile deve essere contrassegnato come default (predefinito), in modo che venga sempre raccolto come quello che sarà allineato alla scena esistente.

Nell'immagine qui sopra, una stanza, due casse, tre pilastri, un solo altare, due luci e due articoli sono stati creati e contrassegnati. Una stanza contiene una serie di marcatori che fanno riferimento ai tag di altri modelli, come ad esempio il chest (cassapanca), pillar (pilastro), altar (altare), o wallLight (torcia da muro). Un altare ha tre item (oggetto) indicatore su di esso. Applicando la tecnica di generazione di dungeon per una camera singola, possiamo crearne numerose varianti.

Lo stesso algoritmo può essere usato per creare oggetti procedurali. Se si desidera creare una spada, è possibile definire l'impugnatura come modulo di partenza. L'impugnatura si collegherebbe al pomello e alla guardia. La guardia si collegherebbe alla lama. Avendo solo tre versioni di ciascuna parte della spada, si potrebbero generare 81 spade uniche.

Avvertenze

Avrete probabilmente notato alcuni problemi nel modo in cui questo algoritmo funziona.

Il primo problema è che la versione più semplice costruisce segrete come un albero di moduli, dove la sua radice è il modulo di partenza. Se si segue una qualsiasi diramazione della struttura nel dungeon, si è certi di finire in un vicolo cieco. Le ramificazioni dell'albero non sono interconnesse e il dungeon manca di un loop di stanze o corridoi. Un modo per risolvere questo sarebbe mettere da parte alcuni delle uscite del modulo per successive elaborazioni, non collegando nuovi moduli a queste uscite. Una volta che il generatore ha attraversato abbastanza iterazioni, si potrebbe scegliere, in modo casuale, una coppia di uscite, e tentare di collegarle con una serie di corridoi. Ci sarebbe un po' di lavoro algoritmico da fare per trovare un insieme di moduli e un sistema per interconnetterli in modo tale da creare un percorso accettabile tra queste uscite. Questo problema in sé è abbastanza complesso da meritare un articolo a parte.

Un altro problema è che l'algoritmo non è a conoscenza delle caratteristiche spaziali dei moduli che piazza; conosce solo i tag delle uscite, il loro orientamento e posizione. Questo fa sì che i moduli si sovrappongano. L'aggiunta di un semplice controllo di collisione tra un nuovo modulo da collocare intorno ai moduli esistenti permetterebbe all'algoritmo di costruire sotterranei che non soffrono di questo problema. Quando i moduli collidono, si potrebbe eliminare il modulo che si è cercato di piazzare e cercarne di piazzarne un'altro.

Gestire le uscite e le loro etichette è un altro problema. L'algoritmo suggerisce di definire tag per ogni istanza di uscit, e di "taggare" tutte le stanze, ma questo richiede un bel pò di lavoro di manutenzione, se c'è un modo diverso di collegare i moduli provate se volete. Ad esempio, se si desidera consentire alle stanze di connettersi a corridoi e svincoli, invece che solo corridoi, dovremmo passare attraverso tutte le uscite di tutte le stanze e aggiornare le loro etichette. Un modo per aggirare tutto questo è quello di definire le regole di connettività su tre livelli distinti: dungeon, modulo e uscite. Il livello dungeon dovrebbero definire le regole per l'intero dungeon, dovrebbe definire quali tag possono interconnettersi. Alcune delle stanze potrebbero essere in grado di ignorare le regole di connettività, quando sono elaborate. Si potrebbe avere una stanza "capo" che garantisse la presenza di una "stanza del tesoro" dietro di se. Alcune uscite dovrebbero sostituire i due livelli precedenti. Definire i tag per l'uscita permette la massima flessibilità, ma a volte troppo flessibilità non è buona.

La matematica in virgola mobile non è perfetta, e questo algoritmo si basa fortemente su di essa. Tutte le trasformazioni di rotazione, gli orientamenti arbitrari di uscita, e le posizioni si sommano e possono causare artefatti come cuciture o sovrapposizioni in cui le uscite si collegano, soprattutto lontano dal centro del mondo. Se fosse troppo evidente, è possibile estendere l'algoritmo per posizionare un punto supplementare dove i moduli lo richiedono, come ad esempio un telaio della porta o una soglia. Il vostro amico artista saprà sicuramente trovare un modo per nascondere le imperfezioni. Per dungeon di dimensioni ragionevoli (inferiore alle 10.000 unità), questo problema ancora non è evidente, assumendo che il posizionamento e rotazione dei marcatori di uscita dei moduli sia stato fatto con sufficiente cura.

Conclusione

L'algoritmo, nonostante alcuni difetti, offre un modo diverso di guardare alla generazione dei dungeon. Non sarete più costretti a rotazioni di soli 90 gradi e a stanze rettangolari. I vostri artisti apprezzeranno la libertà creativa che questo approccio offrirà, ed i vostri giocatori potranno godere di una sensazione più naturale dei dungeon.