Making Galaxies
A look at a random data generation technique
by Patrick Down

*Note all images in this article are PNG format. If this is a problem email me.

A while back Bryan sent me a small spiral galaxy generator that he had produced. It was based off a small code snippet he found in a flipcode forum.

Here is a summarized version of the code that generated the image on the left. I'm leaving why it works as an exercise for the reader. The source that generated the galaxy images on this page can be found here.

float fArmAngle = (float)((360 / m_nArms)%360);
float fAngularSpread = 180/(m_nArms*2);

for ( int i = 0; i < nStars; i++ )
{
  float fR = fRandom(0.0, fRadius);
  float fQ = fRandom(0.0, fAngularSpread ) * (rand()&1 ? 1 : -1);
  float fK = 1;

  float fA = (rand() % m_nArms) * fArmAngle;

  float fX = fR * cos( fDeg2Rad * ( fA + fR * fK + fQ ) );
  float fY = fR * sin( fDeg2Rad * ( fA + fR * fK + fQ ) );

  //... draw star at point fX,fY
}

It looks pretty cool but it was very regular and stylized looking. I continued to think about ways to make the galaxy look more realistic. I realized that what I wanted was a specific instance of a problem that I had encountered before. I wanted to generate a random population of data that fit a specific statistical profile. In the case of the Galaxy generator I want the stars to bunch up in the center of the Galaxy as well as along the center line of each arm.

To elaborate...

Every programmer who has played with the rand() function has probably done this to a certain extent already. Take for example the tank in the following game. At the street intersection you might use code like this to choose the tank's new direction.

int nDir = rand()%4;
if(nDir == 0)
  TurnLeft();
else if(nDir == 3)
  TurnRight();
else
  GoStraight();

Let's just look at turning right with 4 choices...

int nAngle = rand()%10;
if(nDir <4)
  GoStraight();
else if(nDir < 7)
  Turn(45);
else if(nDir < 9)
  Turn(90);
else
  Turn(135);

On the right you can see how we picked 10 as range of random number to choose from. But suppose we want more choices? The if statement could get too big to handle. What we want is a ( not quite so ) random function whose return values sampled over time fits a certain pattern. But how do we create such a function?

Defining the function...

Let's take the set of bars above and stand them up on the graph to the left. Notice how the X-Axis now represents the four selections we made in the code above. The Y-Axis represents the "choosability" of the corresponding X-Axis value. Let's describe this relationship with a function f(x)=y. The value 10 which we used for the range of the of our random selection above represents the area under the function f(x). Using expression nAngle = rand()%10 was choosing a part of the total area under the line defined by f(x). Let's call g(x) the function that returns the area under the line defined by f(x) between 0 and x. Whoops, this is all starting to resemble the "C" word. Yes, I'm sorry, Calculus. The function g(x) is obtained by integrating f(x) with respect to x.

But don't fear! Sometimes an intuitive answer to the problem works almost as well and there is always Quick Math if you want a more exact answer.

Knowing these things we can follow these steps to define the function we want:

Determine the range of values to choose from 0..R
Determine f(x) the "chooseable" function for x in 0..R
Find g(x), the area under the function f(x) from 0..R
Calculate A = g(R), the total area
Generate P, a random number between 0..A
Find the inverse of g(x), this is g'(x)
Calculate g'(P), this is the return value

Example

Let's use the straight 45 degree line from above as our example. Here's one of those situations where we don't really need Calculus to determine the answer. The line forms a right triangle with the X-Axis and Y-Axis. The area of a triangle is easy to calculate. We make our range of desired values equal to the width of the triangle and also make the simplifying assumption that the width and height are the same. Let's create a new random function to replace the one we us in the galaxy generator above. We solve g(x) with the quadratic formula and simplify.

This is the galaxy with the new random function. I also increased the value of fAngularSpread to bring the edges of the arms closer together. It's better but not quite there yet. Here is the new random function:

float fLineRandom(float fRange)
{
  static float fRandMax = 1.0f * RAND_MAX;

  float fArea = fRange*fRange/2;
  float fP = fArea * (rand()/fRandMax);

  return fRange-sqrt(fRange*fRange - 2*fP);
}

A hat like function

Ok one more try. I won't bother you with the math. The plot of the function we are using is on the right.

Here's the random function and the results.

float fHatRandom(float fRange)
{
  static float fRandMax = 1.0f * RAND_MAX;

  static float fArea = 4*atan(6.0);

  float fP = fArea * (rand()/fRandMax);

  return tan(fP/4)*fRange/6.0;
}

This bunches the stars up in the middle more. It's still not perfect but I think it probably because of the poor simulation of the greater apparent luminosity of the stars in the middle. But we will leave that problem as an exercise to the user.

I hope at lease that this little exercise gives you a few more techniques to use in generating various simulations.

Many thanks to Bryan Mau for lending me his galaxy plotting code.

Discuss this article in the forums

Date this article was posted to GameDev.net: 3/5/2001
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
General