Adaptive/Dynamic Categorization

Any static partitioning of data flows using a static algorithm (like a geometric grid) will break down. Either due to something intrinsic, or because the players are evil, and delight in ignoring your simplifying assumptions.

So for stability and performance/scale reasons a categorization policy that is dynamic will be better. Periodically a centralized or distributed computation can inspect the in-use categories and determine whether there is a better mapping.

Imagine there was a flash-crowd come to see an epic battle. The initial mapping had that area mapped to one category. The area can be split into two area and given two distinct categories. At a specific point in time, the new mapping will be instituted. Call that the next epoch. We need to do that across all users of those categories. The easiest way would be to broadcast the new mapping. Once all participants have acknowledged they have the new mapping and re-subscribe using that mapping, producers can start using the new categories. Once all participants have acknowledged adopting the new mapping, the old categories can be unsubscribed from.

There are many interesting dynamic categorization policies. They are based on live measurement of the system as the game is being played. The new categorization is then applied live. Clearly this can provide better efficiency than offline analysis and updating a static mapping, since in-game patterns can change minute to minute.

• Split and merge geometric grid cells or triangles. This is how many mmo systems work today, so if that is your preference you can keep it while migrating to using categories.
• Compute "nearness" between producers and consumers, and identify clusters of entities. The set of entities identified is given a category. As entities move around, they subscribe to other clusters of entities. Once the interconnections become too "stretched", a new clustering can be computed. There are pretty simple clustering algorithms, such as inspecting R-squared for an Entity against various proposed clusters to find the nearest one inside some threshold. Note that this approach can be applied to individual entities incrementally as they move.
  
• A similar clustering algorithm can be applied to actual communication patterns as opposed to assuming that geometric nearness always indicates high interaction rates. The recategorization system would record and analyze metrics of interactions as they change in real time.
• The hosting software can detect overloads of various resources, and indicate to the recategorization system that splitting off instances of busy areas would be valuable (assuming your game design supports that approach).
• As dungeons or PvP arenas are spawned, a new set of categories especially for the players involved will be computed and used. Because the subscribers indicate which instance they are currently assigned to, the categorization policy will compute the Categories for that instance, and a player will not see anything from a different instance.
• A game may have unique capabilities like being able to add, remove or move land masses. As coordinate systems drift around, the categorization policy would need to take this into account. It may be able to do that using relative coordinates, or it may need to completely recategorize space.
• Changes in team or guild size may trigger recategorization.
  
• As a clarification, in contrast to dynamic categorization, consider this scenario: As density increases in an area, the policy can adjust the maximum sight distance. While this doesn't directly change the decomposition of the data, it will result in fewer categories being consumed. (This is really a subscription policy change, not a categorization policy change)

Really, the key thing is to consider that real time feedback can be used to help improve the data distribution performance of your system.

Obviously an algorithmic policy is better than an enumerated one, since distributing new parameters to factor into a computation requires less data than a complete enumeration of the descriptions for each category.

Like almost any distributed computation, recategorization can benefit from incremental changes. Local measurements and performance triggers can instigate a categorization change to just a few mappings, and may be able to be distributed to only a few machines. These incremental changes can quickly ripple through the category space and come to an approximately optimal mapping. One benefit of the incremental approach over the periodic approach is that the trigger to recompute can be an event as opposed to a polling of metrics and a recomputation that may have limited or no effect.

Static Categorization Policy

A Static Categorization policy is one that partitions the data flows in an online game using a fixed function (usually a function of the values of the data being partitioned). The algorithm used does not change, and the tuning values do not change during gameplay. The performance of the system is determined by the designer during development testing. There are many examples:

• A 2-d grid with infinite altitude. Any entity in a grid cell transmits to the associated category. Any entity that can see into that grid cell subscribes to that category. And the grid size does not change. This can lead to lots of categories (not a real problem if your categorization implementation is designed for that), too many entities in a cell (if the cells are tuned too large), too many subscription changes (if the cells are too small). Etc.
  
• Variations of the grid approach include non-uniform grids (quad-trees), or arbitrary polygon "tiling".
  
