Unit refactoring: Physics extraction

Development directions, tasks, and features being actively implemented or pursued by the development team.
Post Reply
chuck_starchaser
Elite
Elite
Posts: 8014
Joined: Fri Sep 05, 2003 4:03 am
Location: Montreal
Contact:

Unit refactoring: Physics extraction

Post by chuck_starchaser »

Been trying to procrastinate this, but can only do it for so long.
In order to integrate the RK4 physics that Errol wrote for us, and that I'm writing a scheduler for,
we're going to have to refactor the physics out of class Unit.

The idea is this:

Currently, class Unit is gargantuous; humongous; unmanageably big. It needs to be broken down and
its separate concerns separated; but we got no hero to do this. A more modest approach is to take
one piece out of it at a time, as needed. Right now we need to take the physics out, and have a class
that represents all variables and functions related to unit physics, and nothing else.
I'm suggesting the name "phys_unit" for this class.

My current plan is to allow for up to a maximum of 1024 phys_unit objects at run-time. The number
is not set in stone, though; but what I suggest BE set in stone is that we make a fixed size allocator,
--a fast, array-allocator--, so that there are no slow calls to new/malloc all over the place. Thus, if
we decide we'd better go for 2048 that's fine; but we should decide off-line what the maximum is,
rather than leave it to the runtime to decide. But, assuming 1024, for now, we got a fixed size array
allocator, very fast. Then...
There will be "frequency bins" for simulation, that will simulate units under their control at various
frequencies. The number of bins is fixed to 8, and the frequencies are:
16Hz, 8Hz, 4Hz, 2Hz, 1Hz, 0.5Hz, 0.25Hz and 0.125Hz.
Each bin has a bit array, of 1024 bits, each bit being a flag that signals that the unit at its offset in
the array allocator is simulated by this frequency bin.

Anyways, I got side-tracked to discussing the simulation scheduler...

The matter at hand is this phys_unit class that we want to separate from Unit, and that will be
allocated in this fixed size (1024) allocator. What I've done for now is make a first visual scan of Unit
in unit_generic.h, and copy to this class anything that seems relevant to physics. But it's rather big...

Code: Select all

#ifndef __PHYS_UNIT_H__
#define __PHYS_UNIT_H__


//For now, this is just an extract from class Unit (from /src/cmd/unit_generic.h) which may have
//to be further weeded out. It contains things that may be needed for physics considerations, and
//was meant to be physics-only, but currently spans various categories:
//  *  Propulsion: Engines, energy, thrusters, thrust and rotation limits, etceteras variables.
//  *  Forces and force resolving variables and function declarations.
//  *  Physics: Mass, moment of inertia, acceleration, position, etceteras.
//  *  Weapon hit stuff, which may be relevant if we want reactions to hits.
//  *  Some, but not all stuff relating to subunits, parent, etceteras.
//  *  Some collisions-relate stuff.


class physics_unit
{
public:
    class Limits
    {
public:
//max ypr--both pos/neg are symmetrical
        float  yaw;
        float  pitch;
        float  roll;
//side-side engine thrust max
        float  lateral;
//vertical engine thrust max
        float  vertical;
//forward engine thrust max
        float  forward;
//reverse engine thrust max
        float  retro;
//after burner acceleration max
        float  afterburn;
//the vector denoting the "front" of the turret cone!
        Vector structurelimits;
//the minimum dot that the current heading can have with the structurelimit
        float  limitmin;

