Struttura dati intelligente per rappresentare un cerchio stratificato

Question

Sto facendo un gioco e ho bisogno di rappresentare un cerchio "a strati" in una struttura dati intelligente.

Un cerchio può avere un numero qualsiasi di livelli. Ogni livello ha un numero di "fette", possono essere di diverse lunghezze e pezzi possono essere mancanti. Lo strato più interno è sempre un cerchio completo. Ogni segmento ha un colore, più segmenti con lo stesso colore possono essere uno accanto all'altro.

circle with layers http://webbfarbror.se/dump/datastructure.gif

realisticamente un cerchio solito hanno più di circa 40 strati o circa 1500 singole sezioni.

Dovrò essere in grado di trovare facilmente pezzi adiacenti a un pezzo specifico, vedere se un pezzo è "sospeso nell'aria libera" (immagina la gravità verso il centro) e rimuovere i pezzi lasciando un buco al loro posto.

Ho già alcune idee su come archiviare questo, ma ho pensato che fosse una domanda interessante quindi ho pensato di pubblicarlo qui per i calci.

Lo codificherò in Actionscript 3.0, ma non esitate a postare idee in qualsiasi lingua.

Answer 1

Pensando rapidamente a questo, ho potuto vedere una sorta di grafico diretto con diversi tipi di bordi. Probabilmente qualcosa di simile

Node: 
+ List<Node *> ParentLevel: a list of nodes at the level above (ie. more external) 
+ List<Node *> ChildrenLevel: a list of nodes at the level below (ie. more internal) 
+ Node * ClockwiseNeighbourgh 
+ Node * AntiClockwiseNeighbourg 

avreste due nodi set, uno dei quali il cerchio centrale e uno che rappresenta un cerchio più outter fittizio.

È quindi possibile spostarsi facilmente tra i livelli, da vicino a vicino in qualsiasi direzione. Per trovare tutte le fette che sono "in aria", puoi iniziare dal nodo interno o esterno e trovare qualsiasi fetta che non ha un genitore o un bambino.

L'unica cosa che non gestisce è il caso in cui ci sono due parti disgiunte nel cerchio a strati, ad es. con un livello completamente mancante. Potrebbe supportarlo aggiungendo pesi sui bordi per rappresentare la distanza.

Answer 2

Pensa alla proiezione di Mercatore per una mappa dell'emisfero Nord (o se preferisci del Sud). Disegna su alcune linee di longitudine e latitudine. Ora, tenendo presente che una proiezione standard di Mercatore non può mostrare +/- 90 lat della banda latitudine più in alto che rappresenta il cerchio attorno al Polo della tua mappa. Disegna la griglia sufficiente per i tuoi scopi. Ora disponi di un bel array 2D planare su cui rappresentare i tuoi dati con la proprietà di adiacenza che desideri (ricordandoti di avvolgere il primo anti-meridiano). Dovrai rappresentare fette vuote assegnando loro un valore nullo.

Spero che questa spiegazione piuttosto affrettata sia sufficiente, e mi dispiace se un array 2D non è una struttura di dati abbastanza intelligente.

Answer 3

Questa è una domanda interessante. Sono al lavoro quindi al momento dovrò dare una risposta veloce ma lo metterò alla prova stasera.

Mi chiedo se un array/elenco di collegamenti concatenati circolari funzionerebbe? È possibile contrassegnare ciascun elemento nell'elenco con un identificatore per mostrare che si trova in una sezione. Più elementi aggiungi all'array esterno più livelli hai. Non è troppo interessante ma è semplice. Dovresti essere in grado di trovare facilmente pezzi adiacenti in questo modo.

Answer 4

