Frontier Sets in Large Terrain Environments with Applications to Decentralized Online Games

Abstract

In current online games, player positions are synchronized by means of continual broadcasts through the server. This solution is expensive, forcing any server to limit its number of clients. With a hybrid networking architecture, player synchronization can be distributed to the clients, bypassing the server bottleneck and decreasing latency as a result. Synchronization in a decentralized fashion is difficult as each player must communicate with every other player. The communication requirements can be reduced by computing and exploiting frontier sets: For a pair of players in an online game, a player's frontier is the region of the game space where the player may move without seeing (and without communicating to) the other player. A pair of frontiers is called a frontier set. This thesis describes the first fast and space-efficient method of computing frontier sets in large terrains.

Frontier sets are computed by growing regions in a connected set of quads in a hierarchical decomposition of the terrain. The solution involves the precomputation of a potentially visible set (PVS) for each quad in the decomposition, which stores all the quads potentially visible from any point within the current quad. Since the memory needed to store the PVSs for all the quads is quite large, a compression technique is introduced which controls the size of each PVS. A PVS merging algorithm, with both lossless and lossy variations, is also described which permits adding the PVS of a point or quad to the PVS of a growing region. The new algorithm is compared to a simple region growing approach where frontiers are grown along the individual terrain points. Using similar merging techniques, the new algorithm performs better, producing larger frontier sets with faster execution times.