        Limits() : yaw( 0 )
            , pitch( 0 )
            , roll( 0 )
            , lateral( 0 )
            , vertical( 0 )
            , forward( 0 )
            , retro( 0 )
            , afterburn( 0 )
            , structurelimits( 0, 0, 0 )
            , limitmin( 0 ) {}
    }
    limits;
    //Takes out of the collide table for this system.
    void RemoveFromSystem();
    void RequestPhysics();               //Requeues the unit so that it is simulated ASAP
    bool InCorrectStarSystem( StarSystem* );
    virtual int nummesh() const
    {
        return ( (int) meshdata.size() )-1;
    }
//The owner of this unit. This may not collide with owner or units owned by owner. Do not dereference (may be dead pointer)
    void *owner;                                 //void ensures that it won't be referenced by accident
//The number of frames ahead this was put in the simulation queue
    unsigned int   sim_atom_multiplier;
//The number of frames ahead this is predicted to be scheduled in the next scheduling round
    unsigned int   predicted_priority;
//The previous state in last physics frame to interpolate within
    Transformation prev_physical_state;
//The state of the current physics frame to interpolate within
    Transformation curr_physical_state;
//When will physical simulation occur
    unsigned int   cur_sim_queue_slot;
//Used with subunit scheduling, to avoid the complex ickiness of having to synchronize scattered slots
    unsigned int   last_processed_sqs;
//Whether or not to schedule subunits for deferred physics processing - if not, they're processed at the same time the parent unit is being processed
    bool do_subunit_scheduling;
//Does this unit require special scheduling?
    enum schedulepriorityenum {scheduleDefault, scheduleAField, scheduleRoid}
    schedule_priority;
//number of meshes (each with separate texture) this unit has
//The cumulative (incl subunits parents' transformation)
    Matrix cumulative_transformation_matrix;
//The cumulative (incl subunits parents' transformation)
    Transformation cumulative_transformation;
//The velocity this unit has in World Space
    Vector cumulative_velocity;
//The force applied from outside accrued over the whole physics frame
    Vector NetForce;
//The force applied by internal objects (thrusters)
    Vector NetLocalForce;
//The torque applied from outside objects
    Vector NetTorque;
//The torque applied from internal objects
    Vector NetLocalTorque;
//the current velocities in LOCAL space (not world space)
    Vector AngularVelocity;
    Vector Velocity;
//mass of this unit (may change with cargo)
    float  Mass;
protected:
//are shields tight to the hull.  zero means bubble
    float  shieldtight;
//fuel of this unit
    float  fuel;
    float  afterburnenergy;              //short fix
    int    afterburntype;                        //0--energy, 1--fuel
//-1 means it is off. -2 means it doesn't exist. otherwise it's engaged to destination (positive number)
//Moment of intertia of this unit
    float  Momentofinertia;
    Vector SavedAccel;
//What's the size of this unit
    float rSize() const
    {
        return radial_size;
    }
//Returns the current world space position
    QVector Position() const
    {
        return cumulative_transformation.position;
    }
    const Matrix& GetTransformation() const
    {
        return cumulative_transformation_matrix;
    }
//Returns the unit-space position
    QVector LocalPosition() const
    {
        return curr_physical_state.position;
    }
//Sets the unit-space position
    void SetPosition( const QVector &pos );
///Sets the cumulative transformation matrix's position...for setting up to be out in the middle of nowhere
    void SetCurPosition( const QVector &pos )
    {
        curr_physical_state.position = pos;
    }
    void SetPosAndCumPos( const QVector &pos )
    {
        SetPosition( pos );
        cumulative_transformation_matrix.p = pos;
        cumulative_transformation.position = pos;
    }
//Rotates about the axis
    void Rotate( const Vector &axis );
/**
 * Fire engine takes a unit vector for direction
 * and how fast the fuel speed and mass coming out are
 */
/*unit vector... might default to "r"*/
    void FireEngines( const Vector &Direction, float FuelSpeed, float FMass );
//applies a force for the whole gameturn upon the center of mass
    void ApplyForce( const Vector &Vforce );
//applies a force for the whole gameturn upon the center of mass, using local coordinates
    void ApplyLocalForce( const Vector &Vforce );
//applies a force that is multipled by the mass of the ship
    void Accelerate( const Vector &Vforce );
//Apply a torque in world level coords
    void ApplyTorque( const Vector &Vforce, const QVector &Location );
//Applies a torque in local level coordinates
    void ApplyLocalTorque( const Vector &Vforce, const Vector &Location );
//usually from thrusters remember if I have 2 balanced thrusters I should multiply their effect by 2 :)
    void ApplyBalancedLocalTorque( const Vector &Vforce, const Vector &Location );

//convenient shortcut to applying torques with vector and position
    void ApplyLocalTorque( const Vector &torque );
//Applies damage to the local area given by pnt
    float ApplyLocalDamage( const Vector &pnt,
                            const Vector &normal,
                            float amt,
                            Unit *affectedSubUnit,
                            const GFXColor&,
                            float phasedamage = 0 );
//Applies damage from network data
    void ApplyNetDamage( Vector &pnt, Vector &normal, float amt, float ppercentage, float spercentage, GFXColor &color );
//Applies damage to the pre-transformed area of the ship
    void ApplyDamage( const Vector &pnt,
                      const Vector &normal,
                      float amt,
                      Unit *affectedSubUnit,
                      const GFXColor&,
                      void *ownerDoNotDereference,
                      float phasedamage = 0 );
//Clamps thrust to the limits struct
    Vector ClampThrust( const Vector &thrust, bool afterburn );
//Takes a unit vector for direction of thrust and scales to limits
    Vector MaxThrust( const Vector &thrust );
//Thrusts by ammt and clamps accordingly (afterburn or not)
    virtual void Thrust( const Vector &amt, bool afterburn = false );
//Applies lateral thrust
    void LateralThrust( float amt );
//Applies vertical thrust
    void VerticalThrust( float amt );
//Applies forward thrust
    void LongitudinalThrust( float amt );
//Clamps desired velocity to computer set limits
    Vector ClampVelocity( const Vector &velocity, const bool afterburn );
//Clamps desired angular velocity to computer set limits
    Vector ClampAngVel( const Vector &vel );
//Clamps desired torque to computer set limits of thrusters
    Vector ClampTorque( const Vector &torque );
//scales unit size torque to limits in that direction
    Vector MaxTorque( const Vector &torque );
//Applies a yaw of amt
    void YawTorque( float amt );
//Applies a pitch of amt
    void PitchTorque( float amt );
//Applies a roll of amt
    void RollTorque( float amt );
//executes a repair if the repair bot is up to it
    void Repair();
//Updates physics given unit space transformations and if this is the last physics frame in the current gfx frame
//Not needed here, so only in NetUnit and Unit classes
    void UpdatePhysics( const Transformation &trans,
                        const Matrix &transmat,
                        const Vector &CumulativeVelocity,
                        bool ResolveLast,
                        UnitCollection *uc,
                        Unit *superunit );
    virtual void UpdatePhysics2( const Transformation &trans,
                                 const Transformation &old_physical_state,
                                 const Vector &accel,
                                 float difficulty,
                                 const Matrix &transmat,
                                 const Vector &CumulativeVelocity,
                                 bool ResolveLast,
                                 UnitCollection *uc = NULL );
//Useful if you want to override subunit processing, but not self-processing (Asteroids, people?)
    virtual void UpdateSubunitPhysics( const Transformation &trans,
                                       const Matrix &transmat,
                                       const Vector &CumulativeVelocity,
                                       bool ResolveLast,
                                       UnitCollection *uc,
                                       Unit *superunit );
//A helper for those who override UpdateSubunitPhysics - Process one subunit (also, an easier way of overriding subunit processing uniformly)
    virtual void UpdateSubunitPhysics( Unit *subunit,
                                       const Transformation &trans,
                                       const Matrix &transmat,
                                       const Vector &CumulativeVelocity,
                                       bool ResolveLast,
                                       UnitCollection *uc,
                                       Unit *superunit );
    void AddVelocity( float difficulty );
//Resolves forces of given unit on a physics frame
    virtual Vector ResolveForces( const Transformation&, const Matrix& );
//Returns the pqr oritnattion of the unit in world space
    void SetOrientation( QVector q, QVector r );
    void SetOrientation( Quaternion Q );
    void SetOrientation( QVector p, QVector q, QVector r );
    void GetOrientation( Vector &p, Vector &q, Vector &r ) const;
    Vector GetNetAcceleration();
//acceleration, retrieved from NetForce - not stable (partial during simulation), use GetAcceleration()
    Vector GetAcceleration() const
    {
        return SavedAccel;
    }
//acceleration, stable over the simulation
    float GetMaxAccelerationInDirectionOf( const Vector &ref, bool afterburn ) const;
//Transforms a orientation vector Up a coordinate level. Does not take position into account
    Vector UpCoordinateLevel( const Vector &v ) const;
//Transforms a orientation vector Down a coordinate level. Does not take position into account
    Vector DownCoordinateLevel( const Vector &v ) const;
//Transforms a orientation vector from world space to local space. Does not take position into account
    Vector ToLocalCoordinates( const Vector &v ) const;
//Transforms a orientation vector to world space. Does not take position into account
    Vector ToWorldCoordinates( const Vector &v ) const;
//Returns unit-space ang velocity
    const Vector& GetAngularVelocity() const
    {
        return AngularVelocity;
    }
//Return unit-space velocity
    const Vector& GetVelocity() const
    {
        return cumulative_velocity;
    }
    Vector GetWarpVelocity() const;
    void SetVelocity( const Vector& );
    void SetAngularVelocity( const Vector& );
    float GetMoment() const
    {
        return Momentofinertia+fuel;
    }
    float GetMass() const
    {
        return Mass+fuel;
    }
//returns the ammt of elasticity of collisions with this unit
    float GetElasticity();
//returns given limits (should not be necessary with clamping functions)
    const Limits& Limits() const
    {
        return limits;
    }
//Sets if forces should resolve on this unit or not
    void SetResolveForces( bool );
};

