c# - Diseño de juegos/teoría, Loot Drop Chance/Spawn Rate

probability

Question

Tengo una pregunta muy específica y larga para todos ustedes. Esta pregunta es sobre programación y teoría de juegos. Recientemente agregué mineral desovable a mi Juego de estrategia por turnos: http://imgur.com/gallery/0F5D5Ij (Para aquellos de ustedes que miren, perdonen las texturas de desarrollo).

Ahora, sobre el enigma que he estado contemplando. En mi juego, el mineral se genera cada vez que se crea un nuevo mapa. Se generan 0-8 nodos de mineral por nivel de creación. Ya tengo este trabajo; excepto que solo genera "Esmeralda" en este punto, lo que me lleva a mi pregunta.

¿Cómo lo haría yo, el programador, para que los nodos tengan una rareza específica? Considera esta pequeña maqueta que no es en realidad datos del juego:

(Seudo posibilidades de que un nodo sea uno de los siguientes)

Bloodstone 1 in 100
Default(Empty Node) 1 in 10
Copper 1 in 15
Emeraldite 1 in 35
Gold 1 in 50
Heronite 1 in 60
Platinum 1 in 60
Shadownite 1 in 75
Silver 1 in 35
Soranite 1 in 1000
Umbrarite 1 in 1000
Cobalt 1 in 75
Iron 1 in 15

Quiero hacerlo para que un nodo generado pueda ser, teóricamente, cualquiera de los anteriores, sin embargo, con las probabilidades también consideradas. Espero que la pregunta sea lo suficientemente clara. He estado tratando de envolver mi cabeza en torno a esto, e incluso traté de escribir algunas afirmaciones si con randoms, sin embargo, sigo con las manos vacías.

Básicamente, solo quiero que vean mi problema, y ​​espero que me brinden una idea de cómo podría abordar esto de una manera dinámica.

Si se necesita alguna aclaración, por favor pregunte; Lo siento de nuevo si esto fue complicado.

(Estoy agregando C # como etiqueta solo porque es el idioma que estoy usando para este proyecto)

Answer 1

Astrotrain ya dio mi respuesta, pero como ya la codifiqué, la publicaré. Lo siento por la sintaxis, trabajo principalmente en Powershell y ese es el contexto que actualmente tengo en mente. Considera este código psuedo:

// Define the odds for each loot type
//           Description,Freq,Range
LootOddsArray = "Bloodstone",1,100,
"Copper",1,15,
"Emeraldite,"1,35,
"Gold",1,50,
"Heronite",1,60,
"Platinum",1,60,
"Shadownite",1,75,
"Silver",1,35,
"Soranite",1,1000,
"Umbrarite",1,1000,
"Cobalt",1,75,
"Iron",1,15

// Define your lookup table. It should be as big as your largest odds range.
LootLookupArray(1000)

// Fill all the ''default'' values with "Nothing"
for (i=0;i<LootLookupArray.length;i++) {
    LootOddsArray(i) = "Nothing"
}

// Walk through your various treasures
for (i=0;i<LootOddsArray.length;i++)
    // Calculate how often the item will appear in the table based on the odds
    // and place that many of the item in random places in the table, not overwriting
    // any other loot already in the table
    NumOccsPer1000 = Round(LootOddsArray(i).Freq * 1000/LootOddsArray(i).Range)
    for (l=0;l<NumOccsPer1000;l++) {
        // Find an empty slot for the loot
        do
            LootIndex = Random(1000)
        while (LootLookupArray(LootIndex) != "Nothing")
        // Array(Index) is empty, put loot there
        LootLookupArray(LootIndex) = LootOddsArray(i).Description
    }
}

// Roll for Loot
Loot = LootLookupArray(Random(1000))

Answer 2

Creo que es fácil entender cómo funciona. (Cobalto, 20: significa 1 de 20 -> 5%)

Dictionary<string, double> ore = new Dictionary<string, double>();
Random random = new Random();

private void AddOre(string Name, double Value)
{
    ore.Add(Name, 1.0 / Value);
}

