Guida MMOG Optimizations

ManHunter

Utente Jade
14 Settembre 2009
985
111
780
818
Ultima modifica:
Salve,
in questo thread cercherò di raccogliere informazioni, consigli ed esperienze di chi ha già avuto a che fare con lo sviluppo di giochi multiplayer e massive multiplayer.
Il fine ultimo è quello di avere una conoscenza ampia e alla portata di chi vuole imparare seriamente, scambiandosi informazioni e crescendo. Pertanto, quindi non raccoglierò codice, ma algoritmi e concetti specifici. Starà poi a chi si affaccia a questo campo (o chi si è già affacciato) assimilare ed applicare queste conoscenze.
Abbiamo due modi per far crescere questa discussione: porre domande sensate/dubbi che incontrate nello sviluppo di questi concetti o condividere una conoscenza che avete già acquisito.

Detto ciò, inizio io con la mia esperienza acquisita dallo sviluppo di Heroes of Asgard, un MMORPG in sviluppo da quasi due anni.

DEFINITION
Per definizione, un MMOG deve mettere in condizione di giocare con una enormità di persone contemporaneamente ed interagire con loro come fosse un normale gioco multiplayer, tutto questo in un mondo persistente.
Ora, se vogliamo sviscerare un po' di più questa affermazione, inizieremo a notare come questo sia impossibile senza applicare vari "trucchi" dietro le quinte.

WE ARE COMPLAINING ABOUT PERFORMANCES
Si può sicuramente capire come al crescere dei giocatori connessi, le performance del server vadano degradandosi.
Molte delle operazioni sul server necessitano di operare sull'insieme totale dei giocatori connessi o su un subset di essi, su tutti gli oggetti in giro, su tutti i mostri e le loro AI, ecc. Il tutto varie volte al secondo: immaginiamo, quindi, di dover iterare su 200 giocatori, dover iterare su 2000 giocatori o dover iterare su 20000 giocatori, ad ogni frame della simulazione. Ad ogni iterazione dovrò mandare pacchetti, fare calcoli, modificare posizioni, ecc. C'è, quindi, una crescita esponenziale del carico computazionale per ogni nuovo giocatore connesso.
Come si può ben immaginare, è una mole di lavoro molto grande per una singola macchina, questo per via di un ovvio cap hardware.
Di solito, quindi, esiste una soglia massima di giocatori gestibili contemporaneamente, oltre la quale il server stesso (la macchina fisica) non riesce a stare al passo, creando un'esperienza di gioco negativa (lag, unresponsive commands, etc).
Si può non accettare nuove connessioni oltre questa soglia finché non si libera un posto, al fine di non rovinare l'esperienza a chi è già collegato e sta giocando.
Si potrebbe quindi avviare più server su diverse macchine ai quali far collegare il giocatore, però ovviamente non potranno interagire con giocatori di altri server.
La divisione in varie "server instance" sicuramente non rientra nella definizione di MMOG, in quanto non ti permette di interagire con tutta l'utenza in un mondo persistente, ma crea istanze differenti dello stesso mondo.

Detto ciò, cosa si può fare per "aggirare" un pochino questo problema? E cosa è stato fatto nello specifico di Heroes of Asgard? Quello che descriverò è frutto della mia esperienza e, quindi, è anche ciò che ho infuso nella scrittura di Heroes of Asgard, tentando ovviamente di ottenere il meglio.

WHAT CAN WE DO?
Ci sono diversi accorgimenti che si possono applicare per migliorare quella soglia massima. Sì, migliorarla: ci sarà sempre una soglia massima oltre la quale è difficile andare mantenendo il medesimo hardware.

keep-calm-and-optimize-169-257x300.png

