Qual è una buona strategia per costruire un grafico diretto per una mappa di gioco (in Python)?

Question

Sto sviluppando un mondo di gioco generato in modo procedurale in Python. La struttura del mondo sarà simile al paradigma MUD / MUSH delle stanze e delle uscite disposte come un grafico diretto (le stanze sono nodi, le uscite sono bordi). (Nota che questo è non necessariamente un grafico aciclico, anche se sono disposto a prendere in considerazione soluzioni acicliche.)

Per l'algoritmo di generazione mondiale, le stanze di diversi tipi saranno distinte dai "tag" di ogni stanza. attributo (un insieme di stringhe). Una volta che sono stati istanziati, le stanze possono essere interrogate e selezionate da tag (tag singolo, intersezione tag, unione tag, miglior candidato).

Creerò tipi specifici di stanze usando un sistema glorificato di oggetti modello e metodi di fabbrica - non credo che i dettagli siano importanti qui, poiché l'implementazione attuale probabilmente cambierà per adattarsi alla strategia scelta. (Ad esempio, sarebbe possibile aggiungere tag e query di tag al sistema di template room.)

Per un esempio, avrò stanze di questo tipo:

side_street, main_street, plaza, bar, hotel, restaurant, shop, office

Infine, la domanda: qual è una buona strategia per creare un'istanza e organizzare queste stanze per creare un grafico che potrebbe corrispondere a determinate regole?

Alcune regole potrebbero includere: una piazza per 10.000 abitanti; main_street si collega a plaza ; side_street si collega a main_street o side_street ; hotel favorisce le connessioni main_street o plaza e riceve di conseguenza ulteriori tag; ecc.

Punti bonus se una strategia suggerita consentirebbe un'implementazione basata sui dati.

Answer 1

Innanzitutto, è necessario un certo senso della posizione. I tuoi vari oggetti occupano una certa quantità di spazio delle coordinate.

Devi decidere quanto sono regolari queste varie cose. Nel caso banale, puoi rilasciarli nel tuo spazio di coordinate come semplici rettangoli (o solidi rettangolari) per rendere le posizioni più semplici da pianificare.

Se le cose sono irregolari - e densamente piene - la vita è un po 'più complessa.

Definisci una mappa per contenere posizioni. Ogni posizione ha un arco di coordinate; se lavori con rettangoli semplici, ogni posizione può avere una tupla (sinistra, in alto, a destra, in basso).

La tua mappa avrà bisogno di metodi per determinare chi risiede in un determinato spazio e cosa è adiacente allo spazio, ecc.

Puoi quindi testare l'unità con una serie fissa di posizioni che hai elaborato che possono essere tutti rilasciati nella mappa e passare alcuni controlli di integrità di base per non in conflitto, adiacenti e simili.

---

In secondo luogo, hai bisogno di una sorta di "generatore di labirinti". Un labirinto semplicemente collegato viene generato facilmente come una struttura ad albero che si ripiega nello spazio dato.

Il labirinto / albero ha un " root " nodo che sarà il centro del labirinto. Non necessariamente il centro fisico del tuo spazio, ma il nodo radice sarà al centro della struttura del labirinto.

Idealmente, un ramo da questo nodo contiene un "ingresso". all'intero spazio.

L'altro ramo di questo nodo contiene uno " exit " da tutto lo spazio.

Qualcuno può girovagare da un'entrata all'altra, visitando molti "vicoli ciechi" posizioni lungo la strada.

Scegli un tipo di spazio per il nodo principale. Rilascialo nel tuo spazio Mappa.

Questo avrà 1 - n entrate, ognuna delle quali è un sottoalbero con un nodo radice e 1 - n entrate. È questa attività a più ingressi che rende un albero una misura naturale per questa struttura. Inoltre, un albero appropriato è sempre ben collegato in quanto non hai mai sezioni isolate che non possono essere raggiunte.

Potrai - ricorsivamente - smazzare dal nodo principale, selezionando le posizioni e rilasciandole nello spazio disponibile.

L'unità prova questo per assicurarsi che riempia lo spazio ragionevolmente bene.

---

Il resto dei tuoi requisiti è la messa a punto del modo in cui il generatore di labirinti seleziona le posizioni.

Il più semplice è avere una tabella di pesi e scelte casuali. Scegli un numero casuale, confrontalo con i pesi per vedere quale tipo di posizione viene identificata.

---

La tua definizione di spazio può essere 2D o 3D - entrambi sono piuttosto razionali. Per il credito bonus, considera come implementeresti uno spazio 2D piastrellato con esagoni anziché quadrati.

Questa "geometria" può essere un plug-in Strategia per i vari algoritmi. Se puoi sostituire il 2D quadrato con il 2D esagonale, hai fatto un buon lavoro di OO Design.

Answer 2

Dai un'occhiata alle discussioni su Il connettore MUD - ci sono grandi discussioni sul layout e sulla generazione del mondo, e diversi tipi di sistemi di coordinate / navigazione nella "Codifica avanzata e progettazione" (o simile) forum.