Why wouldn't you just keep your entire world in one big coordinate system, and use that for all simulated entities? Why use this ship as a point of reference, when you can just express both the ship, and the things on it, in the world coordinate frame?

The coordinate system is global.

The reason for the hierarchical structure is message culling at a node level.

In this way, a mobile entity may actually contain its own effective hierarchy - say that the ship contains corridors and rooms within it. Neighbourhood relations can constrain message traffic within that hierarchy.

Quote:

(snip) Events that cross the boundry would have to be converted from the local coordinate system to that of the parent (which the ship sits on) or PARENTS (when the ship crosses one or more boundries at that level of the hierarchy).

The global coordinate system fixes scale and orientation, not origin - this is always 'local to parent' - ie. the parents 'real' position is 0,0 for the children.

The AP is correct, assuming that a mobile built using a mobile POR is designed for constraining messages inside itself - otherwise Hplus is correct and less work is involved in having multiple mobile 'limpets' (a term I use for occupants of a POR) being moved together - most likely through the use of a 'congregation' mobile. Mobile POR's are not designed for things like rafts, where the contents are visible, but physically tied. They are designed for discrete hierarchies which roam within a larger hierarchy - like cruise ships.

Quote:

Yet another fun case is having objects on 2 ships interact with each other. The topic author is working on formalizing the way the events are passed between different referents (including where the other 'referent entity' exists on another machine).

This is actually trivial and is best examined by a 'bad case' scenario, where a fairly large amount of traffic may be generated across a machine division. I'll avoid going into too much detail about synching the various steps of the process and the worker threads that deal with inter-server communication, since its all fairly simple.

Assume we have three physical POR's, Land, Bay and Ocean, forming part of the divisive POR, Coastline, which is part of GameWorld.

Land is hosted on ServerA.
Bay is hosted on ServerA.
Ocean is hosted on ServerB.
ServerA is the Master Server for this cluster, and also hosts Coastline.

Land neighbours Bay, Bay neighbours Ocean.

Bay contains mobile POR ShipA, partially in Ocean.
Ocean contains mobile POR ShipB, partially in Bay.
ShipA has two occupants, PCA and PCB.
ShipB has a single occupant, PCC.

For the sake of argument, Land will be out of range of 'shout' events from both ships.

As mentioned, a relevance update occurs in 3 stages, the logical update, the handling update and finally the client update.

Step 1 - Logical update:
ServerA syncs ServerB.

PCA (on ShipA) shouts "Ahoy there!", for the sake of argument.
This generates a 'PCA shouts "Ahoy there!"' message.
The PC, being a limpet, deposits its message directly to its owner, ShipA.

ShipA being mobile, forwards the message to its parent, Bay. The current location of ShipA and the origin of the message give the location of the event relative to Bay. Mobile PORs cannot be responsible for message distribution, since their extents may cover varying portions of the fixed hierarchy.

Bay is now responsible for dealing with forwarding the message to all PORs that are in range of the event. Our shout message expands outside the area occupied by Bay, and so must be passed to the parent, Coastline for handling.

Coastline recieves the message and calculates the event origin relative to itself. In this case the message and its radius of effect lie entirely within the division governed by Coastline. The message is queued for handling. GameWorld need not be informed of the event.

ServerA being Master, checks that no slaves have pending events this cycle before continuing.

Step 2 - Message handling:
ServerA syncs ServerB.

On ServerA:

Coastline checks its child nodes' extents, Land, Bay and Ocean. Bay and Ocean are covered by the event, Land is not. Note that Coastline knows nothing about the contents of Ocean, since that is on a different machine, although contents can be queried for.

Since Bay is local, a handler function is called directly with a pointer to the message. Since Ocean is not local, a network message is created with a copy of the message data, is encrypted (if internal encryption is used on the cluster) and added to the server send queue. A worker thread despatches these immediately. This is efficient on dual processor systems, but has no advantage over waiting till the end of this step on single processor systems.

Bay handles the message by passing it to all its contents' message handlers (since it is a shout). ShipA receives the message and behaves similarly, passing it to PCA and PCB.

Both PCA and PCB handle the message by adding it to their network send queues.

On ServerB, simultaneously to the above:

ServerB gathers update messages from machineA using a worker thread, and processes them immediately, in addition to handling any events generated and handlable internally (in this case none this cycle).

