Having objects interact in C++?

PoopLoops · 05-24-2009, 09:35 PM

Hi all, I'm trying to make a gravity simulator using C++ and using SDL for the graphics part. I just can't figure out how to get my objects to interact with each other.

So, my plan of attack is to have a Planet class and a Comet class. Planets have mass, position, and size. Comets have position, velocity and acceleration. At least for now, just to get things running.

The idea is pretty basic. Planets will attract comets using Newton's law, which gives me a formula for acceleration of the comet, while planets stay put.

My question, then, is if I put up 2 or more planets and let loose one comet, how do I get the planets to affect the comet? I can do an ad-hoc solution, but my plan is to let the user decide how many planets to place and where.

I'd have to find some way for the comet to calculate the total force it is feeling. A friend of mine (comp sci major now working for Google

) told me (this was over a year ago) to use a container class. I did a search on it, but I'm still kind of confused.

Would it work to have a "Universe" class which contains an array of planets and comets, and one by one takes the info from all planets and calculates the force felt by each comet? I'm not sure how viable that is, since the other objects would just sit there waiting for their turn to be calculated.

Anybody got any suggestions?

kellinwood · 05-24-2009, 09:55 PM

How about a list of planets and a list of comets. Each time you update the simulation just iterate the list of planets applying the forces of gravity to the comets.

Maybe something like this:

Code:

#include <list>

list<Planet> planets;

planets.push_back( new Planet());  // need some sensible planet constructor arguments here
planets.push_back( new Planet());

for (list<Planet>::iterator i = planets.begin(); i != planets.end(); i++) 
{
   Planet p = *i;
   // apply gravity to comets here
}

PoopLoops · 05-24-2009, 10:06 PM

Well that's my question, how do I apply gravity to the comets? I can't figure out how to have a planet tell a comet "Hey you, I'm gonna pull you in."

Best thing I could come up with is my Universe class that has a list of Planets and a list of Comets, and uses getPosition() from each object to calculate the distances between each object in order to then tell each comet what the resultant force is.

I guess that wouldn't have to be a separate class, though, just part of my main() function. But I'm just curious whether or not that would make everything "stutter", as in, comet A is waiting because everything is still being calculated for comet B.

Or, does everything get calculated before any update is done on screen? I guess it would depend on how I implement it. I just want to make sure it ends up being smooth.

graemef · 05-24-2009, 10:10 PM

Quote:

Originally Posted by PoopLoops

Would it work to have a "Universe" class which contains an array of planets and comets, and one by one takes the info from all planets and calculates the force felt by each comet? I'm not sure how viable that is, since the other objects would just sit there waiting for their turn to be calculated.

That looks like an appropriate design. Comets and planets live in a universe and so your Universe should have two containers, although rather than an array which is static use a list (as kellinwood suggests) which can grow dynamically.

Then for each comet calculate the force it receives, this will be a single method call to each comet. This calcForce() method will then ask the Universe object what forces it receives from each of the planets.

Initially, it may look to be slow with all those request back and forth with the Universe object but that is the O-O way and it's advantage is that it breaks the bigger problem down into small discrete problems.

PTrenholme · 05-24-2009, 10:13 PM

Technically speaking, your "definition" of both "planets" and "comets" seems unnecessarily complicated. Wouldn't be easier to just define a object with a radius, mass, and location, and an associated motion vector, and use that object for both your "planet" and "comet" definitions.

Then you set up the differential equation of motion, set a relatively small time step, and calculate the the effect of the time increment on the location of all the objects. If your time increment is sufficiently small, the first (linear) term of the equations will give you a reasonable approximation.

The point, re your question, is that - while you compute the motion of each "object" one at a time - that time is only an instant after the last time you computed the object's location. Thus the error introduced by summing the effect of each object on each other object is relatively small. (Those errors will, however, accumulate over a lengthy computation, as will inaccuracies inherent in using a digital computer for the computation. Thus your orbits may not well match any "reality" after some elapsed time. But you scenario is not too realistic to start with, eh?)

Bottom line: I think your friend offered you some good advice.

PoopLoops · 05-24-2009, 10:23 PM

I don't doubt my friend pointed me in the right direction, I just wasn't sure if I understood correctly.

Eventually I do want to have just one "celestial body" object, where both comets and planets would be able to move, but I'm trying to keep it simple for now and just have planets fixed in their spots and ignore the mass of comets on gravity calculations.

This would also simplify a diffEQ into just a sum of values. Calculate the force from each planet on a given comet, and then just add it up to get my net force. At this point I am trying to learn programming, so I don't want to get bogged down with the math. And when I get to that point, there's Numerical Recipes to the rescue.