private string GetOreType()
{
    double probSum = 0;
    double rand = random.NextDouble();

    foreach (var pair in ore)
    {
        probSum += pair.Value;
        if (probSum >= rand)
            return pair.Key;
    }
    return "Normal Ore";  //Reaches this point only if an error occurs.
}

private void Action()
{
    AddOre("Cobalt", 20);
    AddOre("Stone", 10);
    AddOre("Iron", 100);
    AddOre("GreenOre", 300);

        //Add Common ore and sort Dictionary
        AddOre("Common ore", 1 / (1 - ore.Values.Sum()));
        ore = ore.OrderByDescending(x => x.Value).ToDictionary(x => x.Key, x => x.Value);

    Console.WriteLine(GetOreType());
}

Editar:

Añado la sección "Añadir mineral común y ordenar diccionario".

Answer 3

En primer lugar, no es necesario especificar la probabilidad del nodo vacío predeterminado. Las otras probabilidades deben definirse de tal manera que se cree el nodo vacío si no se crea ningún otro tipo.

¿Cómo hacer esto y asegurarse de que las probabilidades de generación sean iguales a las que especificó? En breve:

• convertir las probabilidades a un punto flotante (es un valor con un divisor común de 1)
• Sume todas las probabilidades y verifique si son <1
• Escribe una clase que almacenará todas las probabilidades.
• escribe una función que obtendrá un nodo aleatorio basado en esas probabilidades

Para su ejemplo:

Bloodstone 1 in 100 = 0.01
Copper 1 in 15 ~= 0.07
Emeraldite 1 in 35 ~= 0.03
Gold 1 in 50 = 0.02
Default = 0.87

Ahora la clase se puede implementar en al menos dos formas. Mi opción consume mucha memoria, realiza los cálculos una vez, pero también redondea los valores de probabilidad que pueden introducir algún error. Tenga en cuenta que el error depende de la variable arrSize : cuanto mayor sea, menor será el error.

La otra opción es como en la respuesta de Bogusz. Es más preciso, pero requiere más operaciones por cada elemento generado.

La opción sugerida por Thomas requiere una gran cantidad de código repetible para cada opción, por lo que no es versátil. La respuesta de Shellshock tendrá probabilidades efectivas inválidas.

La idea de Astrotrain de obligarte a usar el mismo divisor es prácticamente igual a la mía, aunque la implementación sería ligeramente diferente.

Aquí hay una implementación de ejemplo de mi idea ( en java, pero debe ser portada muy fácilmente ):

public class NodeEntry {

    String name;
    double probability;

    public NodeEntry(String name, double probability) {
        super();
        this.name = name;
        this.probability = probability;
    }

    public NodeEntry(String name, int howMany, int inHowMany) {
        this.name = name;
        this.probability = 1.0 * howMany / inHowMany;
    }

    public final String getName() {
        return name;
    }

    public final void setName(String name) {
        this.name = name;
    }

    public final double getProbability() {
        return probability;
    }

    public final void setProbability(double probability) {
        this.probability = probability;
    }


    @Override
    public String toString() {
        return name+"("+probability+")";
    }

    static final NodeEntry defaultNode = new NodeEntry("default", 0);
    public static final NodeEntry getDefaultNode() {
        return defaultNode;
    }

}

public class NodeGen {

    List<NodeEntry> nodeDefinitions = new LinkedList<NodeEntry>();

    public NodeGen() {
    }

    public boolean addNode(NodeEntry e) {
        return nodeDefinitions.add(e);
    }

    public boolean addAllNodes(Collection<? extends NodeEntry> c) {
        return nodeDefinitions.addAll(c);
    }



    static final int arrSize = 10000;

    NodeEntry randSource[] = new NodeEntry[arrSize];

    public void compile() {
        checkProbSum();

        int offset = 0;
        for (NodeEntry ne: nodeDefinitions) {
            int amount = (int) (ne.getProbability() * arrSize);
            for (int a=0; a<amount;a++) {
                randSource[a+offset] = ne; 
            }
            offset+=amount;
        }

        while (offset<arrSize) {
            randSource[offset] = NodeEntry.getDefaultNode();
            offset++;
        }
    }

    Random gen = new Random();

    public NodeEntry getRandomNode() {
        return randSource[gen.nextInt(arrSize)]; 
    }

