unit confusion

[safemode]

Having realized that i'm gonna need a book to learn python to any usable extent, and i have a lot more to learn how to utilize GL well enough to contribute, i've re-focused back to unit_generic. the Unit class has bothered me from the moment i read it.

we have templated GameUnit's of a given type. This class inherits the type it's templated to. The type inherits the base Unit class. Then we have separate classes of specific types that inherit the templated GameUnit class.

So to just go over that again, say for the Planet type.

we have GamePlanet -> GameUnit<Planet> -> Planet -> Unit

That is repeated for the 6 other types we currently use.
And yes, we also have a Unit type that doesn't have a "GameUnit" class like GamePlanet, but we do operate on
GameUnit<Unit> -> Unit

So, Unit is obviously a base class in this layout. Unit however, when you read it, is obviously a superclass. It contains code relating to every type of specific unit, rather than only code that is shared by all the units. There are obvious sections of code that belongs in specific types of units like planets or missiles etc.

So here is my first plan of attack.
First,
I want to move functionality that is specific to planets to the Planet class. Anything that is calling on those functions/data members, would obviously have the knowledge that they're dealing with a planet, so any typecasting required shouldn't be an issue.

I'll do the same for the other 6 types for which there are already Unit type classes for.

Second,
I want to create a "ship" unit type and move data members and functions related to ships to it.
Leaving Unit with only that functionality that is shared by all the different types of units.

Hopefully this is just basic physics, drawing and other generic functions. Unit thus would not have headers and code needed for missiles, planets, AI, computer etc. These would all be included in the higher level Type classes.


My goal with this is to not only organize Unit in a more logical manner as it's currently intended to be used, but to decrease the overhead of Unit creation. Also, by organizing Unit we can decrease the complexity of any source files that need to access Unit but not any of the type specific aspects of it, like in the use of lists and physics transforms and such.

[pyramid]

Sounds like a clean way to go ahead. As you have described, it would make specific changes to unit types much more flexible. I very much welcome the idea.

[GoldenGnu]

yerh.. definitively sound like a better way to store the data...
Super classes should only have functions that are specific to all child classes... I think anyway.... But, I'm no real programmer

[ace123]

As to python, it's actually pretty easy to learn, after you understand the way indenting works and the fact that all variables are untyped.

By having a superclass, planets will not have a few of the fields, however the vast majority of units that are created will have and need every element of the Unit class.
A lot of code might rely on certain fields existing in every unit.

Probably not something to do before 5.0, but it might be possible to create a branch.

Perhaps it would be more worthwhile making large subsystems of each unit into a pointer to another class, which can be NULL if it is not needed.
That way you avoid having yet another class that can be instantiated, and the hassle of building more factory functions, etc. and moving certain code over to the old class.

I'm just not sure how much we will gain with a superclass to "Ship".

[safemode]

all the code that deals with just missiles, doesn't nead a majority of what's in Unit, same for asteroids, planets, nebula's, enhancement's, and whatever building refers to. Also, things that just deal with units on a basic level, where it doesn't matter what kind of unit it is.

We can thus avoid having to include every header in the project each time we want to deal with Unit. We can decrease the size and time it takes to instantiate Unit and probably decrease the complexity of Unit in case people want to actually add a type down the road.

By splitting ship from unit, we can make Unit an actual base class, for use in those generic functions and code that dont care what kind of Unit, a Unit* is.

Making certain classes a pointer inside unit is another idea I had that i was thinking about utilizing after this splitting and refactoring. certain methods could be created to indicate whether a unit should have AI initiated, etc. I figured that less effective than refactoring however, since it's more of a corner case to not need all aspects of a "ship" when you are dealing with a ship, since there is only one unit that isn't PC controlled, etc.

[chuck_starchaser]

You got a good grip on it, safemode.
Another thing to check for with inheritance, is to make sure the destructors of inheritable classes are virtual. I once found cases of concrete inheritance without virtual destructors, in the vs code, which could lead to slicing or leaks if classes are being used polymorphically; --I think I mentioned it, but just in case... Ideally, there should be no concrete inheritance, and those virtual destructors would be pure. And inheritable classes should have explicit constructors, and assignment operator overloads from convertible classes, if any; --and have them anyways, just with an assert(0), for prohibited conversions.
EDIT:
Or, better yet, make them private.

I once saw code by AMD that used SIMD instructions to make a highly accelerated version of memcpy. It used MMX instructions, which by now every machine has. Not sure how much copying is going on, but this would accelerate a lot of copying that compilers generate that aren't always obvious from looking at the source code... (like temporaries).

[tuna]

and the fact that all variables are untyped.

All variables in python are typed. Specifically, they are strongly and dynamically typed.

It's not just semantics, there is a huge difference to untyped languages like old c. There are plenty of oldtimers around who still are afraid of dynamically typed languages because they still carry their battle wounds from c and people erroneosly call dynamic typing weak typing or "untyped".

Typing in python is actually more strict than it is in c/c++; there is no casting.

[ace123]

I believe we use virtual destructors everywhere... GCC usually (maybe not always) makes a big error message if you forget to make the destructor virtual, however it will not catch it if the class itself is not virtual, so that's a tradeoff.