Oh, and my concern wasn't with a realistic calculation (at least for now), but the animation. I am not sure that if I have all that stuff on screen, will other comets just sit there while waiting for another comet to get its info calculated, or if they would all move simultaneously. I guess the CPU is just fast enough these days that it doesn't even make a difference at this point, huh?

Thanks for the help, everyone. I'd welcome any other tips you guys can throw at me. I've only taken one quarter of C++ and one of C so I have a lot to learn.

Lee-Pro · 05-24-2009, 11:37 PM

Well, in addition, you might want to have a class for forces as well and put them together like this:

Code:

class Rect
{
    public:
        double x;
        double y;
        Rect(double _x, double _y):x(_x), y(_y){}
};

typedef Rect Force;
typedef Rect Position;
typedef Rect Velocity;

class Comet
{
    public:
        double mass;
        Position p;
        Force f;
        Velocity v;
};

class Planet
{
    public:
        double mass;
        Position p;
};

So for the physics part we take into account a few laws:

Newton's law of gravity: Force = G * (mass1 * mass2) / distance^2
G is the gravitational constant = 6.673 * 10 ^ -11

The resultant force is directional, but we can use the law of similar triangles to split them up into x force and y force:

Code:

void calForce(Planet planet, Comet comet)
{
    double xdiff = planet.p.x - comet.p.x;
    double ydiff = planet.p.y - comet.p.y;
    double dist = sqrt(xdiff ^2 + ydiff ^ 2);
    double force = G * (planet.mass * comet.mass) / dist ^ 2;

    double angle = atan(diffy / diffx);
    double xforce = cos(angle) * force;
    double yforce = sin(angle) * force;
    
    comet.f.x += xforce;
    comet.f.y += yforce;
}

Repeat that between each planet and each comet and you got all the resultant forces that you need.

---------------------------------------

For the velocity part:

NOTE: Time is the time elapsed between frames

Horizontal and Vertical forces are independent of each other
acceleration = force / mass
finalvelocity = acceleration * time + initialvelocity
distnace = velocity * time

Or simplified:

finalvelocity = (time * force / mass) + initialvelocity;

Code:

void calVelAndPos(Comet comet, Uint32 lastframe)
{
    Uint32 currentframe = SDL_GetTicks();
    double time = (float)(currentframe - lastframe) / 1000;
    comet.v.x += (time * comet.f.x / comet.mass);
    comet.v.y += (time * comet.f.y / comet.mass);

    comet.p.x += comet.v.x * time;
    comet.p.y += comet.v.y * time;
}

So, there you go. The entire physics section written already. I haven't got time to test it out but considering that I got my physics exam next week, I should be correct about this. Otherwise I'm doomed.

The closer it is between frames, the more accurate it should be, but involves more calculation. Also, the units here must all be SI units, which means seconds, metres and so on. Otherwise, things would be out of scale.

Good luck on your project!

PS: If you happen to use this code, do mention me in the credits.

graemef · 05-25-2009, 01:19 AM

In the longer term I would suggest an abstract class CelestialBody, from which the classes Planet and Comet inherit. Your Universe object would then have a single list of CelestialBody objects. The CelestialBody class will have a method calcForce() that will receive another CelestialBody object and from that it will calculate the force it receives from that other object. This class will also have an abstract method (pure virtual function in C++ spiel) move() which will move the celestial body. The move() method will be implemented in the concrete class, the planet class will just return zero, whilst the comets will calculate the force and thus their new location.

For the animation you want to calculate the adjusted movement for each object and then when you have the new locations draw the new screen, once the new screen has been drawn display it. To avoid flicker you may need to look up details on screen buffering.

johnsfine · 05-25-2009, 06:59 AM

Quote:

Originally Posted by PoopLoops

Or, does everything get calculated before any update is done on screen?

That is the usual way and that is the answer to most of what seems to be confusing you.

It sounds like you are talking about few enough Comets and few enough Planets that in the frame time between updates you can easily loop through all the Comets and for each Comet loop through all the Planets and for each compute the distance squared (easier and more useful than computing the distance) and from that and the mass get the contribution to acceleration, sum all those contributions and compute the new velocity and position for one frame time into the future.

A frame time might be too long for accurate division into discrete steps. The CPU is probably fast enough to compute (do the whole above loop) several times per frame time and then redraw just once.

There are also more accurate methods for discrete integration (modeling a differential system in small time steps) than the simple method implied above. But it doesn't sound like you care about detailed accuracy.

Quote:

Originally Posted by PoopLoops

will other comets just sit there while waiting for another comet to get its info calculated, or if they would all move simultaneously.

If either the number of Comets or the number of Planets is fairly small, the computation time for updating all the velocities and positions will be quite small compared to the time required to redraw everything.

