Come dovrei costruire la struttura dati per un "labirinto" dinamico e illimitato?

Assegna le coordinate di ogni stanza (start dovrebbe essere (0,0)) e memorizza ogni stanza generata in un dizionario / hashmap per coordinate.

È banale determinare le coordinate adiacenti per ogni stanza, che è possibile utilizzare per verificare se una stanza esiste già. È possibile inserire valori nulli per rappresentare posizioni in cui è già stato determinato che non esiste alcuna stanza. (o se ciò non è possibile, non sono sicuro atm, un dizionario / hasmap separato per le coordinate che non contengono una stanza)

Nella maggior parte dei casi, ciò che descrivi sembra un grafico. Dati alcuni dei tuoi requisiti (l'aspetto crescente) probabilmente sceglierei un elenco di adiacenze come implementazione (l'altra opzione comune sarebbe una matrice di adiacenza ).

Non sono sicuro di quale lingua stai usando, ma un buon tutorial / spiegazione con dettagli di implementazione per un grafico implementato con un elenco di adiacenze in .NET è here .

Un paio di pensieri sull'implementazione (ho pensato a Carcassonne, che ha una serie di altri aspetti stimolanti per costruire la matrice - è stata anche una domanda di intervista che mi è stata fatta una volta).

Ci sono alcune domande che vengono poste su questa struttura:

1. c'è una stanza in X, Y?
2. c'è una stanza [N / S / E / W] della posizione vuota X, Y?

Il problema con elenchi e grafici semplici

La difficoltà con le liste semplici è che si deve percorrere la struttura per verificare se qualcosa può essere posizionato in una determinata posizione. Il sistema ha bisogno di un modo per accedere a una posizione arbitraria O (1).

Si consideri:

1 2 3 ? 4
5 . . * 6
7 8 9 A B

Per trovare le informazioni sulla possibile posizione '?', quando a 3, si deve camminare tutto intorno per arrivare a 4. La risposta di collegamento con informazioni aggiuntive su quanti nodi salta (in modo che 3 sarebbe collegato a 4 con informazioni extra di "salto 1") richiede ancora le passeggiate quando si trova l'adiacenza di "*" da 6 o A.

Array semplici, grandi

There is a limited number of Rooms available

Se questo è un numero non grande, basta creare un array 2N x 2N e lasciarlo lì. Un array 100 x 100 è "solo" 10.000 puntatori e 50 oggetti. Indicizza direttamente nell'array.

Questo potrebbe essere ridotto a solo NxN se le attività fuori limite spostassero l'array intorno per essere sempre entro i limiti. Ad esempio, se fosse necessario aggiungere una stanza che avrebbe sottoperformato la matrice, fare in modo che la griglia spostasse ogni elemento di una posizione in modo che non ci fosse più alcun underflow. A questo punto, la dimensione del mondo per 50 stanze sarebbe di 2500 puntatori e 50 oggetti.

Array e matrici sparse

Per crearlo in modo ottimale, guarda in array sparse in cui la maggior parte degli elementi sono 0 o null. Per due dimensioni, questa è conosciuta come matrice sparsa . Molti linguaggi di programmazione hanno varie librerie per lavorare con questa struttura. Se la libreria limita i numeri interi, si potrebbe usare questo numero intero come indice in una matrice fissa di stanze.

Il mio approccio preferito sarebbe quello di avere le stanze come una struttura (puntatori a stanze adiacenti e coordinate) e di avere nella stanza anche un puntatore da una tabella di hash che è hash sulle coordinate. In questa situazione per chiedere quale stanza è [N / S / E / W] da una stanza nulla, si interrogherebbe la tabella hash. Questo, per inciso, è il formato 'DOK' per la memorizzazione di una matrice sparsa.

Che ne dici di questo ..

Dai a ciascuna cella un link a ciascuno dei suoi vicini. Assegna ad ogni cella una sorta di nome (es. "0/0", "-10/0" (Supponiamo di iniziare da 0,0)). Aggiungi un hashset con tutti i nomi in esso contenuti. Mentre provi a spostarti in un'altra cella, controlla che il vicino non esista già nell'HashSet.

