Sign in to follow this  

Voronoi State Management for P2P MMOGs

Recommended Posts

Hello, I'm the maintainer of the SourceForge project VAST ( We've been trying to research ways that could realize P2P-based virtual worlds/MMOGs. We've a new design for game state management that tries to utilize both client & server resources, in a paper that'll appear in the IEEE NIME'08 workshop next year ( We're mainly interested in a scalable design for game states management that also supports existing consistency controls, load balancing, and fault tolerance. Some basic ideas of the designs are: - use Voronoi diagrams based on the users' positions to partition the virtual world into many small cells and allows one 'arbitrator' to manage all game states/updates in the Voronoi cell authoritatively. - Within each cell, consistency is handled in client-server fashion. - initially, each client is its own 'arbitrator', and would connect with their area of interest (AOI) neighbors directly (so user actions/events can affect other cells, but the results must be handled by the other respective arbitrators). - as cells would change shape, objects that stay in the same place (or dynamic objects that move from cell to cell) would transfer ownerships among arbitrators through explicit messages. - when too many clients are within the AOI of each other (i.e. crowding occurs), a capable superpeer or the server would be called in as an 'aggregator' to take care of the management of several overloaded cells. - if crowding no longer exists, the aggregator disintegrates itself and returns control back to the clients it was managing. - to prevent Voronoi cells from being too big initially (and clients might handle too many states), 'virtual peers' assumed by the server are in place initially. - arbitrators and aggregators have respective backup nodes, and would assume the original one's functions in case of the originals' failures. - security & persistence/storage issues are not yet considered For a more complete description, the paper can be found here: What I'd like to know is: 1. security/cheating issues aside (for example, in a social virtual world, only chats/gestures/simple items exist), does the design seem practical/make sense? 2. what are some of the main/critical flaws? overlooked issues? We'll appreciate any comments or suggestions. Thanks! [Edited by - syhu on October 12, 2007 11:55:35 AM]

Share this post

Link to post
Share on other sites
Original post by hplus0603

Did you fix the issue where a fast-moving client could move outside its area of interest, and potentially cause world view splitting? If so, how?

This problem occurs with the original Voronoi-based Overlay Network (VON) design, as only the "boundary neighbors" (BN) would help to check if a moving node has new neighbors, and they also only check for their "enclosing neighbors" (EN) (see for definitions for BN & EN) as the potential new neighbor set. So if a node is moving fast enough (that is, out of the boundary neighbor's enclosing neighbor set), then neighbor discovery might be incomplete, and the moving node's view on its AOI boundary would be temporarily inconsistent with the reality.

The obvious fix is that, instead of checking only the "enclosing neighbor" set, boundary neighbors can check for all its AOI neighbors that might be visible on the moving node's moving direction, at the cost of additional computations. This has a potential problem though, as multiple boundary neighbors might notify the moving node redundantly. However, if we can choose carefully the BNs that do the checking, then redundancy can be minimized (note that a little redundancy for neighbor discovery is good for fault tolerance purposes).

Of course, all this still requires that the moving node cannot step out of its own AOI in at least one or two steps (to allow enough time for BNs to notify for new neighbors). The discovery would still be incomplete/problematic, if a moving node's moving so fast that within one step, it's already beyond its own AOI (and thus beyond the help zone of any boundary neighbors). So likely a jet-plane vs. ground troop scenario is still not supportable. But for regular human movement, I think the neighbor discovery should be fine given a reasonably large AOI for each users.

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this