Supporting a seamless map in peer-to-peer system for Massively Multiplayer Online Role Playing Games
Xinbo Jiang, Farzad Safaei · 2008
Massively multiplayer online role playing games feature huge maps that can be partitioned into smaller components called zones to achieve scalability. In peer-to-peer (P2P) systems, those zones can be assigned to peers who are willing to take up the role of zone servers. A seamless map requires inter-zone communications to allow interactions between players across zone boundaries. In assigning zones to peers, it is critical to seek approaches to reduce the inter-zone communication cost in P2P system. In this paper, we formulate the zone assignment problem for P2P system and demonstrate that the problem is NP-hard. We hence propose a low-cost heuristic that partitions the physical network into bins, as well as, aggregating the partitions of the virtual world by clustering neighboring zones in a game map. We then demonstrate that by assigning clustered neighboring zones in the virtual map into peers in common physical network bins, we are able to achieve similar inter-zone communication cost for the zone assignment problem as that can be achieved by the optimization model we formulated, while avoiding the prohibitively high computation cost required by the latter.