Randomising the chance that something will appear
BlitzMax Forums/BlitzMax Programming/Randomising the chance that something will appear
| ||
| Well as the thread title says, I need to randomise the chance that something will appear. I've done this before when I like say 2% of the time a bonus may appear, and that's fine. But now I need to say that something WILL appear but it will be one of 5 items. Each of those items has a predefined % chance that it will appear. So for example: A = 10% B = 10% C = 10% D = 20% E = 50% Previously I've done things like populated and array with 1xA, 1xB, 1xC, 2xD, 5xE and then I've randomised a number from 1 to 10 and picked an array slot. That works fine, but if I want to use decimal places for my % chance then I'd have to make an array 1000+ or more slots long which is silly. OK so I could do this: 1) Create a random number from 0 to 100. 2) Start a loop going and test if the random number is in the range of A, and if not check B and so on until E has been checked (well E does not need to be checked because if the random number is not in the range of D, we know it's in the range of E) This seems a bit slow though, especially if I have LOTS of the items generating each logic loop. Can anyone think of a quicker way? A Select Case would be pretty much the same as running a loop. Thanks! |
| ||
| I would use a select/case or If/elseif with the largest percentage first. <edit> Thought it had come up before... This might help as well. |
| ||
I'd probably do it like this (untested but I'm 99.99% sure this works):N = Rand(1,100)
Select True
Case N >=1 And N <=10
'do stuff
Case N>=11 And N <=20
'do other stuff
'....etc
End Select |
| ||
| Thanks. I like the idea of presorting the percentages and putting the largest first to reduce loop iterations (or if/then select/case steps). I guess there is no quicker way to do it then. The weights are dynamic by the way so I can't use consts. |
| ||
This is the way I do it:
Function picksomething(probabilities#[])
p#=rnd(0,1)
t#=0
i=0
while t<=p
t:+probabilities[i]
i:+1
wend
return i - 1
End Function
Local probabilities#[5]
probabilities=[.1,.1,.1,.2,.5]
number=picksomething(probabilities
|
| ||
| I suggest you create an array with 1 element for each object, and in that element store the floating point percentage `weight` for that item. Then to look up an item, generate a floating point percentage: Local Percentage:Float=FloatRnd()*NumberOfArrayElements Then implement a binary search which starts at the middle of the array and reads the weight of that item and goes from there to find the closest matching weight. Your percentages in the array have to be sorted in order. That will be a lot quicker than searching through the array. |
| ||
| I'd probably do it like this (untested but I'm 99.99% sure this works): I've seen the same exact method used in the source code for RunUO. Seems pretty stable.. |
| ||
ImaginaryHuman, something likeFunction picksomethingbinary(probabilities#[],sumprobabilities#[]) l=Len(probabilities) p#=Rnd(0,1) i=l/2 move=i While 1 move:/2 If move=0 Then move=1 s#=sumprobabilities[i] If s<p i:+move ElseIf s-probabilities[i]>p i:-move Else Return i EndIf Wend Return i - 1 End Function I did a little test to see how much faster it is, and it's not a massive amount: Local probabilities#[5] probabilities=[.1,.1,.1,.2,.5] Local sumprobabilities#[5] t#=0 For i=0 To 4 t:+probabilities[i] sumprobabilities[i]=t Next ms=MilliSecs() For i=1 To 100000 number=picksomethingbinary(probabilities,sumprobabilities) Next diff=MilliSecs()-ms Print "binary search method took "+String(diff)+"ms" ms=MilliSecs() For i=1 To 100000 number=picksomething(probabilities) Next diff=MilliSecs()-ms Print "lazy method took "+String(diff)+"ms" |
| ||
| 6 ms each in non-debug. 28 ms for binary and 24 ms for "lazy" in debug. Interesting results to keep in mind; opposite what you might think... |
| ||
| Previously I've done things like populated and array with 1xA, 1xB, 1xC, 2xD, 5xE and then I've randomised a number from 1 to 10 and picked an array slot. That works fine, but if I want to use decimal places for my % chance then I'd have to make an array 1000+ or more slots long which is silly. Is it? Modern PCs have tons of RAM -- you might as well use it. I don't believe for a second that you really need to account for nths of a percent in the context of a videogame deciding whether to give someone a lemon or a melon though. :D What you were already doing -- do that. |
| ||
| I just tried increasing the number of options to 1000, and the binary search is about ten times quicker. So, right algorithm for the right situations, I suppose. |
| ||
| Um, yah, the more items the better it gets. Probably for only a few items it's pointless because the memory-access speeds are going to be the determining factor more than the number of elements that need to be looked at. |
| ||
| Previously I've done things like populated and array with 1xA, 1xB, 1xC, 2xD, 5xE and then I've randomised a number from 1 to 10 and picked an array slot. That works fine, but if I want to use decimal places for my % chance then I'd have to make an array 1000+ or more slots long which is silly. I'm with Sledge.... is it? it's clean, fast and very little code. |
| ||
| Agreed that a Binary Search only becomes useful after a certain number of elements, maybe 10. @Sledge: It's true that actually I was NOT going to use decimal places so I only need an array of 100, BUT I thought I'd see what solutions people came up with if I said I DID need decimal places ;-) |
| ||
| I would go with your original approach too. It's a straight forward hash over 100 elements. It's easy to implement and it only really costs you what? 400 bytes of RAM? And you can adjust it on the fly. Wrap it in Type, if you want, to encapsulate the functions. It will simplify even further your game code. |
| ||
| Probably I'll just oldskool it and make a 400byte global array which I populate when the level loads. |
   |