For smooth animation, you should be able to redraw everything in one frame time. You might need some careful attention to performance in the redrawing code to make all the Comets move simultaneously. I think performance in the computational part will be secondary.

If both the number of Comets and the number of Planets is high, then the simple version of computation would be slower than the redrawing. That is a very complex issue with some very complex solutions in game programming. But I don't get the idea you are trying to tackle that now.

johnsfine · 05-25-2009, 07:45 AM

Quote:

Originally Posted by Lee-Pro

float x;

Use double, not float.

Neither the space nor the time costs of using double instead of float are worth even considering in this problem.

The accuracy benefits of using double may be significant. It's a lot easier to use double than to even figure out whether the choice between float and double matters.

Quote:

Newton's law of gravity: Force = G * (mass1 * mass2) / distance^2

But it is simpler to directly compute acceleration (of the object whose mass is mass2):

Acceleration = G * mass1 / distance_squared

There is no point multiplying by the Comet mass in a Force computation just to divide by it later.

Even in a more detailed simulation using the masses of the Comets for their effects on each other and on the planets, each object's mass is still needed only for its effects on other objects, not for computing its own motion.

I would also save distance_squared as computed before the sqrt in your code, rather than resquare it.
But the sqrt may still be required as the simplest way to decompose the acceleration into x and y components.

Quote:

float angle = atan(diffy / diffx);

What if diffx happens to be zero?
What about other quadrants? You are losing information there.
There is an atan2 function available which is safer and doesn't lose information. But you don't need even that, if you decided to keep the above sqrt.

Quote:

float xforce = cos(angle) * force;
float yforce = sin(angle) * force;

I think it is simply:
xacceleration = - acceleration * diffx / distance;
yacceleration = - acceleration * diffy / distance;

Quote:

finalvelocity = acceleration * time + initialvelocity
distnace = velocity * time

Each of those formulas is linearizing a nonlinear step. It is a rather complex question whether you will get best accuracy using the beginning or ending value of velocity or some combination to compute the increment between beginning and ending position. Intuitively, one would expect that the average of beginning and ending values would be best, but I don't think it really works out that way (since in this simple integration method you have only the beginning value of acceleration for use in each step). Obviously the OP doesn't care about accuracy to that level of detail, but you should at least be aware of the issues you are not explicitly managing.

Quote:

float time = (float)(currentframe - lastframe) / 1000;

You want to do 1000 position updates per displayed frame !!?

Probably not a good idea.

Quote:

The entire physics section written already. I haven't got time to test it out but considering that I got my physics exam next week, I should be correct about this. Otherwise I'm doomed.

I suggest you pay a lot more attention to the sign of each component of acceleration on that exam than you did here.

Quote:

The closer it is between frames, the more accurate it should be

Nonsense! You are working with floating point numbers, not actual real numbers. The closer it is between frames the less error you make due to linearization, but the more error you make due to floating point rounding. If the step size is too small, the error can be very large. Using double instead of float gives you a lot more range in which the step might be small enough for linearization before it is too small for the floating point, but the issue still shouldn't be entirely ignored.

Quote:

Also, the units here must all be SI units, which means seconds, metres and so on.

All units should be consistent with each other and with the chosen value of G. But since this isn't a physics exam, they don't need to be SI. If you have a fixed timestep, you might select a unit of mass such that G*timestep*timestep = 1 so you don't need to multiply be either of them in the actual code.

Quote:

Good luck on your project!

PS: If you happen to use this code, do mention me in the credits.

Good luck on your exam, but I think that sample code might not justify much credit.

PTrenholme · 05-25-2009, 11:59 AM

Quote:

Originally Posted by PoopLoops

I don't doubt my friend pointed me in the right direction, I just wasn't sure if I understood correctly.

Eventually I do want to have just one "celestial body" object, where both comets and planets would be able to move, but I'm trying to keep it simple for now and just have planets fixed in their spots and ignore the mass of comets on gravity calculations.
[...]

This is not possible. Perhaps you meant "ignore the mass of the planet" rather than the comet? The gravitational acceleration between two masses is

Code:

  F=[-GmM/|r|^2] n

where      m = comet's mass
           M = planet's mass
           G = gravitational constant
           r = vector from M to m
           n = r/|r| = Unit vector in the r direction

As you can see, that equation requires both masses be known. Of course, if m is small relative to M, then the movement of M towards m can reasonably be ignored, although the presence of another mass of comparable size to M would invalidate that assumption.

johnsfine · 05-25-2009, 12:51 PM

Quote:

Originally Posted by PTrenholme

This is not possible. Perhaps you meant "ignore the mass of the planet" rather than the comet?

No, PoopLoops meant ignore the mass of the comet and that was perfectly reasonable.

