May 23, 2000July 22, 1996

Dan Moen
 
 

Introduction

This document describes the proposed design for the next incarnation of the Virtual Universe (VU). VU is a library of reusable code which provides transparent and efficient distributed game object management for game programmers. Version 2.0 represents a redesign of the interface and implementation of much of the functionality. The forces which drive this significant departure from the earlier interface and design are many, but prime among these are emerging project requirements which are not easy to implement in the current code. The following list enumerates those requirements which will be addressed in this design:

• Support for a C++ interface. Ideally, this should be clean and easy to use.
• Support for ‘painless’ transfer of entity ownership to another machine on the net.
• Entity Ids which are constant over the lifetime of the entity, even after ownership transfer and/or game restore.
• Support for multiple threads accessing the VU database at the same time.
• Serialization and deserialization of VU entities for game save and restore.
• Simplification of the abstract VU data type (eliminate mover/static distinction).
• User defined entity sorting (on access).
• Reliable message interface, for entity push and pull transfer.

• Actual reliable messages (most likely point to point).
• Increase maximum message size from it's current 400 byte level.
• Low level modem support under Windows 95.

The basic design of VU is broken into three primary areas: Entity Database, Events, and Miscellaneous. The Entity Database will satisfy the functionality currently provided by CDB, Collision, Netcons, Dead Reckoning, and Smoothing components. Event management will provide a class interface but will otherwise be very similar to the current Event interface. Miscellaneous covers specialized techniques for fulfilling project requirements. Comms support for this effort will be relatively unchanged from its current incarnation. Native support for Windows 95 modem connectivity, reliable messaging and other low level comms extensions are not covered in this document.

Globals and Defines

Although small, this portion of the interface is central to its function. Components considered to be global appear in the files apitypes.h and vu.h. The elements contained therein include:

• Global #define's and typedef's (no class definitions)
• Global function declarations, and externs of functions needed by VU.

• VuEntity – the base class for all game entities managed by VU and distributed to other machines on the network.
• VuCollection – this is the repository for VuEntities. Custom collection approaches should inherit from this class. The VuCollection class itself has no method for accessing individual members.
• VuIterator – This is the interface used to extract some subset of the VuCollection from the entity database for iterative processing.
• VuFilter – Used to specify the conditions for inclusion in a subset returned by VuIterator. A provided subclass of this will be used to specify ordering.
• VuDriver – This is the base for classes which provide motion or modeling behavior to entities. It is also the base for smoothing, dead reckoning, and child (entity tracking) behavior, which will be included as modules in the VU interface.

At its simplest level, all that the event module of VU 1.x provides is a message queue and a well defined asynchronous interface to messages from remote machines. These characteristics and much of the code will remain intact. VU 2.0 will also provide a class based interface to events, a larger collection of pre-defined event types, and a simple method to add new event types. The base classes defined as a part of the Event Management component are listed below:

• VuEvent – the base class for all events.
• VuEventQueue – The repository for unprocessed events.

Miscellaneous

There also exist a few techniques required by VU 2.0 which do not neatly fall into any of the above categories:

• Non-event messaging (push and pull, etc.)
• Thread safety.
• Session startup (for multi-node play).
• Session shutdown.
• VuEntity ownership transfer algorithm.
• Support for entity fragmentation and aggregation.
• Standard Network Updates.

Globals and Defines

Certain functions and interfaces provided required by VU do not fit well into an object paradigm, and are truly global to the scope of the library. There are two header files supplied by VU, which can be overridden by the game developer if need be. Some types (such as float) are masked within VU by #defined values (SM_SCALAR and BIG_SCALAR in the case of float). These can either be redefined in the case of simple types, or turned into a full fledged class. The latter approach should not be embarked upon lightly but would be perfect for substitution of a fixed point class for the floating point types. Note also that all header files in the VU library will be ‘wrapped’ with #ifndef-#define-#endif constructs.

Apitypes.h

#define BIG_SCALAR float

#define SM_SCALAR float

#define VU_DAMAGE unsigned long

#define VU_TIME unsigned long

#ifndef BYTE

#define BYTE unsigned char

#endif

Vu.h

void VuInit(VuEventQueue *queue, VU_TIME currentTime);

void VuCleanup(VuEventQueue *queue);

void VuUpdate(VuEventQueue *queue);

#ifdef VU_THREAD_SAFE

extern void VuEnterCriticalSection();

extern void VuExitCriticalSection();

#else // !VU_THREAD_SAFE

inline void VuEnterCriticalSection() {}

inline void VuExitCriticalSection() {}

#endif // VU_THREAD_SAFE

VuInit() should be called by each thread. VuUpdate() should be called at periodic intervals, and is where VU does internal housekeeping. Thread handling functions are discussed in the Miscellaneous section.

Entity Database

The Entity Database provides an interface to game data, organized into game objects. Game objects which are managed by VU are called VuEntities, named after the base class for all such objects managed by VU, the VuEntity class. The Entity Database provides functionality where possible, and interfaces where functionality cannot be easily or adequately provided by VU. In addition, the C++ inheritance and virtual function mechanism makes it relatively easy to override default VU implementation. Even so, virtual functions will be used as sparingly as possible so as to minimize the performance hit for common but trivial class data access.

The functionality and interface feature set provided by the Entity Database follows:

