Quote:Original post by _winterdyne_

Quote:Original post by hplus0603
I could tell you how it all works, but first you'd have to sign a bunch of legal papers :-)

Isn't that always the way? :-)

Quote:
We run one server process per machine. Running multiple processes has no advantage, because the area served by our processes can be irregular in shape (and even discontiguous, although that's usually not a great idea for other reasons). If we need to shift load, we change the area that each machine is responsible for, rather than moving the processes. Each simulating object knows how to move itself to the "most optimal" server for that object, so when we change around mappings, the appropriate objects will automatically migrate. Usually the players won't notice when their objects migrate (because of the "seamless streaming world" implementation, which already involves real-time migration).

So, given a change in area on a particular machine/process that change has to be migrated to all processes in the grid? You've stated you use a modified quadtree, I take it this is used to determine which is the most optimal server, given an objects extents and the known areas covered by each process in the grid. Elegant, given a fixed origin coordinate system. I also assume you are generally dealing with a 2D world (as far as zones are concerned).

Couple of questions, I was reading up on DungeonSiege's continuous world design and they ran across floating point precision errors at large distances. In short they overcame this by using an alterable point of reference. Are you using sliding scales for determining quadtree nodes (a 10km tree vs a 1m tree)?

Also, given an irregular shape, how do you determine continuity? Colinear edges on area perimeters? It's one of the reasons my fixed POR's have AABBs rather than arbitrary - I considered the design difficulties of placing continuous arbitrary hulls nightmarish, not to mention the fact I always hated Tetris, especially in 3d, whereas most people can easily figure out how to put together axis aligned box.

If I remember, DungeonSiege was a single player and they would recalculate all the relevant coordinates (all zones within view) when the player crossed into a new current area and convert to use use that area's origin (and maybe only really recalc all when the displacement was significant enough to start effecting accuracy....) I dont think this would work too well with a N-player continuous world where events really need to be compared using a universal coord system.

Quote:Original post by _winterdyne_
The actual operation of node transformations on events is independent of the number of players. So one, or a thousand players, if only a few events occur at zone boundaries, the system works pretty much the same. Problems occur only if many events are crossing zone boundaries within a short time frame.

Arranging the layout of such areas that interesting, congregation-attracting content is near the centre (out of event range of the boundaries) alleviates this problem.

If we know transformations between neighbouring coordinate systems for zones, when an event crosses a boundary it can be implicitly converted to the new coordinate system when placed in the events list / queues for the new zone.

With event comparisons being done within each zone/process, rather than in a centralised place, there is no need for a unified coordinate system, since events and boundaries can be transformed to the appropriate coordinate system as they migrate. There is little overhead to doing this in addition to the network transmission of those events between machines.

If you can work with those constraints (few events crossing boundries)then it woudnt be a problem. But the idea of load leveling runs contrary if you give the players the freedom to mass in small areas and you have to subdivide the concentration AND you dont want high loss of important events between players (from filtering/culling cross boundry events).
If you do have to send those events, the coordinate conversion does add up to some significant CPU....

Quote:Original post by _winterdyne_
Yes, in the situation where the congregation is not in a divisible area (loads of players at the bank), or you have one large congregation in a zone as opposed to several smaller ones, there isn't really a lot you can do, whether or not you have a unified coordinate system. Such areas can be designed to minimize the cross-boundary traffic.

I disagree that the conversion cost of events would be substantial, especially compared to the updates that are running regardless of event migration - even the migration of a complex object's collision hulls only implicitly needs a position and quaternion for orientation ([Edit] and subsequent loading of the appropriate mesh, unless a similar mesh is already in play). Subsequent transformations of hull geometry are the responsibility of the physical simulation layer which would occur anyway.

It's more likely that problems occur from the data associated with an event, especially chat events, which have larger data sizes than most other events, and do not loan themselves well to lossless compression methods (like RLE, for example). I reckon network lag will hit before CPU strain.

Edit: Spelling.

I was thinking of you having continuous floods of events (ie- position updates) crossing seamless boundries and traversing your hierarchy (and having to be translated numerous times as it spread to many adjacent areas). But if you can eliminate cases of seeing objects at long Line Of Sight (etc) from a players viewpoint (thus having few cross boundry cases) then the problem pretty much goes away.


The loading delay problem calls for a preload threshold to pull data into memory ahead of need. This buffer area then becomes its own headache with predicting and prioritizing when data needs to be preloaded across machine boundries (or complex hulls etc.. precalculated ) before the actual transition between zones takes place. Default place holder data is handy when the transition happens before the data transfer is completed...

Quote:Original post by hplus0603

Quote:I also assume you are generally dealing with a 2D world (as far as zones are concerned).

No, it's a full 3D earth-sized planet. One of the modifications in the quadtree is to make it map to a full sphere, although it does wedges centered on the center of the planet. We could easily use an octree instead; the specifics don't matter that much.

We use double precision for all physics, so we don't have to worry about the sliding scale. That way, we can cover an area from +/-8,000,000 meters without worry. Which means we'd have to switch to another coordinate system if you traveled to the moon. We have the technology to support that, but haven't had the need to implement it.

Regarding events crossing zone boundaries, you can make the observation that all events are either: 1) generated by predictable server-side algorithms or 2) generated by unpredictable users. Then you can build the entire system to make sure that both sides see the same thing, without necessarily having to send anything across at all. If you are really gung-ho on the gory details, then please apply for our open jobs :-)

