Non-uniform simulation granularity

[eddit]

There are analytical solutions for bodies orbiting with respect to time. This website has several examples, including some neat java applets.

For small mass objects you can simplify things even further to make it a single body problem. the probel comes when you have three celestial bodies of significance. For this there is no general analytical solution. However, there are some special cases.

[eddit]

Sorry, I didn't check that website properly. It's giving examples of numerical solutions! But there are analytical solutions with respect to time for the single body problem.

[klauss]

Planets will always be modelled by defining the orbiting shape (ie. an ellipse), etc. etc... it's the easiest and most efficient way. That is: the system designer (either people or autogen) defines the orbit and that's it: no simulation, either numerical integration or whatsoever, needed.

The issue is for ships and other objects. Objects not exerting their own (significant) gravitational pull, basically.

[pincushionman]

If we're not discussing the motion of objects based on gravitational and other forces, then what are we talking about?

[klauss]

If we're not discussing the motion of objects based on gravitational and other forces, then what are we talking about?

Ship movement under gravity. It's nothing like Planet movement: ships don't attract other objects.

[smbarbour]

Actually following the rule that if it has mass it has gravity, they do attract other objects, but only at an extremely minute scale. If you have a cloud of dust in space, eventually (within the timeframe of the universe) it will condense into a ball forming a planet, asteroid, or whatever (depending on the size of the cloud). The time span that this occurs is much like glass (which technically is a liquid). Eventually, your windows will turn into a puddle. Eventually being some time that MAY occur before the sun turns into a red giant.

Sorry for going OT there.

[pincushionman]

It's nothing like Planet movement: ships don't attract other objects.

It's exactly like planet movement. They accelerate in the direction of the sum of the forces acting on them. Except that for planets, moons, and stations the sum of forces is the sum of gravitational forces, while for ships it's that sum plus the sum of thrust. Other than that distinction, they behave exactly the same.

It's not exactly like VEGASTRIKE'S planet movement. But Vegastrike's planet movement is "faked," unless that's changed since we last discussed simulation of planets a year and a half ago in the Rylix forum. And there's no reason we CAN'T fully simulate these massive orbiting bodes according to the same mechanics as well...although there are some gameplay arguments as to why we would choose not to, but even those issues could be dealt with if we wanted.

[klauss]

It's nothing like Planet movement: ships don't attract other objects.

It's exactly like planet movement. They accelerate in the direction of the sum of the forces acting on them. Except that for planets, moons, and stations the sum of forces is the sum of gravitational forces, while for ships it's that sum plus the sum of thrust. Other than that distinction, they behave exactly the same.