I cleaned up the contents of unit_generic.h, taking out all the function names so as to see how it divides up.

There are some things that could possibly be taken out... but nothing strikes me as entirely obvious. I would go for big things like structures.

I think that if we have a heirarchy, it should be something like:
Unit as the base class
then, on the next layer:
Ship Planet Nebula Asteroid

Then Missile inherits from ship... so the only difference here being splitting up Unit and Ship.

For graphical classes (GameUnit), I don't see how the heirarchy will change... Having more than two levels will make it more complicated...
GameMissile -> GameShip<GameUnit<Missile> > -> GameUnit<Missile> -> Missile -> Ship -> Unit

The other issue is that *most* of the units will fall in the "Ship" category... Sure, there will be a few planets floating around, and a few asteroid fields which might have many subunits, I am under the impression that the majority of units will still be standard ships... am I missing something big?


So here's my stripped down unit_generic.h

Code: Select all

		// How many lists are referencing us
		int ucref;
		StringPool::Reference csvRow;
		UnitSounds * sound;
		StringPool::Reference name;
		StringPool::Reference filename;

		/**** NETWORKING STUFF ****/
		bool networked;
		ObjSerial serial;
		Vector net_accel;
		ClientState old_state;
		unsigned short damages;

		/**** UPGRADE/CUSTOMIZE STUFF ****/
		UnitCollection SubUnits;
		std::vector <Mount> mounts;
		float gunspeed;
		float gunrange;
		float missilerange;
		class graphic_options
		{
			public:
				unsigned SubUnit:1;
				unsigned RecurseIntoSubUnitsOnCollision:1;
				unsigned missilelock:1;
				unsigned FaceCamera:1;
				unsigned Animating:1;
				unsigned InWarp:1;
				unsigned WarpRamping:1;
				unsigned unused1:1;
				unsigned NoDamageParticles:1;
				unsigned specInterdictionOnline:1;
				unsigned char NumAnimationPoints;
				float WarpFieldStrength;
				float RampCounter;
				float MinWarpMultiplier;
				float MaxWarpMultiplier;
				graphic_options();
		} graphicOptions;

		/**** GFX/PLANET STUFF ****/
		std::vector <Mesh *> meshdata;
		unsigned char attack_preference;
		unsigned char unit_role;
		Nebula * nebula;
		StarSystem * activeStarSystem;

		/**** NAVIGATION STUFF ****/
		class Computer
		{
			public:
				class RADARLIM
				{
					public:
						float maxrange;
						float maxcone;
						float lockcone;
						float trackingcone;
						float mintargetsize;
						char iff;
						bool locked;
						bool canlock;
				} radar;
				// The nav point the unit may be heading for
				Vector NavPoint;
				// The target that the unit has in computer
				UnitContainer target;
				// Any target that may be attacking and has set this threat
				UnitContainer threat;
				// Unit that it should match velocity with (not speed) if null, matches velocity with universe frame (star)
				UnitContainer velocity_ref;
				// The threat level that was calculated from attacking unit's threat
				float threatlevel;
				float set_speed;
				float max_combat_speed;
				float max_combat_ab_speed;
				float max_speed () const;
				float max_ab_speed() const;
				float max_yaw_left;
				float max_yaw_right;
				float max_pitch_down;
				float max_pitch_up;
				float max_roll_left;
				float max_roll_right;
				unsigned char slide_start;
				unsigned char slide_end;
				bool itts;
				bool combat_mode;
		} computer;
		struct UnitJump
		{
			float warpDriveRating;
			float energy;		 //short fix
			float insysenergy;	 //short fix
			signed char drive;
			unsigned char delay;
			unsigned char damage;
			// negative means fuel
		} jump;
		Pilot *pilot;
		bool selected;

		/**** XML STUFF ****/
		XML *xml;

		/**** PHYSICS STUFF ****/
		void *owner;
		unsigned int sim_atom_multiplier;
		unsigned int predicted_priority;
		Transformation prev_physical_state;
		Transformation curr_physical_state;
		unsigned int cur_sim_queue_slot;
		unsigned int last_processed_sqs;
		bool do_subunit_scheduling;
		enum schedulepriorityenum { scheduleDefault, scheduleAField, scheduleRoid }
		schedule_priority;
		Matrix cumulative_transformation_matrix;
		Transformation cumulative_transformation;
		Vector cumulative_velocity;
		Vector NetForce;
		Vector NetLocalForce;
		Vector NetTorque;
		Vector NetLocalTorque;
		Vector AngularVelocity;
		Vector Velocity;
		UnitImages *image;
		float specInterdiction;
		float Mass;
		float HeatSink;
		float shieldtight;
		float fuel;
		float afterburnenergy;	 //short fix
		int afterburntype;		 // 0--energy, 1--fuel
		float Momentofinertia;
		Vector SavedAccel;

		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;
		// -1 is not available... ranges between 0 32767 for "how invisible" unit currently is (32768... -32768) being visible)
		int cloaking;
		int cloakmin;
		float radial_size;
		bool killed;
		enum INVIS {DEFAULTVIS=0x0,INVISGLOW=0x1,INVISUNIT=0x2,INVISCAMERA=0x4};
		unsigned char invisible; //1 means turn off glow, 2 means turn off ship
		Vector corner_min, corner_max;
		bool resolveforces;

		/**** WEAPONS/SHIELD STUFF ****/
		Armor armor;
		Shield shield;
		float hull;
		float energy;
		float maxhull;
		float recharge;
		float maxenergy;
		float maxwarpenergy;
		float warpenergy;

		/**** TARGETTING STUFF ****/
		// not used yet
		StringPool::Reference target_fgid[3];

		/**** AI STUFF ****/
		Order *aistate;

		/**** COLLISION STUFF ****/
		CollideMap::iterator location[2];
		struct collideTrees * colTrees;

		/**** DOCKING STUFF ****/
		unsigned char docked;
		const std::vector <struct DockingPorts>

		/**** FACTION/FLIGHTGROUP STUFF ****/
		Flightgroup *flightgroup;
		int flightgroup_subnumber;
		int faction;

		/**** MISC STUFF ****/
		unsigned char tractorability_flags;
		std::string fullname;

[chuck_starchaser]

I believe we use virtual destructors everywhere...

Ahh, glad to hear!

I think that if we have a heirarchy, it should be something like:
Unit as the base class
then, on the next layer:
Ship Planet Nebula Asteroid

Then Missile inherits from ship... so the only difference here being splitting up Unit and Ship.

My first thought would be to have a layer of attribute, mix-in abstract classes,

like

• physical
• visible
• collidable
• landable
• tractorable
• self_propelled
• plays_music
• ...etceteras...

So, for example, class physical would have mass and moment of inertia.
Class collidable would have collision detection interfaces.
Class self-propelled would have acceleration and turning rate stuff.

And then use multiple inheritance to create mixes of attributes that represent the various concrete unit types (in addition to unit, of course).

So, a jump point, for instance, would inherit unit, visible and collidable; but not physical, landable, tractorable or self-propelled.

The advantage of this 2-layer system is that it allows code re-use, as each attribute class may be used in a number of concrete classes; while avoiding putting everything in one class and have to have "if(this->is_tractorable()){ yada yada; }"-type conditional blocks all over the place.

[ace123]

I was worried you were aiming towards multiple inheritance.

I would love to do something like this. And maybe it would work fine. But my impression of such a change is that it would require rewriting or modifying much over half of the code.

The only major gain that I can see is the example you just specified, the Jump point. Maybe this would stop the Nebula from being so quirky too. Many more open-ended engines might want to take such a route...


Now, assuming we could actually separate out these properties enough to have entirely independent classes to represent them, we might be fine.

I am completely sure that these classes will have to be interconnected to some level. Which means that we probably will need a common virtual base class. And I have heard that doing this is not all that healthy for performance.

Consider the visible, collidable and physical classes. All three of those need access to the mesh, and those could be narrowed down to a single mesh with two booleans.
Then take landable. That itself could be narrowed down to a list of docking port locations. tractorable is part of a physical property... it should be based on Mass and whether it's a physical object, and nobody's going to be able to tractor a planet of 10^24 kg.

Still, assuming we do all that, now we need "Game" or Client-side versions of all these objects to handle graphical stuff. Okay, maybe we can now avoid that on some of the subclasses.

Anyway, I hate to be the absolute pessimist and get your hopes down on this, but I think starting from scratch might be easier, and I honestly don't see a rewrite from scratch going anywhere (just look at how far the OGRE port has gone in the past few years). That's why I'm defending the existing, albeit hacked-up solution.

I am thinking that this is one of the things that has to be done at some point to keep the code from getting too messy, and there's no real harm in trying to do this.


One thing that did occur to me would be to split up current state with unit properties... but I don't think that will significantly help memory problems, since upgrades and non-real units usually have a singleton.

[chuck_starchaser]

Touche.

Maybe a less ambitious approach would be to make attribute classes that are included, as opposed to inherited. Virtual inheritance indeed slows down executables and causes problems. Having included attribute classes or structs would still help keep things in separate files... keep the code more compartmentalized; though it would force adding member attribute names to function calls.

Another solution, to avoid the need for virtual inheritance, might be to use multiple inheritance but NOT have a common unit base class, at all... Instead, have the various final concrete unit types be un-polymorph-able, (except via common attributes, --but this could stir up the buggy depths of compilers, by having shared base classes possibly inherited at different offsets..).

EDIT:
Or, another alternative: use some pseudo-inheritance:

Code: Select all

class unit
{
public:
  virtual ~unit() =0; //make abstract, to avoid vtables
  ...
  virtual void show(){};
  virtual void collide( t whatever ){};
  ...
};
...................................................................
class jump_point : public unit
{
   visible visible_;
   collidable collidable_;
   ...
public:
   ...
   void show(){ visible_.show(); }
   void collide( t whatever ){ collidable_.collide( whatever ); }
   ...
};

... i.e.: use inclusion, rather than inheritance, but bring the interfaces of the attribute components back to the surface, so it doesn't require use of attribute names.