    private void checkProbSum() {
        double sum = 0;

        for (NodeEntry ne: nodeDefinitions) {
            sum+=ne.getProbability();
        }

        if (sum >1) {
            throw new RuntimeException("nodes probability > 1");
        }

    }



    public static void main(String[] args) {
        NodeGen ng = new NodeGen();
        ng.addNode(new NodeEntry("Test 1", 0.1));
        ng.addNode(new NodeEntry("Test 2", 0.2));
        ng.addNode(new NodeEntry("Test 3", 0.2));

        ng.compile();

        Map<NodeEntry, Integer> resCount = new HashMap<NodeEntry, Integer>();

        int generations = 10000;
        for (int a=0; a<generations; a++) {
            NodeEntry node = ng.getRandomNode();
            Integer val = resCount.get(node);
            if (val == null) {
                resCount.put(node, new Integer(1));
            } else {
                resCount.put(node, new Integer(val+1));
            }
        }


        for (Map.Entry<NodeEntry, Integer> entry: resCount.entrySet()) {
            System.out.println(entry.getKey()+": "+entry.getValue()+" ("+(100.0*entry.getValue()/generations)+"%)");
        }
    }

}

Esto asegura que las probabilidades sean realmente uniformes. Si comprobó el primer nodo de generación, luego el otro, luego el otro: obtendría resultados incorrectos: los nodos seleccionados primero tendrían mayor probabilidad.

Ejecución de la muestra:

Test 2(0.2): 1975 (19.75%)
Test 1(0.1): 1042 (10.42%)
Test 3(0.2): 1981 (19.81%)
default(0.0): 5002 (50.02%)

Answer 4

Hace poco tuve que hacer algo similar, y terminé con este genérico "generador de spawn".

public interface ISpawnable : ICloneable
{
    int OneInThousandProbability { get; }
}

public class SpawnGenerator<T> where T : ISpawnable
{
    private class SpawnableWrapper
    {
        readonly T spawnable;
        readonly int minThreshold;
        readonly int maxThreshold;

        public SpawnableWrapper(T spawnable, int minThreshold)
        {
            this.spawnable = spawnable;
            this.minThreshold = minThreshold;
            this.maxThreshold = this.minThreshold + spawnable.OneInThousandProbability;
        }

        public T Spawnable { get { return this.spawnable; } }
        public int MinThreshold { get { return this.minThreshold; } }
        public int MaxThreshold { get { return this.maxThreshold; } }
    }

    private ICollection<SpawnableWrapper> spawnableEntities;
    private Random r;

    public SpawnGenerator(IEnumerable<T> objects, int seed)
    {
        Debug.Assert(objects != null);

        r = new Random(seed);
        var cumulativeProbability = 0;
        spawnableEntities = new List<SpawnableWrapper>();

        foreach (var o in objects)
        {
            var spawnable = new SpawnableWrapper(o, cumulativeProbability);
            cumulativeProbability = spawnable.MaxThreshold;
            spawnableEntities.Add(spawnable);
        }

        Debug.Assert(cumulativeProbability <= 1000);
    }

    //Note that it can spawn null (no spawn) if probabilities dont add up to 1000
    public T Spawn()
    {
        var i = r.Next(0, 1000);
        var retVal = (from s in this.spawnableEntities
                      where (s.MaxThreshold > i && s.MinThreshold <= i)
                      select s.Spawnable).FirstOrDefault();

        return retVal != null ? (T)retVal.Clone() : retVal;
    }
}

Y lo usarías como:

public class Gem : ISpawnable
{
    readonly string color;
    readonly int oneInThousandProbability;

    public Gem(string color, int oneInThousandProbability)
    {
        this.color = color;
        this.oneInThousandProbability = oneInThousandProbability;
    }

    public string Color { get { return this.color; } }

    public int OneInThousandProbability
    {
        get
        {
            return this.oneInThousandProbability;
        }
    }

    public object Clone()
    {
        return new Gem(this.color, this.oneInThousandProbability);
    }
}

var RedGem = new Gem("Red", 250);
var GreenGem = new Gem("Green", 400);
var BlueGem = new Gem("Blue", 100);
var PurpleGem = new Gem("Purple", 190);
var OrangeGem = new Gem("Orange", 50);
var YellowGem = new Gem("Yellow", 10);