The shout message is received and passed to the default slave root node, which contains Ocean. Ocean passes it to ShipB, which passes it to PCC, which places it in its send queue.

On ServerA:
ServerA informs its slaves there are no further events from it this cycle. This puts the worker thread on the slaves to sleep.

Step 3 - Client update:
ServerA syncs ServerB.

On ServerA and ServerB, simultaneously:
Send queues are processed cascade fashion. PCA and PCB receive messages from ServerA, PCC receives messages from ServerB.

The worse-case scenario where the shout is sent from ShipB works similarly, but the shout message actually crosse the server boundary TWICE, rather than once, since Coastline is remote as far as Ocean is concerned - the message is passed up across a network connection, rather than just down as in the example above.

Does this make sense? Maybe I should do a diagram?

[Edited by - _winterdyne_ on October 11, 2005 8:43:47 AM]

Quote:

The ship moves (translation and rotation) and you would have to constantly update the coordinates of all the objects on the 'mobile' as well as all the terrain geometry (like the decks, passageways etc...) for the objects on board to interact

When the ship lurches, you want the player to lurch, too, not just stay rock solid on the ship's deck. In fact, gravity doesn't change when the ship moves, but the ship changes. If you run an actual physical simulation, it would be simpler to simply change the ship, keeping everything in world coordinates, because the physical simulation will take care of everything. ("having to update all the objects" is not a problem -- because they are simulated, they are updated every frame anyway)

If you run a non-physical, old-game kind of simulation, perhaps using an old-school scene graph system, then isolated coordinate system islets would make sense. But hopefully nobody's actually building yet another one of those in this day and age!

Quote:

When the ship lurches, you want the player to lurch, too, not just stay rock solid on the ship's deck. In fact, gravity doesn't change when the ship moves, but the ship changes. If you run an actual physical simulation, it would be simpler to simply change the ship, keeping everything in world coordinates, because the physical simulation will take care of everything. ("having to update all the objects" is not a problem -- because they are simulated, they are updated every frame anyway)

I see what you're saying here, but this doesn't really affect the relevance graph, unless you consider falling from one POR to another. It does affect the physics layer for player position checking and may alter pathfinding hierarchies.

The effect you're describing could be achieved by using a matrix stack to concatenate transformations as the hierarchy is traversed, effectively giving each POR a transformation specific to its orientation and position.

Rather than simply having position, a POR has a matrix (or quat/vector) to dictate where it is. In most cases there won't be any rotation, just translation, since blocks are easier to work with in design terms.

The most complex objects, in terms of physics abstraction (collision hull), at any time on the server are likely to be static POR geometry sets. Other items are likely to be simple boxes, particles, spheres, cylinders, or self-righting cylinder entities such as creatures. I don't intend to implement rag-doll physics on the server, nor do I intend to model 'long footprint' entities (think a horse from above). All of these are transformed by the matrix stack.

In order to lurch (or indeed rotate relative to gravity), we do actually need to inverse-transform the inherited gravity vector which will dirty the physical abstractions for the POR. New accelerations can be calculated for them and they can then update as normal. Route paths for certain movement types will have to be recalculated based on the altered gravity vector (a floor may become a wall) so angular tolerances for paths on the route finding node map must be checked.
Since self-righters will have to self-right, a player associated with the simulation entity can receive a 'I have self righted by [optional quaternion]' message to make their avatar 'stagger', in full on Star Trek styley. The quaternion can be used to determine direction of stagger. Immediately following may be an 'I am falling' message.

Any POR can specify a new gravity vector - although this is intended for spaceships with no global gravity vector - allowing us to model artificial gravity environments but NOT centripetal force environments.

Quote:

Also are there any additional complexities for an event that dont just have a simple origin and spherical effect (shout) but have more directional interactions (ie- an arrow fired) that may need to do a collision check/ LOS (line of site) and/or non-instantaneous (a traveling arrow) that itself moves over time and ack! may have secondary effects (like being visible/viewed by other obects as it moves...).

For a typical MMOG, I'd probably not model items such as arrow shots as explicit entities. An arrow shot would be calculated to either miss or hit, and the visible representation of it would be handled on the client. A standard spherical event would be used to notify of the shot, or the entry of the shot to a POR.

