Rappresentare un Gameworld di forma irregolare

Question

Sto lavorando a un progetto in cui il mondo di gioco è di forma irregolare (si pensi alla forma di un lago). questa forma ha una griglia con le coordinate posizionate sopra di essa. Il mondo del gioco è solo all'interno della forma. (Ancora una volta, pensa Lake)

Come posso rappresentare in modo efficace il mondo di gioco? So che molti mondi sono fondamentalmente quadrati e funzionano bene in un array di 2 o 3 dimensioni. Mi sento come se usassi un array che è quadrato, quindi fondamentalmente spreco spazio e aumentando la quantità di tempo che ho bisogno per scorrere l'array. Tuttavia, non sono sicuro di come funzioni un array frastagliato.

Esempio forma del mondo di gioco

X 
XX 
XX X XX 
XXX XXX 
    XXXXXXX 
XXXXXXXX 
XXXXX XX 
    XX X 
    X 

Edit: Il mondo di gioco sarà molto probabilmente bisogno di ogni posizione valida varcò. Quindi vorrei un metodo che lo renda facile.

Answer 1

C'è un sovraccarico computazionale e una complessità associati alle rappresentazioni sparse, quindi, a meno che l'area di delimitazione sia molto più grande del tuo mondo reale, è probabilmente più efficiente accettare semplicemente lo spazio "sprecato". In pratica stai sfruttando l'utilizzo della memoria aggiuntiva per accedere più rapidamente ai contenuti del mondo. Ancora più importante, l'implementazione dello "spreco di spazio" è più facile da comprendere e mantenere, il che è sempre preferibile fino al punto in cui è necessaria un'implementazione più complessa. Se non hai una buona prova che è necessario, allora è molto meglio mantenerlo semplice.

Answer 2

Utilizzare una struttura di dati come un elenco o una mappa e inserire solo le coordinate del mondo di gioco valide. In questo modo l'unica cosa che stai salvando sono posizioni valide, e non sprechi la memoria salvando le posizioni del mondo non di gioco poiché puoi dedurne quelle dalla mancanza di presenza nella tua struttura dati.

Answer 3

Si potrebbe presentare il mondo come un grafico (non orientato) di patch di terra (o acqua). Ogni patch ha quindi una forma regolare e il mondo è la combinazione di queste patch. Ogni patch è un nodo nel grafico e ha i bordi del grafico per tutti i suoi vicini.

Questa è probabilmente anche la rappresentazione più naturale di qualsiasi mondo generale (ma potrebbe non essere la più efficiente). Dal punto di vista dell'efficienza, probabilmente batterà un array o una lista per una mappa altamente irregolare ma non per una che si adatta bene a un rettangolo (o un'altra forma regolare) con poche deviazioni.

Un esempio di una mappa molto irregolare:

x 
x x 
    x x x 
    x  x 
    x xxx 
    x 
    x 
    x 
    x 

Non c'è praticamente alcun modo questo può essere montato in modo efficace (sia in rapporto spazio e tempo di accesso) in una forma regolare. Di seguito, d'altra parte, si adatta molto bene in una forma regolare applicando trasformazioni geometriche di base (è un parallelogramma con piccole parti mancanti):

xxxxxx x 
xxxxxxxxx 
    xxxxxxxxx 
    xx xxxx 

Answer 4

La cosa più semplice è usare solo la matrice, e proprio marchio le posizioni non di gioco con un pennarello speciale. Potrebbe anche funzionare una matrice seghettata, ma non la uso molto.

Answer 5

È possibile utilizzare uno quadtree per ridurre al minimo la quantità di spazio sprecato nella rappresentazione. I quad alberi sono ideali per partizionare lo spazio bidimensionale con granularità variabile - nel tuo caso, la granularità migliore è un quadrato di gioco. Se avessi un'intera area 20x20 senza quadrati di gioco, la rappresentazione quadrangolare ti permetterebbe di usare solo un nodo per rappresentare quell'intera area, invece di 400 come nella rappresentazione dell'array.