#endif
I think it could be broken down finer:
I think that thrusting concerns fall somewhere between physics, AI, user controls (fly by wire), and autopilot.
Sub-unit/parent concerns are a huge concern of physics, but they are also a huge concern of other parts of
the code. Perhaps Unit should embody a Composite pattern.
Collisions stuff...
This is a biggie: Thing is, collisions are really close to physics. I can't imagine a type of unit that would have
its physics simulated but NOT be part of the collision system, or viceversa. Secondly, the collisions scheduler
will be VERY different (algorithmically) from the physics scheduler... (long story) but it can share the parts
of the code related to using a 1024 bit array of flags IF our collision data structures use the same array
allocator as phys_unit; so I'm very tempted to upgrade phys_unit to phys_and_collision_unit.

Anyways, I only posted this here to encourage exchange of ideas on how to best do this surgery.
Neskiairti
Confed Special Operative
Confed Special Operative
Posts: 334
Joined: Thu Jan 11, 2007 4:10 am

Re: Unit refactoring: Physics extraction

Post by Neskiairti »

I'm not sure if this applies to what you are referring to, but.. just a small suggestion to save yourself some trouble, pre-define certain scalable definitions...

for instance, a ship in the shape of a cube, no matter how large the cube, is going to have a regular physics profile.
or a rectangle definition, triangle, pyramid, cylinder.. and so forth.
the goal of such a definition, take a ship, figure out what category it best fits in to, give it that keyword and some extra variables (scale mostly i think)

