Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I am currently contributing to a particle system for our game and developing some emitter shapes.

My uniform random distribution along a line or along a rectangular area works fine - no problem.

But now I would like to have something like a 1 dimensional gradient in this distribution. This would mean for example lower values are more common than higher values.

I don't know what would be appropriate mathematical terms for this problem, so my search skills are rather useless with this one. I need something that is computationally simple, as the particle system needs to be efficient.

share|improve this question
    
Check this out staffwww.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf –  Oakcool Nov 22 '13 at 23:42
add comment

6 Answers 6

up vote 20 down vote accepted

Take a look at this picture:

Curve mapping

It shows the process of mapping a (random) value to a curve. Suppose you generate a uniformly-distributed random value X, ranging from 0 to 1. By mapping this value to a curve - or, in other words, using f(X) instead of X - you can skew your distribution in whatever way you like.

In this picture, first curve makes higher values more likely; second makes lower values more likely; and the third one makes values cluster in the middle. The exact formula of the curve is not really important, and can be chosen as you like.

For example, first curve looks a bit like square root, and second - like square. Third one is a bit like cube, only translated. If you consider square root to be too slow, first curve also looks like f(X)=1-(1-X)^2 - an inversion of square. Or a hyperbole: f(X)=2X/(1+X).

As a fourth curve shows, you can simply use a precomputed lookup table. Is looks ugly as a curve, but will probably be good enough for a particle system.

This general technique is very simple and powerful. Whatever distribution you need, just imagine a curve mapping, and you'll devise a formula in no time. Or, if your engine has an editor, just make a visual editor for the curve!

share|improve this answer
    
+1 clean, clear and as simple as can be, great answer! –  Maik Semder May 24 '11 at 9:24
    
thank you very much for your very thorough and understandable explanation. all of the other posts were very helpful too, but i really could understand your post the easiest and fastest. it sticked out bc it really hit the spot for my way of understanding things. and the aspects you are explaining are exactly what i was looking for (or wandering about)! it will enable me to use this in a lot of cases in future. so thx again!!! btw, i played around with some of your curves of them and it works like charm. –  didito May 24 '11 at 12:11
2  
FYI: These are called quantile functions: en.wikipedia.org/wiki/Quantile_function –  Neil G May 24 '11 at 19:27
add comment

You'd probably get a close approximation to what you want by utilizing an exponential system.

Make the x based on something like 1-(rnd^value) (Assuming rnd is between 0 and 1) and you'll get a few different behaviors of left to right skewing based on what you use. A higher value will get you a more skewed distribution

You can use an online graphing tool to get some rough ideas on the behaviors different equations will give you before placing them in, or you can just fiddle with the equations directly in your particle system, depending what style is more to your tastes.

EDIT

For something like a particle system where CPU time per particle is very important, using Math.Pow (or language equivalent) directly can lead to a decrease in performance. If more performance is desired, and value isn't being changed in run-time, consider switching to an equivalent function such as x*x instead of x^2.

(Fractional exponents could be more of an issue, but someone with a stronger math background than I could probably come up with a good way to create an approximation function)

share|improve this answer
1  
Instead of using a graphing program, you can just plot the Beta distribution as this is a special case. For a given value, this is Beta(value, 1). –  Neil G May 24 '11 at 3:48
    
thx. i tried plotting some graphs and i think it could get me where i want. –  didito May 24 '11 at 9:36
    
@Neil G thanks for the tip with "beta distribution" - this sounds interesting and useful ... i'll do some research on that topic –  didito May 24 '11 at 9:37
add comment

The term you are looking for is Weighted Random Numbers, most of the algorithms I have seen use trig functions, but I think I figured out a way that will be efficient:

Create a table/array/List(whatever) that holds a multiplier value for the random function. Fill it out by hand or programatically...

randMulti= {.1,.1,.1,.1,.1,.1,.2,.2,.3,.3,.9,1,1,1,} 

...then Multiply random by a randomly chosen randMultiand finally by the max Value of the distribution...

weightedRandom = math.random()*randMulti[Math.random(randMulti.length)]*maxValue

I do believe that this will be much faster than using sqrt, or other more computationally complex functions, and will allow for more custom grouping patterns.

share|improve this answer
2  
If you can sacrifice the memory, a table of 100 pre-computed values would be faster (and slightly more accurate). I doubt the user would be able to distinguish between the full and pre-computed versions. –  Daniel Blezek May 23 '11 at 18:43
    
@Daniel it would be faster, but with 100 random values, it is pretty easy to see repeating patterns. –  AttackingHobo May 23 '11 at 18:44
    
Just because there appears to be a repeating pattern doesn't mean it isn't random. The essence of randomness is its unpredictability, which literally means that as much as one can't predict that there won't be a pattern, one also can't predict that there could be one (at least for a short time). You'll have to do some testing, but if you do find patterns with multiple tests using different seeds, then your algorithm for generating pseudo-random numbers may need to be reviewed. –  Randolf Richardson May 24 '11 at 3:16
    
@AttackingHobo thx for that trick. i like the use of LUTs. and the formula is quite easy to understand. i did not think of it this way before. not seeing the wood for the trees ... :) also i think repeating patterns should be avoided but probably would not be recognized in this case anyway. still, precomputing all values would hurt the visual experience. anyway, thx for reminding me that this is a factor to consider on the topic of randomness ... –  didito May 24 '11 at 9:44
    
also thanks for bringing up the term Weighted "Random Numbers"! –  didito May 24 '11 at 12:04
show 1 more comment

Just use a Beta distribution:

  • Beta(1,1) is flat
  • Beta(1,2) is a linear gradient
  • Beta(1,3) is quadratic

etc.

The two shape parameters need not be integers.

share|improve this answer
    
thx for your help. as stated above, beta distribution sounds interesting. but i cannot make sense of the content of the wikipedia page yet. or a formula / code. well, also i don't have time right now to investigate further :s i see that boost has code for beta distributions, but this would be overkill. well, i guess i need to go through it first and then write my own simplified version. –  didito May 24 '11 at 10:07
1  
@didito: It's not so hard. You just replace your uniform_generator() call with gsl_ran_beta(rng, a, b). See here: gnu.org/software/gsl/manual/html_node/… –  Neil G May 26 '11 at 0:19
    
thx for the hint. i do not use GSL (actually have not heard about it before), but good call. i will check the source! –  didito May 26 '11 at 16:41
    
@didito: In that case, I would go with Lunin's solution. Good luck. –  Neil G May 26 '11 at 17:19
add comment

A longer explanation:

If you have a desired probability distribution such as the gradient didito asked for, you can describe is as a function. Let's say you want a triangular distribution, where the probability at 0 is 0.0, and you want to pick a random number from 0 to 1. We might write it as y = x.

The next step is to calculate the integral of this function. In this case, it's ∫x = ½x². Evaluated from 0 to 1, that's ½. That makes sense — it's a triangle with base 1 and height 1, so its area is ½.

You then pick a random point uniformly from 0 to the area (½ in our example). Let's call this z. (We're picking uniformly from the cumulative distribution.)

The next step is to go backwards, to find what value of x (we'll call it x̂) corresponds to an area of z. We're looking for ∫x = ½x², evaluated from 0 to x̂, being equal to z. When you solve for ½x̂² = z, you get x̂ = sqrt(2z).

In this example, you pick z from 0 to ½ and then the desired random number is sqrt(2z). Simplified, you can write it as sqrt(rand(0, 1)) — exactly what eBusiness recommended.

share|improve this answer
    
thx for your valueable input. i always like to hear how skilled people solve problems. but i still need to wrap my head around it to be honest... –  didito May 24 '11 at 9:47
add comment

I think what you ask for is the distribution achieved using a square root function.

[position] = sqrt(rand(0, 1))

This will give a distribution in the single dimension field [0, 1] where the probability for a position is equivalent to that position, i.e. a "triangular distribution".

Alternate squareroot-free generation:

[position] = 1-abs(rand(0, 1)-rand(0, 1))

A square root in optimal implementation is just a few multiplication and sum commands with no branches. (See: http://en.wikipedia.org/wiki/Fast_inverse_square_root). Which one of these two functions are faster may vary depending on platform and random generator. On an x86 platform for instance it would take only a few unpredictable branches in the random generator to make the second method slower.

share|improve this answer
    
The probability of a position won't be equal to the position (that's mathematically impossible - trivially, the domain and range of the function includes both 0.50 and 0.51), nor is it a triangular distribution. (en.wikipedia.org/wiki/Triangular_distribution) –  user744 May 23 '11 at 18:45
1  
While sqrt gives some interesting patterns, particle systems generally need to be very CPU light per particle, so I would recommend avoiding square roots (which are computationally slow) where possible. You can sometimes get away with just pre-computing them, but it can make your particles have noticeable patters over time. –  Lunin May 23 '11 at 20:25
1  
@Joe Wreschnig, did you read that Wikipedia article yourself, stuff a=0, b=1, c=1 into the generation formula and you get the formula in my post. –  eBusiness May 23 '11 at 22:13
3  
@Lunin, why are you complaining about the square root when you have got an exponent in your answer? –  eBusiness May 23 '11 at 22:34
1  
@Lunin: Performance theory is a pretty neglected field, a lot of what people think they know where approximately correct 30 years ago when ALUs were big expensive and slow. Even the exponent function which you have just discovered to be a quite slow arithmetic function is rarely a highly significant performance sinner. Branching (using an if statement) and cache misses (reading a piece of data not currently residing in cache) are typically what cost the most performance. –  eBusiness May 24 '11 at 19:23
show 7 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.