One neat aspect of doing this is that concrete unit types could only "re-surface" those interfaces they need from the attribute classes they use, so jump point might resurface a boolean query function from collidable to test for being within a jump point, but NOT resurface bounce momentum functions; --i.e. avoid exposing unnecessary interfaces.

it should be based on Mass and whether it's a physical object, and nobody's going to be able to tractor a planet of 10^24 kg.

In the WC novel End Run, Jason Bondarevsky makes the Tarawa fly high speed (hydrogen scoops closed) sling shot around Kilrah, by "tractoring the planet"... ... though I still don't understand how tractor beams work...

[safemode]

Perhaps something along these lines for the most ambitious short of a rewrite from scratch.


You have "aspect" classes.

graphics
collidable
ai
physics
weapons
upgrades

These are included, not inherited.

Next we have the "type" classes.

missile, planets, asteroids, nebula, jump points, ships, cargo and the abstract base Unit type.

These types would all inherit the Unit class, which would only contain the base functionality common to all unit types. Basically, virtual functions taking the place of most of the functionality in the current unit_generic header. The virtual functions would be defined in the actual type classes, negating the need for including a ton of headers.

Certain base functionality would also be expanded to include the abilty to on the fly add and delete "ai" and "graphics" as needed. Most of the time though, these would be set at construction for the given type of unit we are creating and it's purpose. For instance cargo, cargo is a type of unit because it can exist outside of the ship in space. But we dont need to have ai, weapons, upgrades or code for any of the other types of units in it. We can construct it as type cargo and ignore all that other uneeded code.

Granted, the vast majority of units in the game are going to be ships, and ships contain most of the code in unit_generic but we're looking to clean up the bottom end, to make things cleaner and more organized and in effect, flexible, ships are a top end class, we dont have to worry that it includes everything.

So we have inclusion, and inheritance, avoiding multiple inheritance at all costs.

Next we have the templated game unit. Rather than make this class inherit the type unit, which is in my opinion, retarded, we work out the special cases for each type of Unit we'll be templating GameUnit to. So we would basically have a "*_generic.h/.cpp" file for each type of unit, consisting of it's inherited class definition, defining all the virtual functions of unit and adding all the type specific methods we need when dealing with that type of unit, then we have "game_*.cpp/.h" files that define the special case templated GameUnit class for that specific type.

By defining the api for each special case templated unit, we can negate the additional level of inheritance when dealing with GameUnit<UnitType> as if it was UnitType, allowing gcc to optimize out function calls and what not.

That may sound like a lot of redundent code, but really it's not. We'd have the generic GameUnit template exposing most of the api's ...which are not really unit type specific for the most part, and then we would have the special case GameUnit templates rewriting the functions that are different per unit. The idea is to compartmentalize GameUnit away from the Unit and UnitType classes, since templates require everything to be compiled in at once. We dont want to pollute our dependencies.


The idea here isn't that we are aiming to just reduce the memory footprint or cpu footprint or code complexity, but rather how do we logically organize Unit such that it's maintainable, while maximizing all those other aspects. My goal is first and foremost, to want to make Unit maintainable. And i dont believe it is now. To make it maintainable, we have to compartmentalize it, in a logical way that tries to minimize duplicate functionality and reproduce a logical inheritance or inclusion of features from those compartments.


So while little will change as far as how much code needs to be included to compile a GameUnit, a lot should change as far as how much code needs to be included for base functionality in the game and all the generic features that dont care what type of Unit Unit* is.

The GameUnit api should change very little, if at all, because we're hardcoding the necessary "inherited" methods into the templated class. This should make these vast and major rewrites to unit_generic, of little consequence to python code.

[safemode]

and btw, tractoring a planet requires a huge amount of suspension of belief. Lets assume a tractor beam operates on some way of quantumly attaching your ship to some object. Be it via gravity, or some entanglement or whatever. We can all agree, that the beam must contact the mass you are going to attach to. We also agree, that the masses of your ship and the object, are directly related to the power of the tractor effect. Of course, in addition to the power of the tractor beam.

So mister jason is artificially increasing the gravity well of Kilrah with his tractor beam so he can slingshot at a faster velocity than he would be able to with kilrah's normal gravity. The problem is, he's gotta tractor beam something that's about 500,000 meters away even in low orbit. Thats' 10 times farther than most "powerful" weapons in the game.

Even pretending this is star trek land where mass doesn't matter, because the tractor beam warps space-time in front of the target towards the emitter, even star trek had to resort to all kinds of crazy deflector dish modifications to move a moon, let alone an entire planet.


I would have found it more believable to slingshot as kilrah's moon was opposite of the slingshot arc, allowing the moon's gravity to have a tidal effect increasing the gravity felt at the slingshot arc, allowing Jason to pull around at super-speeds.

[chuck_starchaser]

I agree that was totally retarded In fact, just think of the amount of force that tractor beam has to exercise. How big is it, and how and where is it attached to the carrier? Insane.
My point was that if you tractor something bigger than your ship, your ship will accelerate towards it. And unless you can "feel" the acceleration of your ship, visually you cannot distinguish betwen the object accelerating towards your ship, or your ship accelerating towards the object.

