Gravity Engine - dev blog

[annikk.exe]

As you may or may not have heard, now that I have finished my AI map I intend to begin work on a "gravity engine", with moving asteroids.. and basically my first project once the engine is finished will be to build a rendition of our solar system.  Earth, Venus, Mars, etc, all will be represented, along with their moons, and will orbit one another.


I expect this to take several months to complete, but I suppose it depends how obsessed I get.  :>

[annikk.exe]

Last night I learned the equation for calculating the force of attraction between two masses.

It is: Fg = (G * CheckedRoid * DistantRoid) / SeperationDistance^2


Fg, G, CheckedRoid, DistantRoid, and SeperationDistance are all variables.

• Fg is a variable describing the amount of gravitational force acting on an object
• G is the gravitational constant (in reality 0.667 x 10^-11), which I will probably change to something more suited to the scale of a Eufloria level
• CheckedRoid is the asteroid whose gravitational forces we are calculating on this pass
• DistantRoid is the asteroid to which we are measuring the gravitational pull
• SeperationDistance is the distance between CheckedRoid and DistantRoid - calculated using pythagoras theorum: SeperationDistance = math.sqrt((horizontal difference between checkedroid and distantroid)^2 * (vertical difference between checkedroid and distantroid)^2)

I will use a For loop to check all of the asteroids in turn.
Then, for each asteroid I check (ie checkedroid), I will use another For loop to check all the gravitational forces from other asteroids that are acting upon it.
Then, once I have all the different forces acting on checkedroid, I combine them using Force Vector Summing, another crazy maths concept I learned about last night.

Basically imagine one of the gravitational forces.  It has a direction that it is pulling, and it has a magnitude.  You could imagine this like an arrow pointing from checkedroid towards distantroid.  You can imagine that the length of the arrow is indicative of the amount of force it is exerting.  So a large distantroid with a lot of gravity would exert a large force on checkedroid, and would mean a longer arrow.

So when you plot all of these arrows, you basically get lots of arrows spiking outward from checkedroid, and pointing at all the distantroids.  The size and the distance of the distant asteroids would be the determining factors of the length of the arrows.

To add all of these arrows up into a single combined arrow, first you pick up all of the arrows except for the very first one.
Where the first one ends, you place the second one's start.
At the end of the second arrow, you place the start of the third arrow, and so on.

If all of the forces acting upon the object are equal and cancel each other out, the line you draw with these arrows will always end up back at checkedroid where it started - regardless of the order you put the arrows down in.

If the tip of the final arrow is some way off from checkedroid, you can draw a line between that point and checkedroid and this line that you draw is the combined direction and magnitude of all of the asteroids.

So that's the principle behind force vector summing.  To do it mathematically I have to find something called the dot product of all of the different vectors.


Here is some pseudo code representing how I intend to do this:

Code: [Select]

for passnumber = 1, number of asteroids do

if distantroid is in the North East Quadrant compared to checkedroid then:
summedvectorx = summedvectorx + x[passnumber]
summedvectory = summedvectory - y[passnumber]
end

if distantroid is in the North West Quadrant compared to checkedroid then:
summedvectorx = summedvectorx - x[passnumber]
summedvectory = summedvectory - y[passnumber]
end


if distantroid is in the South East Quadrant compared to checkedroid then:
summedvectorx = summedvectorx + x[passnumber]
summedvectory = summedvectory + y[passnumber]
end


if distantroid is in the South West Quadrant compared to checkedroid then:
summedvectorx = summedvectorx - x[passnumber]
summedvectory = summedvectory + y[passnumber]
end

end


At the end of that, summedvectorx and summedvectory will be the values needed to show where to draw the force vector for the combined force.  Some quick pythagoras gets the distance, and thus the magnitude of the force, and it should be no problem to calculate the angle.


Then its some Newton laws or something, to calculate the effect that force has on that mass, given its present momentum and direction.  I will research that later I guess.

[annikk.exe]

It occurs to me I should really check out the Asteroid move functionality to see what it's like...  but eh... SCIENCE!!!

[njursten]

FYI, the Fg is the size of the force acting on both CheckedRoid and DistantRoid, it's symmetrical. This means that you only need to calculate the force for a certain pair once.

Code: [Select]

for i = 0,numAsteroids do
   for j=i+1,numAsteroids do
      ForceMatrix[i][j] = Fg
      ForceMatrix[j][i] = Fg
   end
end

Also, you shouldn't have to check which quadrant DistantRoid is in, that will be taken care of automatically:

Code: [Select]

ForceVector = Fg * NormalizedVector(PosChecked - PosDistant)
Here ForceVector, PosChecked and PosDistant all are 2D vectors (ie. a pair of x-y components) but not Fg.

If you need any help with the math I can probably help you out, just prod me in a PM.

[annikk.exe]

heh... wow... that's so much more elegant than my method :>

I will try to learn about matrices and the other stuff you mentioned, and prod if necessary.. :>

[annikk.exe]

Ok so I'm imagining the matrix as basically a table with columns and rows.
Where i is the column number and j is the row number.

Is that correct?

If so then for each step of i, you will in all of the top column and for each one you also set its symmetrical value to be the same.  So because you are saying Fg = both ForceMatrix[ i ][ j ] and also ForceMatrix[ j ][ i ], basically you are still storing the value twice because you need to know it both ways around, because at some point both asteroids will be the checked one.  The advantage is that it becomes more convenient to call the force acting on an asteroid, and results in less cluttery code.  Is that correct..? :>


I am not clear at all on how your second piece of code is working.  Can you explain it to me? :>

[njursten]

