Random thoughts: Extreme speed 2D physics

Game Mechanics
#1

TL;DR: How do I detect collisions between meter-sized objects moving tens of kilometers per second in arbitrary directions? =S

Let´s say we theoretically have a 20x5 meter sized (2D) space ship in orbit around the Earth. It´s currently flying at around 7 km/sec relative to the Earth in a clockwise orbit. However, Earth is a mean bastard and launches a 4x1 meter sized missile to take out our poor little space ship. The missile enters an unstable orbit COUNTER clockwise around the Earth and attempts to intercept the ship. Its very fast and reaches a speed of around 13 km/sec while accelerating. With the relative speed between the ship and the missile is between 15 and 20 km/sec depending on the angle the missile is coming from, and I want it to be possible to for this collision to happen.

However, it get´s worse. The simulation is sped up so that one day in real life is one year in simulation time. The simulation is however run at 30 updates per second, which gives us a time step of 365/30 = around 12 in-game seconds per update. This is low enough to simulate accurate stable orbits, but obviously not for doing traditional collision detection by detecting intersections between geometry since the ship and the missile will move over 20km relative to each other in one update. Doing many smaller updates, even for just a subset of all bodies, is not practical due to the several thousands of steps needed to detect.

Detecting collisions would be done in multiple stages. The first stage could be a quad tree to filter out most bodies. We could then do a bounding box collision test between AABBs of the movement lines. Then we could do a line intersection test between the two movement lines, and finally more sensitive tests to determine exactly exactly where the missile hit the ship, so we can calculate a collision response. However, this is can pose BIG problems. What if the collision causes the ship to completely change course and should have hit another nearby body? Since we still complete a full time step before applying new forces the body will end up several kilometers away from it´s correct position.

To solve this I´m going to rely on assumptions. For example, when the speed difference is big enough we can safely assume things based on the properties of the bodies. In the above case we can easily predict that any detectable collision between the missile and the ship will detonate the missile, disintegrating both the ship and the missile due to collision forces, the missiles´s payload and the ship´s weapons/reactor exploding. As long as the collision is detected, collision response is very easy.

Another case would be if a a rail gun or gauss cannon launched a small projectile at an insanely high speed (30+ km/sec) towards the ship. Again, assumptions can easily be made. The bullet will most likely pass straight through the ship with a very low loss of velocity (though with potentially fatal damage to the ship), or be absorbed by the shields of the ship the ship is equipped with shields, in which case the kinetic energy of the bullet is pretty low compared to the mass of the ship, so it will be very hard to find a case where this leads to a missed collision. In short, we rely on the fact that a collision either generates a low enough force that it doesn´t matter much or that the generated force destroys the body. It´s in space, and spaceships aren´t really known for being strong or being able to handle X km/sec collisions well. xD

One problem with this idea though is that “destroyed” does not implied “disappeared”. The ship might break up into parts of debris which could tunnel through other bodies if the collision occurs just in front of them. For example: We have 1 ship going in clockwise orbit and a small probe followed by a 5 km long battle cruiser going counter clockwise. The simulation accurately detects a collision between the probe and the ship, and both heavily break appart and continue in their current directions. The debris from the ship would possible spawn behind the battle cruiser since the battle cruiser very likely has passed the point where the probe and the ship collided by the next time step. Creating the debris in-between the time steps (= create an extra time step) would force us to rewind the whole simulation to the time of the collision which will perform terribly, be very difficult to implement and possible cause pathological scenarios when a collision requires undoing collisions that were detected earlier, e.t.c.

Uh, this kind of ended up with me just brain storming my ideas here. The TL;DR question still stands though, how would you do this?

And here´s a question to the physics pro´s out there: Kinetic energy depends on velocity square, but velocity has always been relative to a fixed point in the system. For example, a rocket taking off from Earth. In this case the rocket starts at 0 m/s and accelerates upwards. The faster it goes the more energy is needed to accelerate it more. However what happens if we use a velocity relative to the sun? The Earth is blasting through space at an insane speed compared to the speed of the rocket. That would mean that the rocket isn´t accelerating from 0 to 11 km/sec to get into orbit, but maybe 100 to 111 km/sec, or even “accelerating” from 100 to 89 km/sec depending on where on Earth the rocket is launched. Guys, did I break physics?

#2

QuadTree vs. Uniform Grid: depends on your average case distribution of object. Also reasonable to have a forest of these if the world is big rather than “one” structure. In either case if the number of thing is high you would want to walk in a sweeping order. Other fine tuning factors include (like say for a uniform grid) storing cells in flat primitive arrays store in Z-curve or hilbert-curve order. Data for bounding volumes is stored in these as well (linear walks of memory)…enitiy pointer or index is stored in aux data and only noted for the later fine grain collision.

Fast moving: swept circles.

#3

It takes the same amount of energy to accelerate from 0 to 1 m/s, as it would take to accelerate from 10000 to 10001 m/s.

This only falls apart once we reach speeds where Newtonian physics are no longer accurate.

#4

o_O? E = mv^2 —> E/m = v^2 —> v = sqrt(E/m)???
I will obviously stay with Newtonian physics, but…

#5

IIRC, E = 1/2mv^2 … :slight_smile:

#6

the thing is that while accelerating from 0 to 1m/s the mass has to fly a much shorter ways as if it gets accelerated from 100 to 101m/s.

