2008年04月17日

Area of Interest Filter

Today I’m going show you one implementation for reducing network packets sent to and from the server and clients using an Area of Interest Filter.

The Problem
When multiple clients share a single game world the number of packets usually increase exponentially this is because the high cost of broadcasting. For example let’s say we have a player named Bob running around a world and Bob sends his position at a rate of 5 packets/sec to the server. Let’s say we have another player named Jim who joins the world. He also sends 5 packets/sec. So within 1 sec. the server takes in 5 packets from Bob and 5 packets from Jim which means 10 total packets going to the server. The server then echos Bob’s packets to Bob and also sends them Jim and does the same for Jim’s packets. So the total is 20 packets going down or each client receiving 10 packets.

Now let’s add another player called Cindy. She also sends 5 packets/sec to the server. Now Bob, Jim and Cindy all combined together send 15 packets to the server. For each player the server now echos back the senders packet and broadcasts them to all the other players. That’s a total of 45 packets or 15 packets for each client. The number of packets the server sends equal to players^2 * packets per second. If we have a MMO game with 200 players in one scene that would be 200^2 * 5 = 200,000 packets/sec the server needs to handle and 1000 packets/sec the client needs to handle.

The Area of Interest Filter is used to reduce the amount of packets needed to be sent by filtering out things that the client doesn’t have to know about. For example, if an enemy is 100km away from the player there is no need to send any updates to the client because they can’t see or interact with the enemy yet.

Vocab
One possible implementation of an Area of Interest Filter is using foci’s and nimbi.

• Focus/Nimbus: The focus represents an observing entity’s interest and nimbus represents an observed entity’s wish to be seen in a given medium (Benford et al. 1994; Greenhalgh1998)
• Publisher: An entity which sends out data.
• Subscriber: An entity which can recieve data.

Visually the nimbus can be thought of a bounding area of an entity and the focus being the entities field of view.

A general interaction would be

1. Entity B’s nimbus falls into view of another entity A’s focus.
2. If the B’s nimbus is a publisher and A is interested in that publisher, subscribe to it.
3. Now Entity A is a subscriber to B.
4. The publisher B will now send its data to the subscriber A.

Demo
I created a sample flash application below to demonstrate all these ideas. The circles represent the nimbus of the entity and the triangles represent the focus. When the focus touches another entities nimbus it subscribes to that entity and receives position updates. The green entities are the actual real time positions the server should see. The blue shadows represent proxies that the clients see. When a entity has no subscribers then it’s proxy is not updated and does not move. The red lines represent two entities in which at least one entity has subscribed to the other. The stats show the global entity (ID: ids), it’s subscriptions (SUB: subscriptions), entities that have subscribed to it (SUBC: subscribers) and total packets received from the server (PACKETS). Also, in the upper left is a graph shows a history of total output(red) and input(green) from the server.

Controls:
Left - Right = Rotate your entity clockwise and counterclockwise (White entity)
Up - Down = Move your entity back and forth
Space = Toggle Area of Interest Filter on and off
Enter = Toggle Nimbus only detection

You can grab the source code here.

You can also view it directly.

Few more words
This can also be extended to other things such as

• Distance based filtering. Changing priority of who gets the packets based on how close they are to an entity.
• Multiple Nimbi. Each nimbus could represent a certain data like chat, animation update or position.
• Dynamic Nimbus/Focus.

References
Comparing interest management algorithms for massively multiplayer games
by Jean-Sébastien Boulanger, Jörg Kienzle, Clark Verbrugge

Algorithms and Networking for Computer Games
by by Jouni Smed and Harri Hakonen

• Posted by brian on 13:00 filed in ActionScript, English
• パーマリンク