Inoltre, se crei un'apertura in un'altra stanza, ciò implica che le stanze esistano? Quindi dovresti creare un collegamento a una stanza vuota senza collegamenti a nessuna stanza. Probabilmente vorresti anche controllare i vicini delle nuove stanze. Se ne esiste uno e si aprirà alla tua nuova stanza, aggiungi una porta a quella stanza.

   Empty   
   (0,1)        

---    ---            ----------
|        |            |        |
    0,0       1,0        2,0       Empty
|        |            |        |   (3,0)
---    --- ---------- ---    ---
|        | |        | |        |
|   0,-1      1,-1       2,-1      Empty
|        | |        | |        |   (3,-1)
---    --- ---    --- ----------

   Empty     Empty   
  (0,-2)    (1,-2)

HashSet = {0 | 0, 1 | 0, 2 | 0, 3 | 0, 0 | -1, 1 | -1 ....} 1,0: W = 0,0 / porta; 1,0: N = 1,1 / Vuoto; E = 2,0 / porta; S = 1, -1 / Muro

Dovresti anche assicurarti di dare ad ogni nuova stanza almeno una porta non adiacente (ad un'altra stanza) in modo che il labirinto possa crescere in quella direzione.

Ciò che stai progettando sembra molto simile a un grafico.

Questi sono spesso rappresentati come un insieme di stati Q , uno stato iniziale q ₀ ∈ Q , e alcune transizioni Δ . Quindi, ti suggerisco di archiviarlo in questo modo.

• Un insieme Q : {s, 1, 2, 3, 5, 6}
• Uno stato iniziale q ₀ : s
• Una mappa delle relazioni di transizione Δ : {s → 1, s → 5, 1 → 2, 2 → 3, 3 → 4, 4 → 5}

Le lingue più ragionevoli hanno sia mappe che set.

Potresti considerare una lista collegata a 4 vie ...

I first thought about just using a [X][X] array of Room objects, but I'd really rather avoid that since the thing is supposed to grow in any direction, and only rooms that are "visited" should be built.

Puoi ancora usare un [] [] per quello. La crescita dinamica potrebbe essere lenta, specialmente quando si aggiunge all'inizio, ma forse non è poi così male. Dovresti profilo da controllare. Cercare di manipolare alcune liste o mappe collegate potrebbe effettivamente essere peggiore, a un livello costante piuttosto che occasionale.

Puoi costruire solo stanze visitate implementando una valutazione pigra. È possibile posizionare un oggetto che contiene una stanza e non creare quella stanza finché non viene chiamato room() . Quindi restituisce sempre la stessa ogni volta. Non è difficile da fare.

Ho imparato a farlo tramite il libro "Creazione di giochi di avventura sul tuo computer". Se sei disposto a scavare attraverso il codice BASIC (il libro è così vecchio) leggi qui:

link

Per la scorciatoia, quello che fanno è avere una serie di stanze, con un elemento in ogni array che è un puntatore a un'altra stanza a cui puoi andare, con 0 (userei -1 in questi giorni) per indicare che tu non può andare in quel modo Ad esempio, crei una struttura di stanza (o classe o cosa-hai-te)

room {
 int north_dir;
 int south_dir;
 int west_dir;
 int east_dir;
 // All other variables and code you care about being attached to the rooms here
}

Quindi potresti avere una matrice o una struttura di liste collegate o comunque vuoi gestire le tue stanze. Per i vettori in stile array (o C ++) userei quel codice e le direzioni terrebbero l'indice della stanza a cui si collegano; per un elenco collegato, è possibile utilizzare i puntatori per la stanza successiva.

Come altri hanno già detto, se devi generare dinamicamente nuove stanze quando le persone le inseriscono, puoi anche farlo.

Non cercare di risolvere tutti i problemi con una struttura.

Definisci il tuo oggetto stanza per memorizzare le cose sulla stanza, non le sue relazioni con altre stanze. Quindi un array 1D, un elenco, ecc. Può crescere come preferisci.

Una struttura separata può contenere "raggiungibilità" - quali stanze sono accessibili dalla stanza in cui mi trovo. Quindi decidere se la raggiungibilità transitiva deve essere un calcolo veloce o meno. Potresti volere un calcolo di forza bruta e una cache.

Evita l'ottimizzazione iniziale. Usa strutture davvero semplici e algoritmi stupidi facilmente comprensibili, quindi ottimizza quelli che vengono usati.