You're right, that's a bigger issue. But I was referring to the fact that the model can be greatly simplified if the attraction is not mutual (and I did say I considered the ships' gravitational pull insignificant rather than nonexistent)

It's not exactly like VEGASTRIKE'S planet movement. But Vegastrike's planet movement is "faked," unless that's changed since we last discussed simulation of planets a year and a half ago in the Rylix forum. And there's no reason we CAN'T fully simulate these massive orbiting bodes according to the same mechanics as well...although there are some gameplay arguments as to why we would choose not to, but even those issues could be dealt with if we wanted.

Yes, we could. But it's so much simpler to compute the trajectory while generating the system, and then following that trajectory (and it would free some system resources), that I think we should. It's only a matter of computing those trajectories correctly, but since that's done offline, any method is OK.

[pincushionman]

Okay, I think I'm getting on the same page as you now.

Yes, we could. But it's so much simpler to compute the trajectory while generating the system, and then following that trajectory (and it would free some system resources), that I think we should. It's only a matter of computing those trajectories correctly, but since that's done offline, any method is OK.

I'm not totally convinced it saves us any resources to do it that way. In fact, I'd argue real time simulation takes up less RAM. If you precompute the entire trajectory, you need position data for every frame, and then the computer has to determine how best to interpolate between the two, that is, judge an appropriate speed. If you simulate the trajectory live, at any frame you only need a position vector and a velocity vector. It's a little harder computationally in that you then need to compute an acceleration vector every frame, but the actual motion is a pretty low-cost once you have that. The only really complex part is the summation of all the gravitational forces.

You're right, that's a bigger issue. But I was referring to the fact that the model can be greatly simplified if the attraction is not mutual (and I did say I considered the ships' gravitational pull insignificant rather than nonexistent).

It would be pretty reasonable for us to limit the number of bodies that affect each other as well - any body small enough and far away enough shoud be ignored. A body we define as "orbiting" (planet, moon, asteroid, station) could have a list of "parent" bodies and it ignores the effect of all others. Like a planet is only affected by its sun. A moon is only affected by its planet and that planet's sun, and so forth. An approach like this would give results that are pretty reasonable, yet make the computation of the gravitational acceleration vector low-cost enough to use it in real time.

SO with live numerical integration you give up processor cycles (and if we simplify the gravitation vector as I discussed above, I would argue we give up very little in that department) for a potentially huge savings in RAM, since you don't have to save the waypoints for the entire period of revolution.

AND if you're really worried about processor usage, you can take a best-of-both worlds approach - the frequency of the simulation frames for massive bodies can be pretty darn coarse, so you can "burst compute" several frames (possibly several hundred frames) of planetary orbit during lulls in processor usage, such as ordinary cruising flight, so you have an inventory of waypoints the planets and moons can "ride out" when you really need to devote the processor to other things, like combat (ships would still be done in real-time, but since they're too small to affect planets and moons...). Then when processor use dies back down you burst compute yourself ahead again.

I'm gonna dig around for my MATLAB earth-orbit simulation I did for class a couple of years ago and see if I can pull up how fast I can process it and the memory requirements.

[klauss]

You're talking about sampling the trajectory, while I'm talking about describing it functionally (ie. an ellipsoid with x parameters). Doing that, there's almost no memory footprint, and a very tiny computation cost: evaluating the function of time that gives the position.

[pincushionman]

You're talking about sampling the trajectory, while I'm talking about describing it functionally (ie. an ellipsoid with x parameters). Doing that, there's almost no memory footprint, and a very tiny computation cost: evaluating the function of time that gives the position.

That would indeed be the easiest -- if you're satisfied with the results. Do you know which function you're going to use to approximate the position?

[klauss]

That would indeed be the easiest -- if you're satisfied with the results. Do you know which function you're going to use to approximate the position?

Ehem... that's the real issue... no.
Still, it shouldn't be overly cumbersome coming up with something. It doesn't have to be too accurate: just don't contradict the well-known kepler laws.

Also: I was thinking about what you said earlier, and you can't forget about the sun while computing the moon's orbit. Otherwise... how would it follow the earth? (unless you provide an awful hack my making it orbit the earth, like what's currently being used).

Now, let's get back to the main topic:

@jackS: What do you think about the idea I threw around, about making each unit decide whether to update physics or interpolate in updatePhysics()?

[jackS]

Each unit will be simulated with a simulation atom determined by an abstracted priority function invoked at the time of the processing of that unit. That unit will not be revisited for physics processing until its particular simulation atom has passed. Drawing currently does a simple linear interpolation between the present and next physics state - this is not slated to change at present, only to be modified to properly account for the variable distance between the two endpoints.

[klauss]

Each unit will be simulated with a simulation atom determined by an abstracted priority function invoked at the time of the processing of that unit.

You mean at the time of Unit::UpdatePhysics()? It sounds good. Just make the call after the processing of the unit, so the processing itself can decide in there what to tell when asked. And try to make it so that the priority function is free to choose any simulation atom, and not make it say, for instance: high priority/low priority. That way, the engine could accomodate the computation method I was proposing: the UpdatPhysics() evaluates the next step, and the priority function reports the time to next step.

My original idea would go like this:

Code: Select all

for (it = unit_list.begin(); it<unit_list.end(); it++) {
  it->UpdateAI();
  it->UpdatePhysics();
}
...
for (it = unit_list.begin(); it<unit_list.end(); it++) {
  it->Draw();
}

Now, both UpdateAI() and UpdatePhysics() will keep track by themselves of their simulation atom. If AI is not to be computed, then it just returns quickly without doing anything. If physics is not to be computed, it just interpolates and returns (technically, in-between frames physics simulation is approximated by interpolation):

Code: Select all

void Unit::UpdatePhysics()
{
  timeToNextPhysicsFrame -= GetElapsedTime();
  if (timeToNextPhysicsFrame > 0)
    InterpolatePhysics(); else
    SimulatePhysics();
}
void Unit::UpdateAI()
{
  timeToNextAIFrame -= GetElapsedTime();
  if (timeToNextAIFrame > 0) return;
  ... blahblah / AI execution ...
}
void Unit::Draw()
{
  ... blahblah ...
  // MOST IMPORTANTLY:
  // DOES NOT INTERPOLATE (as it is currently happening)
  // since interpolation is taken care of by InterpolatePhysics() in
  // UpdatePhysics()
}

I think this is quite good. There's no overhead implied, since when you're never iterating through uselessly: if you don't use the occasion to simulate physics, you use it for interpolation. That is, it doesn't need multiple queues. In fact, IIRC, Draw() does not actually draw, but adds the unit to the drawqueue, so you may as well do this:

Code: Select all

for (it = unit_list.begin(); it<unit_list.end(); it++) {
  it->UpdateAI();
  it->UpdatePhysics();
  it->Draw();
}

Get it?

That unit will not be revisited for physics processing until its particular simulation atom has passed. Drawing currently does a simple linear interpolation between the present and next physics state - this is not slated to change at present, only to be modified to properly account for the variable distance between the two endpoints.

Ok. Changing it, anyway (at least the way I want to) is not a big deal.

[chuck_starchaser]

I don't get it.
Ok, here's how I assume things work:
There's a physics frame, that happens every 1/14th of a second, or so I heard.
Then there's a display frame happening every 1/70th of a second or whatever, probably synchronous to the video card's vsynch. Right or wrong? IOW, display happens a lot more often than physics, already by default. And that's why we have interpolation between physics frames.
What we've been discussing since the OP is the introduction of physics frames that occur at submultiples of the standard physics frame rate, that is, say plant growt, planet rotation and the movement of tectonic plates don't need to be run at 14 Hz, but 7 Hz, 3.5 Hz, 1.75 Hz, whatever, might be good enough.
At least, this has been my understanding of the topic.
And I mentioned Runge Kutta, because using Runge Kutta instead of Euler we could cut back the frequency of updates *a lot* more.

Now: Collisions weren't mentioned until later. How often are collisions computed? I'm not familiar with the VS code yet, but here's how I would implement collisions: 5 stages of ellimination...
1) Ships flying at SPEC speeds are only collision tested versus planets, since collisions with other ships in space are so improbable they aren't worth computing. The rest is for ships not in SPEC...
2) Determine closest planet or base for each ship. Ships whose closest planet isn't the same, need not be tested for collisions. In other words, group ships by closest planet or station.
3) Use collision spheres first, since they are the simplest to compute: Just compute distance between them and compare to the sum of their collision radiuses. Ships whose collision spheres don't intersect, are elliminated from the list of candidates. As for the rest...
4) Collision boxes, where the boxes are aligned with the ship's geometry, would give us then a much higher probability of elliminating close misses, while only testing 8 vertexes for each ship being inside the box of the other.
5) Finally, for any ships passing all the above tests, we perform a thorough mesh intersection.