The mobile POR is designed to segregate a chunk of hierarchy - ideally within itself. Typically, the mobile POR would be 'teleported' into, rather than entered through a neighbour relation. It's not really designed for its contents to be interacted with.

Assuming you have a ship, with a deck, and belowdecks section, with several PORs. The deck, and entry to belowdecks (potentially visible) I'd model as a standard mobile limpet, with a complex collision hull. Mobiles on deck are linked to the limpet, characters below decks are not, they are tied to a mobile POR, since they are 'separated' from the world at large.
Linking the mobile POR to the limpet for the ship as well gives us a single point of control; Rotating the limpet (according to the normal of the bit of sea its on) rotates the mobile POR (but not its physical abstractions which are separate, but do get a modified gravity vector etc. as described).
Anything linked to the limpet inherits its transformation when updated, so any physical abstractions may get dirtied.

This allows the ship itself to be interacted with, as well as people on decks, as standard occupants of the fixed POR the ship is in, whilst keeping local interactions below decks separate from the world at large (keeping network updates down).

Quote:

Unfortunately you will have to decide where you want the 'realism' to stop (in order to make a game that doesnt require a supercomputer to run in real time). Sure you could have the player lurch about (and check all the friction effects that keep objects in place most of the time) but what of the entire structure of the ship/boat. Do you want to have to calculate all those structures effects by every force upon them to calculate all the transformations for positions (culling methods would help this some). Its probably more cost effective to apply the various 'lurch' forces to the player and other 'moveables' within a local coordinate system to minimize the CPU load.

OK, I respectfully disagree. My daytime job includes a distributed simulation system that simulates all physical entities in global space, and it works very well. We've solved all the problems the OP talks about (although differently from his suggestion), and we've been operating since 2001. The servers, and clients, are regular x86 PC hardware, not supercomputers.

Bear in mind that I'm aiming for very small clusters with this library - it's intended use is for low-budget / indie projects, so a large cluster performing complex simulation of a large number of entities is out of the window.

Instead, since there may be large numbers of small items lying around, simplified physics have to be used serverside(particles for objects). Performing true physics on such items seems like a lot of work for a tiny cluster, which is preoccupied with game event handling.

We don't have all of the data public, but yes, it's a continuous world that scales up by the amount of hardware you plug into the cluster; the actual mapping from world to hardware is heterogenous (not just same-sized squares). We step everything at 30 Hz (client and server), and the number of messages per object is "whatever interactions actually happen" (it's not really a limitation in the system). The limits to scalability are mainly related to how dense you want the congregations of simulated objects to be, and how complex they are, as well as what the CPU memory speed is.

You can check out the web site at http://www.forterrainc.com/ and you can also try the older version of the platform via the free trial download of http://www.there.com/ . Other things we do include simulation of an entire round planet, the size of Earth; a very believable model of human emotions; a fully working virtual economy driven by player-created content; and integrated voice chat that routes through the server (all interactions are server authenticated). There.com runs on pretty old server hardware; it has some "city plaza" type locations with hundreds of avatars and more hundreds of other simulated objects (user-customizable buildings, trees, etc).

And, yes, some players have taped down the "forward" button and driven vehicles around the entire world. It takes them about three weeks ;-)

Nice product!

Somewhat larger scale than I'm aiming, but similar goals.

I'm interested in what happens with large, active congregations in your system.
I assume your quadtree is stored on a centralised for the operating grid so node relations can be queried centrally, and I assume you're tracking stats for each node on that server as well. I assume that each node knows where the master server is (probably its own machine in the grid). I also assume that you can isolate a quadtree node that's causing lag, and I assume each process is aware of at least a portion of the quadtree to allow direct inter-process communication (given that you've mentioned a smart switch for the grid).

When a particular node in your quadtree is known to be causing lag, what do you do with it? You've mentioned that each node has its own process - are you moving processes to machines with less lag using beowulf as you mentioned earlier? Are you subdividing the node (similarly to the mechanism I have planned) and distributing the subnodes? As you mentioned, this doesn't cause problems with non-seamless worlds, but your reference to continuous implies its seamless, so taking a process out of the loop whilst shifting it in its entirity is going to cause synchronisation issues, made worse by the amount of active content in the node.

Hehe, here comes the 'I could tell you, but I'd have to kill you' post. ;-)