IOW, I disagree about the solution of only allowing tractoring of things that are smaller than your ship.
What I would do, though, is,
a) making tractor beams very weak.
b) approach acceleration = f * { 1/m1 + 1/m2 } I think...
c) disable loading (into the hold) of stuff that wouldn't fit.


Good stuff about the unit organization.

One type of thing that definitely belongs in the abstract base class, and private, is any pointers to other units, physics atom counters and indexes, and any intrinsic container stuff, like pointers to previous or next... --Stuff needed to handle and organize units, but which are not proper "parts" of unit. And such items should also be mutable, so that they can change without affecting the constancy of unit-const functions.
For instance, if displaying a unit causes the unit to be moved to a recently used queue that necessitates changing some intrinsic fields in unit, this should not be reason enough to turn,
void display() const
into
void display()
Come to think of it, position, velocity and acceleration are not parts of unit, --rather external attributes or relationships--, and so perhaps should be mutable as well. Not sure; just brainstorming...

[safemode]

what you see and what happens in the game, would be two very important different things. While it may look like you are moving towards a common midpoint with your tractoring object, the game would be very wrong to actually do that if the other object is huge.

I'd suggest that tractor beams only operate on unshielded items. They operate only on a limted distance. (far too short to reach the surface of a planet or moon from any orbit). They operate in the star-trek manner, in that it doesn't cause your ship to proportionally be drawn to the object you are tractoring, but the force of the tractor beam is dependent on the distance and mass of the object (but not on your mass).

anyway

Unit is obviously victim to a lack of enforcement of any sort of api. As is other parts of the game too. Often it seems that the methods used to access a data member is just circumvented and the access is made directly to the data member. This happens a lot outside with unitcollection. There is a function to get the unit list, then the list is made public so a lot of code simply accesses the list directly. Making sure data members are not accessed directly, especially by reference/pointer is paramount towards any work directed towards threading. and there is plenty reason to work towards threading more of the engine.

[chuck_starchaser]

what you see and what happens in the game, would be two very important different things. While it may look like you are moving towards a common midpoint with your tractoring object, the game would be very wrong to actually do that if the other object is huge.

Wrong? The force on both objects is the same.
a = f / m so the acceleration of each towards the other is inversely proportional to its mass. Unless an object's mass is infinite, there will be some motion. Instead of making arbitrary rules as to the sizes of objects, just divide the force by the mass and you get the exactly right acceleration and behavior.

I'd suggest that tractor beams only operate on unshielded items.

There'd be 2 or 3 posts per day from players questioning the rationale of shields being able to stop tractor beams. Bad enough to have magical technologies, to begin with; if you start making hard rules about how they interact, be prepared for heavy flak. A lot of people feel strongly about how magical technologies should work.

They operate only on a limted distance. (far too short to reach the surface of a planet or moon from any orbit).

I've never heard of any kind of lights, or radio waves, or forces that work for a certain distance and then stop there. Attenuation is usually quadratic with distance, but there's no hard range limit.

They operate in the star-trek manner, in that it doesn't cause your ship to proportionally be drawn to the object you are tractoring, but the force of the tractor beam is dependent on the distance and mass of the object (but not on your mass).

That's no more absurd than start-trek itself, I grant that much...

The best way to deal with tractor beams would be to get rid of them. Failing that, make them weaker.
But coming up with all kinds of arbitrary rules, discontinuous functions and symmetry violations to govern them --for no reason whatsoever-- is not an option, IMO.

In any case, are you talking about Vegastrike the engine (VSE), or Vegastrike the game (VSG)? The engine must be flexible.

anyway

Unit is obviously victim to a lack of enforcement of any sort of api. As is other parts of the game too. Often it seems that the methods used to access a data member is just circumvented and the access is made directly to the data member. This happens a lot outside with unitcollection. There is a function to get the unit list, then the list is made public so a lot of code simply accesses the list directly. Making sure data members are not accessed directly, especially by reference/pointer is paramount towards any work directed towards threading. and there is plenty reason to work towards threading more of the engine.

To plan for multithreading is the best plan of all, indeed; and for more than one reason.

[safemode]

in star trek the force on them is not the same. In non-star trek the force on them is not gravity, because you dont need an emitter to cause gravity, so whatever the emitter is doing, it's not gravity in a traditional sense.

While EM radiation doesn't just stop, it does have a range of effectiveness based on power. Since tractor beams dont exist, we can make it function by needing to resonate the target material and that would require a power level of at least N and if you are farther than X, you can't do that.

And yes, i'm talking about the game VS, this would all be tunable stuff.


but back to Unit....

[safemode]

thread-safing Unit wont be hard. Thread-safing UnitCollection wont be hard. Figuring out a way to have persistant threads that do something worthwhile in parallel would be hard. and beyond the scope of this thread and probably wont be even considered until way down the road.

But just to entertain the idea for a second. The easiest and most parallel thing to thread is AI. Like the player, the game can go on in parallel to the processing of "thought" and goals. AI processing could be done by a queue run on a thread and have no worry at all about if it gets done in the same frame. Plus, we can use the spare cpu power on that thread to do more complex AI, like economics amongst bases without effecting the graphics. But Unit would also have provisions for physics locks, graphics locks, and collision locks. Likely rwlocks. Basically the Unit class would have a static AI object, and the AI object on construction would create a thread that basically sleeps, traverses it's queue and sleeps again. Then during a physics frame when the ai would normally be processed, is processed by pushing a pointer to the queue in the AI class. There would be no further need to syncronize beyond that point.