• VuEntity memory management (safe entity allocation and cleanup).
• VuEntity state propagation to all interested machines in a network environment. Several complex issues (such as smoothing, dead reckoning, entity transfer, and network node startup and shutdown) all are covered by this feature.
• Storage of the Entity Database to a file system, and retrieval from same.
• Iteration across subsets of the VuEntity database. Such subsets (and the sort order) are defined by specification of a VuFilter.
• Three space collision detection between managed entities.
• Time (CPU) efficient access to individual elements and collocated groups of elements.

Class diagram notation is relatively simple. Base classes are positioned at the top of the tree in ovals. Subclasses appear underneath, with arrows pointing to the immediate parent class. Classes supplied by VU are given in solid ovals, classes which must be supplied by the game developer are given in dashed ovals. Below is the VuEntity Class tree:

The base class for all entities managed by VU is the VuEntity. In addition, each ‘type’ of object in the game can have its own entity type, represented by an instance of a VuEntityType. Note that there is no intention to directly correlate a C++ class definition with a VuEntityType. The game developer is free to make such a construct, but VU does not require it. The two typing systems are completely independent.

A quick note about code conventions. In this document, all naming uses the descriptive intercap naming convention. Classes and structs, as well as class methods begin with a capital letter. Variables all begin with a lower case letter, and member variables always end with a trailing underscore. This is to avoid scoping awkwardness with method arguments.

VuEntityType Class

struct VuEntityType {

ushort id;

ushort collisionType;

SM_SCALAR collisionRadius;

uchar classInfo[CLASS_NUM_BYTES];

VU_TIME updateRate;

VU_TIME updateTolerance;

VU_DAMAGE damageSeed;

long hitpoints;

ushort majorRevisionNumber;

ushort minorRevisionNumber;

};

As mentioned above, the VuEntityType class is used to differentiate objects in the game by type. Differences in behavior as handled by VU are all given in this structure. For more involved type constructs, the game developer can derive from the VuEntityType structure. CollisionType identifies the collision radius detection used by the type, and a value of 0 indicates that the default VU method (simple 3 space radius collision) is used. The classInfo array is unchanged from VU 1.3. The value of CLASS_NUM_BYTES will be 8 by default. UpdateRate and updateTolerance specify the default time required between updates and the maximum amount of time that can pass between updates, respectively.

DamageSeed and hitpoints are used as default initial values for the damage_ and hitpoints_ elements of the VuEntity instances, respectively. The majorRevisionNumber and minorRevisionNumber are not transferred to the VuEntity class, but can optionally be saved with the entity in the serialize functions, and compared on restore. Default behavior will be to bail out of a restore where the majorRevisionNumber does not match the value stored for that class, and minorRevisionNumber will be ignored.

VuEntity Class

The VuEntity class is a pure virtual base class, meaning that only sub-classes of this class can be instantiated. This is the reason for the protected characteristic of the constructor. Also, any private data and methods are left off of this class definition as they are strictly not part of the interface.

class VuEntity {

friend VuReferenceEntity(VuEntity *ent);

friend VuDereferenceEntity(VuEntity *ent); // note: may free memory!

public:

// destructor

virtual ~VuEntity();

// setters

void SetPosition(BIG_SCALAR x, BIG_SCALAR y, BIG_SCALAR z);

void SetYPR(SM_SCALAR yaw, SM_SCALAR pitch, SM_SCALAR roll);

void SetDelta(SM_SCALAR xdelta, SM_SCALAR ydelta, SM_SCALAR zdelta);

void SetYPRDelta(SM_SCALAR yawdelta, SM_SCALAR pitchdelta, SM_SCALAR rolldelta);

virtual void InflictDamage(long points, VU_DAMAGE region = 0);

virtual void SetUserState(ushort newState);

// getters

BIG_SCALAR XPos();

BIG_SCALAR YPos();

BIG_SCALAR ZPos();

SM_SCALAR Yaw();

SM_SCALAR Pitch();

SM_SCALAR Roll();

SM_SCALAR XDelta();

SM_SCALAR YDelta();

SM_SCALAR ZDelta();

SM_SCALAR YawDelta();

SM_SCALAR PitchDelta();

SM_SCALAR RollDelta();

ushort VuState();

ushort UserState();

VuEntityType *EntityType();

VU_DAMAGE Damage();

int Health();

// entity driver

VU_TIME DriveEntity(VU_TIME currentTime);//returns time of next update

VuDriver *Driver() // returns Driver pointer

VuDriver *SetDriver(); // returns pointer to old Driver

void SetUpdateRate(VU_TIME updateRate);

VU_TIME UpdateRate();

VuDriver *EntityDriver();

int CollisionCheck(VuEntity *other); // uses built-in

virtual int CustomCollisionCheck(VuEntity *other); // user defined

virtual int TerrainCollisionCheck(); // default return FALSE

int LineCollisionCheck(VuEntity *origin, BIG_SCALAR range);

// virtual function interface

// serialization functions

virtual int Save(FILE *file);

virtual int Save(BYTE **stream);

virtual int MakeCreateData(char **buf);

virtual int MakeUpdate(char **buf);

virtual int MakePositionUpdate(char **buf);

// event handlers

virtual int HandlePositionUpdate(VuPositionEvent *event);

virtual int HandleStateUpdate(VuStateEvent *event);

virtual int HandleUnmanageEvent(VuUnmanageEvent *event);

virtual int MakeStateUpdate(char *buf);

protected:

// constructors

VuEntity(VuEntityType type);

VuEntity(FILE *file);

VuEntity(BYTE **stream);

// DATA

protected:

// shared data

ulong id_;

ulong ownerid_; // owning session

ushort entityType_; // id (table index)

BYTE ownerId_;

BYTE vuState_;

ushort userState_;

ushort refCount_;

BIG_SCALAR x_, y_, z_;

SM_SCALAR xdelta_, ydelta_, zdelta_;

SM_SCALAR yaw_, pitch_, roll_;

SM_SCALAR yawdelta_, pitchdelta_, rolldelta_;

VU_DAMAGE damage_;

int hitpoints_;

VU_TIME updateInterval_;

// local data

VU_TIME lastUpdateTime_;

VuDriver *driver_;

ulong changeFlag_;

};

The VuEntity base class should be fairly self-explanatory. Note that all data is protected, which means that access from anything other than subclasses will have to be through the accessor interface (set and get). In all likelihood, all of these accessors will be implemented as inline functions, which means that there will be no performance penalty associated with using the provided interface. This class provides a connection to the VuDriver hierarchy, which is used to move the entities through the VU space. The general philosophy is that shared and stored data lives in the VuEntity class construct, while modeling, unshared and unsaved data lives in the VuDriver class construct.

The damage and hitpoints fields represent a scalar and bitfield hit location scheme respectively. Default behavior will be for an object to generate a VuStateUpdateEvent (object destroyed) when either hitpoints falls below zero, or all bits in the VU_DAMAGE field are set. By default, VU_DAMAGE will be defined as a ulong, but it is quite possible for the game developer to redefine this as a class in its own regard, or some other built in data type.

VuEntity also provides the interface for event handling and generation, and file IO.

There are two friend functions in the interface which are used for reference counting, VuReferenceEntity and VuDereferenceEntity. These functions allow application code to lock an entity (prevent it’s destruction) until all references are cleaned up. Note, however, that because of the way that VU does its entity cleanup, any pointers to objects which are acquired on the stack need not be locked in order to guarantee that the handle remain valid. In addition, since VU guarantees that entities will not be destroyed until after all threads have handled the VuDeleteEvent for that object, any references which are cleaned up upon receipt of the VuDeleteEvent also does not need to acquire a lock.

VuSharedEntity Class

The VuSharedEntity class derives from VuEntity and is also an abstract class. Any object which is to be distributed to other machines on the network should inherit from VuSharedEntity.

class VuSharedEntity : public VuEntity {

public:

// destructor

virtual ~VuSharedEntity();

// virtual function interface

virtual Save(FILE *file);

virtual Save(BYTE **stream);

virtual MakeStateUpdate(char *buf);

virtual MakePositionUpdate(char *buf);

protected:

// constructors

VuSharedEntity(VuEntityType type);

VuSharedEntity(FILE *file);

VuSharedEntity(BYTE **stream);

// DATA

protected:

};
 

VuSessionEntity Class

The VuSessionEntity class inherits from VuSharedEntity and is a network (shared) representation of a single machine on the net. It’s update provides a heartbeat for other machines to watch in order to determine whether or not a session is still active. Strictly speaking, it does not really need all of the position information associated with other VuEntities, but since there is only one such entity per machine, the cost is minimal.

class VuSessionEntity : public VuSharedEntity {

public:

// constructors & destructor

VuSessionEntity(ulong manangementDomain, char *callsign);

VuSessionEntity(FILE *file);

VuSessionEntity(BYTE **stream);

virtual ~VuSessionEntity();

ushort SessionId();

ushort ManagementDomain();

char *Callsign();

// virtual function interface

virtual Save(FILE *file);

virtual Save(BYTE **stream);

virtual MakeStateUpdate(char *buf);

virtual MakePositionUpdate(char *buf);

protected:

VuSessionEntity(VuEntityType type, ulong manangementDomain, char *callsign);

// DATA

protected:

// shared data

ushort sessionId_;

ulong managementDomain_;

char *callsign_;

};

The managementDomain field is a bitfield which identifies which kinds of data this session is capable of managing. This is needed to support entity transfer between linked products which are running different versions of the software or different linked products (such as a flight and tank simulator). This proposal is probably inadequate to the task identified, and the harder problem would the assignment and management of entity domains. 32 available slots will certainly eventually fill up, using even the most frugal of methods, but it is possible that it will be satisfactory for the expected lifetime of compliant products. In any case, this is a complex issue which will not be resolved in this document.

VuLocalEntity Class

VuLocalEntity is an abstract class which represents entities which are never sent across the network, but which must be accessed the along with other VuEntities. Entities which meet these criteria should inherit from VuLocalEntity.

class VuLocalEntity : public VuEntity {

public:

// destructor

virtual ~VuLocalEntity();

// virtual function interface

virtual Save(FILE *file);

virtual Save(BYTE **stream);

virtual MakeStateUpdate(char *buf); // stubbed out here

virtual MakePositionUpdate(char *buf); // stubbed out here

protected:

// constructors

VuLocalEntity(VuEntityType type);

VuLocalEntity(FILE *file);

VuLocalEntity(BYTE **stream);

// DATA

protected:

};
 

VuVolumeEntity Class

VuVolumeEntity is an implementation class which maintains a subset of the entire VU database which resides in a volume anchored or projected from the location of each such entity. Exact shape and method of projection is not yet defined. It is expected that this function will provide object culling for rendering engines and such. For custom or more sophisticated filtering schemes, the game developer should create a subclass of the VuVolumeEntity class.

class VuVolumeEntity : public VuLocalEntity {

public:

// constructors & destructor

VuVolumeEntity();

VuVolumeEntity(FILE *file);

VuVolumeEntity(BYTE **stream);

virtual ~VuVolumeEntity();

virtual Save(FILE *file);

virtual Save(BYTE **stream);

protected:

VuVolumeEntity(VuEntityType type);

// DATA

protected:

// no data is shared

VuIterator iter_;

VuFilter *filter_;

};
 
 

VuDriver

The VuDriver hierarchy provides an abstract interface to the entity motion modeling system. Since this tree is completely separate from the VuEntity tree, it is also possible to very easily change the motion model for an object at run time. While it is unlikely that a missile will suddenly start behaving like a plane or a building, it is quite possible that a plane, missile, or mech will start getting its motion data from local modeling rather than network updates. In fact, this one requirement is one of the driving factors behind the need for an update to VU.

The VuDriver class is pure virtual abstract class which provides an interface to three types of motion models: master (modeled), slave (driven by network updates), and tracker (always moves relative to another object). For those familiar with VU 1.x, the tracker model would be used wherever the Child object was used before.

Below is the VuDriver class tree:

The VuDeadReckon class contains code for performing fast motion modeling. The VuMaster class contains dead-reckoning threshold data, as well as being the base for motion modeling classes. The VuSlave class embodies all smoothing behavior, and can even be used to drive playback data. The user classes which inherit directly from VuDriver would be those which do not perform any dead-reckoning or smoothing.
 

VuDriver Class

The VuDriver class is the base class for all object motion models. It is pure virtual, and so only subclasses can be instatiated.

class VuDriver {

public:

virtual ~VuDriver();

virtual void HandleStateChange(VuEvent *event) = 0;

virtual void Exec(VU_TIME *timestamp) = 0;

// Accessor

VuEntity *Entity();

protected:

VuDriver(VuEntity *entity);

// Data

protected:

VuEntity *entity_;

};

The VuDriver has a back-pointer to the owning VuEntity so that changes can be communicated and the appropriate fields in the VuEntity can be modified. It is expected that the VuDriver class will be responsible for updating the VuEntity position data, whenever the Exec or HandleStateChange methods are called.
 

VuDeadReckon Class

The VuDeadReckon Class contains data and code for performing dead reckoning motion modeling for objects. Since this mechanism is quite cheap, it can be performed every cycle. Master and Slave objects both perform dead reckoning, but Masters still drive actual data from the real model, and then use their version of the dead reckoning data to determine whether or not a position update message needs to be sent out.

class VuDeadReckon : public VuDriver {

public:

VuDeadReckon(VuEntity *entity);

virtual ~VuDeadReckon();

virtual void Exec(VU_TIME *timestamp);

// DATA

protected:

// dead reckoning

BIG_SCALAR drx_, dry_, drz_;

SM_SCALAR drxdelta_, drydelta_, drzdelta_;

SM_SCALAR dryaw_, drpitch_, drroll_;

SM_SCALAR dryawdelta_, drpitchdelta_, drrolldelta_;

VU_TIME lastUpdateTime_;

};
 

VuMaster Class

The VuMaster class is the base for all motion model classes, as well as providing dead reckoning threshold data. This allows the Master to detect when actual entity position deviates too much from the dead-reckoned values maintained by slaves on other nodes.

class VuMaster : public VuDeadReckon {

public:

VuMaster(VuEntity *entity);

virtual ~VuMaster();

virtual void Exec(VU_TIME *timestamp);

void SetPosTolerance(SM_SCALAR x, SM_SCALAR y, SM_SCALAR z);

void SetRotTolerance(SM_SCALAR yaw, SM_SCALAR pitch, SM_SCALAR roll);

// DATA

protected:

// dead reckoning tolerances

BIG_SCALAR xtol_, ytol_, ztol_;

SM_SCALAR yawtol_, pitchtol_, rolltol_;

};
 

VuSlave Class

The VuSlave is the class which handles updates from an external source, such as a remote machine or a data playback stream. In any case, this communication will be through the HandleStateChange interface. The Exec interface is used to make a "best guess" as to where the object should be based on position delta information maintained by the owning VuEntity, as well as dead reckoning and smoothing data maintained by the VuSlave class.

class VuSlave : public VuDeadReckon {

public:

VuSlave(VuEntity *entity);

virtual ~VuSlave();

virtual void Exec(VU_TIME *timestamp);

// DATA

protected:

// smoothing

BIG_SCALAR x_, y_, z_;

SM_SCALAR xdelta_, ydelta_, zdelta_;

SM_SCALAR yaw_, pitch_, roll_;

SM_SCALAR yawdelta_, pitchdelta_, rolldelta_;

char countdown; // ????

};
 

VuSlaveSmootherSettings Class

This is a global class. All VuSlave entities require access to a single global instance of this class which will contain smoother settings.

class VuSlaveSmootherSettings {

public:

VuSlaveSmootherSettings(SM_SCALAR x, SM_SCALAR y, SM_SCALAR z,

SM_SCALAR yaw, SM_SCALAR pitch, SM_SCALAR roll,

BIG_SCALAR maxJumpDist, SM_SCALAR maxJumpDist,

SM_SCALAR maxJumpAngle, VU_TIME lookaheadTime,

int countDown);

~VuSlaveSmootherSettings();

SM_SCALAR xtol_, ytol_, ztol_;

SM_SCALAR yawtol_, pitchtol_, rolltol_;

SM_SCALAR maxJumpDist_;

SM_SCALAR maxJumpAngle_;

VU_TIME lookaheadTime_;

int countDown_;

};
 
 

VuCollection

The VuCollection classes provide entity collection, filtering, sorting, and iteration. In addition, it uses a simple database locking and mark and sweep garbage collection mechanism to provide safe access for multiple threads. The class hierarchy itself is given below:

