Qual è un buon modo per generare cluster e percorsi casuali?

Question

Sto giocando con un generatore di mappe casuali e non sono sicuro di come generare in modo casuale paesaggi realistici. Sto lavorando con these sorts di mappe su scala locale, che presenta alcuni problemi interessanti.

Uno dei casi più semplici è la forest:

    Sparse Medium Dense 
Typical trees  50%  70%  80% 
Massive trees  —  10%  20% 
Light undergrowth 50%  70%  50% 
Heavy undergrowth —  20%  50% 

alberi e sottobosco possono esistere nello stesso spazio, in modo da una foresta media rada ha il 25% di alberi tipici e sottobosco luce, il 25% di alberi tipici, 25 % sottobosco leggero e 25% di spazio aperto. Le foreste medie e fitte richiederanno un po 'più di riflessione, ma non è dove sia il mio problema, perché è uniformemente disperso.

Il mio problema sta nel generare cluster e percorsi, mantenendo i vincoli di percentuale. Marshes sono un buon esempio di questo:

    Moor Swamp 
Shallow bog   20% 40% 
Deep bog   5% 20% 
Light undergrowth 30% 20% 
Heavy undergrowth 10% 20% 

profonde piazze palude sono solitamente raggruppati insieme e circondate da un anello irregolare dei quadrati palude superficiali.

Un elemento mappa aggiuntivo, una siepe, può anche essere presente, così come un percorso di terreno aperto, che serpeggia attraverso la torbiera. Entrambi questi tipi di elementi della mappa (cluster e percorsi) presentano problemi, in quanto la composizione totale della mappa deve contenere X% dell'elemento, ma non è distribuita uniformemente. Altri elementi, come flussi, stagni e sabbie mobili, richiedono una generazione di cluster o di percorso.

Quale tecnica è possibile utilizzare per generare mappe realistiche in base a questi vincoli?

---

sto usando C#, FYI (ma questo non è una domanda -specifica C#.)

Answer 1

realistica distribuzione "random" è spesso fatto usando Perlin Noise, che può essere usato per dare una distribuzione con "grumi" come dici tu. Funziona sommando/combinando più livelli di valori interpolati linearmente da punti di dati casuali. Ogni livello (o "ottava") ha il doppio dei punti dati dell'ultimo e limitato a un intervallo di valori più ristretto. Il risultato è una trama casuale dall'aspetto "realistico".

Ecco una bella dimostrazione di the theory behind Perlin Noise di Hugo Elias.

Ecco la prima cosa che ho trovato su Perlin Noise in C#.

Ciò che si può fare è generare un'immagine Perlin Noise e impostare una "soglia", in cui qualsiasi valore sopra un valore è "on" e tutto quanto sotto è "off". Quello che finirai con è ciuffi dove le cose sono sopra la soglia, che sembrano irregolari e terrificanti. Assegna semplicemente quelli sopra la soglia dove vuoi che sia la tua caratteristica del terreno.

Here is a demonstration se un programma genera una bitmap Perlin Noise e quindi regola la soglia di interruzione nel tempo. Un chiaro "agglomerante" è visibile. Potrebbe essere proprio quello che volevi.

Si noti che, con una soglia alta, pochissimi punti sono sopra di esso, ed è scarso. Ma man mano che la soglia si abbassa, quei punti "crescono" in gruppi (dalla natura del rumore di Perlin), e alcuni di questi ci si uniscono a vicenda, e fondamentalmente creano qualcosa di molto naturale e simile al terreno.

Si noti che è anche possibile impostare il "fattore di clump" o la tendenza delle feature a raggrupparsi, impostando la "turbolenza" della funzione Perlin Noise, che fondamentalmente determina l'accentuazione dei picchi e delle valli della funzione PN. più vicini tra loro.

Ora, dove impostare la soglia? Maggiore è la soglia, minore è la percentuale della feature sulla mappa finale. Più bassa è la soglia, maggiore è la percentuale. Puoi scherzare con loro.Probabilmente potresti ottenere percentuali esatte facendo un po 'di matematica (sembra che la distribuzione dei valori segua uno Normal Distribution; potrei sbagliarmi). Tweak fino a quando non è giusto :)

EDIT Come sottolineato nei commenti, è possibile trovare l'esatta percentuale con la creazione di un istogramma cumulativo (indice di quello% della mappa è sotto di una soglia) e scegliere la soglia ti dà la percentuale di cui hai bisogno.