[chuck_starchaser]

Actually, thread-safing any class is hard. To have objects accessible from 2 or more threads involves making sure that all public methods are atomic. The reason being that, while private functions are not required to leave the state of a class self-consistent (satisfying class invariants), public functions are. But in a multi-threaded system, non-const public functions could be called from one thread before another (or the same) public function being called on the same object from another thread has had a chance to complete, and so the new function call starts executing while the object may be in an inconsistent state.

You'd have to put a mutex into the object, and have all public function pass through the mutex. Needless to say, this would be madness.

Sharing objects, or any data for that matter, is NOT the way to go. The way to go in multithreading is to divide the program so that each thread has its own objects and object types it operates with; and have threads cooperate by exchanging short and sweet messages (by "sweet" meaning: NOT containing any pointers or references).

You need a class "abstract_message" that is queue-fiable, from which you derive the various message types. Message types don't have to be thread-safe, since inter-thread messaging takes care of that.

The idea of putting the AI on a separate thread is very good. Just don't mix AI and non-AI datas in a single unit class, though. Instead, you can have the AI thread use its own AI_unit class. When a unit is created or loaded from disk, have the constructor or factory method put the AI-related data into a "create_AI_unit" message, and send this message to the AI thread. It should include a unit ID, so that when the AI thread wants to send you a message about that unit, it can refer to it by the ID as the first field in the message. You can use the address of the unit as the ID, but only if the code guarantees that units are never moved.

Secondly, you don't want to create one thread for each AI unit. That's too many threads. There's a cost associated with each thread: The time it takes the kernel to switch between them. There should be just one AI thread that processes all the AI_unit's in its queue in round-robin fashion, or using some kind of time atom scheme, if desired.

There's also a question that needs to be asked: Is multithreading targetting the multicore advantage?, or is it to hide latencies in single-core operation?
I would suggest that both possibilities should be considered, so that multithreading gives a net benefit in either type of hardware platform.
Having the AI on a separate thread would be an excellent way to split things for multicore advantages, but less than stellar if the AI thread is being kernelized.

For kernel threads, running on a single cpu core, the best performance gain is when both threads do a lot of file i/o. Then, whenever a thread arrives at a file operation that must wait for the resource, the kernel blocks it and executes the other thread.
AI wouldn't usually be waiting for resources, so it would rip less advantage on a single core.
If I may suggest, I think the best initial split would be to separate the graphics from the rest of the engine (physics, AI, etceteras). So, we'd have a front_thread (physics, ai, etc.), and a back_thread (graphics). There'd be three main message queues: unit creation messages, unit update messages, and unit destruction messages. Unit creation messages would say "create a llama at location x y z, having a vector such and so, faction, flightgroup, and give it permanent id number 123456". A unit update message would say "unit 123456 current position is x, y, z, vector changed to ... etceteras". Unit destruction messages would simply say "unit 123456 is goners; remove from your queue."

The back thread, upon pulling a unit creation message from the queue, goes and loads its mesh and textures and loads them into the videocard.

So, as you see, splitting the graphics would benefit from multithreading regardless of whether we're running on two cores or on a single core. By taking a big load of disk i/o out from the front thread's shoulders, the kernel would block threads on i/o waits, and therefore hide i/o latencies.

Then, a second split of these two threads (into four) could be a bit less concerned with single-core issues. But a second split could be done later, after the first split is done and running smoothly.

EDIT:
The other concern in multithreading is re-entrancy of functions. No static variables in functions that can be called from more than one thread. This rules out class member functions, as the class data IS static from the perspective of member functions. But if each thread uses its own types, then there's no risk of code sharing between threads, at least from VS code's side.

That leaves libraries: Any shared libraries must be thread-safe. But you'd use thread safe libraries anyways, if only because they are better maintained and less buggy...

[safemode]

i said static ai object in Unit. so only one will be made for no matter how many Unit's we create, and indeed, it would exist before any Unit's are made. So that is settled there.

Two, thread safing behind rwlocks is easy. Getting it down to the absolute minimum of what needs to be locked up isn't. I would lock everything at first and remove as needed, or reduce the code that is held by the locks as needed. Total locking would result in mostly serial processing, like we do now, so it would be of little benefit. rwlocks are cool, I've used them before in audio players i've helped develop.

like i said though, thread safing isn't the same as actually making the class usefull to thread. we can put locks everywhere we need to and still not have a situation where we can do 2 things at once to a unit. Many of the most intensive operations may be serial in nature, and we'll be stuck with that. AI was one that is obviously not.

The AI class would create a thread in it's constructor, and have a static data member that is a queue. Then a rwlock'ed member function that adds and writes data back to the Unit, via passing data needed to do so. THe main unit would lock around reading AI info, and the AI class would lock around writing that data. But both could execute without any additional care while the AI was being processed or the AI class was reading ai data.