var spawnGenerator = new SpawnGenerator<Gem>(new[] { RedGem, GreenGem, BlueGem, PurpleGem, OrangeGem, YellowGem }, DateTime.Now.Millisecond);
var randomGem = spawnGenerator.Spawn();

Evidentemente, el algoritmo de generación no se consideró un código crítico, por lo que la sobrecarga de esta implementación no fue motivo de preocupación en comparación con la facilidad de uso. Los engendros se ejecutaron en la creación mundial y fue fácilmente más que lo suficientemente rápido.

Answer 5

Podría volver a escribir todas las oportunidades para que usen el mismo divisor (por ejemplo, 1000), sus posibilidades se convierten en

• Bloodstone 10 en 1000
• Predeterminado (Nodo vacío) 100 en 1000
• Oro 20 en 1000

A continuación, cree una matriz de 1000 elementos y rellénela con
10 elementos de piedra de sangre,
100 elementos vacíos,
20 elementos de oro,
etc.

Finalmente, genere un número aleatorio entre 0 y 1000, y use eso como el índice en la matriz de elementos, esto le dará su elemento aleatorio.

Es posible que tengas que jugar con las posibilidades un poco, ya que probablemente quieras que se llenen los 1000 elementos de la matriz, pero esta es la idea general.

La edición no es la implementación más eficiente (al menos en términos de uso de memoria, su tiempo de ejecución debería ser bueno), pero elegí esto ya que permite una explicación concisa que no requiere mucha matemática.

Answer 6

