Using Groupings for Networked Gaming

Networked computer games present new data distribution challenges to the developer. With stand-alone games, all game information is available in one place, on one computer, all the time. When designing networked games, however, the developer has to consider what information the other players on the network need, when they need it, and how to deliver it to them. The easy way out is to broadcast everything you can think of to everyone on the network as often as possible. This keeps everyone synchronized, but quickly consumes all available bandwidth - not a good idea for groups of players dialed in to the Internet. The other extreme is to carefully consider each packet of data and to send it only to other players who really need it. This approach makes efficient use of bandwidth, but deciding who needs data and who doesn't chews up so many of the sender's CPU cycles that no processing power is left to play the game.

There is a middle ground, however, and it's called "grouping." Grouping allows networked games to route essential data among the players while making efficient use of both network and CPU resources. In some cases, underlying network service providers support an efficient way to distribute grouped data; this is called multicasting. In other cases, games may be limited to broadcast or point-to-point connections. Still, grouping can provide some efficiencies. Grouping can help a networked game scale up to include large numbers of players. This article covers logical ways to group data and the schemes used to implement grouped communications.

What Is a Grouping?

The first thing to consider is why you'd want to group data at all. If you're developing a one-on-one boxing game played on two computers, then chances are both players will need to know everything about one another; every move and every change will need to be exchanged. It's a very different situation, however, if you're building a large-scale space war scenario with lots of players. You may have a very high-performance spaceship and may be doing rolls in seven dimensions, but if I'm far away from the maneuvers, you just look like a dot to me. You're too far away for me to see your detailed maneuvers, so I don't need to know the details of your motion. Furthermore, if neither one of us can see the "cloaked" alien spaceship hovering nearby, then there's really no need for him to send us his position at all until he becomes visible. The bottom line is that if you think about various players' data requirements, you can save a lot of bandwidth, network interrupt overhead, and CPU processing by only sending information to the players who need it. The trick is to make routing decisions without spending more cycles than you stand to save.

How Is Grouped Data Transmitted?

Before we get into the mechanics of creating data groups, let's look at how grouped data can be distributed among computers on a network. Ordinarily, each sender can communicate with other players on the network using either broadcast, one-to-everyone communications such as UDP/IP or via one-to-one links such as TCP/IP. For computer games, what you really want is one-to-many or many-to-one communications. Multicast-capable networks implement this capability at the physical level, using addressing schemes that allow a single transmitted message to be routed to many receivers while being ignored by others, even others on the same LAN. Even in environments where multicasting is not available, or in server-based game environments, the server can still effectively implement multicasting. A single transmission is reflected (or "exploded") back to multiple receivers, albeit with added latency. Figure 1 shows multicast transmission and its server/exploder equivalent.

The DirectPlay component of DirectX that provides an abstraction of one-to-many and many-to-one messaging is called, not surprisingly, group management. DirectPlay's group management methods provide the ability to define, join, leave, and send data to groups of players. To create a group in DirectPlay, any player within a session calls IDirectPlay3::CreateGroup. After a group is created, any of the other players in the session can join the group via the IDirectPlay3::AddPlayerToGroup method or leave via the IDirectPlay3::DeletePlayerFromGroup method. Any player can then send a message to all the other players in the group via a single call to IDirectPlay3::Send. Note that these interfaces don't change with the underlying communication mechanism of the service provider; rather, DirectPlay abstracts away whether a group is implemented as a physical multicast group, an exploder group, a broadcast that's filtered on the receiver end, or some other mechanism.

Assigning Data to Groups

Basic multicast technology doesn't say anything about what types of groupings to use, and indeed, in DirectPlay any player can join any group. So how do you make best use of groups? The approach to take in grouping data is to come up with some easily calculable measure for each message and to route the message to groupings based on that measure.

When looking at any piece of data, the game has basically three pieces of information that it can use to decide where to send it.