How often?
Well, what's expensive about a collision is when it happens. When ships get elliminated early in the chain of tests, the testing is cheap. And once it happens, something happens to elliminate the collision condition, namely, either you blow up or bounce off, so there's no point in delaying the detection, so, I'd run collision detection at each *video* frame. Then, when a collision happens we need to do some physics, so in this case, a special physics frame for the two objects colliding can be invoked.

Finally, and to get back to physics, if we're going to have self-controlled physics frame rates for objects, then we might as well forget about the 14 Hz "standard frame" and just use any submultiple of the *video* frame-rate a unit deems best. Every 14, every 1400, or every 5 videoframes, whatever. In which case, we'd call the physics (as well as the collisions) at each video frame, and let each unit, AFTER collision detection passes with no news, decide wheter or not to run physics, and whether or not to even interpolate for display's sake, since some objects may move so slowly or be so far away, that even interpolation at each video frame isn't warranted.

Hmm... Now that I look at your code again, klauss, I realize I end up with the same thing...

[smbarbour]

Sorry if I'm wrong and forgive me if I use incorrect terminology, but for determining collisions between ships wouldn't you want to create a hemisphere capped cylinder for the two ships with one focus being the ship's old position and the other being the ship's new position. If those intersect then there is a possibility of a collision having occurred. This would occur very rarely, but if two ships are in high SPEC and their paths cross, they may not drop far enough out of SPEC for the engine to notice, but checking for an intersection this way, would ensure everything is proper.