The VuOctTree and VuLinkedList classes are currently placeholders for actual implementations. In order to increase the execution efficiency of the collection mechanism (especially for access), it is likely that the actual implementation will be a flat tree without inheritance or virtual methods. It is expected that in actual use, the developer will know what the underlying list structure is, and so a virtual class interface will not provide much benefit. However, from a design standpoint, the logical relationship between VuCollection, VuLinkedList, and VuOctTree are exactly as shown. As this is an interface spec, and there will be no difference between the interfaces of all of the collection types, only the VuCollection spec is given in this document.
 

VuCollection Class

The VuCollection class contains code and data for managing collections of VuEntity object instances. The interface itself is rather minimal, especially since it does not include an interface for iterating across any subset of the collection. This interface is instead provided by the VuIterator class, covered later.

class VuCollection {

friend class VuIterator;

public:

VuCollection(int size);

~VuCollection();

int Insert(VuEntity *entity);

int Remove(VuEntity *entity);

int Remove(ulong entityId);

VuEntity *Find(ulong entityId);

int Purge();

int Count(); // returns element count – prob not efficient

// priveledged interface

protected:

VuNode *GetHead();

// DATA

protected:

// implementation (and members) to be defined

VuNode *root_;

...

};

The Insert, Remove, and Find interface methods each have the obvious functionality. The Purge method is used to explicitly perform a purge of entities which have been marked for deletion by calls to Remove, but not yet freed. Note that a linked list and oct-tree are not the only potential implementations. It is also quite conceivable that a red-black tree or some similar construct would be used as the primary database.

The size parameter in the constructor is intended to be a size hint, and not an absolute max or min.

Note that the Remove method simply marks the specified node for future deletion, and ensures that it will not be returned by iteration/queries of the collection. It will also automatically generate a VuDeleteEvent if said removal is from the main database. If the game developer holds onto pointers outside of the protection of an iterator read lock (see VuIterator below), then he should write an event handler for the delete event and NULL out the reference or take whatever other action is appropriate. The alternative to this is to acquire a lock on the object by using the VuReferenceEntity/VuDereferenceEntity interface. Note that the actual purge (physical delete call) will not take place until after this event has successfully fired and all references have been released. Note also that this scheme means that there is no need for reference counting on each individual VuEntity.
 

VuFilter Class

The VuFilter class is the mechanism the developer uses to specify the criteria for inclusion in a subset and/or the sequencing of the iteration (sorting). The VuFilter class itself is a pure virtual class. Although this means that invocation of the comparison Test method will therefore incur the overhead of a virtual function call, this offers a great degree of flexibility and is only slightly more expensive that a callback function interface, which is the generally accepted mechanism for accomplishing this generic inclusion/exclusion. Note that for extremely time critical iterations, other alternatives exist for improving performance, including custom iterator implementations with filter comparison criteria built in, and maintenance of cached collections.

class VuFilter {

public:

virtual ~VuFilter();

virtual BOOL Test(VuEntity *ent) = 0;

// TRUE --> ent in sub-set

// FALSE --> ent not in sub-set

virtual BOOL Compare(VuEntity *ent1, VuEntity *ent2) = 0;

// < 0 à ent1 < ent2

// == 0 à ent1 == ent2

// > 0 à ent1 > ent2

virtual VuFilter *Copy() = 0; // allocates and returns a copy

protected:

VuFilter();

// DATA

// implementation (and members) probably empty

// --> must be provided by sub-classes

};
 

VuIterator Class

The VuIterator class is the interface used to access some subset of a collection. Each iterator maintains its own node pointer, multiple threads (logical, not physical threads) of code can access the list at the same time. Note that since each instance of a VuIterator automatically acquires a read lock on the referenced collection, it is important that VuIterators be temporary rather than static. (The collection goes through a purge cycle when it has no locks on it, which can only happen if there are no active iterators accessing it). If the developer requires an iterator to be static, then the code in question should use the GetFirst and Cleanup methods, on first access and when each iteration is complete.

class VuIterator {

public:

VuIterator(VuCollection *coll, VuFilter *filter = 0);

~VuIterator();

VuEntity *GetFirst();

VuEntity *GetNext();

VuEntity *CurrEnt();

int DeleteCurrent();

int Cleanup();

protected:

VuCollection *collection_;

VuFilter *filter_;

VuNode *curr_;

...

};
 

Open issues:

• Purge must disallow read and write access. Physical threads may thus find their iteration blocked. Is this problematic? Note that deadlock is not possible in this scenario, but manual thread switching mechanisms might be defeated.

• We should enable VuFilters to be made resident. This will ensure that any index list created for this filter will remain resident, and will be updated by way of the event mechanism. Note that this will trade update cost for access cost. This would be implemented by specifying VuFilter sub-classes.

Although driving game events through an event management system makes some debugging problems much more complicated to trace, it does make it much easier to handle local and remote events in the same manner with a single block of code which does not need to distinguish between the two cases.

Without further ado, below find the VuEvent class diagram:
 

VuEventQueue Class

The VuEventQueue is responsible for posting and dispatching events. If a VuSession is active, then the events will be propogated to the network on event dispatch (rather than event post). This allows multiple events to be easily grouped together. Note, however that for multi-threaded games, each thread will need to maintain its own VuEventQueue. When multiple queues are active, all event writes will test the event for each queue, and post it to all interested queues. The event itself will be freed after all queues have processed the event.