YOU ARE THE CODE THAT YOU WRITE
Primo fra tutti: scrivere codice decente, con un cervello collegato e senza inutile spreco di risorse. Può sembrare ovvio e banale, ma non lo è. Sprecare risorse equivale a peggiorare le risorse disponibili del server, facendo giungere prima alla soglia massima di giocatori ospitabili.
Sprecare banda significa esaurirla prima, ogni singolo dato che viene trasmesso va accuratamente selezionato. Se io mando un byte in più per ogni utente, quando ne ho 20000 significa inviare quasi 20KB in più per ogni frame.
Sprecare cicli di CPU è come darsi la zappa sui piedi: le operazioni che si eseguono devono essere ridotte al minimo indispensabile, aggiungere una sola chiamata a funzione in più per utente può significare aggiungere N cicli di CPU, che per 20000 utenti saranno N x 20000 cicli di CPU aggiuntivi.
Sprecare memoria (quindi allocare risorse inutili) è deleterio: l'allocazione richiede sia vari cicli di CPU, sia memoria. E la memoria finisce.
In ambienti managed, inoltre, lasciare risorse allocate provoca Garbage Collection, che può significare spendere enormi tempi di CPU per liberare risorse, anziché servire i giocatori e simulare il mondo.
In definitiva, sprecare risorse nel vostro codice farà sì che spenderete più soldi per server migliori e li spenderete più frequentemente per migliorarli al crescere dell'utenza, al fine di mantenere performance accettabili.

FIX YOUR SIMULATION
Come saprete, la simulazione di un mondo virtuale può essere eseguita un tot di volte al secondo dal server. Questo significa che ogni secondo, tutte le entità e i sistemi presenti nel mondo vengono "simulati" un tot di volte. La simulazione può comprendere routine di AI, aggiornamenti di posizioni/rotazioni, etc. Permette di dare una "vita propria" al mondo virtuale.
Il numero di volte che la simulazione viene eseguita è detto FPS, ovvero Frames Per Second. Va da sè che se la simulazione è pesante e richiede tempo, il nostro hardware tenderà a simulare il mondo meno volte in un secondo. Questo può portare ad un degrado della simulazione.
Ma riflettiamo: per ogni gioco è necessario un gran numero di simulazioni al secondo da parte del server? Dobbiamo per forza sforzare l'hardware in questa maniera? Non si può, invece, migliorare la cosa?
Sì. Per gran parte dei giochi con pochi giocatori nella stessa mappa e una velocità di gioco elevata (vedi gli FPS, con un alto numero di comandi) sono sufficienti 60FPS (o meno, dipende dal tipo di gioco ovviamente).
Per un MMOG possono bastarne anche meno, a seconda del genere.
Non c'è necessità di simulare il mondo quante più volte al secondo possibile, dato che la simulazione cambierebbe in modo minimo sprecando più risorse del necessario.
In Heroes of Asgard, ad esempio, il mondo è simulato 20 volte al secondo per ora.

DO WE NEED TO KNOW ABOUT THE ENTIRE WORLD?
Abbiamo detto che in un MMOG si deve interagire con gli altri giocatori e con l'ambiente circostante e devo avere la possibilità di farlo con chiunque si trovi nel mondo in quel momento. Giustissimo, certo.
Ma dal punto di vista di un giocatore è davvero necessario sapere cosa sta facendo un giocatore dall'altro lato della mappa? No, non sempre. Anzi, nella maggioranza dei casi ad un giocatore non interessa minimamente sapere se un altro giocatore, ad esempio, sta camminando o meno in un'altra area distante. Inviare, quindi, informazioni non rilevanti e che non possono essere mostrate sullo schermo dell'utente equivale ad uno spreco di risorse.
Questa osservazione è importante, ci permette di attuare un'ottimizzazione di un certo spessore.
Come posso fare ad informare un determinato giocatore solo sulle entità che possono interessargli?
Perché non suddividere la mappa (o le mappe) in zone? La suddivisione più facile è quella a griglia: dividere la mappa in N x M zone, dove N ed M sono maggiori o uguali ad 1. Questa tecnica è anche nota come space partitioning o zone partitioning.
In questo modo, un giocatore potrà ricevere informazioni solo sulle entità contenute nella sua zona, senza dover per forza avere conoscenza di entità lontane. Se nella mia mappa sono uniformemente distribuite 8000 entità ed è divisa in una griglia 4 x 4, il giocatore che si trova nella zona [1, 1] avrà l'onere di ricevere informazioni solo su 500 entità. Un bel vantaggio, no?
Ma riflettiamo: se il giocatore si trova sul bordo di una zona, non vedrà i giocatori nella zona vicina, nonostante essi debbano essere visibili.
Possiamo dunque capire che il giocatore dovrà essere informato sulle entità contenute nella sua zona e in quelle immediatamente contigue.
La dimensione delle zone permette di ottimizzare molto questo metodo, quindi a seconda delle dimensioni di una mappa può variare la dimensione della griglia, al fine di ottenere l'effetto migliore. Addirittura, può variare la forma delle zone, per adattarsi meglio alla composizione della mappa.