that way you wont have to describe the turning rates and so forth per ship, just feed it the size and the shape and you get a decent approximation.
chuck_starchaser
Elite
Elite
Posts: 8014
Joined: Fri Sep 05, 2003 4:03 am
Location: Montreal
Contact:

Re: Unit refactoring: Physics extraction

Post by chuck_starchaser »

No; I think you missed it; we're going to write an off-line program (maybe in python) that computes physics-related data
by analyzing mesh data, and updates units.csv. Basically, reading just the vertices from the bfxm or from an obj, then
assigning some mass to each vertex, and computing center of mass, center of inertia, and tensor of inertia. It could
also look at engine positions and determine some ad-hoc maneuverability numbers; like have some baseline numbers for
maneuverability; but if a ship has engines far apart in X, then give it more yaw. Better than some lesser hack that we're
not going to be happy with, after all the work involved.
safemode
Developer
Developer
Posts: 2150
Joined: Mon Apr 23, 2007 1:17 am
Location: Pennsylvania
Contact:

Re: Unit refactoring: Physics extraction

Post by safemode »

little edit: Let me preface the following with something i make a distinction with later on. Physics simulation != physics unit in my eyes. Physics simulation is analogous to what i later call a simulation frame and what we've been calling a physics frame. So the following 3 steps has to occur every simulation frame (as opposed to a drawing frame), but not all of the 3 steps is to be contained in a physics_unit object. I explain that at the end, but the beginning here is mostly in reference to scheduling.
end_edit

I dont see any reason why you would want to separate collision detection from physics simulation. You can't ever have one without the other happening immediately after.

1. You need to create a transform (the physics part). (this is done by calling ai routine or user input and getting the new vector state (this would also be where anything not draw related gets done))
2. You need to check if this transform causes you to collide with anything else (the collision detection part)
3. You need to adjust your transform if you do collide and call the necessary damage functions (the physics part again)

Then you move on to something else.

That's 1 physics frame. That's how you have to have it or you risk missing collisions or shit not happening in the correct order, leading to crazy things happening.

You never want to move on to another unit while your unit is not in a sane state. The above is what is required to always exit in a sane state. If you skip or decide to interrupt between any of those steps, then you either dont know if you're in a sane state or you knowingly could be leaving your unit in a non-sane state. And by non-sane, i mean, my ship is halfway inside your ship, your turn. Type stuff. you can't have that, which means you need to do the above steps each physics frame un-interrupted.

So yea, your physics unit is going to get big, but in reality, it should be polymorphic or such since what a ship needs to do to figure out it's transform is different drastically from what an asteroid, planet or base has to do for example. the most complex would be a ship, since it's ai can alter it's transforms and that requires interacting with lots of stuff. Simplest would be the roid and planet, since their transforms are strictly determined by initial state and collisions. Bases would be in that simplest boat too if they didn't also have ai that involves self defense and damage response and such. :)

But what about threading and parallelization you say? You can achieve this by making sure the parallelization only occurs between physics units that are some appreciable distance apart. So no two units being simulated at the exact same time could ever collide with eachother or the same units around them.

As far as the 1024bit array idea, the only suggestion i have is that whatever we end up making it, it should be tested to be robust at 10,000 units. ie, its gotta be something that can scale whether we are dealing with 1024 units or 10,000 without modifying the code. The general idea here is not that we intend on having 10,000 simultaneous simulated units, but that if we can function with that many in a particular class, then we will perform very well with whatever number we actually have.

Your choice for what units get scheduled should be based on proximity to the player and proximity to other units and unit type, ie, we are deciding what units get physics priority based on how likely to they are to collide with eachother and how likely they are to interact with the player. a player and it's target are special, as a target can respond to a lock and need to at a distance greater than say, ships may happen to be that are around the player), so a player's target gets to jump priority to respond realistically to such things. Otherwise basically we have shells starting at the player, and we order the units within a given shell in clusters with the closest units to eachother starting the list, and those furthest away from any other unit in that shell at the end. In this way, the most dynamic parts of the system occur at the beginning of each shell list (frequency), allowing the majority of anything interesting that will happen to get processed first, and such events are much more likely to result in modification of units within a shell, thus distrupting the order and so we respond much faster to such noticable changes this way.