Solo pensando ad alta voce e non una soluzione completa, ma per ogni banda ci sono 360 spazi vuoti che possono essere riempiti (corrispondente al numero di gradi). Vieni a pensarci, perché limitarlo a 360 gradi interi. Ma in ogni caso è possibile determinare se i segmenti sui livelli adiacenti toccassero semplicemente controllando la gamma che occupavano su ciascun livello. Quindi se il segmento x al livello n è occupato da 120-240 e il segmento z occupa l'80-300 al livello n + 1, allora sono adiacenti.

Vieni a pensarci, in che modo la tua applicazione dipende anche realmente dagli attributi di cerchi concentrici o anche da un cerchio. Sembra che potresti immaginare un grappolo di anelli impilati l'uno sull'altro per formare un tubo, o anche un gruppo di file lineari impilati l'uno sull'altro per formare un muro e la struttura dei dati sarebbe la stessa in tutti questi casi (dato quello che posso dedurre dalla descrizione del problema.) Quindi è solo una questione di implementazione più efficiente di liste concatenate o qualcosa del genere.

Answer 5

Non hai detto nulla sul comportamento delle sezioni e dei livelli, il che sarebbe importante per sviluppare una struttura dati che rappresenterebbe più della pura struttura geometrica del tuo campo di gioco.

Creare un elenco di livelli. I livelli [0] sono il tuo livello più interno.

Ogni livello è un elenco di sezioni. Ogni fetta è definita dal suo angolo iniziale e dal suo colore. Se c'è una porzione in un livello, essa gira attorno all'intero livello. Se ci sono più fette ognuna inizia all'angolo iniziale e finisce dove inizia quella successiva, senza memorizzare i dati in modo ridondante. Un buco è un colore speciale. Una fetta è sospesa nell'aria se il livello sottostante è colorato "vuoto" sopra l'angolo iniziale e finale. Le sezioni adiacenti sullo stesso livello sono gli indici successivi nell'elenco delle sezioni o l'ultimo e il primo nell'elenco. Le sezioni adiacenti in altri livelli si trovano nuovamente sopra gli angoli finali finali della sezione.

Answer 6

Perché non utilizzare un graph (dalla teoria dei grafi). Basta aggiungere spigoli (collegamenti di connettività tra spazi colorati) per ogni vertice (ogni spazio colorato sulla tua plancia di gioco). I grafici sono progettati in modo che sia facile recuperare un elenco di vertici vicini (spazi colorati nel tuo caso).

Answer 7

Solo una rapida idea, senza offesa se è stupido - è tardi qui: P

• Creare un vettore di Livelli per iniziare.
• Ogni livello contiene un vettore di pezzi.
• ogni pezzo memorizza un valore del rapporto (0-1) e un colore che può alternativamente essere NULL
• La somma di tutti rapporto del Pezzi è sempre uguale a 1.

All'inizio di ogni strato può contenere un pezzo singolo (con il rapporto di 1).

Se ora si decide di aggiungere un pezzo blu di un rapporto di 0,5 (180 °) per un livello vuoto al di offset .25 Questo sostituirà i vuoti creare 3 pezzi:

• [NULL .25 ] [blue .5] [NULL .25]

... e quindi un modo ricorsivo, così si finisce con qualcosa di simile:

• [NULL .25] [blue .2] [ NULL 0] [rosso .1] [NULL .2] [nero.25]

Supponendo che si vuole fare qualcosa di interattivo con questo ... Questo può essere utile se si desidera che alcuni gli spazi per essere statico mentre altri regolare, o se volete un pezzo di colore adiacente ad essere magnetico basta controllare se il Pezzo in mezzo ha un rapporto di zero/o abbastanza per attirare l'altro senza dover fare calcoli extra. Fondamentalmente la cosa bella è che i calcoli si farebbero quando un pezzo viene modificato. Il resto sarebbe solo logica. Dì se un pezzo viene spostato, devi solo essere a conoscenza dei valori del rapporto spazio vuoto sinistro/destro, e non è necessario iterare gli altri angoli di calcolo. Sarebbe in qualche modo abbastanza simile al modo in cui le UI elastiche si adattano in realtà.