La cosa più bella qui è che è possibile creare funzionalità che si aggrappano a determinate altre funzionalità (come le caratteristiche della palude) banalmente qui: basta usare la stessa mappa Perlin Noise due volte - la seconda volta, abbassando la soglia. Il primo sarà scomodo e il secondo sarà irregolare intorno alle stesse aree, ma con i grumi ingranditi (fare riferimento all'animazione flash pubblicata in precedenza).

Come per altre caratteristiche come le siepi, è possibile provare a modellare semplici linee random walk che hanno una tendenza più alta a andare dritte rispetto al turno e posizionarle in modo casuale sulla mappa basata su perlin.

---

campioni

Ecco un 50x50 tegola campione Sparse Forest Mappa. Il sottobosco è di colore marrone e gli alberi sono di colore blu (scusate) per chiarire quale è quale.

Sparse Forest http://img688.imageshack.us/img688/7005/forestmap.png

Per questa mappa non ho fatto soglie precise per abbinare il 50%; Ho impostato solo la soglia al 50% del massimo. Statisticamente, questo si aggirerà intorno al 50% ogni volta. Ma potrebbe non essere abbastanza preciso per i tuoi scopi; vedere la nota precedente per come farlo.

---

Ecco una demo delle vostre caratteristiche Marsh (esclusi sottobosco, per chiarezza), con poca palude in grigio e profonda palude in retro:

Marshes http://img202.imageshack.us/img202/5092/marshdemo.png

questo è solo 50x50, così ci sono alcuni artefatti da questo, ma puoi vedere con quanta facilità puoi far "crescere" la palude poco profonda dalla profonda palude, semplicemente regolando la soglia sulla stessa mappa di Perlin. Per questo, ho messo a fuoco il livello di soglia per dare i risultati più piacevoli, ma per i tuoi scopi, potresti fare ciò che è stato menzionato prima.

Ecco una mappa palude generato dalla stessa mappa del rumore Perlin, ma si estendeva su 250x250 mappa piastrelle invece:

Marshes 250x250 http://img251.imageshack.us/img251/2867/marshdemo250.png

Answer 2

Non ho mai fatto questo genere di cose, ma qui ci sono alcune riflessioni.

È possibile ottenere i cluster variando la selezione casuale in posizioni sulla griglia vicine a elementi esistenti di quel tipo. Assegna un valore predefinito di 1 a tutti i quadrati. Per i quadrati con elementi cluster esistenti, aggiungere il valore di raggruppamento ai quadrati adiacenti (maggiore è il valore di clustering, maggiore sarà il clustering). Quindi fai una selezione casuale per il prossimo elemento di quel tipo sulla funzione di distribuzione di probabilità di tutti i quadrati.

Per i percorsi, è possibile avere una procedura simile, eccetto che i percorsi sarebbero estesi in senso decrescente (la probabilità di percorso è finita a riquadri vicino alla fine del percorso e zero ovunque altrove). I percorsi direzionali potrebbero essere fatti aumentando la probabilità di selezione nella direzione del percorso. I percorsi meandri potrebbero avere una direzione che cambia nel corso dell'estensione casuale (new_direction = mf * old_direction + (1-mf) * rand_direction, dove mf è un fattore di momentum tra 0 e 1).

Answer 3

È possibile iniziare a leggere i collegamenti here. Ricordo di aver visto un documento molto migliore. Pubblicheremo se lo trovo (era anche basato su sistemi L).

Ma questo è sul lato generale; sul problema particolare si faccia Credo che si dovrebbe modello in termini di

• percentuali
• altre regole (cluster e percorsi)

Il punto è che anche se non si sa come per costruire la mappa con le proprietà date, se sei in grado di valutare le proprietà (rapporto di clustering, gradevolezza del percorso) e ottenere un punteggio su di esse puoi quindi forzare la forza o fare qualche altro spazio problematico trasversale.

Se vuoi ancora fare un approccio generativo, dovrai esaminare un po 'più da vicino le regole generative; ecco un'idea che vorrei perseguire

• creare modelli di diversi terreni e le coperture del terreno che hanno richiesto le proprietà di 'clusterness', 'pathness' o uniformità
• creare i modelli in modo tale che i valori di profondità la palude non è discreta, ma assegna il valore di probabilità; dopo che il modello era stato creato è possibile normalizzare questa probabilità in modo tale che esso produrrà percentuale di copertura richiesto
• mix diversi modelli insieme

Answer 4

Si potrebbe avere un certo successo per alcuni tipi di zona con un modello Voronoi . Non l'ho mai visto usato per creare mappe ma l'ho visto usato in un numero di campi simili.

Answer 5

Per espandere i commenti di academicRobot, è possibile iniziare con un marsh predefinito o un seme della foresta in alcune celle della griglia e lasciarli crescere dall'origine utilizzando un numero casuale correlato. Ad esempio una torbiera potrebbe avere otto celle di griglia adiacenti ciascuna delle quali ha una probabilità del 90% di essere anche una torbiera, ma una probabilità del 10% di essere qualcos'altro. Puoi lasciare la forma dell'ecosistema dal seme e regolare la correlazione fino a ottenere qualcosa che sembra giusto. Probabilmente abbastanza facile da implementare anche in un foglio di calcolo.