Frontier Sets in Large Terrain Environments with Applications to Decentralized Online Games
Loading...
Authors
Avni, Shachar
Date
2010-05-26T14:48:43Z
Type
thesis
Language
eng
Keyword
Computer Graphics , Visibility , PVS , Frontier Sets , Terrains , Game Programming , Computer Science
Alternative Title
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.
Description
Thesis (Master, Computing) -- Queen's University, 2010-05-25 14:53:24.375
Citation
Publisher
License
This publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner.