Struttura dati per un mondo casuale

Question

Quindi, stavo pensando di creare un semplice generatore di mondo casuale. Questo generatore creerebbe una "cella" iniziale che avrebbe tra una e quattro uscite casuali (nelle direzioni cardinali, qualcosa come un labirinto). Dopo aver deciso quelle uscite, avrei generato una nuova "cella" casuale a ciascuna di quelle uscite, e ripeterei ogni volta che un giocatore si avvicinava a una parte del mondo che non era ancora stata generata. Questo concetto consentirebbe un mondo "infinito" di generi, tutti generati casualmente; tuttavia, non sono sicuro di come rappresentare al meglio questo internamente.

Sto usando C++ (che non importa, potrei implementare qualsiasi tipo di struttura dati necessaria). All'inizio ho pensato di usare una sorta di grafico diretto in cui ogni nodo avrebbe diretto i bordi di ogni cella che lo circondava, ma probabilmente non funzionerebbe se un utente trova un punto nel mondo, torna indietro e torna a quello spot da un'altra direzione. Il mondo potrebbe fare alcune cose strane, come generare due celle in una posizione.

Qualche idea su quale tipo di struttura dati potrebbe essere la più efficace per una simile situazione? O sto facendo qualcosa di veramente stupido con la mia generazione del mondo casuale?

Qualsiasi aiuto sarebbe molto apprezzato. Grazie, Chris

Answer 1

A map< pair<int,int>, cell> probabilmente funzionerebbe bene; la coppia rappresenterebbe le coordinate x, y. Se non c'è una cella nella mappa a quelle coordinate, crea una nuova cella. Se si desidera renderlo veramente infinito, è possibile sostituire gli interi con una classe intera di lunghezza arbitraria che si dovrà fornire (ad esempio un bigint)

Answer 2

Non si può avere un hash (o set STL) che è stato memorizzato una raccolta di tutte le coordinate della griglia che contengono celle occupate?

Quindi, quando si sta cercando di creare una nuova cella, è possibile verificare rapidamente se la posizione della cella candidata è già occupata.

(se si dispone di uno spazio finito, è possibile utilizzare un array 2d - penso di averlo visto in un articolo della rivista Byte in ~ 1980-ish, ma se ho capito bene, vuoi un mondo che potrebbe estendersi indefinitamente)

Answer 3

Se le celle del mondo sono disposte in una griglia, è possibile assegnarle facilmente le coordinate cartesiane. Se si mantiene un grande elenco di celle esistenti, quindi prima di determinare le uscite da una determinata cella, è possibile controllare tale elenco per vedere se esiste uno dei suoi vicini. Se lo fanno, e non vuoi avere porte a 1 via (grafico diretto?), Allora devi prendere in considerazione le loro uscite. Se non ti dispiace avere degli scivoli nel tuo gioco, puoi comunque scegliere casualmente le uscite, assicurati di collegarti alle celle esistenti se sono lì.

Nota di ottimizzazione: il controllo di una tabella hash per verificare se contiene una chiave particolare è O (1).

Answer 4

Vi consiglio di leggere sui grafici. Questa è esattamente un'applicazione di generazione di grafici casuali. Invece di 'cell' e 'exit' stai descrivendo 'node' e 'edge'.

Inoltre, è possibile eseguire operazioni come l'analisi del percorso più breve, il rilevamento del ciclo e tutti i tipi di altre utili applicazioni di teoria dei grafi.

This vi aiuterà a capire sui nodi e spigoli:

e here è un'applicazione finita di questi concetti. L'ho implementato in un modo OOP: ogni nodo sapeva che i suoi bordi erano agli altri nodi. Un'alternativa popolare è implementare questo utilizzando un adjacency list.Penso che il concetto di elenco di adiacenza sia fondamentalmente quello che user470379 ha descritto con la sua risposta. Tuttavia, la sua soluzione mappa consente di avere grafici infiniti, mentre una tradizionale lista di adiacenze no. Adoro la teoria dei grafi, e questa è un'applicazione perfetta di esso.

Buona fortuna!

-Brian J. Stianr-