[SOLVED] A fail-safe 'random' algorithm?

Okay, before anybody starts spitting out how to use Randoms in Java, I would like to make it very clear that this is not about how to use/create random values in Java.

I'm currently working on a re-write of my WIP ZombieCraft, and I've been slamming my head against a wall trying to figure out how to go about improving my 'special type' spawning probabilities.

The current system works as follows:
- Random number generated to decided whether or not the zombie will be a 'special'
- If it is a special, a random number for each type is generated, and compared with the config values of each special zombie
- If it 'meets' the value, it creates the zombie as the specified type

However, there is a rather large problem with this system: It prioritizes types based on how they're listed in my code.

For example:
Webbers are checked first, then Leapers, then Splitters,(etc)...and finally Infernites.

Now, even though they all have their own random values rolled for them, Infernites still have a statistically lower chance (significantly so) of spawning (as it checks all of the other types first).

I don't suppose there is any obvious solution that I'm missing here...or even a complicated solution that someone can think of off the top of their head? Having spawning-probabilities being configurable seems a little pointless if it doesn't actually control all of the chances.

 

I don't know any java yet (want to learn) but you could try compensating for the lower chance by increasing the chance it spawns in the code.
ex.
current: 25%type1 25%type2 25%type3 25%type4
new: 20%type1 24%type2 26%type3 30%type4

 

You should only generate one random number. Then you can do something like this:

Code:

int chance1 = 25;
int chance2 = 25;
int chance3 = 25;
int chance4 = 25;
if (rand < chance1) {
    // first option
} else if (rand < chance1+chance2) {
    // second option
} else if (rand < chance1+chance2+chance3) //etc

This way each option has the correct chance of being selected. It's just a basic idea though, you'd probably want to create a loop, with a counter adding up previous failed chance numbers (if that makes any sense). For a working example, see my minion spawning code:
http://code.google.com/p/nisovin-mi...isovin/magicspells/spells/MinionSpell.java#87

 

@nisovin
I -half- understand what you're saying.
So, lets say I have these values for chances:
Infernite = 15%
Leaper = 25%
Webber = 65%

If the random number was 30:
30 < 15 = false
30 < 15+25 = true
At which point it would spawn a Leaper without having the right spawn percentage.

Am I missing a key concept here? I looked through your code, and you do the same thing there. Would this not have a slight chance of generating a certain type without the required percentage?

 

@DrBoweNur You're using an else if. Thus, you're only spawning a Leaper if the number is between 15 and 40, which is 25%.

 

A simpler yet crude solution could also be randomizing the order in which the types are checked as well.

 

I get that aspect, but I don't think you're getting my point. Take that scenario and throw yet another type into it: Shade: 20%
You then get that a shade will spawn because it is between 15 and 35.
However, leapers are also located in the 15-35 range, in which case the shade just took priority over the leaper.

I'm either going crazy, or that code will still give priority based on order (in certain scenarios)

That was my first thought, but I wanted to come here just to make sure that there wasn't a cleaner solution.

EDIT by Moderator: merged posts, please use the edit button instead of double posting.

 

No, you aren't seeing it correctly. There will never be an overlapping range. Each range would follow the previous range. You'd end up with something like this:

Infernite: 1-15
Leaper: 16-40
Shade: 41-60
Webber: 61-100

Code:

int infernite = 15;
int leaper = 25;
int shade = 20;
int webber = 40;
if (rand < infernite) {
      // infernite
} else if (rand < infernite+leaper) {
     // leaper
} else if (rand < infernite+leaper+shade) {
    // shade
} else {
    // webber
}

See? Because each of the test before fail, the range of the one that it ends up using will be correct.

Edit: For clarity's sake, the code above could be rewritten to look like this (which is exactly the same):

Code:

int infernite = 15;
int leaper = 25;
int shade = 20;
int webber = 40;
if (rand >= 0 && rand < infernite) {
      // infernite
} else if (rand >= infernite && rand < infernite+leaper) {
     // leaper
} else if (rand >= infernite+leaper && rand < infernite+leaper+shade) {
    // shade
} else {
    // webber
}

 

Although there may be cleaner ways, it wouldn't be as bad as you'd think. I would put the types into a list and shuffle it like so:

Code:java

List zombieTypes = new ArrayList(); // List with all the types
Collections.shuffle(zombieTypes);
for(Zombie z : zombieTypes) {
    // calculate probability as normal
}

 

@nisovin
I'm not stating my intentions clearly. I'm looking for a way to generate a random value, and then spawn accordingly. If the value is 'applicable' for multiple types, it would then go a step further and select one of those types at random. So if the random number rolled a 19, the applicable types would be [Shade, Leaper, Webber] (but not Infernite, since 19 isn't < 15). It would then select one of those 3 at random. This is what I mean by saying that your method is prioritizing the first one to be applicable.

But now I'm starting to realize that I'm thinking with failed logic to begin with. If I 'narrow the choices down' based off of the config values, then randomly pick one of choices, the values defined in the config would still wouldn't have full control over the spawns.

EDIT:
I may have just had an epiphany. I'm beginning to see the logic behind your code now. I'm thinking too literally in terms of comparing the numbers. It doesn't prioritize anything, only gives each type a range based on their percentage.

 

I'm confused, and I think you're confused too. My method allows you to generate one random number, and based on that number, choose a type. It will use the random chances to choose it, and it will be correctly random.

You seem to be making this way more complicated than it needs to be. You shouldn't need to choose a first random number, determine that 3 apply, then choose a second random number to choose one. Just choose one percentage for each type, and my method will correctly choose one.

 

@nisovin
Edited my post right as you posted that

I just now realized what you were doing with the code. In my head, I was reading the number comparisons too directly. I thought that 15-35 literally meant any percentage that was between 15-35 would fall into that category. (IE: 16% and 24% and 31%) However, the range(20%) is where the actual percentage lies. I just needed to look into it a bit more.

Wow, my head hurts. I'm going to go face-desk at my own stupidity.

Thanks for your help.