Data-Based Grouping. Data-based grouping is the most intuitive form of creating groupings, and for many games, geographic sectorization is the most common form of data-based grouping. Under geographic sectorization, the virtual world is broken up into regions and data is grouped according to region. For example, in the scheme shown in Figure 2, 12 groups are used to segment the play area based on a rectangular North/East grid. Each entity knows what region it's in and sends its data to the corresponding group. Thus, the airplane shown in the figure sends data to Group 6. It's important to note that entities don't have to recheck their region location with every internal update (that is, every time they update their position). If you know that a single region is 100 miles or 20 light-years across, and you know how fast your vehicle can go, then you know the soonest you could possibly enter another region, and thus can postpone checking your region until that time. The result is that geographic sectorization yields an inexpensive (because it's infrequently calculated) way of creating groups of data.

A player's computer would control the flow of data to it by joining only those groups it cares about. For example, as shown in Figure 2, an entity in Region 6 might care only about entities in its immediate area, in which case it would only need to listen to Group 6. If the entity has a larger area of interest, it might subscribe to adjacent groups as well, in this case adding all the groups shown in blue. Of course, there's a tradeoff in using simple groupings; data isn't perfectly filtered. Let's say the entity in Region 6 is interested in all other entities within a certain radius of its location, shown by the dashed circle around the entity. In this case, the entity still has to join groups covering the entire blue region and will get some extraneous information. In general, this is acceptable - the extra data just has to be filtered out upon receipt.

Geographic sectorization is just one example of data-based grouping. In practice, any of an object's attributes can be used to assign that object to a grouping. For example, my space war game might simply sort data into two groups: data for "cloaked" spaceships and data for "uncloaked" ships. Players who don't have the ability to see cloaked ships listen only to the uncloaked group and therefore don't waste time and bandwidth processing packets for ships they can't see. Grouping can also be based on data type. For example, in a war game, you might have separate groups for land vs. air vs. sea vehicles. Chances are that submarines don't care about individual infantrymen on the battlefield and can avoid having to ever see infantry data by using groupings.

Source-Based Grouping. In source-based grouping, every source of data (where a source can be a LAN, a player, or even a particular entity) is assigned its own group, and every player then subscribes only to those sources that it cares about. Under DirectPlay, only one player per group would send to a group, though many players can issue IDirectPlay3::AddPlayerToGroup commands to listen to the group. The problem then becomes one of telling the destinations what information is being produced by each source and determining which groups to join?

In some cases, this problem is solved simply by well-known sources of particular data. For example, if there's one computer that provides weather and terrain information for the entire session, then all other players automatically know to listen to that player's group if they want to get weather updates. A more general solution lies in creating a special group, which carries very low frequency information about all entities or players in the game, to which everyone subscribes. Since all players subscribe to this low-fidelity data channel, they know rough information about all the entities in the game. They can then get more detail about the entities they really care about by subscribing to the groups representing the sources that they want to hear. One good thing about this scheme is that the number of groups used scales linearly with the number of sources. In principle, the "source" can be anything, including a single entity or avatar. A side benefit of this approach is that the low-fidelity group automatically gives each player enough data to create a rough, "radar-screen" picture of the entire play space.

Recipient-Based Grouping. Finally, we come to recipient-based grouping. This scheme is something of an inverse of source-based grouping in that in this scheme groups are created on the basis of recipients with common interests. For this scheme to work, each sender needs to know which players might be interested in each message it sends out. Once a list of interested parties is known, the data can be addressed to the groups that represent just those destinations.

As an example, consider a situation similar to that discussed under geographic grouping. Once again, each player is interested in other nearby entities. This time, though, each player must send a message to all the other computers in the game saying something along the lines of "I'm at location (x,y,z) and want to know about anyone within one light-year of me. By the way, I listen to multicast Group 10." This interest expression tells the other computers in the game what this player's data needs are and what communications channel to use. Then, each other computer, when it's about to send out information about its entities, must look at the interest expressions from all the other players on the network and transmit the data over the proper multicast groups.

This scheme carries with it some extra communications overhead in that the data requirements of every player must be transmitted to every other player during the exercise. Fortunately, these interest expressions change rather slowly, so they don't result in a large amount of information flowing between hosts, as is the case with dynamic game data. Recipient-based grouping can also use up the largest number of groups of all the possible schemes, if you're interested in creating groups for each possible combination of recipients. Recipient-based grouping can be expensive to implement in terms of CPU cycles on the sending side, but unlike either of the other schemes, it can offer perfect segmentation of data (you receive only what you need, with no extra information).