I'm not looking to create a microkernel for VS. I dont want to think of the program in terms of multiple servers that use IPC to do any sort of sharing. While that may make races an impossibility, it is an ENTIRE rewrite.

using nothing more than rwlocks, we can separate AI out from Unit, run it on it's own thread and hand any locking races easily, with no upstream changes in code needed. Unless there are hacks put in place to alter a unit's AI code directly outside of normal Unit visisible functions. (someone has access to AI data members directly outside of Unit class). anything shared across the thread would have to be accessed only within the Unit class, since it would have to be locked. This should be the behavior for properly coded classes anyway so that should be fixed if it's not like that anyway as per this thread's (forum thread) purpose.

We can do this all within the AI class which is within Unit class.

Edit:
We get around having to worry about making multiple AI threads by calling the Unit method that does this in the game, which is not threaded, once. We dont have to code the class like we're making a library, we just need to make sure we know which parts are exposed to threads and which aren't. The part that would be is the AI class. The reading /writing of various variables dealing with the rest of the unit by the AI class will have to be looked at, but for the most part there is little if any chance of having a race in that respect. So long as we hold all thread locks during destruction.

Eventually, we'd make sure that any missions and other computer comm to the ai controlled units would be done via the AI queue, making sure nobody changes unit data at the same time as the AI, confusing it or negating it. But changing int's floats is atomic, so the worst that can happen for the majority of what the AI would be altering outside of it's class in Unit, would be that the value the ai changed or read is now different. Next physics frame, it would react to the new value, accordingly. Just like a human player that tells the ship to fire but at that moment the ship is damaged and cant, so now they have to do something else. There would be no need to lock against that type of data change from happening.

[safemode]

let me see if i can explain what i'm talking about better.


a static ai object, so it's shared amongst all unit's and is persistant no matter if a Unit is created. This object deals with methods and private data, not accessible to anything outside, except a function to create the thread and one function to add to the AI queue.

a function call outside of unit in the game initiates the AI thread via an AI class member function. This fuction calls a thread function that never dies and returns immediately. The thread function reads a queue and sleeps, executing ai routines that the queue tells it.

units and outside code can call a unit's AI queue method to add to the queue. A writable AI lock is set. They pass a data member relating to commands to the AI queue, a Unit pointer to the unit this is to affect, and a pointer to the AI_rwlock of that unit. then the AI_rwlock is unset and the function returns.

The AI queue would be processed and pop this AI request. The first thing that is done is an AI_rwlock is set as read. This keeps the unit from being destroyed while we are reading data members from it, because the unit destructor would also need to grab a writeable AI_rwlock.

I dont care about protecting the variables that the AI reads from the Unit pointer or writes to it so long as it's reading and writing ints,floats,chars. These are atomic operations, and wont impact anything to have the values changed between reading them in and writing a new value based on that. If the AI needs to alter anything in Unit that is not a basic data type, we'd have to hold an AI_rwlock and wrap that data member in a function, disallowing direct access.

It's really not as messy as you think. Not with AI, because we dont care if the data we read in remains the same all the way through to writing out data. We get to ignore most of what we'd otherwise need to lock up.

and the AI code is serial. So it doesn't have to be reentrant. The unit only pushes commands onto the queue, everything else ai related happens in serial on that AI thread. The reading and writing of data back to the unit would be atomic (unless something necessary isn't) and thus, we'd need no locks around them to read and write. And we wouldn't care about the synchonisity of the values we write relating to the source input.


Like i said before though, this cant happen until Unit is cleaned up. It would be a cluster F in it's current state to thread the AI.

[chuck_starchaser]

Okay, I misunderstood the "static within unit" bit.

I agree with the organization; just not with the implementational detail of using locks --of any kind. It's a lot cheaper to send a message and grab a message back, than it is to acquire a lock. I took a look at the rwlock, and it's a wonderful idea; but even so, a lock is a weapon of last resort. Think about all that has to happen for lock acquisition: The fact that rwlock is first come first serve, implies that there's a queue implementation within rwlock. So you got code for keeping a queue of requests, pushing and pulling stuff. At the input end of the queue, there ought to be some kind of lock as well, to make sure that two requests aren't pushed into the queue simultaneously. Plus, I don't see where the windows port for rwlock is, though maybe I missed it. And yes, int and float are atomic operations in most machines, but doubles... it depends on the hardware and/or your alignment...

But anyhow, I once read an article in Game Developer about multithreading for games. The author spent most of the articles discussing architectural ways of avoiding using locks. He ended the article, paraphrasing, "With proper design and good separation of tasks, there's no reason your multithreaded code should need even a single lock or mutex." And to prove the point he had a simple but multithreaded game engine and game, working, that totally avoided locks.

There's no question about the correctness of using locks. But I've a huge question about performance issues.

