How to get a random number with 'weight'?

BlitzMax Forums/BlitzMax Programming/How to get a random number with 'weight'?

Smurftra

(Posted 2006) [#1]

Ok, the famous balls in the sack example (no pun intented):

I have 20 balls, 15 are red, 3 are black and 2 are blue

I take one in the sack, the odds are i'll get a red one more often that a black or blue one.

Now lets say i have 3 objects in an array

Array[0].Name = RedBall
Array[0].Weight = 15

Array[1].Name = BlackBall
Array[1].Weight = 3

Array[2].Name = BlueBall
Array[2].Weight = 2

OccurenceTotal = 20

how do i randomize a number from 0 to 2 that takes into account the Weight?

The idea being this: imaging a tetris that once in a while has a special piece instead of the normal ones. The 7 basic tetris pieces would have the same weight, and the specials pieces would have a much smaller weight..

Thanks for the help,

Smurftra (not makign a tetris, just thought it was a clear example)

TartanTangerine (was Indiepath)

(Posted 2006) [#2]

Well there are many ways to do this.

1) Use a wieghted SQL query (that don't help here)
2) Fill an array with the possibilities and choose at random from the array, for example.

Lets assume:

Red ball = 1 (weight 15)
Black ball = 2 (weight 3)
Blue Ball = 3 (Wieght 2)

So our array of numbers is :
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,3,3]

Choose a random position from the array and select the correct ball :)

This method is used widely.

ImaginaryHuman

(Posted 2006) [#3]

So you want the `heavier` weighted ones to show up more often? You could just set them all the same weight and then add more instances of the heavier ones

H&K	(Posted 2006) [#4]

a=rnd (20)
if a <= NumberRed
red
else if a<= NumberRed+NumberBlack
Black
else if a<= NumberRed+NumberBlack+NumberBlue
Blue
endif endif endif

Smurftra

(Posted 2006) [#5]

Wow thanks for the quick answers. I've though of and used in the previous version of my game the method of creating such an array. The problem i wanted to solve was that i have lots of elements (and they are dynamic) and the array becomes really big and i figured some maths could save me some memory/process time.

The other way I could do it would be to have something like

Array[0].Name = RedBall
Array[0].WeightStart = 1
Array[0].WeightEnd = 15

Array[1].Name = BlackBall
Array[1].WeightStart = 16
Array[1].WeightEnd = 18

Array[2].Name = BlueBall
Array[2].WeightStart = 19
Array[2].WeightEnd = 20

OccurenceTotal = 20

randomizing a number between 1 and 20

and then going through the array to find which one's limits englobes my random number. That would save up on memory but not so sure on cpu time.

Tachyon

(Posted 2006) [#6]

My choice:

Ball = Blue
X = Rand(20)
If X > 2 then Ball = Black
If X > 5 then Ball = Red

sswift

(Posted 2006) [#7]

http://www.blitzbasic.com/codearcs/codearcs.php?code=963

Smurftra

(Posted 2006) [#8]

Thanks, i forgot to say that the list of objects to randomize from is dynamic so a IF or Case doesnt work. It has to work for all kinds of weight and object numbers.

Thanks sswift thats what i'm looking for

bradford6

(Posted 2006) [#9]

try this

I just came up with it

(I'm pretty wiped out today but I ran it a few times and it is pretty consistent.) :)

SeedRnd(MilliSecs())

For w = 1 To 20
	For x = 1 To 10000
		If WeightedRND(W) = True Then hit:+1
	Next
	Print "Weight"+W+":"+hit+" Hits"
	Hit=0
Next


Function WeightedRND(weight:Int)
	If Rand(0,weight*weight) = 1 Then Return True
End Function

the lower the weight, the more likely the function will return TRUE. just assign a high weight to the things you want to be scarce.

H&K	(Posted 2006) [#10]

@Tachyon,

Whilst yours looks smaller than mine. Yours has to go through every If statment every time, whereas mine stops going through them when the condition is satisfied.
(If you wish to counter argue that mine has all those additions, I would point out that so does yours, but you just havent put them in. ie you ether pre calculate the "Weights" or you dont)

bradford6

(Posted 2006) [#11]

here si a graphical example:

Graphics 1024,768,16

Type Ball
	Field image:timage
	Field r:Int , g:Int , b:Int
	Field weight:Int
	Field Drawn:Int
	
	Method draw()
		SetColor r , g , b
		DrawOval (Rand(0 , GraphicsWidth() ) , Rand(0 , GraphicsHeight() ) , 25 , 25)
		drawn:+1
	End Method	
End Type

Local redball:Ball = New Ball
redball.weight = 4
redball.r = 255

Local blueball:Ball = New Ball
blueball.weight = 16
blueball.b = 255


Local yellowball:Ball = New Ball
yellowball.weight = 33
yellowball.r = 255
yellowBall.g = 255

SetBlend ALPHABLEND
SetAlpha 0.25
SeedRnd(MilliSecs())

	While balls<100000
	
		If WeightedRND(redball.weight) = True Then redball.draw
		If WeightedRND(blueball.weight) = True Then blueball.draw
		If WeightedRND(yellowball.weight) = True Then yellowball.draw
		
		balls:+1
	
	Wend
Local scale:Float = 3
SetScale 3 , 3
SetAlpha 1
SetColor 255,255,200
DrawText "Red:" + redball.Drawn , GraphicsWidth()/2 ,  GraphicsHeight()/2
DrawText "Blue:" + blueball.Drawn , GraphicsWidth()/2 , scale*(TextHeight("X"))+GraphicsHeight()/2
DrawText "Yellow:"+ yellowball.Drawn,GraphicsWidth()/2 , scale*(TextHeight("X")*2)+GraphicsHeight()/2

Flip

WaitKey
	
	
	
	
Function WeightedRND(weight:Int)
	If Rand(0,weight*weight) = 1 Then Return True
End Function

Grey Alien

(Posted 2006) [#12]

I did the array method for my Bonus games to determine which bonuses can appear.

TartanTangerine (was Indiepath)

(Posted 2006) [#13]

At least with the array method you can guarantee that 20 balls will always be delivered and 15 will be red etc. etc.