• The designer could identify rooms, or spaces between rendering portals. Each would be assigned a unique category, and all data within them would be grouped. Only when near doors would a consumer subscribe to more than one category.
  
• FPS engines have used BSP trees to optimize rendering and visibility (and auditory effects) calculations (e.g. http://developer.valvesoftware.com/wiki/BSP_Map_Optimization) Whether automatically computed ahead of time or defined with hints, these 3-d volumes could have a category each. It is easy to query the data structure to determine the category corresponding to the current position. Doing an approximate spherical or convex volume query of the BSP tree should also be easy for consumers to find all their needed categories.
  
• Data limited to team, quest party, or clan can be separated each into its own category. A consumer (client) always knows which "entity set" they are in, so can determine where to publish and where to consume. Same with chat channels.
  
• Chat channels are interesting in that you may want to use a 3rd party chat infrastructure, but use in-game position or group membership to determine connectivity. Categories can be very useful for that, or if you want, could be used to route chat through the game engine. That way gameplay mechanics could affect chat (jamming, ambient "noise", battery charge, ...)

Again, all these are considered static because the algorithm and tuning do not change. If something gets overloaded there is no recourse to retune at runtime. Best you can do is change the policy in the next patch.

Note that membership is dynamic, however. That is how the system is able to limit what data is received (for security and bandwidth reduction), but still get everything that is needed to the right consumers.

Dynamic categorization is even more fun, but has some interesting challenges. More next time.

Subscribing ahead

Interest management is the process of delivering interesting data to those interested. An entity ensures that its sensor model has all the correct entities available to it by subscribing to the set of categories known to contain those entities. That subscription fills the local cache with replicas of the interesting entities. Then the sensor can be implemented to immediately query the cache knowing that it contains accurate data.

The policy the application uses to fill the cache can be as simple as a grid, or as complex as a dynamically determined set of clusters of nearby entities. In either case, the consumer knows the category being used by any entities that might be within the consumer's area of interest, field of view, line of sight, range of hearing or what not. Note that the producer generally produces into a single category.

So now producers send updates, and interested consumers get them. But what if someone moves? They will change the category they produce into, or the set of categories they consume from. But what about latency? That is where it gets "fun". A consumer can use its maximum velocity and an estimate of subscription latency to compute the extra distance needed to guarantee that the cache contains those moving entities even when the producer and consumer are moving toward each other at maximum velocity. That will ensure that its cache is populated with any entities that will-be interesting in a few moments. The cache will necessarily have more entities than are logically visible, so the sensor algorithm must filter out ones that are too far away but have been delivered "just in case".

But what about producers that are moving? We use latency hiding and bandwidth optimization to reduce the number of updates being sent, and then predict where the producer is at the current time. But that increases the latency of the produced data. OK. We increase the subscription range even farther. But you have to factor in the producer's maximum velocity. And you don't know what type of entity it is. So you have to use the maximum velocity of the fastest entity in the game.

That can suck if there are a few jet fighters, but tons of infantry. The solution? Separate the fast movers from the slow movers and use two distinct "layers" of categories. You would subscribe out quite a bit further for fast movers, but wouldn't get any slow movers in that wide subscription because they are produced into a different layer. And there won't be very many fast movers to consume. If you think about it, there is just no way to consume all the data from fast movers that are far away and might suddenly move toward you if there are a lot of them. The worst case example is an entity that can teleport anywhere instantly. Consumers would have to be subscribed to everything. Or you would have to change the game design to hide the latency from subscribing on-demand (like making a poof of smoke, or invulnerable just after teleport, or something).

The beauty of category based subscription is that these game-specific factors can be reduced to a set of integer values that can be computed by both producer and consumer. The consumer doesn't need to know that there are entities in the interesting category. If there are, the publish/subscribe system will deliver them. All that system does is match up integer values: hey this thing goes to these guys. The system doesn't need to assume that the categories are related to geometry, or that they are a linear function, or anything. You can use them as sets. Or unique addresses for multi-point to point communication, or for radio broadcasts on a single station. Or anything.

But my point: you have to use prediction to reduce bandwidth. But you also have to use prediction when subscribing or might miss something "interesting".