Leviathan - WWII sub simulator

[Jonathan]

I just edited the post you're quoting and added some stuff because probably not many people know what I meant and what Armagetron does.

Back to your reply, I don't see a problem with the following.

Code: Select all

position += t*velocity + .5*t*t*acceleration; // possibility 1
position += t*(velocity + .5*t*acceleration); // possibility 2
velocity += acceleration;

Hmm, not sure. The m/s^2 function is based on time since the beginning of acceleration, and if you're calculating it with just the interval between frames, the function is different.

If the sum of all times is identical, so is the result. This is not true for Armagetron.

I sincerely think (and I could well be wrong), that the function is just velocity + acceleration in this case, and if I'm right, armagetron is doing it right. Which also means:

Code: Select all

velocity += acceleration;
position += t*velocity;

looks right to me.

That's horrible. Try it and watch it fail.

I admit I'm only about to take my trig class and I'm skipping college-level algebra to do it, but we did cover acceleration in exercises anyway, last semester.

There are two things to keep in mind here.

1. Like a movie, we use frames to approximate motion because we can't simulate it in realtime. We can only show where everything is at certain intervals, and we can only do collision-testing and movement at those intervals. So some inaccuracy has to be allowed to accomodate it.

Doing everything right is at least difficult and impractical, depending on what you're doing. But if something is easy to do right, do it right.

2. We don't have to be perfectly exact anyway. The player isn't going to notice a difference of +-0.02 m/s. How high is our margin of error really?

Armagetron is .5*t*t*acceleration too far ahead. When I tried an internet game with a fixed client, it became unplayable.