Also, we should make a note to refer to our frames as simulation frames and drawing frames, to avoid confusion with what goes on in one and the other. Drawing frames dont modify anything. They are strictly read-only. Everything else that happens in the game is done in the simulation frame. What i'm saying is, dont confuse phsyics unit for a simulation_frame_unit. Make the phsyics unit not care if we're dealing with a ship, planet, asteroid or anything. All it needs to do is have a mesh, have a collider, have a beginning state (maybe vector of forces acting on us), create our transform, check for collisions, if necessary, modify the transform and write our ending state. Everything else is dealt with higher up, like if we collided, call the damage function, who we collided with, what to do i we didn't etc etc.
The physics unit should only care about force vectors, the mesh, the collider and resultant transform and collision state and whatever we need to refer higher code to what we collided with. What i think you mentioned above is mixing physics unit up with simulation frame work.
How the forces come to be is simulation frame work (high level), what they do is physics unit work (low level), and how we react to what they do is again, simulation frame work. And we repeat.
Ed Sweetman endorses this message.
chuck_starchaser
Elite
Elite
Posts: 8014
Joined: Fri Sep 05, 2003 4:03 am
Location: Montreal
Contact:

Re: Unit refactoring: Physics extraction

Post by chuck_starchaser »

safemode wrote:little edit: Let me preface the following with something i make a distinction with later on. Physics simulation != physics unit in my eyes. Physics simulation is analogous to what i later call a simulation frame and what we've been calling a physics frame. So the following 3 steps has to occur every simulation frame (as opposed to a drawing frame), but not all of the 3 steps is to be contained in a physics_unit object. I explain that at the end, but the beginning here is mostly in reference to scheduling.
end_edit
Nobody here was confusing physics unit with physics frame. Phyisics unit is a data structure. Physics frame is an event; a processing time.
I dont see any reason why you would want to separate collision detection from physics simulation. You can't ever have one without the other happening immediately after.
False. See below.
1. You need to create a transform (the physics part). (this is done by calling ai routine or user input and getting the new vector state (this would also be where anything not draw related gets done))
Let's say yes.
2. You need to check if this transform causes you to collide with anything else (the collision detection part)
3. You need to adjust your transform if you do collide and call the necessary damage functions (the physics part again)
Not yet.
Then you move on to something else.
Totally wrong. Just because this is the way it is done now it doesn't mean it's how it should be done. I've tried to explain to you the problem two or three times, already; and each time I get no feedback; then you repeat this sometime later. Remember me mentioning the problem of "aliasing" in simulation?
That's 1 physics frame. That's how you have to have it or you risk missing collisions or shit not happening in the correct order, leading to crazy things happening.
Just the opposite. You CAUSE crazy things to happen by computing collisions after simulation on a per-unit basis. And I know that explaining it yet again is going to be for nothing, but I'll try one last time:

Suppose you have two ships, A and B
A ................................. B
they are flying towards each other, on a head-on collision.
A >..............................< B
Their speed is 10 km/s.
The distance between them is 1 km.
Your physics simulation speed is 0.1 seconds per frame.
Follow me so far?
So they are going to collide the next frame, right?
Now, we are going through the whole list of ships computing physics immediately followed by collision, the way you like it; and
we pull ship A. Physics says that A travels 1 km to the right; and collision says it hits B.
So, the collision happened NOT at the center, but half a kilometer to the right: at B's location!
But what if ship B was ahead of ship A in the list of ships to process at this physics frame?
Well, in that case, before we even look at ship A, we process ship B, for which the physics says it will travel 1 km to the left,
and then collisions says it hits ship A, but again, NOT at the center, but at A's location.
This is called "ALIASING".
Aliasing causes the results of physics and collision to NOT be *order-independent*. That is, what happens depends on the order
in which the simulation objects are processed. This is a NO-NO-NO-NO-NO-NO. The right way to do simulation is to do the
physics for all units first; THEN do collisions for all.
Did you understand me this time? Did you read the above, first of all?

Now, the bad news is that our problem is a lot more complicated, due to having different units simulated at different speeds.
Some are being simulated 16 times per second; some as seldom as every 8 seconds. (This is with MY scheduler in progress; I've
no idea with the current SIMULATION_ATOM crap.) But so, even doing collisions after the physics doesn't help much, because
some units have had their physics updated very recently, while others haven't. And this is where interpolation comes in:
To compute correct collisions you have to interpolate the positions of all units to be tested, to put them on an even playing
field. I don't know what the engine does now; but I'm sure it is wrong, because everything is done wrong in it. It probably only
uses interpolation for graphics. We need interpolation for collisions; and this another wedge cleaving physics and collisions
apart.