LOOK FAR AS THE EYE CAN SEE
Come detto, la divisione in zone offre già un discreto livello di ottimizzazione permettendoci di inviare informazioni su di una entità solo ai giocatori che realmente possono trarne beneficio.
Ma poniamoci una domanda: all'interno delle zone di interesse (che ricordiamo comprendono anche quelle contigue, quindi in una normale griglia saranno 9 zone nel peggiore dei casi) possiamo individuare informazioni inutili? Certo che sì.
Molto probabilmente ad un giocatore non interesseranno comunque le entità più distanti del suo raggio d'azione, ma di più non interesseranno le entità al di fuori del suo raggio visivo.
Se io non posso vedere un'entità, non mi interessa tracciare cosa sta facendo, nonostante possa trovarsi nella mia zona di interesse. Quindi l'invio di informazioni su quell'entità è uno spreco di risorse.
Come si può determinare quindi cosa effettivamente interessa ad uno specifico giocatore? Il modo più semplice è quello di tracciare, appunto, il raggio visivo. Tutto ciò all'interno di quel raggio è ciò che interessa allo specifico giocatore, le entità al di fuori sono non necessari alla simulazione del mondo per quello specifico giocatore.
E dal momento che abbiamo già una divisione in zone, possiamo semplicemente iterare sulle entità nella zona di interesse (invece che su tutte le entità nella mappa) per stabilire chi è dentro il nostro raggio visivo. Questa concetto è anche chiamato area of interest o AoI.
Quindi, riprendendo l'esempio di prima, itereremo su 500 entità invece di 8000, per estrapolarne quegli ipotetici 25 che rientrano nel raggio visivo e scambiare informazioni attraverso la rete solo con loro.
Da 8000 a 25, un bel risultato. E il tutto senza che l'utente risenta delle mancate informazioni, dato che non le vede. Anzi, potrà notare un minore utilizzo di risorse.
Si può ulteriormente migliorare l'area of interest, applicando vari accorgimenti:
  • organizzare vari livelli di raggi visivi; le entità più distanti riceveranno aggiornamenti meno frequentemente
  • filtrare ulteriormente le entità interessanti a seconda della morfologia della mappa; se una entità è nel nostro raggio visivo, ma dietro ad una montagna, posso eventualmente ignorarla. Quest'ultimo accorgimento, però, a mio avviso ha senso soltanto se già utilizzate il culling per altre cose, in modo da non introdurre ulteriori calcoli solo per filtrare poche altre entità

DISTRIBUTE YOUR COMPUTATION LOAD
Abbiamo già detto che una singola macchina avrà comunque una certa soglia oltre la quale, nonostante tutte le ottimizzazioni fatte, si avvertirà un degrado delle prestazioni (e quindi una cattiva esperienza di gioco).
Bene, ma quindi perché non sfruttare più calcolatori contemporaneamente?
Ci sono ovviamente diversi modi per farlo.
Ad esempio, in Heroes of Asgard ogni mappa che compone il mondo è ospitata su un processo a parte. Questo fa sì che ogni mappa può essere ospitata su una macchina fisica diversa.
Ovviamente, però, si può scendere ancor più di livello e ospitare insiemi di zone su processi separati (in modo che una singola mappa possa essere divisa in più parti e ospitata da diversi server).

SLICE YOUR PIE
Si possono, inoltre, raggruppare servizi globali (come la chat) su processi differenti e/o server differenti, in modo da dare l'impressione che, anche essendo collegati a mappe diverse (quindi server diversi), si possa interagire con giocatori distanti. Inoltre, scindere questo tipo di servizi dal mondo principale fa ottenere un ulteriore guadagno in termini di prestazioni.