Quote:

The gravitational acceleration between two masses is
F=[-GmM/|r|^2] n

That is not the gravitational acceleration between two masses. It is the gravitational force on one of the masses (would have been the gravitation force on each of the masses if you hadn't been specific about direction).

Remember "f = m a". In this case we'll express that as "a = f / m" or

Code:

  a=[-GM/|r|^2] n

where      m = comet's mass
           M = planet's mass
           G = gravitational constant
           r = vector from M to m
           n = r/|r| = Unit vector in the r direction[/quote]

As you can see, that equation does not require both masses be known.

Quote:

Of course, if m is small relative to M, then the movement of M towards m can reasonably be ignored, although the presence of another mass of comparable size to M would invalidate that assumption.

Reasonable or not, it's clear that PoopLoops wants to ignore the acceleration of the Planets and consider only the portion of the acceleration of the Comets that is caused by the Planets (rather than each other). So the mass of the Comets doesn't affect the answer.

b0uncer · 05-25-2009, 01:15 PM

You probably can't solve the many-body problem precisely all at once, but have to split it up to two-body problems which you then combine. If you happen to have access (through your school, university, workplace, ...) to ScienceDirect, you might want to read some articles there (for example this) about how the problem is usually tried to be solved with computers today. It's a big problem once you go beyond two or three bodies, and even bigger when (some of) the bodies become heavy and you need to take into account the effects of special relativity, but with enough simplifications (which physics is all about) it should be doable. The only thing that is left then is to think whether the accuracy is enough or not---if not, then you need more precise theory which usually leads to heavier calculations and need for faster computers. A normal PC will do for game-accuracy physics but not much farther

Though they claim that Sony Playstation 3 is designed so that it could work out some gravity wave calculations..

This thread sounded interesting (personally I work with quantum mechanical many-body problems, at the moment molecular electronic structure calculations), I hope you get something out of this. My advice is to keep things as simple as possible to get started; when it works, then tune it for more accuracy. If you start with too much details, you'll just get bored and the work never finishes..

Lee-Pro · 05-25-2009, 09:19 PM

Quote:

Originally Posted by johnsfine

Nonsense! You are working with floating point numbers, not actual real numbers. The closer it is between frames the less error you make due to linearization, but the more error you make due to floating point rounding. If the step size is too small, the error can be very large. Using double instead of float gives you a lot more range in which the step might be small enough for linearization before it is too small for the floating point, but the issue still shouldn't be entirely ignored.

Oh, right. I forgot about the round-off errors. So, there should be a balance in the step size as well. I've edited my earlier post to use double now.

Quote:

Originally Posted by johnsfine

You want to do 1000 position updates per displayed frame !!?

Probably not a good idea.

It merely converted milliseconds to seconds. SDL_GetTicks returns in milliseconds whereas we need it to be in seconds.

Quote:

Originally Posted by johnsfine

But it is simpler to directly compute acceleration (of the object whose mass is mass2):

Acceleration = G * mass1 / distance_squared

There is no point multiplying by the Comet mass in a Force computation just to divide by it later.

Don't forget there are more than one planets to calculate. All gravitational forces must be added up first before calculating acceleration. That is why I put "+=" in the line:

comet.f.x += xforce;

I forgot to mention that the comet's forces should be reset to 0 at the start of each frame.

Quote:

What if diffx happens to be zero?
What about other quadrants? You are losing information there.
There is an atan2 function available which is safer and doesn't lose information. But you don't need even that, if you decided to keep the above sqrt.

When it comes to programming, I hate trigonometry.

Quote:

Originally Posted by johnsfine

I suggest you pay a lot more attention to the sign of each component of acceleration on that exam than you did here.

Well, at least I got the underlying physics concept alright ... and thankfully I don't have to do programming for my physics paper.

Plus I'm not doing computer studies this year :D

Thanks for pointing out my mistakes.

johnsfine · 05-25-2009, 09:55 PM

Quote:

Originally Posted by Lee-Pro

Don't forget there are more than one planets to calculate.

I didn't forget.

Quote:

All gravitational forces must be added up first before calculating acceleration.

No need to add before computing acceleration. Adding works just as well after.

f1/m + f2/m + f3/m = (f1 + f2 + f3)/m

Since it is easier to compute f/m than to compute f, there is no reason to go to extra effort just to use the right hand side of that equality.

Quote:

at least I got the underlying physics concept alright

Different instructors have different attitudes about that. When I took physics (very long ago), getting the sign reversed on an acceleration would cost you most of the points for that question (I never made that mistake, but most of my classmates did often).

Also knowing (for a given object) that you can combine contributions to force or acceleration or velocities with equal validity is one of those concepts you want to get right.