And always remember everything is relative, accelerating from 100m/s to 101m/s while standing on train which goes 100m/s needs the same energy as accelerating from 0 to 1m/s, or something like that

#7

True, my bad.

That makes no sense.

#8

I presumed the reference frame was the rocket itself (it has it’s own propulsion!). When standing on the (surface of the) sun, it would indeed take incredible amounts of energy to accelerate that rocket, if that is your reference frame, which it isn’t.

The fact that the rocket iself is the frame of reference, explains why satellites can have a constant acceleration with an ion-propulsion engine, dispite their incredibly high (and ever increasing) velocity.

#9

Heh, I took a look at Wikipedia, and my head does not approve. How can something energy depend on what reference frame you pick?! I am confused… I blame it on not having gone to uni yet! xD

#10
  1. Particles are waves and waves are particles.
  2. Energy is mass and mass is energy.
#11

Energy can manifest itself as mass, and (hence) mass is energy.

As:
E=mc2
but that doesn’t mean that
m = E/c2
is always true.

#12

The is no such thing as absolute velocity. We cannot measure at which speed we’re traveling through the universe.

So, velocity is relative (to a moving point is space).

What follows is that the ‘v’ in E=1/2mv<sup>2</sup> is relative to some reference frame, and thus the kinetic energy of an object can be wildly varying for n observers.

This analogy is probably flawed (!), but I imagine it like this:
Let’s say you move (accelerate!) 1kg of mass 1 meter in 1 second (you applied 1 Newton). That 1kg mass will continue to move at 1m/s.

To accelerate that 1kg again, you have to expend energy to move yourself near the object (near its frame of reference), to give it another push. The faster it goes, the faster you have to move to exert that force for one second. The alternative is that you apply the force in a shorter timespan, but the energy required grows exponentially (as the acceleration is measured in m/s<sup>2</sup>, and ‘s’ gets smaller).

force = mass * acceleration
acceleration = meter / sec / sec

mass * meter / sec / sec = force


1kg * 1m / 1.0s / 1.0s = 1N required for acceleration in 1.0s
1kg * 1m / 0.1s / 0.1s = 100N required for same acceleration in 0.1s

Now somebody please correct me.

#13

Is this stuff too many year behind me? I was thinking rest vs. relativistic mass.

#14

Oh. Probably me being silly then.

#15

Today’s lesson is special relativity. I love this forum :slight_smile:

#16

For the simulation question, non of these speeds are insane, most serious orbital mechanics stuff should handle that and collisions. However there are some very nice tricks.

First of all the time integration method really matters. For mostly ballistic trajectory (99.9% of real space stuff) it is better to use a reversible time step method rather than a high order one. So leap frog for example rather than 4th order RK methods.

Next is dealing with round off and other errors. In your case you probably don’t need to care. But long term stability simulations track errors.

However this means that most simulations use very large “bounding spheres” where the sphere is much larger than the bounds. This deals with numerical errors better and this is why earth has a chance of getting hit by a asteroid. Of course i am simplifying a bit here. But for a game, a bounding tube from the last time step based on the bounding sphere is going to good enough. Even for not a game, as a first cut or for first order accuracy you won’t do better.

Physics!
As for the Physics… well I love confusing my students with these types of questions. It gets even the smart students.

The point to remember is the the result is the same in all frames of reference (energy is conserved etc). Also what a frame of reference is does in fact change some rules. For example a rotation frame of reference, the best example is a reference frame fix to somewhere on the surface of the earth. You get an extra acceleration term, the Coriolis force. But i digress.

Another good one is that a rocket can go quite a bit faster than its exhaust velocity. With a mass ratio of 20, its about 3x faster!

If you run the numbers properly you do get things that work consistently. For example, work done in each frame is not the same since work is F x d. With a rocket, in the initial inertial frame of reference, once the rocket is moving, the remaining fuel has both non zero kinetic energy and momentum.

I could go into in detail if you want.

#17

I´m planning on using Verlet integration, though I have tried both Verlet and RK4. Verlet is much faster and the accuracy is good enough with the above time step. RK4 also behaves very differently when the time step is too large. With a non-circular orbit the whole orbit starts to rotate around the body, while RK4 simply loses energy and crashes after a while. Luckily, the ship will enter the atmosphere of the planet, and air resistance hides both these problems.

Long term stability isn´t too important as long as the moon does not crash into the Earth after a few hundred years. I need some more experimentation with this, but otherwise I don´t think that´s a problem. xD

Like I said I´ve already experimented some with integration, so that problem is pretty much solved. I´d like to focus on actually detecting and handling collisions instead, but all tips are welcome! For example, what´s leap frog? =S

#18

Speaking of reversible methods. I do in fact have some reversible 32 & 64 bit LCG RNGs if anyone want to toy with crazy stuff.

#19

leap frog is a special type of verlet integration. As in reversible. That is, it is easy to simulate backwards and get to the original starting state. Even with a 100 years (3000 orbits) small errors really add up if you simulate the full system rather than a approximation. But if it an’t broke don’t fix it.

I would still just go for intersecting cylinders for collision detection. The math is fairly straightforward even in 3d at least with Cartesian coordinates. Which is what i would use.

So no extra physics? :-\

#20

???

Extra physics?