Just my two cents.

[klauss]

The complexity of collision detection does not only lay in the complexity of the intersection test itself, but in the insane amount of iteration it requires.

For each unit, you have to test whether it collided with the rest or not. That's O(N^2) - and bad, even if you accelerate the test itself. The idea is to discard quickly, a bunch at a time. That's done with a 3D hashmap, IIRC: units are... almost... grouped by proximity. So, at any time, you only consider a tiny fraction of the total number of units. That helps keep useless iteration at bay.

Now, for the real computation of the collision, there are two stages: boudning sphere, and mesh intersection.

So, the test is only expensive in few cases. And, the test uses BSP for mesh intersection, IIRC, so it runs at... hm... O(N1 log N2)? (Mesh to Mesh) or O(log N2) (beam/sphere to mesh) with Nn=number of faces of object n

But, chuck, you're almost right in the rest. Except...

What we've been discussing since the OP is the introduction of physics frames that occur at submultiples of the standard physics frame rate, that is, say plant growt, planet rotation and the movement of tectonic plates don't need to be run at 14 Hz, but 7 Hz, 3.5 Hz, 1.75 Hz, whatever, might be good enough.

...that I proposed my method to avoid limiting ourselves to submultiples of anything. At any display frame, any unit may decide to, instead of interpolating it's state, simulate it. Nice and fast, IMO. Plus, any unit may decide how to interpolate (Linear, Quadric, Hunga Kutta*, whatever)

*Sorry, I couldn't help myself. It does sound like that, doesn't it? Ok. I'll say it: Runge Kutta

[jackS]

I don't get it.
Ok, here's how I assume things work:
There's a physics frame, that happens every 1/14th of a second, or so I heard.

Configurable, but yes, ~1/18 to 1/8 of a second depending on the machine speed set in the config file.

Then there's a display frame happening every 1/70th of a second or whatever, probably synchronous to the video card's vsynch. Right or wrong?

Not quite right. Display happens as many times as it can afford to update between physics/AI/etc. frames. It's completely asynchronous.

display happens a lot more often than physics, already by default. And that's why we have interpolation between physics frames.

Yes. We have interpolation, strictly of where things are drawn, between physics frames.

What we've been discussing since the OP is the introduction of physics frames that occur at submultiples of the standard physics frame rate, that is, say plant growt, planet rotation and the movement of tectonic plates don't need to be run at 14 Hz, but 7 Hz, 3.5 Hz, 1.75 Hz, whatever, might be good enough.
At least, this has been my understanding of the topic.

Yes. What we have in fact already implemented recently is a simple priority scheduling scheme that simulates less important objects (importance-->priority determined dynamically) at integer multiples of the base simulation atom (simulation update scheduling randomly distributes over a priority based range to avoid common divisor load spikes).

[chuck_starchaser]

(simulation update scheduling randomly distributes over a priority based range to avoid common divisor load spikes).

That's smart!

[klauss]

(simulation update scheduling randomly distributes over a priority based range to avoid common divisor load spikes).

That's smart!

Indeed. I didn't think of it.

[hellcatv]

Oh... and I noticed strange moving in single player at times too, so perhaps it's not a multiplayer issue. Perhaps it's not quite noticeable with linear interpolation, but it's there as well. I'm trying to fix it, but can't find the reason for that odd behavior: things go back and forth, as if the interpolation factor was getting off the [0,1] range and warping around - but it shouldn't do that in any case, as it gets clipped to that range. So it makes no sense. It started happening with the new physics queue.

