L’algoritmo di generazione procedurale che utilizzo prende in considerazione diversi dati che vengono impostati nel momento in cui viene creato l’istanza del dungeon: anche in questo caso il nome del dungeon influenza la natura e l’entità delle informazioni, come il numero o i limiti alla dimensione delle stanze, la lunghezza dei corridoi, il tipo di stanze presenti o la quantità di liquidi (acqua, fango, lava).

Avendo a disposizione un oggetto contenente tutti questi dati (nonchè la mappa stessa, una matrice bidimensionale di caratteri), procedo con l’esecuzione dell’algoritmo, con la seguente struttura, derivata in parte dal lavoro di Mike Anderson:

1. Riempio l’intera mappa di tile muro.
2. Creo una stanza all’interno della mappa, con posizione e dimensioni casuali.
3. Eseguo un ciclo che ad ogni iterazione si occupa di inserire una “feature” casuale all’interno della mappa:

- mi posiziono su una posizione casuale corrispondente al muro di una stanza (un tile “vuoto” adiacente ad un muro).
- decido casualmente la feature da creare (stanza, corridoio, caverna, ecc.)
- determino le dimensioni e le coordinate della feature, e controllo che questa non vada oltre i limiti di mappa e non si sovrapponga agli elementi già inseriti.
- una volta ottenuti dati validi, creo la feature nella mappa (basilarmente si tratta di aree rettangolari: per le caverne vado a includere tile muro in posizioni casuali per rendere la forma irregolare).
- considero eventuali probabilità di presenza di liquidi, ed in caso effettuo il riempimento (casuale) nell’area selezionata.

4. Inserisco tile muro lungo i bordi di mappa (questo è più che altro per estetica).

5. Se richiesto, aggiungo delle sezioni predefinite (crateri di lava, parti labintiche, fiumi, caverne circolari ecc.)

6. Creo i punti di entrata ed uscita (con i dovuti controlli sulla posizione estratta).

7. Verifico l’esistenza di un percorso valido tra il punto d’entrata ed il punto di uscita del livello, utilizzando un algoritmo di pathfinding A*. Nel caso le due posizioni siano isolate, provvedo a creare un percorso utilizzando uno tra più metodi, estratto a caso (creando tile vuoti lungo la linea Bresenham tra i due punti, incrociando un corridoio verticale ed uno orizzontale che attraversino rispettivamente uno dei due punti in esame, ecc.)

8. Inserisco le porte, in posizioni valide che ne giustifichino la presenza (principalmente, un tile vuoto tra due tile muro).

Per ogni ciclo implementato in genere inserisco un contatore di sicurezza che lanci un break una volta raggiunto un certo numero di iterazioni – una piccola precauzione per evitare loop infiniti (almeno nei casi in cui non riesco a risalire immediatamente al problema, o se effettivamente il risultato del ciclo non è rilevante).

E nell’immagine a lato ecco alcuni dungeon generati dall’algoritmo: la grafica dei muri cambia a seconda del tipo di dungeon, ed il colore dipende dalla temperatura generale. Sono alcuni tocchi stilistici che puntano sempre ad aumentare la varietà. A questo scopo si potrebbero anche inserire ulteriori sezioni predefinite.

Ma l’algoritmo è anche migliorabile: come si può notare, nelle Frozen Caverns c’è una stanza completamente sgombra dal ghiaccio, e dovrebbe essere quella generata al passo 2. E’ qualcosa che si può evitare con molta facilità – anche solo tenendo da conto le coordinate e le dimensioni per essere sicuri che venga presa in considerazione (ora non ricordo perchè questo non accade, ma un motivo ci sarà – un motivo c’è sempre).

E non tutti i dungeon sono soddisfacenti: nella seconda immagine è possibile ammirare alcuni esempi piuttosto anomali, in cui il minimo che può accadere è che siano presenti sezioni scollegate da tutto il resto (ed in questo caso mi basterebbe introdurre un controllo simile a quello al passo 7. per ogni sezione predefinita inserita sulla mappa), mentre il massimo è un dungeon di dimensioni ridottissime.
Non si parla di problemi di natura trascendentale, o tali da rendere impraticabile l’applicazione o il gioco vero e proprio, ma restano comunque dei bug di cui terrò da conto nelle successive rifiniture e ottimizzazioni (a parte nel caso dell’Hot Daedalus, dove dovrei capire come mai non è stato generato praticamente nulla, tanto da costringere l’algoritmo ad utilizzare direttamente una delle soluzioni adottate al punto 7).