class VuEventQueue {

public:

VuEventQueue(int queueSize, int bufSize, ulong eventMask, ushort maxEventType, BOOL ignoreRemote, BOOL ignoreLocal);

~VuEventQueue();

VuMessage *GetMessage(); // also invokes event handlers

int GetAllMessages(); // returns number of events processed

void PostMessage(VuMessage *message);

virtual BOOL TestEvent(VuEvent *event);

// TRUE à belongs in queue; default always returns true

// DATA

protected:

// implementation not yet defined

// --> will almost certainly be a queue of some sort.

};

Queue filtering will work by checking the event against the maxEventType (events with a higher ID are not placed in the queue), then for events with an id < 32, this id is shifted and checked against the eventMask as another compare. If the result is non-zero, then the interest flags (ignoreRemote and ignoreLocal) are compared against the origination of the event, discarding events originating from sources we want to ignore, and finally, the TestEvent() method is called. Any failure will result in the event not being posted to that queue (except for VuDelete events, which always need to be posted, but not necessarily serviced).

VuMessage Class

VuMessage is the abstract class for all events. It provides the abstract handle VU needs to be able to manage the queue. User messages which represent state updates on a VuEntity should inherit from VuEvent (or one of it&rsquo;s children), while all other user messages should inherit directly from VuMessage.

class VuMessage {

public:

VuMessage(int type);

virtual ~VuMessage();

int Invoke(); // invokes handler(s)

int Type();

// DATA

int type_;

};

VuErrorMessage Class

VuErrorMessage is a message class which represents a messaging error of some sort. The ErrorId indicates the actual error, many of which will be defined by VU itself, but other can be defined by the game developer. In most cases, it will be the responsibility of the game developer to take appropriate action based on the nature of the error.

class VuErrorMessage : public VuMessage {

public:

VuErrorMessage(int type, ulong errorType);

virtual ~VuErrorMessage();

ulong ErrorId();

protected:

ulong errorId_;

};

Some sample error messages:

• VU_ERR_NO_SUCH_ENTITY &ndash; session received a request for a non-existent entity.
• VU_ERR_CANNOT_TRANSFER_ENTITY &ndash; request to push or pull entity denied (may already have been promised to another session)
• VU_ERR_BAD_MESSAGE &ndash; session received an message which could not be parsed.

class VuRequest : public VuMessage {

public:

VuRequest(int type, ulong entityId,

BYTE sourceSession, BYTE targetSession);

virtual ~VuRequest();

ulong EntityId();

BYTE Source();

BYTE Target();

// DATA

protected:

ulong entityId_;

BYTE source_;

BYTE target_;

};

VuGetRequest Class

VuGetRequest is a message class which represents a request for create data (or at least full state) for the designated VuEntity. Note that an entityId of 0 is overloaded to mean get all from all.

class VuGetRequest : public VuRequest {

public:

VuGetRequest(int type, ulong entityId, BYTE source, BYTE target);

virtual ~VuGetRequest();

};

VuPushRequest Class

VuPushRequest is a message class which represents a request for the target session to assume management of the designated entity.

class VuPushRequest : public VuRequest {

public:

VuPullRequest(int type, ulong entityId, BYTE source, BYTE target);

virtual ~VuPullRequest();

ulong EntityId();

};
 

VuPullRequest Class

VuPullRequest is a message class which represents a request for the target session to relinquish management of the designated entity to the source session.

class VuPullRequest : public VuRequest {

public:

VuPullRequest(int type, ulong entityId, BYTE source, BYTE target);

virtual ~VuPullRequest();

ulong EntityId();

};
 

VuEvent Class

VuEvent is the abstract class for all events. It boasts entityId and type fields. The type field identifies the event class instance, so that users of the event can check against the type and cast as appropriate. In order to ensure proper typing, the type will be passed in automatically by subclasses. Semantically, a VuEvent represents a state change of some sort on an object. The only exception to this is a rebroadcast of an entity which has not had any change to its data as a keep-alive or as a response to an explicit VuGetRequest. VuEvent messages are almost sent via an unreliable broadcast mechanism.

class VuEvent : public VuMessage {

public:

VuEvent(int type, ulong entityId);

virtual ~VuEvent();

ulong EntityId();

// DATA

protected:

ulong entityId_;

};

VuCreateEvent Class

This event signals the birth of a new object.

class VuCreateEvent : public VuEvent {

public:

VuCreateEvent(ulong entityId);

virtual ~VuCreateEvent();

ulong ownerid_; // owning session

ushort entityClass_; // id (table index)

ushort state_;

BIG_SCALAR x_, y_, z_;

SM_SCALAR dx_, dy_, dz_;

SM_SCALAR yaw_, pitch_, roll_;

SM_SCALAR dyaw_, dpitch_, droll_;

VU_DAMAGE damage_;

int hitpoints_;

VU_TIME updateInterval_;

};
 

VuDeleteEvent Class

This event indicates that the identified entity has ceased to exist in the game universe. Any local copies of this object will disappear soon after this entity is dispatched.

class VuDeleteEvent : public VuEvent {

public:

VuDeleteEvent(ulong entityId);

virtual ~VuDeleteEvent();

// all needed data is in VuEvent

};
 

VuUnmanage Event

This event indicates that an object which is now managed by another entity will soon be deleted. In any case, the session issuing this message is indicating that the identified entity is longer of interest to that session, so another session, which has an interest in said entity, must request and assume control or the entity will be deleted at the specified time.

class VuUnmanageEvent : public VuEvent {

public:

VuUnmanageEvent(ulong entityId);

virtual ~VuUnmanageEvent();

VU_TIME timeOfDeath_;

};
 