Think of it this way: If the two threads are running on the same processor, single core, switching between the two threads not only takes kernel time, but it also causes most of the data and code in L1 and L2 caches to be useless, and so for the first while, the new thread keeps getting cache misses. So you want to organize the threads in a way that maximizes the time each thread runs; and using multithreading to keep the cpu busy when natural blocks are encountered, such as having to wait for disk i/o. Putting locks is like creating excuses for threads to block and trashing the cache. Having the threads encounter locks is like having speed-bumps all over a formula 1 racetrack. Speed-bumps in the pit are okay; but don't throw them on the race-track. If the two threads are running on two cores in an Intel Core Duo, you get the same cache concurrency issue, because in Intel parts, the cores share the cache. In an AMD dual core part you'd be relieved of the cache issue, but if the lock is there to access shared data it means that either one core or the other, but not both, owns that data, and the other has to use the internal HT channel to get at it. And if it's a multiprocessor platform, the problem is even worse.

The best way of organizing threads is to have NO shared data, whatsoever, anywhere at all. Giving each thread its own copy of the data is preferable to sharing any.

Throwing locks at every problem is maybe good enough a solution for a web-browser, but a game engine needs a high performance solution; not just any solution.

[safemode]

btw, i was just thinking. locking on pushing and popping the message queue is not needed. We can just check size() to be != 0 and if so, pop it otherwise sleep. Since we only have one thread pushing to the queue, we dont have to worry about double pushing and we dont have to worry about popping halfway through a push, since the size would only be updated after the data in the push is in the queue.

The only thing we'd need to do is hold a read rwlock when we are reading and writing unit data related to changing AI requests (steering the ship in a new direction etc). So that we dont destroy the unit while reading or writing and segfault. This would only cause a lock to occur in the game thread during unit destruction, and the lock would be almost instant, as it would only be held long enough to write some ints or doubles.


How much of a performance hit the locking would cause is all dependent on how often we encounter situations where the locks are asked to be held by both threads at the same time. The overhead of actually processing the locks is so insignificant in VS that we'd have to have squeezed every ounce of performance out of the rest of the game for the locks to even begin to matter.

The only functions in the game executing enough times for micro-optimizations to matter are the collision routines, UnitCollection routines (advance()) and coming in third would be certain drawing routines.


This method i'm describing is 99% of what you're talking about, only it is simpler and doesn't require expensive copying of data during runtime nor does it require expensive schedulers to check message queues back and forth. It shares a minimal amount of data that only blocks on destruction, an event that doesn't occur often.

[chuck_starchaser]

What I described is orders of magnitude simpler and less expensive.
The same argument you make for not requiring a thread safe queue for the rwlocks applies to the simpler mechanism of thread A sending a message to thread B. When a unit's state is updated that affects the AI for it, you send an update message to the AI thread. What can be simpler? What you are suggesting implies that the AI may visit the unit 77 times even when there's been no relevant updates.

Even if you never had the locks have to lock a thread out, the overhead of passing through the lock is way more than insignificant. Just try it in the debugger. With a single threaded program, put a lock on a char, then step through the assembly to access the char.

Glad you mention the problem of collisions. The AI and collision detection need to communicate. Here's another opportunity of just having collision events send messages to the AI thread, instead of sharing data and having to have locks.

[safemode]

the AI thread doesn't need to send a message to the main game process. The main game process doesn't have to wait for the AI thread for anything.

and no what i'm suggesting is not that the unit would be revisited 77 times without updating. If you read back what i'm describing is basically a message queue from the game process to the AI thread. I'm just not doing the communication back. The unit is only processed as it requests. When there are no requests, the ai thread simply sleeps.

My method is basically a half message queue system. The AI doesn't need to communicate back to the Unit in any way.

And what would the collision system have to do with the AI system? I dont see how they are connected at all. The collision system effects all kinds of Unit variables, but it shouldn't cause anything to be written to something AI related. The AI system merely looks at the same variables in Unit that the collision system affects, and makes decisions based on those and the commands sent to it by the Unit based on faction personality and mission/goals. The AI system needs no knowledge about the mechanisms that set the variables it looks at. The AI subsystem controls everything a player would control, but that's one way communication, and doesn't require any locking as only 1 thing can tell a ship to do what the AI would tell it to do, and that's the AI.

I think of the AI as a player that controls each unit serially as requested by the main game's physics frame scheduler. It's 1 player, that gets passed a command, and a unit to recieve all necessary information to control that unit and do the command. For any given time, there is only 1 unit's ai being processed. What happens on the game thread side is non-ai processing. The game thread communicates what is needed to be processed by sending a "message" to the AI thread each physics frame of the unit being processed. The AI thread then does _whatever_ it needs to do without having to worry about any races, but it is the only thing that can do the things it will do, nothing else in the game should be able to do them. Nothing else should be able to tell the ship where to head, what to fire/when, what to make it's next target, what to do etc. In that way, the data is separated, but in functionality only. We never risk any races.

We dont have to use rwlock, that was just an example of a lock. Since we only have one ai thread working on a Unit at a time, we can make do with something simpler to make sure the destructor doesn't operate while we are working on the unit.

Perhaps by simply utilizing the Ref counter in the Unit class. Each time we send an AI command to the AI queue, we increment the ref counter, and everytime the AI queue completes a command, it decrements.

So if we utilize the ref counter, we dont need to hold locks anywhere in my setup. And my setup would basically be a 1 way message queue thread system that avoids copying everything except the few variables it reads from the unit class. You can share data and not have locks and not need two way messaging. You just have to make sure what you're doing that with doesn't have to be synchronized. And the AI doesn't.