3. (I said I'm only about to take trig) We need these calculations optimized for performance as much as possible, so it's preferable to accept a certain minimum margin of error if that gives us extra cycles to render with. Unless our rendering is spot-on accurate, it's going to hide deficiencies in the physics model anyway.

Do you have any idea how fast programs actually run?

In case you were wondering, correct one-dimensional acceleration (without changing speed) takes 15 cycles on my CPU, and after 11 everything has entered the FPU pipeline or is already finished. With 3 dimensions it needs 17 cycles, and everything has entered the FPU pipeline or is finished in 13. Adding speed+=t*acceleration gets us at 20 and 16, using 64-bit floating point. Now we have a speed problem for sure!

Anyway, I'll reread this after I've slept, when the math will make more sense to me.

It should.

[Lucifer]

edit: I thinkI'd be interested in helping out with this just to test some of the physics I've learned

Somehow I missed your post, probly 'cause Jonathan's post started a new page.

If you're serious, pm or email (you still have my email address?) and I'll give you a shell account you can use to get the code from cvs. And the cvs details, of course. Only takes a minute, compared to setting up pserver access (which doesn't take long either, I would just prefer to wait on that until I upgrade the server OS, at which time I'm thinking seriously about setting up gForge on there).

If you're not serious, no harm done. I just rewrote the math classes again. After I got them all complex and looking the way I wanted them to look there wound up being some really weird anomalies, and I decided rewriting the math classes again to simplify them would be quicker and easier than tracking down the anomalies. They might still be there when I'm done, but you know how it goes. First get the API the way you really want and need it, then debug it.

I'm very interested in your acceleration with mass. How do you figure in water resistance, like on a ship? How does water resistance change acceleration as you go deeper? I'd like realistic acceleration for sure. I'm willing to use grid bearing instead of relative bearing to simplify the UI and a fair amount of the code, but there's a lot of the physics I'd like to have right.

Another thing, down the road, is calculating damage from a shell. I could fake it and probably nobody would notice (except Jonathan, apparently), and there's going to be some abstraction there anyway, but I would like to use a real energy number somewhere in the calculation. Worse, I'm at least two semesters out from physics, and that's one class I didn't take in High School (I hated the physics teacher).

[Lucifer]

Code: Select all

position += t*velocity + .5*t*t*acceleration; // possibility 1
position += t*(velocity + .5*t*acceleration); // possibility 2
velocity += acceleration;

Armagetron:

Code: Select all

speed=speed+t*accel
position=position+t*speed

Hmm, not sure. The m/s^2 function is based on time since the beginning of acceleration, and if you're calculating it with just the interval between frames, the function is different.

If the sum of all times is identical, so is the result. This is not true for Armagetron.

Wait a minute, where's distance being calculated?

Code: Select all

where time is measured in seconds, speed and acceleration also in seconds in appropriate places

interval = time - lasttime
speed += interval * acceleration
distance = interval * speed
position += distance

And yes, mine was on crack completely.

Doing everything right is at least difficult and impractical, depending on what you're doing. But if something is easy to do right, do it right.

Agreed.

2. We don't have to be perfectly exact anyway. The player isn't going to notice a difference of +-0.02 m/s. How high is our margin of error really?

Armagetron is .5*t*t*acceleration too far ahead. When I tried an internet game with a fixed client, it became unplayable.

How is it too far ahead? It depends on what time measures. Is it time at the beginning of the frame, or at the end? It seems like time is time at the beginning of the frame, and at the beginning of the frame, the length of the frame is indeterminate because it varies. That doesn't matter much, you're calculating what happened last frame. So the time period you're calculating for is the interval [last frame, now).

So what is the unit of your .5 here? Is that a millisecond?

Do you have any idea how fast programs actually run?

No, I'm a Python guy, remember?

It's not really a question of how fast the program runs, it's a question of how much work you need to do in each frame. I don't know that acceleration is the place to cut corners for performance, I'm not intending to do it there in my sub simulation, but it is a consideration from time to time. Anyway, an operation that executes in x time that's slightly off but looks right to the user compared to an operation that executes in y time that's perfectly accurate (and looks no different to the user) might be preferred if you're executing that operation 10000000000 times a frame.

Granted, we only have at most 16 cycles at a time, and the cycles are the only things we have to computer acceleration for, but we're not just computing acceleration. We're also dithering it on CYCLE_WALL_NEAR. Since it's just one variable I assume there's just a single multiplier going on, but that still adds another cycle at least. It also means that to compute acceleration in a frame we have to determine how far the walls are, and that's not a small operation. It's not big, but it's not small.

So let's add lasers and bullets and particle systems and all that crap. Now we're computing acceleration for what could very well be 10k objects or more, and we're doing that each frame. How much does it cost then?

[Z-Man]

About timestepping schemes: there are two popular ones that use the interpretation "the stored speed and position are the speed and position NOW". The first one is Euler:

Code: Select all

<calculate acceleration>
position += timestep * speed
speed += timestep * acceleration

Then Jonathan's method (I don't remember its official name, so let's just call it that way):

Code: Select all

<calculate acceleration>
position += timestep * speed + .5 * timestep^2 * acceleration
speed += timestep * acceleration

And there is Verlet, mathematically equivalent to Leapfrog, but better adapted to floating point trouble. Verlet assumes that the position is the position NOW, but speed represents the average speed during the last timestep:

Code: Select all

<calculate acceleration>
speed += .5 ( timestep + last timestep ) * acceleration
position += timestep * speed

Which, at constant timesteps, translates to

Code: Select all

<calculate acceleration>
speed += timestep * acceleration
position += timestep * speed

, the method Armagetron uses. The timer averaging AA uses cares for sufficiently equal timesteps, so the simplification is somewhat justified (I really just wanted to avoid the complications from storing another variable). The difference to Euler in terms of the algorithm is just the swapped evaluation order, but that has a big effect. Try all three methods on the simple, but typical problem

Code: Select all

acceleration = - position * constant

in one dimension. Euler will "explode" quickly, Jonathan less quickly and Verlet not at all, unless constant * timestep gets larger than 1 or 2, I cannot remember. This quite amazing property (that can be analytically proven with eigenvalue methods) that no other viable simulation scheme has comes from the fact that Verlet has a time reversal symmetry: If the acceleration only depends on the position, you can do at one point in time

Code: Select all

speed = -speed
position += speed * last timestep

and, provided you don't get floating point errors, the system will follow the path it went until that point in reverse.
When it comes to accuracy, Verlet and Jonathan are equal: They are second order schemes. If you cut your timesteps in half, the error gets down by a factor of 4. Euler is only first order: to twice as many timesteps and your error only goes down by a factor of 2.

Jonathan's client blew up when he "corrected" the simulation because he forgot to adapt the different interpretations of the speed variable. He would have needed to do

Code: Select all

speed[Jon] = speed[Verlet] + .5 * last timestep * acceleration

when getting syncs from the server.

It's of course possible to rewrite Verlet so the interpretation of the speed variable is the more simple NOW one:

Code: Select all

<calculate new acceleration>
speed -= .5 * last timestep * last acceleration
speed += new timestep * new acceleration
position += new timestep * speed
speed += .5 * new timestep * new acceleration

And of course this can be compactified. This has the slight advantage that it handles speed dependant accelerations better.

[Tank Program]

Somehow I missed your post, probly 'cause Jonathan's post started a new page.

Ooops .

If you're serious, pm or email

I think I am, so will do. Although, my Python experience is limited to once creating a game of BlackJack for a friends school project.

I'm very interested in your acceleration with mass. How do you figure in water resistance, like on a ship? How does water resistance change acceleration as you go deeper? I'd like realistic acceleration for sure. I'm willing to use grid bearing instead of relative bearing to simplify the UI and a fair amount of the code, but there's a lot of the physics I'd like to have right.

At that point I think you'd have to use Energy equations and equations of force rather than equations of motion. E = 1/2mv^2, W=FscosTheta, F=ma, Ffr=(uk or us)Fn... So far though we've just dealt with motion in 2 dimensions at least, but I've got an idea or two for 3 dimensional application. Not sure how well it would work, but I think it'd be fun to try.

Another thing, down the road, is calculating damage from a shell. I could fake it and probably nobody would notice (except Jonathan, apparently), and there's going to be some abstraction there anyway, but I would like to use a real energy number somewhere in the calculation. Worse, I'm at least two semesters out from physics, and that's one class I didn't take in High School (I hated the physics teacher).

It wouldn't just be energy, It'd be force as well. Pressure on a submarine increases with depth, and the submarine absorbs this energy, just when a shell hits it it exposed to a dramatically larger ammount of energy that is very compact for lack of better words. You'd have to have the model of the ship broken into pieces as because of the large size it'd be impossible to treat the whole thing as, well, a whole, at least imo.

And if any of that turns out to be wrong, sorry, I've only had a year of physics.

[Z-Man]

Heh. Semi off topic. Writing the last paragraph of the last post I realized that due to the different lengths of timesteps on server and client, of course AA has to do speed corrections when syncing as well. This is going to be interesting

[Jonathan]

Armagetron is .5*t*t*acceleration too far ahead. When I tried an internet game with a fixed client, it became unplayable.

How is it too far ahead? It depends on what time measures. Is it time at the beginning of the frame, or at the end? It seems like time is time at the beginning of the frame, and at the beginning of the frame, the length of the frame is indeterminate because it varies. That doesn't matter much, you're calculating what happened last frame. So the time period you're calculating for is the interval [last frame, now).

So what is the unit of your .5 here? Is that a millisecond?

???

Do you have any idea how fast programs actually run?

No, I'm a Python guy, remember?

It's not really a question of how fast the program runs, it's a question of how much work you need to do in each frame. I don't know that acceleration is the place to cut corners for performance, I'm not intending to do it there in my sub simulation, but it is a consideration from time to time. Anyway, an operation that executes in x time that's slightly off but looks right to the user compared to an operation that executes in y time that's perfectly accurate (and looks no different to the user) might be preferred if you're executing that operation 10000000000 times a frame.

Granted, we only have at most 16 cycles at a time,

I've had 257, which is not a limit!

and the cycles are the only things we have to computer acceleration for, but we're not just computing acceleration. We're also dithering it on CYCLE_WALL_NEAR.

CYCLE_WALL_NEAR is only used when setting acceleration. Note 1: One of the divisions in the CYCLE_WALL_NEAR calculation takes longer than my code in three dimensions. But there's more than one division so execution speed of my code is certainly not significant, compared to other work. Note 2: Sensors used for calculating acceleration are far worse. Note 3: That's only part of the code that calculates acceleration.

So let's add lasers and bullets and particle systems and all that crap. Now we're computing acceleration for what could very well be 10k objects or more, and we're doing that each frame. How much does it cost then?

Less than memory (if stuff is not in L1 or possibly L2) or what's used to calculate acceleration in Armagetron.

About timestepping schemes: there are two popular ones that use the interpretation "the stored speed and position are the speed and position NOW". The first one is Euler:

Code: Select all

<calculate acceleration>
position += timestep * speed
speed += timestep * acceleration

Then Jonathan's method (I don't remember its official name, so let's just call it that way):

Code: Select all

<calculate acceleration>
position += timestep * speed + .5 * timestep^2 * acceleration
speed += timestep * acceleration

And there is Verlet, mathematically equivalent to Leapfrog, but better adapted to floating point trouble.

Since when does Armagetron run out of sufficient mantissa bits?

Euler will "explode" quickly, Jonathan less quickly and Verlet not at all, unless constant * timestep gets larger than 1 or 2, I cannot remember. This quite amazing property (that can be analytically proven with eigenvalue methods) that no other viable simulation scheme has comes from the fact that Verlet has a time reversal symmetry: If the acceleration only depends on the position, you can do at one point in time

Code: Select all

speed = -speed
position += speed * last timestep

and, provided you don't get floating point errors, the system will follow the path it went until that point in reverse.
When it comes to accuracy, Verlet and Jonathan are equal: They are second order schemes. If you cut your timesteps in half, the error gets down by a factor of 4. Euler is only first order: to twice as many timesteps and your error only goes down by a factor of 2.

Mine is exact if acceleration is constant for the whole timestep, which you can assume if all you have is plain acceleration?

Jonathan's client blew up when he "corrected" the simulation because he forgot to adapt the different interpretations of the speed variable. He would have needed to do

Code: Select all

speed[Jon] = speed[Verlet] + .5 * last timestep * acceleration

when getting syncs from the server.

You can't convert crap (where speed is correct but position is not and framerate-dependent) to true speed and acceleration. I'd rather not change the code at all if I wanted it to be playable.

Btw, I think mainly to Lucifer: position + t*speed + .5*t^2*acceleration = position + distance traveled due to speed + distance traveled due to acceleration

[Z-Man]

Lucifer: The .5 in the formulas is unitless. time * time * acceleration has the unit of length, that's what you want if you add it to another length.

Since when does Armagetron run out of sufficient mantissa bits?

With Leapfrog? Pretty soon. With floats, relative accuracy is about 10^-5. Leapfrog derives velocity from two past positions, so its accuracy is limited by the relative error in the difference of the positions. Say we want velocity to be accurate to 1% (And this is a gross underestimation of what's required). Then, the two points have to lie closer than 10^-3 (relative to their position). And at 1000 fps, that's what you get when you move from the origin of the coordinate system for one second.
Try it. Leapfrog with floats fails to accelerate correctly after 1000 simulation frames.
Just in case: Leapfrog is

Code: Select all

position next frame = 2 * current position - position last frame + timestep * timestep * acceleration

Mine is exact if acceleration is constant for the whole timestep, which you can assume if all you have is plain acceleration?

The acceleration changes constantly depending on your position in real problems. You should really try the simple test problem and compare the results. Or simulate a real physical problem, like celestial motions. If you want stable solar systems, you better use Verlet or an implicit method (which is very expensive).
Edit: Verlet is exact under the same conditions, too, if you set the start data correctly.

Btw, I think mainly to Lucifer: position + t*speed + .5*t^2*acceleration = position + distance traveled due to speed + distance traveled due to acceleration

Yes, for Lucifer, this is good, the basic assumptions that enter hold. But you were also attacking the perfectly good Verlet scheme, so I assumed an explanation was in order. You called it incorrect. I agree that AA's usage of it is sloppy when it comes to initialization and synchronisation, but you can't blame Vertet for it.

[Jonathan]

Since when does Armagetron run out of sufficient mantissa bits?

With Leapfrog? Pretty soon. With floats, relative accuracy is about 10^-5. Leapfrog derives velocity from two past positions, so its accuracy is limited by the relative error in the difference of the positions. Say we want velocity to be accurate to 1% (And this is a gross underestimation of what's required). Then, the two points have to lie closer than 10^-3 (relative to their position). And at 1000 fps, that's what you get when you move from the origin of the coordinate system for one second.
Try it. Leapfrog with floats fails to accelerate correctly after 1000 simulation frames.

Leapfrog looks bad for floating point (though final results are probably similar to storing velocity and such), but Armagetron's range (time to traverse the grid) is quite small. Multiply range by framerate and you can approximate precision in the worst corner, which should be close to accuracy.

Mine is exact if acceleration is constant for the whole timestep, which you can assume if all you have is plain acceleration?

The acceleration changes constantly depending on your position in real problems. You should really try the simple test problem and compare the results. Or simulate a real physical problem, like celestial motions. If you want stable solar systems, you better use Verlet or an implicit method (which is very expensive).

I guess Armagetron is no solar system? (and not as complex, and with near constant acceleration)

Edit: Verlet is exact under the same conditions, too, if you set the start data correctly.

Btw, I think mainly to Lucifer: position + t*speed + .5*t^2*acceleration = position + distance traveled due to speed + distance traveled due to acceleration

Yes, for Lucifer, this is good, the basic assumptions that enter hold. But you were also attacking the perfectly good Verlet scheme, so I assumed an explanation was in order. You called it incorrect. I agree that AA's usage of it is sloppy when it comes to initialization and synchronisation, but you can't blame Vertet for it.

I wasn't attacking Verlet. I only said (or at least meant) Armagetron's acceleration can't be emulated with my code. You can't have both accurate constant acceleration (common in Armagetron) and match Armagetron's acceleration code (I may have missed some code related to acceleration, but things obviously broke in network games).

[Z-Man]

<snip>Try it. Leapfrog with floats fails to accelerate correctly after 1000 simulation frames.

Leapfrog looks bad for floating point (though final results are probably similar to storing velocity and such), but Armagetron's range (time to traverse the grid) is quite small. Multiply range by framerate and you can approximate precision in the worst corner, which should be close to accuracy.

For the default arena size and default speed at 60fps, yes. But we'd never be able to support all the variance in the parameters we do now. Leapfrog steals away half the significant bits of your mantissa. Without giving you anything in return. You still don't know the current speed of your objects, just as with Verlet.
Oh, if you do make the experiment, you'll probably find that I was off by a factor of ten with my estimate.