VuStateUpdateEvent Class

This event is used to indicate a change in an object&rsquo;s state. Note: This info may be bundled with other events, such as collision, etc.

class VuStateUpdateEvent : public VuEvent {

public:

VuStateUpdateEvent(ulong entityId);

virtual ~VuStateUpdateEvent();

ushort state_;

BYTE ownerId_;

};
 

VuPositionUpdateEvent Class

This event communicates a change in an object&rsquo;s position. As this is probably the most common event over the network, it has its own trimmed down event.

class VuPositionUpdateEvent : public VuEvent {

public:

VuPositionUpdateEvent(ulong entityId);

virtual ~VuPositionUpdateEvent();

BIG_SCALAR x_, y_, z_;

SM_SCALAR dx_, dy_, dz_;

SM_SCALAR yaw_, pitch_, roll_;

SM_SCALAR dyaw_, dpitch_, droll_;

};
 

VuFullUpdateEvent Class

This event conceptually contains all of an entity&rsquo;s changeable data.

class VuFullUpdateEvent : public VuEvent {

public:

VuFullUpdateEvent(ulong entityId);

virtual ~VuFullUpdateEvent();

ulong ownerid_; // owning session

ushort entityClass_; // id (table index)

ushort state_;

BIG_SCALAR x_, y_, z_;

SM_SCALAR dx_, dy_, dz_;

SM_SCALAR yaw_, pitch_, roll_;

SM_SCALAR dyaw_, dpitch_, droll_;

VU_DAMAGE damage_;

int hitpoints_;

VU_TIME updateInterval_;

};
 

VuDamageUpdateEvent Class

This event is used to indicate when an entity has acquired damage through some means other than a collision.

class VuDamageUpdateEvent : public VuEvent {

public:

VuDamageUpdateEvent(ulong entityId, ulong shooterId,

VU_DAMAGE hitlocation, int hiteffect);

virtual ~VuDamageUpdateEvent();

ulong shooterId_;

VU_DAMAGE hitLocation_; // affects damage

int hitEffect_; // affects hitpoints/health

};

VuEntityCollisionEvent Class

This event is used to indicate when an entity has collided with another entity. As damage is often the result, hit location and hit effect data are bundled along with it.

class VuEntityCollisionEvent : public VuEvent {

public:

VuEntityCollisionEvent (ulong entityId, ulong otherId,

VU_DAMAGE hitLocation, int hitEffect);

virtual ~VuEntityCollisionEvent();

ulong otherId_;

VU_DAMAGE hitLocation_; // affects damage

int hitEffect_; // affects hitpoints/health

};
 

VuGroundCollisionEvent Class

This event indicates that the identified entity has collided with the ground.

class VuGroundCollisionEvent : public VuEvent {

public:

VuGroundCollisionEvent(ulong entityId);

virtual ~VuGroundCollisionEvent();

// do we want position info as well???

};
 

VuSessionEvent

This event indicates some change in the state of the identified session.

class VuSessionEvent : public VuEvent {

public:

VuSessionEvent(ulong entityId);

virtual ~VuSessionEvent();

// data to be defined

};
 

Open Issues:

• Fundamental design question: should there be one event for each kind of event, which then provides consistent access to the data underneath, or should there be a single kind of event (with different sub-types only when there is a fundamental size difference). The design as written is the latter, but I now suspect that the former makes more sense.

• It is expected that there will be some difference in the way that events are generated in single versus multi-player games. It seems silly to generate VuPositionUpdateEvents for a single player game, for example.

Non-Event Messaging

There are four supported messages of this sort:

• VuErrorMessage
• VuGetRequest
• VuPushRequest
• VuPullRequest

For applications which utilize multiple threads where more than one thread requires access to VU, the following rules must be followed:

• The library must be compiled with VU_THREAD_SAFE defined.
• The first registration with VU (VuInit() invocation) represents the primary event queue, and must be the last de-registration. This thread must also create the main VU database before any other calls to VUInit().
• The application must define the VuEnterCriticalSection() and VuExitCriticalSection() functions. This will enable VU to keep from stomping over itself between threads.

• Call VuInit() prior to any other VU calls.
• Call VuUpdate() at least once per loop after all VU iterations
• Call VuCleanup() when the thread is closed.

• get player callsign
• identify target network game
• negotiate a sessionId (similar to VU 1.x node id assignment)
• broadcast VuSession entity creation (should automatically generate resend of all net data)
• create (and broadcast) all locally managed objects

• what about game load (supporting distributed managment)?
• entity management load balancing?

• Entity announces shutdown, and issues unmanage events or push requsts on all locally managed entities.
• Session shuts down &ndash; it does not need to wait for responses to push requests.
• Entity management is transferred.

First and foremost, the id component of the VuEntity does not in any way determine which machine is responsible for managing that entity. However, to ensure that generated id&rsquo;s for are unique, the id will be assigned in a fashion very similar to the current mechanism. The 32 bit id value is broken down as follows (struct may or may not be literal, but shows bit positions and sizes):

struct idval {

uint transferable : 1; // 0 à not transferable

uint local : 1; // 1 à not public

uint unused : 1; // not used

uint managementDomain : 5; // range 0-31, indicated bit position

uint stationId : 8; // id of creating session

uint id; : 16; // assigned by VU at entity creation time

};

