General question about simulating odds without large number of iterations

Hey everyone. I usually post down in the UDK section because I’m still putting the finishing touches on an Unreal-3-based project. But this question isn’t UnrealScript-specific, so I’m posting here for more visibility.

The issue I have is this: When you defeat an enemy, I want him to drop random loot. In a battle, you could defeat up to 200 enemies and you get the loot at the end. I see two possible ways to calculate the random drops, but I’m not excited about either one.

Sorry for the UnrealScript code here. The question isn’t about the code though, more about the theory.



// Too many loops
foreach PossibleDrops(Drop)
{
    for(i=0; i<EnemiesDefeated; i++)
    {
        if(FRand() < Drop.Odds)
        {
            // This item dropped.
        }
    }
}

// Not enough variation
foreach PossibleDrops(Drop)
{
    NumDropped = FFloor(Drop.Odds * EnemiesDefeated);
    if(FRand() < (DropOdds * EnemiesDefeated) - NumDropped) NumDropped += 1;
    // You get NumDropped instances of Drop.
}


Do you know of a way to simulate the bell-curve randomness of the first method with the speed of the second?

Looping through your proposed code 200 times doesnt seem like it would be that CPU intensive…
I assume the problem is that you want to actually drop the loot and that’s the bit that eats the time and freezes your entire game.

My approach to this would be to create a list using your bell-curve random approach, then in a tick somewhere start clearing the list 10 or 20 at a time. The game gets to process as its not locked up dropping all the loot at once, and the tick will be that fast the users probably wont notice.
Thinking about it, I’d start building that list at the point each enemy dies, rather than right at the end. Spread the love/load.

Even worse psuedo code as I mix about 3 different standards and language syntax!




function OnDeath(deadguy)
{
  super.OnDeath(deadguy);

  foreach PossibleDrops(Drop)
  {
        if(FRand() < Drop.Odds)
        {
            // This item will dropped
            gamestate.droplist.Add(Drop);
        }

  }
}

// in gamestate
Function tick(var deltaTime)
{
   var MAX_BATCH = 20;
   var currentBatchCount = 0;   

   foreach dropitem(droplist) 
   {
      if (currentBatchCount > MAX_BATCH)
        break;
  
     DoDrop(dropItem);
     currentBatchCount ++;
  }
}


IIRC Diablo 3 does this by every creature has a simple drop rate (multiplied by the player magic find and such), but there is also a system watching all the drops that increases the drop rate (particularly for legendaries) as time goes on and there is no “natural” drop yet.

I think just assigning a simple drop rate per creature is by far the easiest/fastest way to do things. If you want to modulate the drop rate based on how many creatures there are in an area, you could create hidden volumes that raise/lower the chances, or some such.

In theory this looks a lot like an inverse Poisson distribution. Sadly my maths skills aren’t good enough to write the pseudocode for it, but it should be possible to pass a random number into an inverse Poisson distribution and get an integer number out that tells you how many ‘events occurred’, which in this case would be the number of pieces of loot dropped.

However, I don’t see that doing this 200 times the ‘slow’ way would actually be slow at all. (Compare to the renderer which is shading many millions of pixels per second - 200 comparisons is nothing.)

I’d probably have the possible drops filtered by enemy type though, rather than iterate across every single possible drop and check to see if it’s relevant to the enemy in question.

Thanks everyone for the great ideas. I like the idea of spreading out the spawning of the loot drops. I think I’ll try that. Playing with the drop rate sounds good too, but I think I’ll put that idea in the backlog if players start to complain about low drop rates or something. And I’m going to read up on Poisson distributions right now.