Eu tenho uma caixa de itens que eu quero preencher com um item aleatório. Mas quero que cada item tenha uma chance diferente de ser escolhido. Por exemplo:
- 5% de chance de 10 pontos de ouro
- 20% de chance de espada
- 45% de chance de escudo
- 20% de chance de armadura
- 10% de chance de poção
Como posso fazer para selecionar exatamente um dos itens acima, onde essas porcentagens são as respectivas chances de obter o saque?
Respostas:
A solução de probabilidades codificadas por software
A solução de probabilidade codificada tem a desvantagem de que você precisa definir as probabilidades no seu código. Você não pode determiná-los em tempo de execução. Também é difícil de manter.
Aqui está uma versão dinâmica do mesmo algoritmo.
Aqui está uma implementação de amostra em Java na forma de uma classe de modelo que você pode instanciar para qualquer objeto que seu jogo use. Você pode adicionar objetos ao método
.addEntry(object, relativeWeight)
e escolher uma das entradas adicionadas anteriormente com.get()
Uso:
Aqui está a mesma classe implementada em C # para o seu projeto Unity, XNA ou MonoGame:
E aqui está um em JavaScript :
Pró:
Contra:
O(n)
complexidade do tempo de execução). Portanto, quando você tem um conjunto muito grande de itens e desenha com muita frequência, pode ficar lento. Uma otimização simples é colocar os itens mais prováveis primeiro, para que o algoritmo termine mais cedo na maioria dos casos. Uma otimização mais complexa que você pode fazer é explorar o fato de que a matriz é classificada e fazer uma pesquisa de bissecção. Isso leva apenasO(log n)
tempo.O(n)
pior tempo de execução)fonte
Nota: Criei uma biblioteca C # para esse problema exato
As outras soluções são boas se você tiver apenas um pequeno número de itens e suas probabilidades nunca mudarem. No entanto, com muitos itens ou probabilidades variáveis (por exemplo, removendo itens após selecioná-los) , você desejará algo mais poderoso.
Aqui estão as duas soluções mais comuns (ambas incluídas na biblioteca acima)
Método de Alias de Walker
Uma solução inteligente que é extremamente rápida (
O(1)
!) Se suas probabilidades são constantes. Em essência, o algoritmo cria um alvo de dardos 2D ("tabela de alias") a partir de suas probabilidades e lança um dardo nele.Existem muitos artigos on-line sobre como funciona, se você quiser saber mais.
O único problema é que, se suas probabilidades mudarem, você precisará gerar novamente a tabela de alias, que é lenta. Portanto, se você precisar remover itens após a seleção, essa não é a solução para você.
Solução baseada em árvore
A outra solução comum é criar uma matriz em que cada item armazene a soma de sua probabilidade e todos os itens anteriores. Em seguida, basta gerar um número aleatório a partir de [0,1) e fazer uma pesquisa binária para onde esse número está na lista.
Essa solução é muito fácil de codificar / entender, mas a seleção é mais lenta que o método de alias de Walker e a alteração das probabilidades ainda é
O(n)
. Podemos aprimorá-lo transformando o array em uma árvore de pesquisa binária, onde cada nó controla a soma das probabilidades em todos os itens de sua subárvore. Então, quando geramos o número de [0,1), podemos simplesmente descer a árvore para encontrar o item que ela representa.Isso nos
O(log n)
permite escolher um item e alterar as probabilidades! Isso tornaNextWithRemoval()
extremamente rápido!Os resultados
Aqui estão alguns benchmarks rápidos da biblioteca acima, comparando essas duas abordagens
Como você pode ver, no caso especial de probabilidades estáticas (sem alterações), o método Alias de Walker é cerca de 50 a 100% mais rápido. Mas nos casos mais dinâmicos, a árvore é várias ordens de magnitude mais rapidamente !
fonte
nlog(n)
) ao classificar itens por peso.A solução Wheel of Fortune
Você pode usar esse método quando as probabilidades no seu pool de itens tiverem um denominador comum bastante grande e você precisar extrair dele com muita frequência.
Crie uma matriz de opções. Mas coloque cada elemento nele várias vezes, com o número de duplicatas de cada elemento proporcional à sua chance de aparecer. Para o exemplo acima, todos os elementos têm probabilidades que são multiplicadores de 5%, então você pode criar uma matriz de 20 elementos como este:
Em seguida, basta escolher um elemento aleatório dessa lista, gerando um número inteiro aleatório entre 0 e o comprimento da matriz - 1.
Desvantagens:
Vantagens:
fonte
Epic Scepter of the Apocalypse
. Essa abordagem em duas camadas aproveita as vantagens de ambas as abordagens.[('gold', 1),('sword',4),...]
somar todos os pesos e, em seguida, rolar um número aleatório de 0 até a soma, iterar a matriz e calcular onde o número aleatório cai (ou seja, areduce
) Funciona bem para matrizes que são atualizadas com freqüência e sem grandes quantidades de memória.A solução de probabilidades codificadas
A maneira mais simples de encontrar um item aleatório de uma coleção ponderada é percorrer uma cadeia de instruções if-else, onde cada if-else provavelmente aumenta, pois a anterior não é atingida.
A razão pela qual os condicionais são iguais à sua chance, mais todas as chances dos condicionais anteriores, é porque os condicionais anteriores já eliminaram a possibilidade de serem esses itens. Portanto, para o condicional do escudo
else if(rand <= 70)
, 70 é igual à chance de 45% do escudo, mais a chance de 5% do ouro e 20% de chance da espada.Vantagens:
Desvantagens:
fonte
Em C #, você pode usar uma varredura do Linq para executar seu acumulador e comparar com um número aleatório no intervalo de 0 a 100.0f e .First () a obter. Então, como uma linha de código.
Então, algo como:
sum
é um número inteiro inicializado zero ea
é uma lista de estruturas de prob / item / tuplas / instâncias.rand
é um número aleatório gerado anteriormente no intervalo.Isso simplesmente acumula a soma na lista de intervalos até exceder o número aleatório selecionado anteriormente e retorna o item ou nulo, onde nulo seria retornado se o intervalo de números aleatórios (por exemplo, 100) for menor que o intervalo de ponderação total por engano , e o número aleatório selecionado está fora da faixa de ponderação total.
No entanto, você notará que os pesos no OP correspondem à distribuição normal (curva de Bell). Penso que, em geral, você não desejará intervalos específicos, tenderá a desejar uma distribuição que diminua em torno de uma curva em sino ou apenas em uma curva exponencial decrescente (por exemplo). Nesse caso, você pode usar apenas uma fórmula matemática para gerar um índice em uma matriz de itens, classificados em ordem de probabilidade preferida. Um bom exemplo é o CDF na distribuição normal
Também um exemplo aqui .
Outro exemplo é que você pode usar um valor aleatório de 90 a 180 graus para obter o quadrante inferior direito de um círculo, usar o componente x usando cos (r) e usá-lo para indexar em uma lista priorizada.
Com diferentes fórmulas, você pode ter uma abordagem geral, onde você apenas insere uma lista priorizada de qualquer tamanho (por exemplo, N) e mapeia o resultado da fórmula (por exemplo: cos (x) é de 0 a 1) por multiplicação (por exemplo: Ncos (x ) = 0 a N) para obter o índice.
fonte
As probabilidades não precisam ser codificadas. Os itens e os limites podem estar juntos em uma matriz.
Você ainda precisa acumular os limites, mas pode fazê-lo ao criar um arquivo de parâmetro em vez de codificá-lo.
fonte
random()
no loop?Eu fiz esta função: https://github.com/thewheelmaker/GDscript_Weighted_Random Now! no seu caso, você pode usá-lo assim:
Ele fornece apenas um número entre 0 e 4, mas você pode colocá-lo na matriz onde obteve os itens.
Ou em função:
Aqui está o código. Eu fiz isso no GDscript, você pode, mas pode alterar outro idioma, também verificar erros de lógica:
Funciona assim: on_normal_case ([50,50], 0) Isso fornece 0 ou 1, tem a mesma probabilidade ambos.
on_normal_case ([50,50], 1) Isso fornece 1 ou 2, tem a mesma probabilidade ambos.
on_normal_case ([20,80], 1) Isso fornece 1 ou 2, pois possui maiores alterações para obter dois.
on_normal_case ([20,80,20,20,30], 1) Isso fornece números aleatórios entre 1 e 5 e números maiores são mais prováveis que números menores.
on_normal_case ([20,80,0,0,20,20,30,0,0,0,33], 45) Esse lançamento corta entre os números 45,46,49,50,51,56 que você vê quando há é zero, nunca ocorre.
Portanto, sua função retorna apenas um número aleatório que depende do comprimento dessa matriz e do número de transformadores, e as ints na matriz são pesos de probabilidade que um número pode ocorrer, onde esse número está localizado na matriz, pluss transformm number.
fonte