Unlimited WordPress themes, graphics, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Game Development
  2. Programming
Gamedevelopment

Generare livelli caverna casuali con gli automi cellulari

by
Difficulty:IntermediateLength:LongLanguages:

Italian (Italiano) translation by Chip (you can also view the original English article)

I generatori di contenuti procedurali sono frammenti di codice scritto nel vostro gioco in grado di creare nuovi contenuti del gioco in qualsiasi momento - anche quando il gioco è in esecuzione! Gli sviluppatori di giochi hanno cercato di generare proceduralmente tutto, dai mondi 3D alle colonne sonore musicali. L'aggiunta di qualche generazione per il gioco è un ottimo modo per portarvi un valore aggiunto: i giocatori lo amano perché ottengono nuovi contenuti, imprevedibili ed emozionanti ogni volta che giocano.

In questo tutorial, vedremo un ottimo metodo per la generazione di livelli casuali e cercheremo andare oltre ai confini di ciò che si pensa sia possibile generare.


Benvenuti nelle Caverne!

In questo tutorial, andremo a costruire un generatore di caverne. Le caverne sono eccezionali per tutti i tipi di generi e le impostazioni di gioco, ma soprattutto mi ricordano i vecchi dungeon nei giochi di ruolo.

Date un'occhiata alla demo qui sotto per vedere il tipo di output che sarete in grado di ottenere. Fate click su 'New World' per produrre una nuova caverna da osservare. Parleremo di ciò che le varie impostazioni possono fare a tempo debito.


Questo generatore in realtà ci restituisce un grande array bidimensionale di blocchi, ciascuno dei quali è o solido o vuoto. Quindi, in realtà, è possibile utilizzare questo generatore per tutti i tipi di giochi, oltre i dungeon-crawler: livelli casuali per i giochi di strategia, mappe di tiles per giochi platform, forse anche come arene per uno sparatutto multiplayer! Se si guarda con attenzione, scambiando i blocchi solidi ed i vuoti rende anche l'idea di un generatore di isole. Tutto utilizzando lo stesso codice e lo stesso risultato, il che rende questo strumento molto flessibile.

Cominciamo da una domanda semplice: cosa, sulla terra è comunque un automa cellulare?


Iniziare dalle Cellule

Nel 1970, un matematico di nome John Conway ha pubblicato una descrizione di The Game Of Life (gioco della vita), talvolta chiamato solamente Life. Life non era davvero un gioco; era più simile a una simulazione che prendeva una griglia di celle (che potevano essere sia vive o morte) e vi applicava alcune semplici regole tra loro.

Quattro regole erano applicate a ciascuna cella in ogni fase della simulazione:

  1. Se una cellula vivente ha meno di due vicini che vivono, muore.
  2. Se una cellula vivente ha due o tre vicini viventi, rimane viva.
  3. Se una cellula vivente ha più di tre vicini che vivono, muore.
  4. Se una cellula morta ha esattamente tre vicini di casa viventi, diventa viva.

Bello e semplice! Ancora, se si provano diverse combinazioni di griglie di partenza, è possibile ottenere risultati molto strani. Loop infiniti, macchine che sputano forme, e altro ancora. The Game of Life è un esempio di un automa cellulare - una griglia di celle che sono governate da alcune regole.

Stiamo andando ad implementare un sistema molto simile a Life, ma invece di produrre modelli e forme divertenti, andremo a creare sistemi di caverne straordinarie per i nostri giochi.


Implementazione di un Automa Cellulare

Andremo a rappresentare la nostra griglia cellulare come un array bidimensionale di valori booleani (true o false). Questo ci si addice perché siamo interessati solo al caso in cui una tessera è piena o vuota.

Ecco la nostra inizializzazione della griglia di celle:

Suggerimento: Si noti che per la matrice, il primo indice è la coordinata x e il secondo indice è la coordinata y. Questo rende l'accesso all'array nel codice più naturale.

Nella maggior parte dei linguaggi di programmazione, questo array viene inizializzato con tutti i suoi valori impostati su false. Questo va bene anche per noi! Se un indice di array (x, y) è false, diremo che la cella è vuota; se è true, che la tile è solida roccia.

Ognuna di queste posizioni dell'array rappresenta una delle "celle" nella nostra griglia cellulare. Ora abbiamo bisogno di impostare la nostra griglia in modo da poter iniziare a costruire le nostre grotte.

Stiamo per iniziare impostando in modo casuale ogni cella come viva o morta. Ogni cella avrà la stessa possibilità casuale di essere viva, e dovremmo fare in modo che questa soglia di casualità si trovi in una variabile da qualche parte, perché vorremo sicuramente modificarla in un secondo momento e averla da qualche parte ce ne garantirà un facile utilizzo. Comincerò usando il 45%.

