Algorithms for biased spawning of items

Question

In my game, I would like to spawn N items, not necessarily at the same time. Some of the items are dependent on what was spawned before (Markov chain-esque), so the probability of spawning two rocket launchers in a row is low, but there's a reasonable probability of spawning a rocket launcher followed by rockets. What would be the most efficient way of doing this? The method will be called very often, so I'm trying to keep calculations to a minimum.

An idea I came up with could be to create an N x N array which acts as a lookup table of the probabilities (Item previously spawned VS Item to spawn). However, in this process, I would need some way of generating a random number with the probability acting as a bias. I am not sure what the best way of doing that is. Things also get slightly tricker when an inventory comes into play, as rockets cannot be generated if Y amount have already spawned. I could create a 3D array and store the inventory number in there, but I'm not sure how efficient it would be to keep updating an array lookup table based on inventory.

That's just an idea I came up with, but there's probably another, better, way of doing this. Are there any data structures that would be more efficient than a 3D array, or algorithms I should read up on?

Answer 1

The most efficient way, if you don't need much state stored, is to do just what you hinted: create a Markov chain. Associated with each state is an array of probabilities of exit to the next state. This gives you complete control over the process and is pretty compact. (Note that you use it by generating a random number from 0 to 1 and doing a binary search on the cumulative probabililties.)

An alternative, fuzzier approach is to maintain a set of probabilities and a set of biases. If you have a bias term like

launcher_bias = 0.8*launcher_bias + 0.2*(1.0 - (last_item == launcher))
rocket_bias = 0.8*rocket_bias + 0.2*(last_item == launcher)

and you weight your probabilities with these values (and then renormalize the whole set to 1, or equivalently if the total probability of all items ends up at 0.7 or somesuch, you pick values from 0 to 0.7) you will find that as you get excess launchers the probability of getting more will drop. But, at the same time, you'll increase the chance of getting rockets. Basically, you'll have some exponentially decaying weighting factor that prejudices you against launchers if you've had one recently.

Answer 2

However, in this process, I would need some way of generating a random number with the probability acting as a bias. Not sure what the best way of doing that is?

Say you have 4 events

• event A, relative probability: 4
• event B, relative probability: 1
• event C, relative probability: 1
• event D, relative probability: 10

The sum of relative probabilities is 16, so generate a random number X in the range [0,16). Four of those numbers should map to A, one to B, etc.

• subtract 4 from X. If X is now negative, pick event A.
• else, subtract 1 from X. If X is now negative, pick event B.
• else, subtract 1 from X. If X is now negative, pick event C.
• else, Pick event D.