RECYCLE YOUR TOYS
Come già detto, allocare memoria costa. Quindi perché non riutilizzare ciò che si è già allocato? L'utilizzo di objects pools è di grande importanza nello sviluppo multiplayer. Permette di spostare l'onere dei costi di allocazione quando essi possono essere affrontati senza problemi, ad esempio in fase di bootstrap della nostra server app.
Un mostro viene sconfitto e muore? Bene, lo metto da parte. Posso riutilizzarlo quando un altro mostro deve essere spawnato, semplicemente recuperandolo dal mio pool.
Ovviamente è chiaro che bisogna utilizzare un determinato criterio per poter scegliere quali oggetti mantenere in memoria e quali no. Mantengo in memoria un pool di un mostro che spawna una volta al mese? No, può essere inutile. Mantengo in memoria un pool di object rappresentanti il drop della valuta? Sì, ha più senso.



USEFUL LINKS
Altra importante parte di questa iniziativa è la raccolta di materiale interessante. Articoli, paper, testi: qualsiasi fonte di conoscenza riguardo questo argomento può essere utile.

Spatial Partitioning
http://gameprogrammingpatterns.com/spatial-partition.html
Objects Pooling
http://gameprogrammingpatterns.com/object-pool.html
Game loop
http://gafferongames.com/game-physics/fix-your-timestep/

Per il momento non aggiungo altro, sentitevi liberi di esporre domande o aggiungere vostre osservazioni.
Aggiungerò informazioni man mano che ne avrò voglia.

Saluti,
Emanuele
 
Il fatto di avere un sistema intelligente che usi TCP o UDP per la comunicazione in base alla qualità della banda del giocatore che gioca è senza dubbio un altro vantaggio enorme.
 
  • Mi piace
Reazioni: ManHunter
Il fatto di avere un sistema intelligente che usi TCP o UDP per la comunicazione in base alla qualità della banda del giocatore che gioca è senza dubbio un altro vantaggio enorme.
Uhm, credo che questo concetto non sia corretto: ti spiego perché.

Mettiamo caso io realizzo la mia architettura basata su TCP. Voglio realizzare anche il sistema che hai detto tu per ottimizzare il tutto a favore dei giocatori che abbiano una certa banda, quindi realizzo anche un sistema identico, ma basato su UDP.
Siccome ci sono diversi tipi di dati da inviare (con differenti necessità), ho bisogno che questo sistema basato su UDP possa riprodurre le stesse funzionalità offerte dall'architettura basata su TCP.
Quindi ho bisogno di implementare un layer di reliability anche per l'UDP, una sorta di "stato della connessione", ecc.

Una volta realizzato il tutto, quindi, cosa ti ritrovi? Una architettura TCP e una architettura UDP con le stesse funzionalità.
Ha quindi senso utilizzare ancora l'architettura TCP, sapendo che hai l'equivalente ottimizzata? Non penso: arrivati a questo punto userai soltanto l'architettura UDP, utilizzandola per ogni utente collegato.
 
  • Mi piace
Reazioni: </Singh>™
Uhm, credo che questo concetto non sia corretto: ti spiego perché.

Mettiamo caso io realizzo la mia architettura basata su TCP. Voglio realizzare anche il sistema che hai detto tu per ottimizzare il tutto a favore dei giocatori che abbiano una certa banda, quindi realizzo anche un sistema identico, ma basato su UDP.
Siccome ci sono diversi tipi di dati da inviare (con differenti necessità), ho bisogno che questo sistema basato su UDP possa riprodurre le stesse funzionalità offerte dall'architettura basata su TCP.
Quindi ho bisogno di implementare un layer di reliability anche per l'UDP, una sorta di "stato della connessione", ecc.

Una volta realizzato il tutto, quindi, cosa ti ritrovi? Una architettura TCP e una architettura UDP con le stesse funzionalità.
Ha quindi senso utilizzare ancora l'architettura TCP, sapendo che hai l'equivalente ottimizzata? Non penso: arrivati a questo punto userai soltanto l'architettura UDP, utilizzandola per ogni utente collegato.
Per chi fosse interessato
http://gafferongames.com/networking-for-game-programmers/udp-vs-tcp/
 
  • Mi piace
Reazioni: ManHunter
E' un po' ciò di cui parlavo!

"My recommendation then is not only that you use UDP, but that you only use UDP for your game protocol. Don’t mix TCP and UDP, instead learn how to implement the specific pieces of TCP that you wish to use inside your own custom UDP based protocol."

P.S: per chi fosse interessato, Glenn ha anche un repository per la sua libreria di networking: https://github.com/networkprotocol/libyojimbo