Our random cave before any cellular automaton simulation steps
La nostra grotta casuale prima di iniziare con qualsiasi simulazione di automa cellulare.

Se lanciamo questo codice, finiremo con una grande griglia di celle, come quella qua sopra, dove sono casualmente vive o morte. E 'disordinato, e sicuramente non assomiglia a nessun sistema di grotte che abbia mai visto. Allora, qual è la prossima mossa?


Accrescere le nostre grotte

Ricordate le regole che governavano le cellule nel The Game Of Life? Ogni volta che la simulazione va avanti di un passo, ciascuna cellula dovrebbe controllare le regole di Life e vedere se dovrebbe cambiare per essere viva o morta. Stiamo andando ad utilizzare esattamente la stessa idea per costruire le nostre caverne - scriveremo una funzione che cicla su ogni cella della griglia, e applica alcune regole di base per decidere se vive o muore.

Come si vedrà in seguito, abbiamo intenzione di utilizzare questo pezzo di codice più di una volta. Diamole anche un bel nome significativo come doSimulationStep().

Che cosa ha bisogno di fare la funzione? Ben prima, facciamo una nuova griglia dove poter mettere i nostri nuovi valori di cella. Per capire il motivo per cui abbiamo bisogno di fare questo, ricordate che per calcolare il nuovo valore di una cella della griglia, abbiamo bisogno di guardare i suoi otto vicini:

gdt_1

Ma se abbiamo già calcolato il nuovo valore di alcune delle cellule rimettendole nella stessa griglia, il nostro calcolo sarà un mix di vecchi e nuovi dati, come questo:

gdt_2

Oops! Questo non è quello che vogliamo. Così ogni volta che si calcola un nuovo valore di una cella, invece di rimetterlo nella vecchia mappa, andremo a scriverlo in una nuova.

Cominciamo a scrivere questa funzione doSimulationStep(), allora:

Vogliamo considerare ogni cella della griglia e contare quanti dei suoi vicini sono vivi e morti. Contare i vostri vicini di un array è una di quelle parti di codice più noiose che vi capiterà di scrivere anche in un milione di volte .. Ecco una rapida implementazione di in una funzione che ho chiamato countAliveNeighbours():

Un paio di cose su questa funzione:

In primo luogo, il ciclo for è un po 'strano, se non hai fatto qualcosa di simile prima. L'idea è che vogliamo guardare a tutte le cellule che sono intorno al punto (x, y). Se guardate la figura qui sotto, si può vedere come gli indici che vogliamo sono uno in meno, pari a, e un in più all''indice originale. I nostri due cicli for partono proprio da  -1 e iterano fino a +1. Poi incrementiamo l'indice originale all'interno del ciclo for per trovare ogni suo vicino.

gdt_3

In secondo luogo, si noti come se stiamo controllando una griglia di riferimento che non è reale (esempio, il bordo della mappa) contiamo come un vicino di casa. Io preferisco questo metodo per la generazione di caverne perché tende a riempire i bordi della mappa, ma è possibile sperimentare facendo diversamente, se volete.

Ora, torniamo alla nostra funzione doSimulationStep() e aggiungiamo qualche codice più:

Questo cicla sopra l'intera mappa, applicando le nostre regole a ciascuna cella della griglia per calcolare il nuovo valore e lo colloca nella newMap. Le regole sono più semplice del Game of Life - abbiamo due variabili speciali, una per il parto le cellule morte (birthLimit), e una per uccidere le cellule vive (deathLimit). Se le cellule viventi sono circondate da meno di deathLimit cellule allora muoiono, e se alle cellule morte sono vicine almeno birthLimit cellule allora rivivono. Bello e semplice!

Tutto ciò che rimane alla fine è il tocco finale per restituire la mappa aggiornata. Questa funzione rappresenta un singolo passo nelle regole del nostro automa cellulare - il passo successivo sarà quello di capire che cosa accade quando si applica una volta, due volte o più volte per la nostra mappa iniziale.


Ritocchi e messa a punto

Diamo un'occhiata a ciò che il codice principale di generazione sembra, utilizzando il codice che abbiamo scritto finora.

L'unico pezzo veramente nuovo del codice è un ciclo for che esegue il nostro metodo di simulazione un determinato numero di volte. Anche in questo caso, prendiamo una variabile in modo da poterla cambiare, perché adesso inizieremo a giocare con questi valori!

Finora abbiamo impostato queste variabili:

  • chanceToStartAlive imposta la densità della griglia iniziale con le cellule viventi.
  • starvationLimit è il limite più basso di vicini con cui le cellule cominciano a morire.
  • overpopLimit è il limite superiore di vicini a cui le cellule cominciano a morire.
  • birthNumber è il numero di vicini che causano per una cellula morta di diventare vivi.
  • numberOfSteps è il numero di volte di passi che la simulazione esegue.
