Il modo migliore per scegliere l'elemento casuale dalla lista ponderata

3

Voglio creare un gioco semplice. Ogni tanto dovrebbe apparire un potenziamento. In questo momento i diversi tipi di power up sono memorizzati in un array.

Tuttavia, non tutti gli accensioni dovrebbero apparire ugualmente spesso: ad esempio, un moltiplicatore di punteggio dovrebbe apparire molto più spesso di una vita extra.

Qual è il modo migliore / più veloce per scegliere un elemento a caso da una lista in cui alcuni elementi dovrebbero essere scelti più spesso di altri?

    
posta Qqwy 04.09.2013 - 20:45
fonte

3 risposte

10

Se per "migliore" in realtà intendi "il più veloce", allora il modo più veloce (anche se non quasi il più efficiente modo) è scegliere un moltiplicatore che rende tutti i pesi interi, almeno per quanto riguarda la precisione a cui tieni, quindi memorizza molte copie di ciascuna di esse in un unico grande array.

Ad esempio, se assegni a "moltiplicatore di punteggio" un peso dell'80% e "vita extra" un peso del 20%, quindi crea un array di 5 elementi con 4 riferimenti all'oggetto / variabile "moltiplicatore di punteggio" e 1 riferimento alla "vita extra". Quindi genera un numero casuale compreso tra 1 e 5 e scegli dall'indice corrispondente. La distribuzione non ha importanza.

In pratica, a meno che tu non abbia tonnellate di memoria e una CPU molto lenta, questo è uno spreco di memoria. È molto più semplice ed efficiente scrivere una serie di istruzioni if confrontando un numero casuale con un limite basso / alto e se il numero di elementi possibili non è così grande (diciamo meno di 10?) Allora non dovrebbe essere così difficile da mantenere.

Se hai centinaia o migliaia di possibili articoli / power-up / qualunque cosa, allora questa non è più una soluzione molto manutenibile. In tal caso l'opzione migliore che conosco è quella di mantenere un elenco ordinato di tuple con il tasto come peso minimo; non è necessario memorizzare il massimo poiché ciò è implicito nell'elemento successivo. Ad esempio [ [0, scoreMultiplier], [80, extraLife], [95, invincibility] ] . Quindi puoi eseguire una ricerca binaria su questo elenco per trovare l'elemento appropriato corrispondente a un numero casuale in tempo O (log N).

    
risposta data 04.09.2013 - 21:18
fonte
2

Funzionerebbe un semplice sistema di ponderazione. Crea un array di indice 100 e le cose che accadono 1 volta su 100 appaiono in un solo punto, mentre le cose che appaiono 1 volta su 5 appaiono in 20 punti. Genera un numero casuale compreso tra 1 e 100 e l'evento che si verifica è quello in quell'indice dell'array.

Ecco come calcolano le tabelle loot per i giochi di ruolo. Puoi anche generare un elenco di eventi che memorizzano internamente il loro intervallo di probabilità, quindi invece di avere un grande array pieno di voci ridondanti, puoi avere un array bidimensionale più piccolo che memorizza un evento, insieme all'intervallo numerico in cui si verifica.

    
risposta data 04.09.2013 - 21:18
fonte
0

Se il peso è una percentuale delle volte che l'oggetto deve essere selezionato (diciamo 1-100), che ne è di passare per l'elenco e assegnare a ciascun elemento un "controllo" uguale alla somma del suo peso più i pesi precedenti. Quindi prendi un numero casuale compreso tra 1 e 100 (ovvero, un numero casuale standard compreso tra 0 e 1, moltiplicato per 100, ottimizzato in modo da essere un numero intero non zero) e scegli il primo elemento il cui valore 'verifica' è maggiore di o uguale al valore casuale?

Quindi, se ci sono tre elementi "A" con peso 25%, "B" con peso 50% e "C" con peso 25%, i valori "punteggio" sono: A = 25 (25 + 0) , B = 75 (50 + 25), C = 100 (25 + 75). Un numero casuale di 12 selezionerebbe A (dal 12 < = 25). Qualsiasi numero casuale da 1-25 seleziona A. Qualsiasi numero casuale di 26-75 seleziona B. Qualsiasi numero casuale compreso tra 76-100 seleziona C.

Funzionerebbe?

Forse è lo stesso suggerito da Aaronaught - ad essere onesti non ero sicuro esattamente di cosa intendesse

write a bunch of if statements comparing a random number to a low/high bound

    
risposta data 05.11.2013 - 07:47
fonte

Leggi altre domande sui tag