venerdì 15 aprile 2011

FACCIAMO UN (VIDEO)GIOCO? - PARTE 2


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".

6 commenti:

Mattia Bulgarelli (K. Duval) ha detto...

Provo a rispondere al quiz a sorpresa.

Perché se considero una sola cella(*) e poi vado avanti con lo "scavo", non riesco ad avere una cella di "muro" per fare le svolte nei corridoi.

Cioè, una svolta diventerebbe una stanza.

Insomma, mi sono spiegato da cani. X_X


(*) (mentalmente la chiamo "casella"... Troppi videogiochi... No, wait...)

Luca Bonisoli ha detto...

Risposta esatta, bravissimo!!!
Riesci a rispondere anche agli altri due quiz a sorpresa? ^__-

Mattia Bulgarelli (K. Duval) ha detto...

Proviamo... Quiz 2: se conti "0;0" la casella d'angolo, le uscite devono essere in posizione dispari per "aprire" in un punto in cui ci sia un corridoio e non un muro.

Anche il numero dispari di lato serve per assicurarsi di finire con una riga di muro...?


Terzo quiz a sorpresa:

Vediamo... La cosa più semplice per un umano (ma non necessariamente la più efficiente) potrebbe essere "per ogni casella controlla che tra le 8 sue confinanti ce ne sia SOLO UNA vuota".

Luca Bonisoli ha detto...

Bravo Mattia! Tre colpi, tre centri quasi perfetti!

Per il quiz n° 2, l'obiettivo è quello di finire in tutte le direzioni con una riga (o una colonna) di corridoio, non di muro. In questo modo posso ottimizzare il numero di corridoi nella mappa, senza "sprecare" righe o colonne che rimarrebbero vuote (in sostanza è la stessa cosa che dici tu, ma traslata di una cella).

Per il quiz n° 3, non è necessario controllare tutte e 8 le caselle adiacenti, ma solo le 4 caselle in alto, in basso, a destra e a sinistra.

Mattia Bulgarelli (K. Duval) ha detto...

2) Con quello che mi hai mandato per mail è più chiaro: tutto ciò che è "fuorimappa" il programma lo considera "muro", giusto?

3) Sì, giusto. Possono esistere corridoi che sono chiusi solo per uno spigolo.

Luca Bonisoli ha detto...

2) Esatto: l'esempio del labirinto scavato nella montagna non era un caso... ^__^

3) Anch'io ci ho messo un po' ad arrivarci. All'inizio mi stupivo del fatto che in alcuni vicoli ciechi non ci fosse un tesoro, poi mi sono reso conto che il programma considerava erroneamente anche le celle "in diagonale" ed ho apportato le necessarie correzioni.