Our random cave after two cellular automaton simulation steps
La nostra caverna casuale dopo due fasi di simulazione automa cellulare.

Si può giocherellare con queste variabili nella demo nella parte superiore della pagina. Ogni valore cambierà la demo drammaticamente, quindi giocateci per vedere ciò che si adatta meglio alle vostre esigenze.

Uno dei cambiamenti più interessanti che si possono fare è la variabile numberOfSteps. Eseguendo la simulazione più volte, la rugosità della mappa scompare e le isole si dissolveranno nel nulla. Ho aggiunto un pulsante in modo che sia possibile richiamare la funzione manualmente voi stessi, e vedere gli effetti. Sperimentare un pò e troverete una combinazione di impostazioni che si adatta allo stile ed al tipo di livello di cui ha bisogno il vostro gioco.

Our random cave after six cellular automaton simulation steps
La nostra caverna casuale dopo sei passi di simulazione dell'automa cellulare.

Con questo, il gioco è fatto. Congratulazioni - avete appena creato un un generatore di livelli procedurale, ben fatto! Sedetevi, eseguite ed eseguite il codice e sorridete ai meravigliosi e strani sistemi di caverne che vengono fuori. Benvenuti nel mondo della generazione procedurale.


Andiamo oltre

Se state a guardare il generatore di caverne e vi chiedete cosa altro ci si può fare, qui ci sono un paio di idee:

Usare il Flood Fill (n.d.a. algoritmo di riempimento per inondazione) per fare Qualità e Controllo

Il Flood Fill è un algoritmo molto semplice che è possibile utilizzare per trovare tutti gli spazi di un array che si collegano a un particolare punto. Proprio come il nome suggerisce, l'algoritmo funziona un pò come versare un secchio d'acqua nel vostro livello - si diffonde dal punto di partenza riempie tutti gli angoli.

Il Flood Fill è eccezionale per gli automi cellulari, perché è possibile utilizzarlo per vedere quanto sia grande una particolare caverna. Se si esegue la demo un paio di volte si noterà che alcune mappe sono costituite da una grande caverna, mentre altre hanno un paio di grotte più piccole che sono separate le une dalle altre. Il Flood Fill può aiutare a rilevare quanto è grande un caverna e quindi a rigenerare il livello se è troppo piccola o a decidere dove si desidera che il giocatore inizi se si crede la caverna grande abbastanza. C'è una ottimo approfondimento sul flood fill su Wikipedia.

Rapido e semplice piazzamento di tesori

Posizionare tesori in zone adatte a volte richiede un sacco di codice, ma possiamo effettivamente scrivere un bel pò di semplice codice per inserire tesori nelle nostro sistema di caverne. Abbiamo già il nostro codice che conta il numero di vicini che ha un quadrato, così iterando il nostro sistema di caverne appena finito, possiamo vedere come una particolare stanza sia circondata da pareti.

Se una cella vuota della griglia è circondata da un sacco di solide mura, è probabilmente alla fine di un corridoio o nascosta dalle pareti del sistema di caverne. Questo è un ottimo posto per nascondere il tesoro - così facendo un semplice controllo dei nostri vicini possiamo infilare tesori negli angoli e nei vicoli.

Questo non è perfetto. A volte mette tesori in buchi inaccessibili nel sistema di caverne, e talvolta i posti saranno molto evidenti. Ma, è un ottimo modo per spargere oggetti collezionabili in giro per il vostro livello. Provatelo nella demo premendo il pulsante placeTreasure()!


Conclusioni e ulteriori letture!

Questo tutorial vi ha mostrato come costruire un generatore procedurale essenziale ma completo. Con pochi semplici passi abbiamo scritto il codice in grado di creare nuovi livelli in un batter d'occhio. Speriamo che questo vi abbia dato un assaggio delle potenzialità nel costruire generatori di contenuti procedurali per i vostri giochi!

Se volete saperne di più, Roguebasin è una grande fonte di informazioni sulla generazione di sistemi procedurali. Si concentra soprattutto su giochi roguelike, ma molte delle sue tecniche possono essere utilizzate in altri tipi di giochi e c'è anche un sacco di ispirazione per la generazione procedurale su altre parti di un gioco!

Se volete saperne di più sulla Generazione Procedurale di Contenuti o sugli Automi Cellulari, ecco una eccezionale versione online di The Game Of Life (anche se io mi raccomando di digitare "Game of Life di Conway" su Google). Ti potrebbe piacere anche Wolfram Tones, un esperimento affascinante nell'utilizzo di automi cellulari per generare musica!

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.