But the final, and biggest, nail in the coffin of your beloved "collisions immediately following physics" philosophy is this:
Physics and collisions need separate scheduling.
Physics needs the kind of scheduling you talk about further down, namely that the closer units are to the player, the more
often they are simulated. Well, not exactly; it also depends on their agility: Capital ships don't need fast simulation of their
flying trajectories, as their acceleration rates are small. But anyhow, roughly as you describe it. The rate of simulation
can vary, but gradually and/or seldom.
Collisions need a different kind of scheduling altogether; collidable units need to be able to book specific times for testing.
Why? Because a ship 1,000,000 km away from any other ship "knows" that it won't be colliding with anything for at least a
few seconds. So, it says to the collisions scheduler "check back with me in 5 seconds". 5 seconds later, when the collisions
scheduler checks with it again, the nearest other ship is 100,000 km away, so it now says "check back with me in half a
second". Half a second later, when we check with it again, it sees it could collide very soon; so it might say "WARNING: check
back with me ASAP", which to the scheduler means 1/32ndth of a second.
So, a ship flying far from any other ship may need collisions testing a lot less often than physics simulation. Conversely, a
capital ship in the middle of a battle may need almost no physical simulation at all, but may need collision testing at the
fastest available rate.

So, the needs of physics and collision scheduling are as different as different can be.
You never want to move on to another unit while your unit is not in a sane state.
Yes I do.
The above is what is required to always exit in a sane state.
Nope. You're are drawing categorical lines on quantitative insanity. When you move ONE ship, it can already be in an insane state. Moving them all first is not categorically different. You have to deal with insanities no matter. The question is when; and dealing with insanities one ship at a time causes ALIASING (read about it above, if you haven't).
If you skip or decide to interrupt between any of those steps, then you either dont know if you're in a sane state or you knowingly could be leaving your unit in a non-sane state.
Ditto. There is no categorical difference between moving all the ships first, then dealing with the insanities, and rushing to deal with insanities after every move; and the latter leads to ALIASING.
And by non-sane, i mean, my ship is halfway inside your ship, your turn. Type stuff.
You get this when you move one ship at a time, all the same. Show me proof that it is necessary to deal with each insanity right away.
you can't have that,
Yes, We Can. :D
which means you need to do the above steps each physics frame un-interrupted.
False.
So yea, your physics unit is going to get big, but in reality, it should be polymorphic or such since what a ship needs to do to figure out it's transform is different drastically from what an asteroid, planet or base has to do for example. the most complex would be a ship, since it's ai can alter it's transforms and that requires interacting with lots of stuff. Simplest would be the roid and planet, since their transforms are strictly determined by initial state and collisions. Bases would be in that simplest boat too if they didn't also have ai that involves self defense and damage response and such. :)
Well, this may or may not be true. Thing is, the new physics code that Errol has written for us, using Runge Kutta 4 (RK4) is extremely accurate. It could simulate planetary orbits for many years, if we wanted to. No; I'm not proposing any such thing; relax. What we ARE going to do is switch to full gravity simulation of planets, stations, etceteras, the moment you enter a system, and until you leave it. So, there's no longer a need to have polymorphic physics. At least not as far as planets are concerned. But where I'm not sure is with asteroids. Right now the crappy things move in circles for no reason. Like, what's attracting them to the center of rotation? They don't behave physically, or sanely, in any way. IMO, we should get rid of that crap. Having bunches of asteroids, I'm not sure it relates to anything, but I'm willing to put up with that unrealism; but them moving in circles (fast, even!!!) is just far too stupid and retarded. It's fine for them to spin around their individual axes; but NOT move in circles.
Heck, even Privateer was more realistic than vegastrike, in this respect. But yeah, the physics cannot simulate dynamics that are physically impossible, so, to have retarded things like that we'd, indeed, need polymorphic physics.
But what about threading and parallelization you say? You can achieve this by making sure the parallelization only occurs between physics units that are some appreciable distance apart. So no two units being simulated at the exact same time could ever collide with eachother or the same units around them.
No. This is further proof that you NEVER read anything I write. NEVER. We discussed this so many times I've lost count. You are AGAIN proposing to parallelize by running Same Code/Different Data. That is the STUPIDEST way to parallelize. You want threads to be running different parts of the CODE, with the output of one thread going to the input of another.
As far as the 1024bit array idea, the only suggestion i have is that whatever we end up making it, it should be tested to be robust at 10,000 units. ie, its gotta be something that can scale whether we are dealing with 1024 units or 10,000 without modifying the code.
As I said, the number is not cast in stone; we can test with 10,000 units, if that's your fetish. What I did say should be cast in stone is the fact on picking a number and sticking to it, rather than make things dynamically resizable.
The general idea here is not that we intend on having 10,000 simultaneous simulated units, but that if we can function with that many in a particular class, then we will perform very well with whatever number we actually have.
Sounds like you're saying it should be dynamic; and if so I disagree. If this is for the sake of asteroids you're talking about, there's more intelligent ways to faking tens of thousands of them than just throwing them all in.
Your choice for what units get scheduled should be based on proximity to the player and proximity to other units and unit type, ie, we are deciding what units get physics priority based on how likely to they are to collide with eachother and how likely they are to interact with the player.
Ditto. For physics, priority is based on agility/distance. For collisions, priority is based on worst case prediction for when a collision may happen. Different animals, with different needs.
a player and it's target are special,
Agreed.
as a target can respond to a lock and need to at a distance greater than say, ships may happen to be that are around the player), so a player's target gets to jump priority to respond realistically to such things.
Yes, but not too much. The first dozen of ships nearest the player could get the fastest simulation AND collisions; not just the ship you're targeting.
Otherwise basically we have shells starting at the player, and we order the units within a given shell in clusters with the closest units to eachother starting the list, and those furthest away from any other unit in that shell at the end. In this way, the most dynamic parts of the system occur at the beginning of each shell list (frequency), allowing the majority of anything interesting that will happen to get processed first, and such events are much more likely to result in modification of units within a shell, thus distrupting the order and so we respond much faster to such noticable changes this way.
Sort of, but ditto.
Also, we should make a note to refer to our frames as simulation frames and drawing frames, to avoid confusion with what goes on in one and the other.
Physics frames, collisions frames, drawing frames and AI frames, all have very different scheduling needs.
Drawing frames dont modify anything. They are strictly read-only.
Yep
Everything else that happens in the game is done in the simulation frame.
Nope
What i'm saying is, dont confuse phsyics unit for a simulation_frame_unit.
Never confused these two; not sure where you got the idea.
Make the phsyics unit not care if we're dealing with a ship, planet, asteroid or anything.
Exactly.
All it needs to do is have a mesh, have a collider, have a beginning state (maybe vector of forces acting on us), create our transform, check for collisions, if necessary, modify the transform and write our ending state. Everything else is dealt with higher up, like if we collided, call the damage function, who we collided with, what to do i we didn't etc etc.
Yep
The physics unit should only care about force vectors, the mesh, the collider and resultant transform and collision state and whatever we need to refer higher code to what we collided with. What i think you mentioned above is mixing physics unit up with simulation frame work.
No; I think you're confusing physics with collisions and whatnot. There's pretty intimate ties between physics and collisions, and as I said, I reconsidered and decided to put their datas together in a "physics_and_collision_unit" but probably just "physics_unit" for short; but the frames can't be the same.
How the forces come to be is simulation frame work (high level), what they do is physics unit work (low level), and how we react to what they do is again, simulation frame work. And we repeat.
Yep
RedAdder
Bounty Hunter
Bounty Hunter
Posts: 149
Joined: Sat Jan 03, 2009 8:11 pm
Location: Germany, Munich
Contact:

