| Roulette Wheel |
» Roulette WheelPage: 1 of 1
By: Daniel
Last updated: 20 April
Most game programmers and the ones using evolutionary programming faced this problem. You have to randomly pick an element from a set, each element having a weight. Example:
Weight ( a )=2
Weight ( b )=1
a has twice as much chances as b to be picked.
In this case the answer is simple: We will generate a random number in the interval [0,3) .
For 0 and 1 we will pick a and b for 2.
We can extend this principle for an entire set.
Lets consider and array of N weights. A simple algorithm to pick and element is:
S <- 0
For I=1 to N do
S<- S+Weight(i)
R<- Choose a random number in the interval [0,S)
S2<-0
P<-0
While S2+Weight(P+1)<=R do
P<-P+1
S2<-S2+Weight(P)
End while
Picked=P
S obtained at the first step.
We could also reuse the partial sums calculated after we choose R at the price
of some extra memory usage used for storing them.
The initialization of the algorithm will look like:
PS - partial sums array
S<-0
For I=1 to N do
S<-S+Weight(i)
PS(i)<-PS(i)+1
End for
R<- Choose random number in the interval [0,S)
Start<-1
End<-N
While Start<= N do
Mid<-(Start+End)/2
If R>=PS(Mid) then
Start<-Mid+1
End if
If R<=PS(Mid) then
End<-Mid-1
End if
End while
Picked=Start
|
|
|
| Programming help |
Do you have problems
with your code?
Please send your question to: askphp@stdlib.com
Somebody will try to help you.
|
|
|
