• 03/05/01 02:02 PM
    Sign in to follow this  

    Making Galaxies

    General and Gameplay Programming

    Myopic Rhino
    [size="5"]A look at a random data generation technique

    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.

    Attached 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.


    [size="5"]To elaborate...

    tank1.png


    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();

    tank2.png


    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);

    tankpropline.png


    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?


    [size="5"]Defining the function...

    bargraph.png


    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.

    formula.png


    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.

    undercurve.png


    Knowing these things we can follow these steps to define the function we want:
    1. Determine the range of values to choose from 0..R
    2. Determine f(x) the "chooseable" function for x in 0..R
    3. Find g(x), the area under the function f(x) from 0..R
    4. Calculate A = g(R), the total area
    5. Generate P, a random number between 0..A
    6. Find the inverse of g(x), this is g'(x)
    7. Calculate g'(P), this is the return value

    [size="5"]Example

    linear.png


    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.

    gal2.png


    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);
    }

    [size="5"]A hat like function

    1ox2.png


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

    gal3.png


    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.


    All text and images Copyright (C) 2001 Patrick Down


      Report Article
    Sign in to follow this  


    User Feedback

    Create an account or sign in to leave a review

    You need to be a member in order to leave a review

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

    There are no reviews to display.