Dynamic Grouping

All of the grouping schemes described previously are based on static definitions of groups. For example, in the geographic sectorization scheme, the boundaries of Sector 1, and hence, the definition of Group 1, are defined before the game starts running. This is the easiest way to implement groups, since group definitions, and consequently, choices about where to send or listen, can be hard-coded into the game.

Sometimes, however, static group definitions don't work out. Suppose in my spaceship game a heated battle is taking place in Sector 6. The remainder of space may be relatively empty, but there's a lot of activity in Group 6. In this case, using groups doesn't buy you much in the way of performance, since most of the players wind up sending and receiving Group 6 data. The solution in this case would be to create dynamic group definitions. With dynamic groupings, each session would designate a player to serve as a group server for the session (under DirectPlay, this role could be filled by the session host). The group server monitors or infers traffic flow in the various groups and can dynamically redefine groups. In the spaceship game, for example, a group server might decide to break up Sector 6 into four smaller sectors. It might add new groups, sending out the new group definitions to each player. If the number of groups available to a session is limited, perhaps by the available number of physical multicast groups, then it might redefine existing groups (for example, by combining Sectors 4 and 8) to free up groups. Figure 3 shows what the geographically sectorized space of Figure 2 might look like after being dynamically adjusted. The bottom line is that with dynamic groups, each player's software must listen to group definitions as broadcast from the group server and modify its group memberships accordingly.

Two Grouping Gotchas

There are a couple of things to look out for when you use groupings to communicate among networked games. The first challenge is to understand the underlying transport mechanism used by the service provider to implement grouped communications. Certain implementations, such as server exploders, impose additional communications overhead on grouped communications. In other cases, such as poorly implemented multicast drivers, the use of large numbers of groups can actually cause a decrease in performance. Unfortunately, most game developers have no control over multicast driver performance, as network drivers are part of the operating system.

One important thing to look out for is the join/leave delay for groups. In general, group creation, joins, and deletes don't happen instantaneously (in fact, group join/leave times are unpredictable, but are generally measured in seconds); games must be prepared to forecast their data distribution needs sufficiently far in advance to allow time for joining and leaving groups.

The other major problem you'll face with grouping is how to bring players up to speed when they join new groups. In a grouped, multicasted world, each player knows only a subset of the globally available data. When a player joins a new group (such as, when a spaceship flies into a new sector), some anomalous things can happen. If the player doesn't immediately get all the information about all the data in that group (such as, the identities and locations of all the other ships in that sector), then he's essentially flying blind for a period; our ship can be blasted by another ship that we've never even seen! This is another case where it's important to join groups well in advance of when you'll actually need their data. If, on the other hand, the game implements a mechanism to bring a new group member up to speed quickly, then a player who joins a busy group may immediately be flooded with information, resulting in packet loss or poor application performance. Any protocol to bring group-joiners up to speed must carefully avoid this problem. This is another situation where a low-fidelity data group (as described under geographic sectorization) can be useful; if all players listen to the low-frequency broadcasted updates on the low-fidelity group, then they'll have at least some idea of what to expect when entering a new sector.

Putting It All Together

Managing data distribution across networked games is not an easy problem. Simple data distribution schemes don't scale well, limiting the potential size of games. More complex schemes, such as the various types of data grouping, require more thought on the part of programmer, but have been shown to greatly increase the potential scale of games. In the military simulation world, the increased network and processor efficiencies resulting from multicasting/grouping have yielded an order of magnitude increase in the number of entities supported when compared to broadcast-based Distributed Interactive Simulation protocols. Current game SDKs, such as Microsoft DirectPlay, offer group facilities but don't provide any support for group definition or use. Any game developer looking to create scalable networked games needs to consider efficient data distribution. The good news is that combining SDK grouping functions with group definition concepts such as those described in this article can yield games that are suitable for large-scale play by large numbers of distributed gamers.

The author would like to thank Dr. Edward Tiberius Powell and Larry Mellon, whose pioneering designs for the JPSD and STOW projects form the basis for many of the ideas presented in this article.

Jesse Aronson is a software architect at Science Applications International Corp., where he designs war gaming simulations covering thousands of entities running on hundreds of computers across dozens of sites. He can be reached at [email protected].