Re: Unit refactoring: Physics extraction

Post by RedAdder »

Well I read that you mentioned doing interpolation in the collision code.
Isn't doing interpolation basically the same as having an "uncommited" physics frame?
Neskiairti
Confed Special Operative
Confed Special Operative
Posts: 334
Joined: Thu Jan 11, 2007 4:10 am

Re: Unit refactoring: Physics extraction

Post by Neskiairti »

:P oops..
thats what I get for posting while half asleep.
I was discussing this stuff with my partner a few months back, stress testing ship designs similar to how spore handled movement physics in their creature creator. its a very fun idea, but difficult to manage. With mutable meshes you can even manage to have fracture points in the ship design, so if it turns too fast, the ship cracks in half along its highest stress point along the turning vector.

btw, by uncommitted physics frame, I believe he means a physics frame simulated, but instead of sent to the rest of the program, checked over to see if anything has collided or whatever else it might be looking for, then updating it to a final one, and committing? Just my guess.
chuck_starchaser
Elite
Elite
Posts: 8014
Joined: Fri Sep 05, 2003 4:03 am
Location: Montreal
Contact:

Re: Unit refactoring: Physics extraction

Post by chuck_starchaser »

I see. Well, what's usually done in game physics is
  • first you compute the physics for all ships (or use interpolations if you have
    variable physics simulation rates)
  • second, you test for collisions (which can be tricky given the high speeds we have; we need to use spherically capped cylinders of length=velocity*frametime, to detect situations where ships have already gone past each other in a physics frame.
  • third, you spend some cpu time on objects that have collided, going back in time to the exact moment of collision, figure out force, damage, bounce, and correct the position and (bounce) velocity vector.
I don't know I would call this an "uncommitted" frame; more like Commit, then Undo/Edit.
klauss
Elite
Elite
Posts: 7243
Joined: Mon Apr 18, 2005 2:40 pm
Location: LS87, Buenos Aires, República Argentina

Re: Unit refactoring: Physics extraction

Post by klauss »

chuck_starchaser wrote:
That's 1 physics frame. That's how you have to have it or you risk missing collisions or shit not happening in the correct order, leading to crazy things happening.
Just the opposite. You CAUSE crazy things to happen by computing collisions after simulation on a per-unit basis. And I know that explaining it yet again is going to be for nothing, but I'll try one last time:
WOW... huge post.

Ok, I won't get too involved here, because I happen to agree with chuck, and I bet he'll argue more passionately than I could ever do ;)

When computing collisions, your description of the universe has to be self-consistent. Having a set of units simulated up to time T and the rest simulated up to time T+delta is the exact opposite, and it is what happens when you check for collisions right after updating a unit.

