Thursday, May 14, 2009

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. 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.

No comments:

Post a Comment