"generated by predictable server-side algorithms" ... A neat trick especially if you have complex NPC AI (one- making it deterministic AND two- duplicating the AI processing in all adjacent areas).

Example of 'complex' -- NPCs react to each other as well as to the player(s), so you would need to process the AI for all the other NPCs it interacts with further away from the boundry, and react to other player's actions that might be out of range of the original player -- again maybe further inside that adjacent area (and maybe across futher boundries in a wonderful cascade of reaction dependencies....)

I have a similar abstract to real LOD mechanism in my project. My areas/zones are a regular grid (instead of variable sized/shaped). I rollin the high detail data on the server when a player is nearby (7x7 areas around each client). The client is streamed the terrain mesh data as the client moves (it does caching locally to minimize resends). Distant terrain is simplified and sent to fill in the horizon (15x15 areas). The worlds terrain is actually computer generated -- using a variation of 'splatting' for the meshes, templates for significant features like coastlines/rivers/mountain ridges and a large master seed pattern (various infinite world type mechanisms rarely generate any realisticly coherant terrain -- especially when you have complex patterns of inhabitant placement and behaviors).

Additional terrain in the form of structural objects (including mobiles/buildings) and 'tunnel' type meshes for interiors/caves etc... Theses sit on the primary terrain and can overlap grid boundries and can themselves be navigated on (so I have a 2 tiered hierarchy) with similar event transmission and boundry crossing problems (and local coordinates conversions for the mobiles).


Even the NPCs are split between 'Significant' objects (with high AI ability and strategic activity in 'abstract mode') and 'Lackeys' which are used for seed driven encounters and local filler populations (the lackey term came from their use to fill out a group that get filled in/expanded/realized when a significant object is a group and is near a player).


The design includes multiple servers to run the active area/zones (assigned in groupings to minimize cross server event transfer and to coordinate NPC community behaviors. Seperate servers run the NPC AI (acting much like clients themselves),here is where I expect to need more flexibility in load leveling.

The most interesting part of the project is going to be automatic quest/mission generation, where a hierarchy of parameterized templates are used to give a wide variety of different problems for the player. A mission scenario would have prologue code to patch in/adapt to the location/environment that it is placed in. When a player triggers a scenario, various props (clues, targets, obstacles) are placed appropriately. The scenarios can chain -- additional seeds can be placed in the vicinity (and only activate if the player gets near them). Yet another abstract/real mechanism to minimize server residency as the scenario details get rolled out of memory if the player walks away....