
Il videogioco che ho iniziato a realizzare e di cui ho parlato nel
precedente post sarà suddiviso sostanzialmente in due parti: una di
esplorazione del labirinto ed una di
combattimento e gestione dei personaggi creati dai giocatori.
Visto che queste due parti si sovrappongono molto poco, possiamo tranquillamente iniziare dalla prima senza preoccuparci troppo, per il momento, della seconda.
Concentriamoci quindi sull'esplorazione del labirinto.
Primo problema: per avere un labrinto da esplorare, bisogna crearlo! Come si può fare?Ricorderete che l'idea iniziale era quella di impostare il gioco in modo
procedurale, quindi la creazione dei labirinti dev'essere
automatica.
Esistono diversi
algoritmi per generare labirinti. Quello che ho scelto è chiamato "
Randomized depth-first search" implementato con una variante detta "
Recursive backtracking". Al di là dei nomi, che sembrano complicatissimi e spaventano, il procedimento in realtà è relativamente semplice:
1 - Il labirinto può essere pensato come una griglia quadrata di celle, che all'inizio sono tutte "piene" (come se si trovassero sepolte all'interno di una montagna).
2 - Si individua a caso una
cella di partenza ad un'estremità del labirinto e la si "svuota" (come se si scavasse via un cubo di roccia dentro la montagna).
3 - Si controlla quali celle tra le confinanti sono "piene", considerando un raggio di 2 celle (cioè: non solo le celle confinanti, ma anche quelle dietro di esse). All'inizio, naturalmente, tutte le celle sono piene e quindi tutte le direzioni sono "ammissibili" per costruire il labirinto. Il dettaglio di considerare 2 celle anzichè 1 è molto importante, ma non voglio addentrarmi troppo in tecnicismi, quindi non sto a spiegarvi il motivo (
quiz a sorpresa: chi riesce ad arrivarci da solo?).
4 - Si sceglie a caso una direzione tra quelle ammissibili e si "scavano" due celle consecutive, svuotandole.
5 - Ci si sposta nell'ultima cella appena svuotata.
6 - Si continua a "scavare" ripetendo i passaggi 3-4-5 e cambiando direzione a caso, fino ad arrivare a una cella dove non è più possibile "scavare" in nessuna direzione.
Questa cella è l'uscita. Se guardiamo bene, ci accorgiamo che
il percorso finora è privo di ramificazioni ed occupa solo una porzione relativamente piccola della griglia, quindi non è un granchè come labirinto.
7 - Per
aggiungere le ramificazioni, si ripercorre all'indietro il percorso "scavato", spostandosi di due passi (due celle) alla volta, fino a trovarne una da cui si può ricominciare a "scavare" in un'altra direzione.
8 - Si "scava" fino a quando è possibile, poi di nuovo si ritorna indietro passo-passo fino al punto in cui si può ricominciare a "scavare" in un'altra direzione, e così via fino a quando non si è ritornati alla cella di partenza e non è più possibile scavare in nessuna direzione.
Il labirinto ora è completo, però è composto solo da corridoi, senza stanze.
9 -
Per
aggiungere anche le stanze, si possono distribuire a caso nella mappa un certo numero di blocchi quadrati di 2 x 2 celle vuote, "scavando" le celle "piene" che cadono all'interno di quei blocchi. Il risultato saranno
stanze dalla forma irregolare, che derivano dall'interazione casuale tra la geometria dei corridoi e quella dei blocchi 2 x 2.
Che fatica! A leggerlo sembrava più semplice!Però almeno adesso i labirinti creati automaticamente hanno un
aspetto decente, inoltre posso
generarne un numero pressochè infinito, ognuno diverso dall'altro... e tutto quello che deve fare il giocatore è
specificare lunghezza e larghezza della griglia!
(altro quiz a sorpresa: per un risultato ottimale, lunghezza e larghezza del labirinto devono essere due numeri dispari e anche la cella iniziale deve trovarsi in posizione "dispari". Sapreste spiegarmi perchè?)Proseguendo, ora che abbiamo il nostro labirinto possiamo
popolarlo di elementi "statici" (cioè: che non si muovono).
-
Entrata e
uscita le abbiamo già individuate. Per aggiungere un pizzico di sfida in più, mettiamo un mostro che funga da "
boss di fine livello" proprio davanti all'uscita.
- Poi passiamo ai
forzieri. Per semplicità li collocheremo alla fine di tutti i "
vicoli ciechi" (
terzo quiz a sorpresa: come posso far capire al computer che una cella si trova alla fine di un vicolo cieco e non invece in mezzo a un corridoio?). Alcuni forzieri conterranno un
tesoro ed altri una
trappola, con una probabilità che dipende dalle impostazioni definite dal giocatore.
- Infine, visto che utilizzando l'algoritmo "depth-first search" i vicoli ciechi (e quindi i forzieri) sono molto pochi, dobbiamo aggiungere anche ulteriori
tesori e trappole distribuiti a caso nei corridoi e nelle stanze. Anche in questo caso il numero di tesori e di trappole dipende dalle impostazioni definite dal giocatore.
Uno dei possibili risultati, disegnato con caratteri di testo, potete vederlo nella figura all'inizio di questo articolo. E' la rappresentazione di un labirinto generato automaticamente in una griglia di 21 x 21 celle. Le impostazioni definite dall'utente sono solo 4: lunghezza, larghezza, frequenza dei tesori, frequenza delle trappole. Tutto il resto è generato dal motore di gioco.
Legenda:# = Muro
* = Casella di partenza
$ = Forziere contenente un tesoro
T = Forziere contenente una trappola
+ = Tesoro lungo un corridoio o in una stanza
! = Trappola lungo un corridoio o in una stanza
B = Boss di fine livello
@ = Teletrasporto (uscita)
Nel prossimo articolo ci occuperemo della schermata che riproduce la visuale "in soggettiva".