Primero representaría la probabilidad de cada tipo de botín como un número simple. Una probabilidad en matemáticas puras se expresa convencionalmente como un número de punto flotante en el rango de 0 a 1, pero para eficiencia, puede usar números enteros en cualquier rango (lo suficientemente grande) (cada valor es el valor 0-1 multiplicado por el máximo (que Estoy llamando a MaxProbability aquí).

e.g. Bloodstone (1 in 100) is 1/100 = 0.01, or MaxProbability * (1/100).
     Copper (1 in 15) is 1/15 = 0.06667, or MaxProbability * (1/15).

Supongo que ''Predeterminado (Nodo vacío)'' significa la probabilidad de que ninguno de los otros. En este caso, la forma más sencilla es no definirla: la obtendrá si no se elige ninguna de las otras.

Si se incluyó ''Predeterminado'', la suma de todas estas probabilidades sería 1 (es decir, 100%) (o MaxProbability , si se usan números enteros).

La probabilidad 1/10 de ''Predeterminado'' en su ejemplo es en realidad una contradicción porque el total de todas esas probabilidades no es 1 (es 0.38247619, la suma de la probabilidad calculada en mis ejemplos anteriores).

Luego elegiría un número aleatorio en el rango de 0 a 1 (o MaxProbability si usa números enteros), y el tipo de botín elegido es el primero en la lista, de modo que la suma de las probabilidades y todos los anteriores ("probabilidad acumulativa ") es mayor que el número aleatorio.

p.ej

MaxProbability = 1000   (I''m using this to make it easy to read).
     (For accurate probabilities, you could use 0x7FFFFFFF).

Type                 Probability  Cumulative
----                 -----------  ----------
Bloodstone             10            10              (0..9 yield Bloodstone)
Copper                 67            77    (10+67)   (10..76 yield Copper)
Emeraldite             29           105    (77+29)
Gold                   20           125    etc.
Heronite               17           142
Platinum               17           159
Shadownite             13           172
Silver                 29           200
Soranite                1           201
Umbrarite               1           202
Cobalt                 13           216
Iron                   67           282

Default (Empty Node) 7175          1000   (anything else)

por ejemplo, si su número aleatorio en el rango de 0 a 999 (inclusive) era 184 (o algo en el rango de 172 a 199), elegiría "Plata" (el primero con una probabilidad acumulada mayor que esto).

Podría mantener las probabilidades acumuladas en una matriz y recorrerlas hasta encontrar una más alta que el número aleatorio, o llegar al final.

El orden de la lista no importa. Has elegido un número aleatorio solo una vez por instancia.

Incluir ''Default (Empty Node)'' en la lista significa que la última probabilidad acumulada siempre será MaxProbability y el ciclo que la busca nunca pasará del final. (Alternativamente, se puede omitir ''Predeterminado'', y usted lo elige si el bucle llega al final de la lista).

Tenga en cuenta que elegir un número aleatorio para cada uno, por ejemplo, una probabilidad 1/10 de ''Bloodstone'', luego 1/15 de Copper si no es Bloodstone, sesga las probabilidades hacia los elementos anteriores: La probabilidad real de Copper sería (1/15) * (1 - (1/10)) - 10% menos que 1/15.

Aquí hay un código para hacerlo (la elección real es de 5 declaraciones, en el método Elegir ).

using System;

namespace ConsoleApplication1
{
    class LootChooser
    {
        /// <summary>
        /// Choose a random loot type.
        /// </summary>
        public LootType Choose()
        {
            LootType lootType = 0;         // start at first one
            int randomValue = _rnd.Next(MaxProbability);
            while (_lootProbabilites[(int)lootType] <= randomValue)
            {
                lootType++;         // next loot type
            }
            return lootType;
        }

        /// <summary>
        /// The loot types.
        /// </summary>
        public enum LootType
        {
            Bloodstone, Copper, Emeraldite, Gold, Heronite, Platinum,
            Shadownite, Silver, Soranite, Umbrarite, Cobalt, Iron, Default
        };

        /// <summary>
        /// Cumulative probabilities - each entry corresponds to the member of LootType in the corresponding position.
        /// </summary>
        protected int[] _lootProbabilites = new int[]
        {
            10, 77, 105, 125, 142, 159, 172, 200, 201, 202, 216, 282,  // (from the table in the answer - I used a spreadsheet to generate these)
            MaxProbability
        };

        /// <summary>
        /// The range of the probability values (dividing a value in _lootProbabilites by this would give a probability in the range 0..1).
        /// </summary>
        protected const int MaxProbability = 1000;

        protected Random _rnd = new Random((int)(DateTime.Now.Ticks & 0x7FFFFFFF));    


        /// <summary>
        /// Simple ''main'' to demonstrate.
        /// </summary>
        /// <param name="args"></param>
        static void Main(string[] args)
        {
            var chooser = new LootChooser();
            for(int n=0; n < 100; n++)
                Console.Out.WriteLine(chooser.Choose());
        }           
    }
}

Answer 7

Un enfoque ligeramente diferente a la idea de Astrotrains sería que, en lugar de una matriz, se usen las declaraciones if. La ventaja es que necesita menos memoria, la desventaja de que necesitará más tiempo de CPU para calcular el valor del nodo.

Así:

Random rnd = new Random();
var number = rnd.next(1,1000);

if (number >= 1 && number <10)
{
  // empty
}
else
{
  if (number >= 10 && number <100)
  {
     // bloodstone
  }
  else
  {
     //......
  }
}

También una desventaja de esta variante relacionada con la variante de la matriz es que ésta ocupa más lugar en el lugar del código donde la usa y es más propensa a errores / correcciones (intente agregar algo dentro de ella, debe actualizar todas las variantes).

Por lo tanto, aquí se menciona por razones de integridad, pero el array vairant (uso de memoria aparte) es menos propenso a los problemas que tiene la variante if.

Answer 8

Use Random.Next http://msdn.microsoft.com/en-us/library/2dx6wyd4(v=vs.110).aspx :

Random rnd = new Random();

if (rnd.Next(1, 101) == 1)
    // spawn Bloodstone
if (rnd.Next(1, 16) == 1)
    // spawn Copper
if (rnd.Next(1, 36) == 1)
    // spawn Emeraldite

El valor mínimo siempre debe ser 1, el valor máximo es la probabilidad de generar el artículo + 1 (minValue es inclusivo, maxValue es exclusivo). Siempre pruebe el valor de retorno para 1, por ejemplo, para Bloodstone hay una probabilidad de 1 en 100 de que el número generado aleatoriamente sea 1. Por supuesto, esto utiliza un generador de números pseudoaleatorios, que debería ser lo suficientemente bueno para un juego.