I have put this in the General forum because it is not platform specific; a departure for me as most of my stuff is Windows based.
Imagine we have an object in two dimensional space moving in a straight line and we wish it to make a random turn. Clearly we can turn left from 0 to -180° degrees or turn tight from 0 to 180°. It may be that we wish to restrict a turn to ± 90° as otherwise it would appear unnatural.
Now we can use RND on the range [-90, 90] but any value in that range will have an equal chance of being chosen because RND is a uniform distribution. A spontaneous change in direction by, say, 90° may also be regarded as appearing unnatural.
Another approach is to use a different probability density function. We could use the normal distribution where a change in direction by, say, 90° would be highly unlikely, 80° more likely, 70° more likely still and so on on until we get to the greatest likely change in the range [-10°, 10°].
I am sure that many of you are familiar with the normal distribution and here it is. We have different shapes according to differing means and variances. The peak of the bell curve will cause a slight change in direction and the tails will see a greater change in direction but a very much less likely one.
Better still, to my mind, is a variation of the normal distribution called the von Mises distribution. instead of two variables dictating the shape of the bell curve we have just one, referred to as kappa. Here it is.
The tails of the normal distribution are asymptotic with the x axis and get increasing closer to the x axis as we move further away from x = 0. With von Mises the tails are bounded in the range [-π, π] or [-180°, 180°]. This suits our purpose.
What further interests me is what we get by differing values of kappa. With kappa equal to zero we get a uniform distribution, which is not what we want but as kappa increases we get the formation of a bell curve. When we get to kappa = 4 we are still outside the range [-90°, 90°] for some values, but not many. With kappa = 8 it looks we are now inside the range [-90°, 90°]. Beyond kappa = 8 our range tightens even more.
In the von Mises function below, because it is an approximation, we cannot use kappa = 0 as we get a division by zero and, as we all know, computers do not like that. In the following table I look at a variety of values of kappa starting with kappa = 0.0003.
10,000 calls to the function were made and counts taken in 10° steps from -90° to 90°. A count was also taken with < -90° and > 90°. Here is a table with some kappas.
Code: Select all
kappa
0.0003 4 8 16 24
2492 38 0 0 0
-90
282 47 0 0 0
-80
273 53 5 0 0
-70
287 131 27 3 0
-60
288 256 68 2 0
-50
263 411 205 21 10
-40
289 668 453 189 66
-30
271 905 926 628 402
-20
266 1141 1510 1562 1519
-10
258 1353 1839 2543 3072
0
283 1283 1815 2633 3025
10
305 1118 1452 1543 1486
20
272 977 882 689 372
30
278 679 509 153 46
40
290 424 204 28 2
50
252 223 70 6 0
60
272 125 26 0 0
70
270 81 5 0 0
80
272 42 3 0 0
90
2537 45 1 0 0
With kappa = 8 we only have one value from the 10,000 calls outside the range [-90°, 90°].
With kappa = 24 our range has decreased to [-50°, 50°]. Our change in direction of our object is now restricted to that range with the upper ends being the less likely to be returned.
The von Mises function uses some heavy arithmetic and the time spent in the function varies and is subject to three values of RND being used.
I did 20 tests of one million calls to establish the slowest frequency of returning values and got between 18.78KHz to 244.14KHz. These values are small compared with the frequency of a single RND but 18.78KHz is a return in 53 micro-seconds so may not have a bearing on a graphics program.
The function returns values in degrees but, obviously, that can be changed to your requirements.
The code is an adaptation of code by Michael Bell at the PowerBASIC forums.
Code: Select all
#define Pi 3.141592654
#define TwoPi 6.283185307
Declare Function vonMises( As Single ) As Single
Function vonMises( kappa As Single ) As Single
'-----------------------------------------------------------------------------
' Returns random deviate in degrees from von Mises distribution with mean zero and a given kappa
' Uses Best & Fisher (1979) Method (Applied Statistics 28 pp.152-157)
'-----------------------------------------------------------------------------
Static as single tau, rho, r
Static BeenHere As Long
dim as double z, u1, u2, u3, f, c, theta
If BeenHere = 0 Then
' initial quantities
tau = 1+Sqr( 1+4*kappa*kappa )
rho = ( tau-Sqr( 2*tau ) )/( 2*kappa )
r = ( 1+rho*rho )/( 2*rho )
BeenHere = -1
End If
step1:
u1 = RND : u2 = RND : u3 = RND
z = COS( Pi*u1 )
f = ( 1+r*z )/( r+z )
c = kappa*( r-f )
step2:
IF c*( 2-c ) - u2 > 0 THEN GOTO step4
step3:
IF LOG( c/u2 ) + 1 - c < 0 THEN GOTO step1
step4:
theta = SGN( u3-0.5 )*acos( f )
IF theta > Pi THEN
theta = theta - TwoPi
ELSEIF theta <- Pi THEN
theta = theta + TwoPI
END IF
Return theta*180/Pi
End Function