The flags field is still being defined, but if the high bit is used to specify whether or not the entity is transferable (for instance, VuSessionEntities are not transferable). Another bit indicates whether or not an entity is shared (local versus public). The distinction here is important, and the local bit is used to preserve name-space across sessions restored from disk, as there is no guarantee that a session will acquire the same id it had when the game data was last saved to disk. This ensures that the entire id (when taken as a ulong) will be unique whether generated at startup or restored from disk. As a result, we can now guarantee that entities will maintain the same id after being saved to and restored from disk.

What does determine which session is responsible for maintaining an entity is the sessionId field of the VuEntity. There are three circumstances when ownership of an entity must change hands:

• a session crashes or falls off the net
• a session requests ownership of an entity
• a session requests that another session assume ownership of an entity
• entity management load balancing

The two entity transfer requests (take and give) require some reliable messaging system which does not currently exist as a part of the low-level VU comms functionality. Note that reliable messaging has been identified as a requirement, but that effort is outside of the scope of this document. If reliable messaging is added, then entity transfer will be added to VU 2.0, time and resources permitting.

Entity management load balancing is a nifty feature which would be especially useful for situations where a large database is restored from disk, or games where players frequently enter and leave the game. This also requires reliable messaging, or some specialized startup mode which allows parceling out of entities before management of any begins.

Entity Fragmentation and Aggregation

This is a difficult problem, and after much discussion with Kevin, we decided it was best to leave the nitty-gritty details up to the game developer, providing enough hooks in VU to make it achievable without too many coding gymnastics. The following features should make aggregation and fragmentation possible:

• VuUnmanageEvent &ndash; A kind way of suggesting that an object will soon be aggregated, allowing another session to assume ownership of said entity.
• VuLocalEntity &ndash; Allows for entities which are not sent around the network. With a sophisticated accounting scheme for aggregates, fragmentation can be done entirely locally.
• Entity transfer. Aggregation is problematic without this feature.

Requirements Analysis

This section will examine each requirement in turn and discuss how the new design will accomplish it.

Support for C++ Interface

The design and implementation provides a class based C++ interface. While the requirement was meant to merely ensure that the VU library and its memory allocation scheme provided allowances for the rather unique &lsquo;new&rsquo; mechanism C++ uses in allocating its memory, a good class based interface makes the boundary between library and game code much more clearly defined and yet better integrated. This will presumably make it easier to understand and debug game code. Note that specialized memory allocation needs can now be performed by using the standard C++ set_new_handler() function.

&lsquo;Painless&rsquo; entity transfer across the net

This is accomplished using the mechanism described in the Miscellaneous section above.

Entity Ids which are immutable over the lifetime of an object

Since entity ids now represent the id of the creating entity (rather than the owning entity), this is trivial.

Support for multiple threads

Requests to delete an entity will unmanage it and mark it for deletion, but the node itself will not be removed until a delete lock can be acquired on the database. This happens only when there are no iterators active on the database, triggering a database purge. In order to prevent iteration while a purge is in place, read access will be blocked until the purge is complete (the alternative is to return a failure code, which would be a pain for developers to code around). Iteration which occurs while objects are in a pending delete state will always skip those entities marked for deletion. Inserts will be performed in a re-entrant fashion. Finally, purge will not delete an entity until after its delete event has fired, ensuring that dangling pointers can be cleaned up by game code before the actual memory is freed.

Game save and restore support

The serialize and deserialize methods provide a simple interface for sequencing all of the data required for successful storage of an entity&rsquo;s state, and reconstruction of the entity from a file. The abstract classes will save all of their data into the given stream. It is expected that subclasses will each call their parent class&rsquo;s serialize method prior to executing their own additions (similar to the way constructors work, except that calls to parent methods must be done explicitly).

Simplify abstract VU type

The VuEntity construct is now a single base class which contains all abstract data. In addition, the virtual function interface provides type-safe access to most of the needed subclass functionality. Some fairly recent innovations in component design by the research community (such as double dispatch) have proposed mechanisms for getting complete type safety for all component accesses, but these are needlessly indirect, complex, and inefficient. I&rsquo;ve used them and wouldn&rsquo;t recommend them to any of my friends (lucrative consultation contracts are another matter ;-).

User defined entity sort criteria

The VuFilter provides an interface to this functionality. Note, however, that this is a "wish-list" item which will be early on the list of features dropped or postponed if the project starts to slip.

Compatibility with VU 1.2 feature set

This item is mostly here as a placeholder for discussion in the document review. If there are some features of VU 1.2 of which the reader is aware, but which would be problematic to implement with this design, it would be better to know now and account for it. Known risk items include:

• Re-implementation of netcons functionality (big, complex body of code, which now works)

The development will proceed in phases. Each phase will list the accompanying work and the time required. Where possible, risk items and milestones will be identified. The high-level disclaimer is that good class design is usually an iterative process. Classes are often expanded or collapsed, and sometimes even central concepts mutate, based on implementation problems or feedback from users.

Phase I &ndash; VuEntity Core --- 3 weeks

This phase includes implementation of the following classes:

• Globals and Defines
• VuEntityClass
• VuEntity
• VuSharedEntity
• VuLocalEntity
• VuSessionEntity
• VuDriver
• NvuCollection (linked list version)
• NvuIterator

• project setup

• VuFilter
• VuSlave
• VuViewEntity

• VuEventQueue
• VuMessage and VuEvent
• event subclasses
• Collision detection

This phase includes implementation of the following features:

• Oct-tree VuCollection
• entity migration
• entity save/restore
• network save/restore

This phase involves maintenance of specified features, as well as documentation of the interface. This phase will probably actually be 8 weeks half time.