Yes, they are row/column indices. You could just store it in ForceMatrix[ i][j], but then when you do lookup in the table you have to make sure you index with i as the higher of the two numbers. Just extra code for no real improvement. The main reason to only loop over half of the elements is that it's quicker. Kind of a moot point if you're not gonna have a few millions objects. Yes, I'm a perfectionist.

Regarding the second part, do you know vector math (linear algebra)?

I've attached an image. The points marked A and B are the two asteroids. If you do the vector operation minus, you get the distance between them, as a vector. This is useful, because you need to know in which direction to add the force of the gravity. But you only want it as a direction. This would be an arrow pointing to the point marked (B-A)/|B-A| in the image, assuming the circle is the unit circle (ie. has a radius of 1).

To transform it into a direction, you normalize the vector. This is done by dividing the vector by its length (length for 2D vector = square root of (x^2 + y^2)). This will always result in a vector with a length of 1. To write x and y separately:

Code: [Select]

x part of force = Fg * xdiff / sqrt(xdiff^2 + ydiff^2)
y part of force = Fg * ydiff / sqrt(xdiff^2 + ydiff^2)

The distance, as a scalar, between the two asteroids is the same as the length of (B-A), normally written |B-A|.


Don't know if this made it clearer? Also, maybe I covered some stuff you already knew.

[annikk.exe]

Making neat, concise code is a good cause... and so is using features of the language that I've not used before, so I am definitely interesting in trying to use this Matrix beasty you are describing.

I am afraid I'm not at all comfortable with vectors and scalars.  If you were to ask me what they meant, I could probably hammer out a rough definition of vector but I honestly have no clue about scalars - what they are, how they are used, and how they differ from other, similar things.

I will try to learn about these things at the weekend.  Failing that, if it's really beyond me, I might just do it the messy way


Actual coding hasn't begun yet, by the way.  It's all planning and contemplation at the moment.

[annikk.exe]

Ok so... a scalar is a line you can draw between two vectors.  Right?

Assuming I'm understanding that correctly, then my next question is how does this help me determine what quadrant a particular force is pulling in?

[njursten]

Ah, no, a scalar is just a single number, as opposed to a vector. A length has only 1 dimension so it's a scalar, while for example a direction has 2 or 3 dimensions, depending on your world geometry.

A vector is simply a collection of numbers. They can be used to describe a position, direction or whatever that has several components. A matrix is more or less a collection of vectors. You should read up on "Linear Algebra". It basically means vector and matrix mathematics. There are some operations, like vector multiplication and matrix multiplication that can be very useful, but I don't think you can use them for this problem though. But general vector addition and subtraction is useful at least.

It's not the scalar that gives you the direction. It's the subtraction of the two positions from each other that gives the vector pointing from the first asteroid to the other. The whole thing about which quadrant the other asteroid is in is just a flawed idea. You should get a changed sign on the numbers automatically, because the direction between the asteroids will turn negative for x-component if the other asteroid is on the left of the first one.

[annikk.exe]

Code: [Select]

x part of force = Fg * xdiff / sqrt(xdiff^2 + ydiff^2)
y part of force = Fg * ydiff / sqrt(xdiff^2 + ydiff^2)


This code would erroneously produce a positive number every time.  In fact, sometimes the forces should be negative - if the overall force is pulling "south", for example, the value of Y part of Force should be negative.  Hence quadrant checking still seems essential.

[annikk.exe]

I am probably still wrong though.

[annikk.exe]

I have figured this out, I think.

I was getting confused because I was thinking about coordinates of the asteroids, instead of a "virtual" plane consisting of vectors that indicate acceleration and momentum.

(0,0) in the context of the summed Force Vector is actually "no additional momentum in any direction", not literally the coordinates (0,0).  The momentum itself is just another line in this virtual plane.

So suppose your CheckedRoid has a momentum which can be expressed as the vector (50,50).  If the Summed Force Vector of all the asteroids' gravitational pull lies at (15,-15) then we can combine the acceleration due to gravity with the existing momentum, to give the new momentum for this Game Cycle, by doing the following: (50,50) + (15,-15) = ((50 + 15),(50 - 15)) = (65,35).  Our new momentum vector, indicating the amount we shall travel in the REAL X-plane, and the amount in the REAL Y-plane, is therefore 65 units horizontally and 35 units vertically.

Suppose we had a Summed Force Vector with different signs... like (-12,30).  Our existing momentum (50,50) combines to give (50 - 12),(50+30) = (38,80).  So we travel 38 units horizontally, and 80 units vertically.



Let me know if this demonstrates the understanding you are looking for Njursten :>

[annikk.exe]

Asteroid initial momentum conditions will be expressed in how many units (+ or -) horizontally and vertically it travels in one game cycle.

So Asteroid0XMomentum = 5 and Asteroid0YMomentum = 0 would give an asteroid drifting slowly sideways.


Seems like I don't actually have to work out the angle it travels at... :>

[njursten]

Code: [Select]

x part of force = Fg * xdiff / sqrt(xdiff^2 + ydiff^2)
y part of force = Fg * ydiff / sqrt(xdiff^2 + ydiff^2)


This code would erroneously produce a positive number every time.  In fact, sometimes the forces should be negative - if the overall force is pulling "south", for example, the value of Y part of Force should be negative.  Hence quadrant checking still seems essential.

No, it won't be positive all the time, because xdiff and ydiff are not always positive. If asteroid B is to the left of asteroid A, then xdiff is negative and otherwise positive. Similarly for ydiff. Another important point is that you can't really do it any other way, you have to see how far into the quadrant the asteroid is. That more or less boils down to my equations.


Regarding the third post: Yes, you seem to have understood it.
Though the diff vector in my image exists in the coordinate plane. Then you scale it to get the real force vector, your acceleration vector more or less.