No, you have to update all units, then check all units for collisions in that time step, which means extruded capsule tests and finer interpolation in the case of potential hits in the ideal case, which is never the case of games, so simply testing in the final state should be enough, perhaps extrusion tests against significant items (planets, stars, things you can hit at high velocity and the player would notice).

So I agree in the overall design chuck is proposing, although I would suggest a few minor modifications which I have no time to explain, sadly - I just got back from a short leave at work and can't afford a huge post of my own.

But I will do ;)
Oíd mortales, el grito sagrado...
Call me "Menes, lord of Cats"
Wing Commander Universe
pheonixstorm
Elite
Elite
Posts: 1567
Joined: Tue Jan 26, 2010 2:03 am

Re: Unit refactoring: Physics extraction

Post by pheonixstorm »

klauss, did the physics ever get refactored or is it still being discussed?
Because of YOU Arbiter, MY kids? can't get enough gas. OR NIPPLE! How does that mkae you feeeel? ~ Halo
klauss
Elite
Elite
Posts: 7243
Joined: Mon Apr 18, 2005 2:40 pm
Location: LS87, Buenos Aires, República Argentina

Re: Unit refactoring: Physics extraction

Post by klauss »

It isn't still being discussed, but it wasn't refactored either.

There was some work done on the Runge-Kutta integrator IIRC, but last time I checked it wasn't tied into the physics engine, it was lying around waiting for testing and integration.

We had a quite workable design mostly laid out... if you have volunteers for their implementation, I could write a design doc (polishing the details as I document it).
Oíd mortales, el grito sagrado...
Call me "Menes, lord of Cats"
Wing Commander Universe
pheonixstorm
Elite
Elite
Posts: 1567
Joined: Tue Jan 26, 2010 2:03 am

Re: Unit refactoring: Physics extraction

Post by pheonixstorm »

I have several people that wanted to help with the tools project but I don't know if they have the C++ experience for implementation.. I can always ask though. Write the design, but don't let it take away too much time from more vital interests.
Because of YOU Arbiter, MY kids? can't get enough gas. OR NIPPLE! How does that mkae you feeeel? ~ Halo
nido
Merchant
Merchant
Posts: 43
Joined: Tue Sep 03, 2013 2:35 pm

Re: Unit refactoring: Physics extraction

Post by nido »

Whilst I do not yet have any comment on the rest of this thread, I would like to take a moment to comment on this sidetrail for a second. This is completely unrelated to the topic at hand and just something I had to write my thoughts about. If there is a better place for these discussions please forgive my infraction and point me there.
parallelize by running Same Code/Different Data. That is the STUPIDEST way to parallelize.
I agree selecting 'random' memory blocks to be processed by the same code at the same time is a bad idea performance wise. This, however, is not because of the 'same code multiple data' part, but more the 'random' part.

If you take a look at x86 and arm architectures you'll notice that both of these have SIMD instructions; This means that you can execute a Single Instruction on, depending on the configuration, 2, 4 or 8 data points. This type of parallelism works on a single core.

If you also happen to have a few instructions you need to apply to the same data sequentially, you can obtain 2x-4x speedups for those vectorised functions. I also project that most of the arm/x86 processors you would think that run vegastrike would support these instructions.
You want threads to be running different parts of the CODE, with the output of one thread going to the input of another.
This kind of pipelining works very well if you have a system where you can program a set of processing units to work on the same local memory. If you are going to do this on a traditional multi-core system and happen to have data significantly smaller then the 1st level cache, you will find that you will spend a lot of time moving the data through the processor's different cores, as they all happen to have their own copy of said memory. In the end you will get cache misses when the next step in the process catches up with the previous one, or you'll need to keep the threads in sync and keep cores stalling until the new data arrives. Nothing bad, but not really optimal either.

Hyperthreading systems can mitigate this problem if you can allocate the threads on different logical cores on the same physical core. Nevertheless, such a pipeline works best on systems created for such workloads. GPU's perform reasonably well as stream processors in the sense that your suggested multithreading approach works well. The question is whether the roundtrip time to the gpu and back is worth the advantages. At this stage I cannot make an competent guess on this matter.

If you wish you do this, I suggest looking into OpenCL. It can utilise NVidia/AMhaD drivers to process the pipelines in an optimum environment. Mesa is also working at this in a project named clover, and free/open software implementations exist as well.
You want threads to be running different parts of the CODE
No argument with this part; but you would be wanting to run different parts of code which have as little interaction with eachother as possible. Playback of music and the rest of the simulation has so little in common that they could be ran on two different computers, in different rooms, with a dude copying the data they would like to exchange over from one computer to the other via a floppy disk. This is already implemented in the engine, but there may be other places where such a separation could work. Unfortunately I have no examples to point out in vegastrike at hand, and at first glance, unit seems to be a bad place to look for such separation of concerns at the moment.
Post Reply