Answer 6

Usare qualsiasi struttura che si è venuta in mente --- si può sempre cambiare in un secondo momento. Se hai dimestichezza con l'utilizzo di un array, usalo. Smetti di preoccuparti della struttura dei dati che utilizzerai e inizia a programmare.

Come codice, costruire astrazioni lontano da questa matrice di fondo, come avvolgendolo in un modello semantico; quindi, se ti rendi conto (attraverso la creazione di profili) che è uno spreco di spazio o lento per le operazioni di cui hai bisogno, puoi sostituirlo senza causare problemi. Non cercare di ottimizzare fino a quando non sai di cosa hai bisogno.

Answer 7

Un altro modo sarebbe quello di memorizzare un elenco bordo - un vettore linea lungo ciascun bordo rettilineo. Facile da verificare per l'inclusione in questo modo e un albero quadruplo o anche un semplice hash di posizione su ogni vertice può velocizzare la ricerca di informazioni. Lo abbiamo fatto con un componente di altezza per ogni bordo per modellare le pareti di uno stadio da baseball e ha funzionato magnificamente.

Answer 8

Un altra opzione che potrebbe consentire di accedere ancora gioco luoghi del mondo in O (1) tempo e non sprecare troppo spazio sarebbe una tabella hash, dove le chiavi sarebbero le coordinate.

Answer 9

V'è un grande problema che nessuno qui affrontato: l'enorme differenza tra la memorizzazione su disco e l'archiviazione in memoria.

Supponendo che tu stia parlando di un gioco world come hai detto, questo significa che sarà molto grande. Non hai intenzione di memorizzare l'intera cosa in memoria in una volta, ma invece memorizzerai immediatamente le immediate vicinanze e lo aggiornerai man mano che il giocatore va in giro.

Quest'area vicinanze dovrebbe essere il più semplice, facile e veloce accesso possibile. Dovrebbe essere sicuramente un array (o una serie di matrici che vengono scambiate mentre il giocatore si muove). Si farà riferimento spesso e da molti sottosistemi del tuo motore di gioco: la grafica e la fisica gestiranno il caricamento dei modelli, il disegno, il mantenimento del giocatore in cima al terreno, le collisioni, ecc .; il suono dovrà conoscere il tipo di terreno sul quale il giocatore è attualmente in piedi, per riprodurre il suono appropriato del passo; e così via. Anziché trasmettere e duplicare questi dati tra tutti i sottosistemi, se li si mantiene in array globali possono accedervi a proprio piacimento e al 100% di velocità ed efficienza. Questo può davvero semplificare le cose (ma essere consapevoli delle conseguenze delle variabili globali!).

Tuttavia, su disco si vuole sicuramente comprimerlo. Alcune delle risposte fornite forniscono buoni suggerimenti; è possibile serializzare una struttura dati come una tabella hash o un elenco di sole posizioni compilate. Potresti sicuramente anche archiviare un octree. In ogni caso, non si desidera memorizzare posizioni vuote sul disco; secondo la tua statistica, ciò significherebbe che il 66% dello spazio è sprecato. Certo, c'è un tempo per dimenticare l'ottimizzazione e farlo funzionare, ma non si vuole distribuire un file vuoto al 66% agli utenti finali. Inoltre, tieni presente che i dischi non sono macchine ad accesso casuale perfette (ad eccezione delle unità SSD); i dischi rigidi meccanici dovrebbero essere ancora circa altri anni, e funzionano meglio in sequenza. Verifica se è possibile organizzare la struttura dei dati in modo che le operazioni di lettura siano sequenziali, in quanto si esegue lo streaming di più terreno di prossimità mentre il giocatore si muove e probabilmente si troverà una differenza notevole. Non credermi sulla parola, non ho ancora provato questo genere di cose, ha senso, giusto?