Have we tracked down this problem--I mostly got it when I added jitter to the sim atoms--now I've turned off nonuniform physics until we're sure collision is how we want it--then I'll turn it back on---
it could also be that the AI depends on the fact that simulation atoms are the same length so it can plan on having just enogh thrust to get it to zero rotational inertia on the dot of hitting the enemy.


any further thoughts on this--the way I calculate the simulation atom is listed in

nterpolation_blend_factor=calc_blend_factor(interpolation_blend_factor,unit->sim_atom_multiplier,sim_counter,current_sim_location);
in star_system.cpp
maybe it's broke! I double checked though and couldn't find a bug

Also could be broke ONLY if we use nonuniform jittered sim atoms--which we *could* work around by making things only be jittered when they *change* between sim atoms

[klauss]

calc_blend_factor was somewhat broken. I can't remember what it was, though. If I remember, I'll post. But, still, that's not the source of trouble.

As you expect, the trouble comes from simulation atoms not being of equal length.

The "jitter on change only" thing I have already done. Once I take out the "collision fix that wasn't", I'll commit a bunch of stuff (and that jitter change) along with it. Even if atoms are back to unity, the change will be beneficial when atoms cease to be so.

But... still... I'm getting some weird stuff sometimes.

I think it has something to do with the physics loop not eating all the physics frames it should be eating when the time between frames gets larger than 1 frame.

[chuck_starchaser]

Code: Select all

static double calc_blend_factor(double frac, int priority, int when_it_will_be_simulated, int cur_simulation_frame) {
	bool is_at_end=when_it_will_be_simulated==SIM_QUEUE_SIZE;
  if (cur_simulation_frame>when_it_will_be_simulated) {
    when_it_will_be_simulated+=SIM_QUEUE_SIZE;
  }
  double distance = when_it_will_be_simulated-cur_simulation_frame;//number between for next SIM_FRAME and SIM_QUEUE_SIZE-1
  double when_it_was_simulated=when_it_will_be_simulated-(double)priority;
  double fraction_of_physics_frame=(cur_simulation_frame-when_it_was_simulated+frac-1)/priority;
  if (is_at_end) {
	  return 1;
  }else {
	  return fraction_of_physics_frame;
  }
}

Just in case my questions might help find the bug... In the last line above, subtracting "when it was" from "current"; i.e. looks to me like the intention is to compute how far into the simulation timeframe we are, BUT, the previous line assigns "when it will be" to "when it was"... And I don't understand: By the looks of it "when it was"'s purpose is to save the last time a simulation was done, but if so it would be static?, and the assignment would be done each time a simulation is computed, like inside the conditional above? ...

Code: Select all

static double calc_blend_factor( double frac, int priority, int when_it_will_be_simulated, int cur_simulation_frame)
{
  static double when_it_was_simulated = 0.0;
  bool is_at_end = (when_it_will_be_simulated==SIM_QUEUE_SIZE);
  if( cur_simulation_frame > when_it_will_be_simulated )
  {
    when_it_was_simulated = when_it_will_be_simulated - (double)priority; //whatever priority means...
    when_it_will_be_simulated += SIM_QUEUE_SIZE;
  }
  if( is_at_end )
    return 1.0;
  else
    return ( cur_simulation_frame - when_it_was_simulated + frac - 1 ) / priority; //whatever frac means
}

Also, "distance" is never used.

And I wonder, isn't "when it will be" a kind of rolling number? Like, the line
bool is_at_end = (when_it_will_be_simulated==SIM_QUEUE_SIZE);
Wouldn't it be...
bool is_at_end = (when_it_will_be_simulated==cur_simulation_frame);
?
Sorry to bother if I'm totally off track.

[klauss]

Ahh... yes. Thanks chuck, I now remember.

I think this

Code: Select all

if (cur_simulation_frame>when_it_will_be_simulated)

had to be changed to this

Code: Select all

if (cur_simulation_frame[b]>=[/b]when_it_will_be_simulated)

Anyway, I rewrote it since I needed it to do some other stuff.

[hellcatv]

interesting..so this fixed the physics bugs? would be nice to have this committed at some point before the ogre fork